# Fully Unconstrained Online Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 45 references that are in the map.
- First posted on arXiv 30 May 2024.

## Builds on (most cited first, 30 of 30)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Mechanic: A Learning Rate Tuner](https://mlsanity.com/paper/2306.00144/) (2023)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Quasi-Newton Steps for Efficient Online Exp-Concave Optimization](https://mlsanity.com/paper/2211.01357/) (2022)
- [Risk-Monotonicity in Statistical Learning](https://mlsanity.com/paper/2011.14126/) (2020)
- [Damped Online Newton Step for Portfolio Selection](https://mlsanity.com/paper/2202.07574/) (2022)
- [Improving Adaptive Online Learning Using Refined Discretization](https://mlsanity.com/paper/2309.16044/) (2023)
- [Matrix-Free Preconditioning in Online Learning](https://mlsanity.com/paper/1905.12721/) (2019)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)

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

- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Parameter-free Algorithms for the Stochastically Extended Adversarial Model](https://mlsanity.com/paper/2510.04685/) (2025)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [A regret minimization approach to fixed-point iterations](https://mlsanity.com/paper/2509.21653/) (2025)
- [Small Gradient Norm Regret for Online Convex Optimization](https://mlsanity.com/paper/2601.13519/) (2026)
- [Online Prediction of Stochastic Sequences with High Probability Regret Bounds](https://mlsanity.com/paper/2602.16236/) (2026)

## Abstract (arXiv)

We provide an online learning algorithm that obtains regret G|w_star|√Tlog(|w_star|G√T) + |w_star|2 + G2 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|√T available with such knowledge (up to logarithmic factors), unless either |w_star| or G is so large that even G|w_star|√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.