Name
Abstract | ||
|---|---|---|
We provide algorithms that guarantee regret $R_T(u)le tilde O(G|u|^3 + G(|u|+1)sqrt{T})$ or $R_T(u)le tilde O(G|u|^3T^{1/3} + GT^{1/3}+ G|u|sqrt{T})$ for online convex optimization with $G$-Lipschitz losses for any comparison point $u$ without prior knowledge of either $G$ or $|u|$. Previous algorithms dispense with the $O(|u|^3)$ term at the expense of knowledge of one or both of these parameters, while a lower bound shows that some additional penalty term over $G|u|sqrt{T}$ is necessary. Previous penalties were exponential while our bounds are polynomial in all quantities. Further, given a known bound $|u|le D$, our same techniques allow us to design algorithms that adapt optimally to the unknown value of $|u|$ without requiring knowledge of $G$. |
Year | Venue | DocType |
|---|---|---|
2019 | arXiv: Machine Learning | Journal |
Volume | Citations | PageRank |
abs/1902.09013 | 0 | 0.34 |
References | Authors | |
16 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cutkosky, Ashok | 1 | 14 | 10.02 |