mlsanityData to 13 Oct 2026

Online Adaptive Methods, Universality and Acceleration

arXiv 1809.02864 ↗First posted 8 Sep 2018cs.LG math.OC stat.MLcited by 51

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 7; 2022: 13; 2023: 9; 2024: 7; 2025: 10; 2026: 5.

51 papers.

Sort:

By area:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 132
  2. 2025ASGO: Adaptive Structured Gradient Optimizationcited by 55
  3. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  4. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  5. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  6. 2025Structured Preconditioners in Adaptive Optimization: A Unified Analysiscited by 30
  7. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  8. 2021Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimizationcited by 27
  9. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  10. 2022Differentially Private Adaptive Optimization with Delayed Preconditionerscited by 18
  11. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  12. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
38 more
  1. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  2. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  3. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 15
  4. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  5. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  6. 2024Tuning-Free Stochastic Optimizationcited by 13
  7. 2025SGD with Adaptive Preconditioning: Unified Analysis and Momentum Accelerationcited by 12
  8. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  9. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 8
  10. 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
  11. 2024Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimizationcited by 8
  12. 2023Adaptive Federated Learning with Auto-Tuned Clientscited by 7
  13. 2022Improved Policy Optimization for Online Imitation Learningcited by 6
  14. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  15. 2021Adaptive Differentially Private Empirical Risk Minimizationcited by 5
  16. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  17. 2025Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillationcited by 5
  18. 2021First-Order Methods for Convex Optimizationcited by 4
  19. 2021Adaptive first-order methods revisited: Convex optimization without Lipschitz requirementscited by 4
  20. 2021AdaLoss: A computationally-efficient and provably convergent adaptive gradient methodcited by 4
  21. 2022Adaptive Accelerated (Extra-)Gradient Methods with Variance Reductioncited by 4
  22. 2023μ2-SGD: Stable Stochastic Optimization via a Double Momentum Mechanismcited by 4
  23. 2025Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimizationcited by 4
  24. 2022Optimistic Optimisation of Composite Objective with Exponentiated Updatecited by 3
  25. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  26. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  27. 2022Finite-Sum Optimization: A New Perspective for Convergence to a Global Solutioncited by 2
  28. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  29. 2024Tracking solutions of time-varying variational inequalitiescited by 1
  30. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
  31. 2025Online Learning-guided Learning Rate Adaptation via Gradient Alignmentcited by 1
  32. 2025Smooth Quasar-Convex Optimization with Constraintscited by 1
  33. 2026Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizescited by 1
  34. 2026When to use what Schatten-p norm in deep learning?cited by 1
  35. 2023Oblivious Stochastic Composite Optimizationcited by 0
  36. 2025A regret minimization approach to fixed-point iterationscited by 0
  37. 2026AdaGrad does not adapt to H"older-smoothness for composite objectivescited by 0
  38. 2026Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Sizecited by 0

50 most cited of 51 All 51 (JSON)