# Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 4 Nov 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [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)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Acceleration through Optimistic No-Regret Dynamics](https://mlsanity.com/paper/1807.10455/) (2018)
- [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)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Accelerated Parameter-Free Stochastic Optimization](https://mlsanity.com/paper/2404.00666/) (2024)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach](https://mlsanity.com/paper/2307.08360/) (2023)
- [Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction](https://mlsanity.com/paper/2406.06398/) (2024)
- [Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization](https://mlsanity.com/paper/2310.12139/) (2023)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Accelerated Over-Relaxation Heavy-Ball Method: Achieving Global Accelerated Convergence with Broad Generalization](https://mlsanity.com/paper/2406.09772/) (2024)

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

- [Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations](https://mlsanity.com/paper/2602.04761/) (2026)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality](https://mlsanity.com/paper/2511.06597/) (2025)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [Small Gradient Norm Regret for Online Convex Optimization](https://mlsanity.com/paper/2601.13519/) (2026)

## Abstract (arXiv)

Smoothness is known to be crucial for acceleration in offline optimization, and for gradient-variation regret minimization in online learning. Interestingly, these two problems are actually closely connected -- accelerated optimization can be understood through the lens of gradient-variation online learning. In this paper, we investigate online learning with H"older smooth functions, a general class encompassing both smooth and non-smooth (Lipschitz) functions, and explore its implications for offline optimization. For (strongly) convex online functions, we design the corresponding gradient-variation online learning algorithm whose regret smoothly interpolates between the optimal guarantees in smooth and non-smooth regimes. Notably, our algorithms do not require prior knowledge of the H"older smoothness parameter, exhibiting strong adaptivity over existing methods. Through online-to-batch conversion, this gradient-variation online adaptivity yields an optimal universal method for stochastic convex optimization under H"older smoothness. However, achieving universality in offline strongly convex optimization is more challenging. We address this by integrating online adaptivity with a detection-based guess-and-check procedure, which, for the first time, yields a universal offline method that achieves accelerated convergence in the smooth regime while maintaining near-optimal convergence in the non-smooth one.