# Adaptive Gradient Descent without Descent

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

## Key facts

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

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

- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [A Neural-Network-Based Convex Regularizer for Inverse Problems](https://mlsanity.com/paper/2211.12461/) (2022)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization](https://mlsanity.com/paper/2201.11066/) (2022)
- [FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning](https://mlsanity.com/paper/2206.08829/) (2022)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Sequential Domain Adaptation by Synthesizing Distributionally Robust Experts](https://mlsanity.com/paper/2106.00322/) (2021)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [Uncertainty Quantification with the Empirical Neural Tangent Kernel](https://mlsanity.com/paper/2502.02870/) (2025)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [A first-order primal-dual method with adaptivity to local smoothness](https://mlsanity.com/paper/2110.15148/) (2021)
- [Adaptive Learning Rates for Faster Stochastic Gradient Methods](https://mlsanity.com/paper/2208.05287/) (2022)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Locally Adaptive Federated Learning](https://mlsanity.com/paper/2307.06306/) (2023)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Non-Uniform Smoothness for Gradient Descent](https://mlsanity.com/paper/2311.08615/) (2023)
- [Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis](https://mlsanity.com/paper/2410.05140/) (2024)
- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)

## 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.