# Artificial Constraints and Lipschitz Hints for Unconstrained Online Learning

arXiv: https://arxiv.org/abs/1902.09013 · HTML: https://mlsanity.com/paper/1902.09013/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)

## Abstract (arXiv)

We provide algorithms that guarantee regret RT(u)≤ tilde O(G|u|3 + G(|u|+1)√T) or RT(u)≤ tilde O(G|u|3T1/3 + GT1/3+ G|u|√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|√T is necessary. Previous penalties were exponential while our bounds are polynomial in all quantities. Further, given a known bound |u|≤ D, our same techniques allow us to design algorithms that adapt optimally to the unknown value of |u| without requiring knowledge of G.