Fully Unconstrained Online Learning
<|reference_start|>Fully Unconstrained Online Learning: We provide an online learning algorithm that obtains regret $G\|w_\star\|\sqrt{T\log(\|w_\star\|G\sqrt{T})} + \|w_\star\|^2 + G^2$ on $G$-Lipschitz convex 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, it matches the optimal bound in all cases in which one can achieve sublinear regret, which arguably most "interesting" scenarios.<|reference_end|>
@article{cutkosky2024fully,
    title={Fully Unconstrained Online Learning},
    author={Ashok Cutkosky and Zakaria Mhammedi},
    journal={arXiv preprint arXiv:2405.20540},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.20540},
    primaryClass={cs.LG math.OC stat.ML}
}