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


1 Answer 1


Here is what you are looking for. It is quite new:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.