2
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Improve this answer
$\endgroup$

Your Answer

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

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