Follow the Perturbed Leader for nonlinear cost functions The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known? 

Note that in the last paragraph of [1] it says "It would be great to generalize FPL to nonlinear problems". 

In [2] (page 69, 70, 71) there is analysis of FTPL for general functions, but the resulting bound $O(T)$ does not attain the optimal bound (i.e. $\sqrt{T}$). Are you aware of better analysis for FTPL (with general nonlinear functions) that attain the optimal regret?

Update:  The algorithm in [2] is indeed $O(\sqrt{T})$ (by choosing $\eta = 1/\sqrt{T}$) but it is calling the linear optimiazation oracle many times (not just once as in [1]), which results in having a different bound. 

[1] http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf

[2] http://ocobook.cs.princeton.edu/OCObook.pdf
Here is what you are looking for. It is quite new:

https://arxiv.org/pdf/1810.07362.pdf