<p>Here is what you are looking for. It is quite new:</p>

<p><a href="https://arxiv.org/pdf/1810.07362.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1810.07362.pdf</a></p>

CC BY-SA 4.0
2019-01-30T13:35:22.987Z
2019-01-30T13:35:22.987Z
user3680510
<p>The famous FTPL algorithm [1] is analyzing <strong>linear</strong> cost function. Is there any generalized proof for <strong>nonlinear</strong> functions known? </p>

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

<p>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?</p>

<p><strong>Update:</strong>  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. </p>

<p>[1] <a href="http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf" rel="nofollow">http://people.cs.uchicago.edu/~kalai/papers/onlineopt/onlineopt.pdf</a></p>

<p>[2] <a href="http://ocobook.cs.princeton.edu/OCObook.pdf" rel="nofollow">http://ocobook.cs.princeton.edu/OCObook.pdf</a> </p>

<optimization><machine-learning><lg.learning><online-algorithms><online-learning>
Follow the Perturbed Leader for nonlinear cost functions
Daniel
# Follow the Perturbed Leader for nonlinear cost functions

(Asked by: username_0 on 2014-12-13)

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>

**Tags:** optimization, machine-learning, lg.learning, online-algorithms, online-learning

---

## 1 answers

### Answer by username_1 on 2019-01-30. Score: 1

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

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


---

