Fully Unconstrained Online Learning
Abstract
We provide a technique for OLO that obtains regret $G\|w_\star\|\sqrt{T\log(\|w_\star\|G\sqrt{T})} + \|w_\star\|^2 + G^2$ on $G$-Lipschitz losses for any comparison point $w_\star$ without knowing either $G$ or $\|w_\star\|$. Importantly, this matches the optimal bound $G\|w_\star\|\sqrt{T}$ available with such knowledge (up to logarithmic factors), unless either $\|w_\star\|$ or $G$ is so large that even $G\|w_\star\|\sqrt{T}$ is roughly linear in $T$. Thus, at a high level it matches the optimal bound in all cases in which one can achieve sublinear regret.
Cite
Text
Cutkosky and Mhammedi. "Fully Unconstrained Online Learning." Neural Information Processing Systems, 2024. doi:10.52202/079017-0326Markdown
[Cutkosky and Mhammedi. "Fully Unconstrained Online Learning." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/cutkosky2024neurips-fully/) doi:10.52202/079017-0326BibTeX
@inproceedings{cutkosky2024neurips-fully,
title = {{Fully Unconstrained Online Learning}},
author = {Cutkosky, Ashok and Mhammedi, Zakaria},
booktitle = {Neural Information Processing Systems},
year = {2024},
doi = {10.52202/079017-0326},
url = {https://mlanthology.org/neurips/2024/cutkosky2024neurips-fully/}
}