# Gradient-Variation Regret Bounds for Unconstrained Online Learning

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

## Key facts

- Cited by 1 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 13 Apr 2026.

## 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)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Adapting to Online Label Shift with Provable Guarantees](https://mlsanity.com/paper/2207.02121/) (2022)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Combining Online Learning Guarantees](https://mlsanity.com/paper/1902.09003/) (2019)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Efficient Methods for Non-stationary Online Learning](https://mlsanity.com/paper/2309.08911/) (2023)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Parameter-free Algorithms for the Stochastically Extended Adversarial Model](https://mlsanity.com/paper/2510.04685/) (2025)
- [Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization](https://mlsanity.com/paper/2511.19937/) (2025)

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

- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)

## Abstract (arXiv)

We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation VT(u) = sumt=2T |nabla ft(u)-nabla ft-1(u)|2. For L-smooth convex losses, we provide fully-adaptive algorithms achieving regret of widetildeO(|u|√VT(u) + L|u|2+G4) without requiring prior knowledge of comparator norm |u|, Lipschitz constant G, or smoothness L. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).