mlsanityData to 14 Oct 2026

Adaptive Gradient Descent without Descent

arXiv 1910.09529 ↗First posted 21 Oct 2019math.OC cs.LG cs.NAcited by 79

Not on the map. Why?

Abstract (arXiv)

We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) don't increase the stepsize too fast and 2) don't overstep the local curvature. No need for functional values, no line search, no information about the function except for the gradients. By following these rules, you get a method adaptive to the local geometry, with convergence guarantees depending only on the smoothness in a neighborhood of a solution. Given that the problem is convex, our method converges even if the global smoothness constant is infinity. As an illustration, it can minimize arbitrary continuously twice-differentiable convex function. We examine its performance on a range of convex and nonconvex problems, including logistic regression and matrix factorization.

Key facts. Cited by 79 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 14; 2024: 15; 2025: 18; 2026: 16.

79 papers.

Sort:

By area:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 133
  2. 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 69
  3. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 52
  4. 2022A Neural-Network-Based Convex Regularizer for Inverse Problemscited by 41
  5. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  6. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  7. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  8. 2022FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learningcited by 23
  9. 2021Regularized Newton Method with Global O(1/k2) Convergencecited by 22
  10. 2023Adaptive Proximal Gradient Method for Convex Optimizationcited by 21
  11. 2023Normalized Gradients for Allcited by 20
  12. 2023Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradientcited by 19
38 more
  1. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  2. 2024Directional Smoothness and Gradient Methods: Convergence and Adaptivitycited by 17
  3. 2021Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Informationcited by 16
  4. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
  5. 2021Sequential Domain Adaptation by Synthesizing Distributionally Robust Expertscited by 14
  6. 2024Tuning-Free Stochastic Optimizationcited by 13
  7. 2025Uncertainty Quantification with the Empirical Neural Tangent Kernelcited by 11
  8. 2022Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Methodcited by 9
  9. 2023Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERMcited by 8
  10. 2021A first-order primal-dual method with adaptivity to local smoothnesscited by 7
  11. 2022Adaptive Learning Rates for Faster Stochastic Gradient Methodscited by 7
  12. 2023Adaptive Federated Learning with Auto-Tuned Clientscited by 7
  13. 2023Locally Adaptive Federated Learningcited by 7
  14. 2024Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizescited by 6
  15. 2023Non-Uniform Smoothness for Gradient Descentcited by 5
  16. 2024Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysiscited by 5
  17. 2025The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applicationscited by 5
  18. 2025Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillationcited by 5
  19. 2025Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimizationcited by 5
  20. 2024Adaptive proximal gradient methods are universal without approximationcited by 4
  21. 2025Theoretical Analysis on how Learning Rate Warmup Accelerates Convergencecited by 4
  22. 2026A lower bound for stepsize-based acceleration of gradient descentcited by 4
  23. 2024SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learningcited by 3
  24. 2025Gradient Methods with Online Scaling Part I. Theoretical Foundationscited by 3
  25. 2023A Second-Order Majorant Algorithm for Nonnegative Matrix Factorizationcited by 2
  26. 2023On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithmscited by 2
  27. 2025AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descentcited by 2
  28. 2025Glocal Smoothness: Line search and adaptive step sizes can help in theory too!cited by 2
  29. 2025Sparse Polyak: an adaptive step size rule for high-dimensional M-estimationcited by 2
  30. 2026Fast and Large-Scale Unbalanced Optimal Transport via its Semi-Dual and Adaptive Gradient Methodscited by 2
  31. 2022Orthogonal Nonnegative Matrix Factorization with Sparsity Constraintscited by 1
  32. 2022Self-adaptive algorithms for quasiconvex programming and applications to machine learningcited by 1
  33. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  34. 2024Towards Stability of Parameter-Free Optimizationcited by 1
  35. 2024WarpAdam: A new Adam optimizer based on Meta-Learning approachcited by 1
  36. 2024The inexact power augmented Lagrangian method for constrained nonconvex optimizationcited by 1
  37. 2024Don't Be So Positive: Negative Step Sizes in Second-Order Methodscited by 1
  38. 2025First-ish Order Methods: Hessian-aware Scalings of Gradient Descentcited by 1

50 most cited of 79 All 79 (JSON)