# Online Adaptive Methods, Universality and Acceleration

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2018.

## Built on by (most cited first, 30 of 51)

- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [ASGO: Adaptive Structured Gradient Optimization](https://mlsanity.com/paper/2503.20762/) (2025)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Structured Preconditioners in Adaptive Optimization: A Unified Analysis](https://mlsanity.com/paper/2503.10537/) (2025)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization](https://mlsanity.com/paper/2101.11075/) (2021)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [Differentially Private Adaptive Optimization with Delayed Preconditioners](https://mlsanity.com/paper/2212.00309/) (2022)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Revisiting Convergence of AdaGrad with Relaxed Assumptions](https://mlsanity.com/paper/2402.13794/) (2024)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Acceleration](https://mlsanity.com/paper/2209.14827/) (2022)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization](https://mlsanity.com/paper/2406.02016/) (2024)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Improved Policy Optimization for Online Imitation Learning](https://mlsanity.com/paper/2208.00088/) (2022)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Adaptive Differentially Private Empirical Risk Minimization](https://mlsanity.com/paper/2110.07435/) (2021)
- [Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers](https://mlsanity.com/paper/2402.02951/) (2024)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)

## Abstract (arXiv)

We present a novel method for convex unconstrained optimization that, without any modifications, ensures: (i) accelerated convergence rate for smooth objectives, (ii) standard convergence rate in the general (non-smooth) setting, and (iii) standard convergence rate in the stochastic optimization setting. To the best of our knowledge, this is the first method that simultaneously applies to all of the above settings. At the heart of our method is an adaptive learning rate rule that employs importance weights, in the spirit of adaptive online learning algorithms (Duchi et al., 2011; Levy, 2017), combined with an update that linearly couples two sequences, in the spirit of (Allen-Zhu and Orecchia, 2017). An empirical examination of our method demonstrates its applicability to the above mentioned scenarios and corroborates our theoretical findings.