Adaptive Gradient Descent without Descent
Yura Malitsky, Konstantin Mishchenko
math.OC, cs.LG, math.NA, stat.ML
2019-10-22
Two gradient-only rules remove stepsize tuning from gradient descent, converging on convex problems even when the smoothness constant is infinite and beating GD and Nesterov with no tuning.
Gradient descent is the oldest optimization method and the backbone of modern machine learning. Its update fits on one line, x{k+1} = xk − λ∇f(xk), but using it runs into an old problem: how to pick the stepsize λ. The textbook bound is λ < 2/L, where L is the global Lipschitz constant of the gradient, also called the global smoothness constant. That L forces a dilemma. Many functions have no finite global L at all: exponentials, logarithms, x to the power p with p greater than 2, the matrix-factorization objective, the cubic-regularization subproblem. They are only locally smooth, so L is infinite and the standard theory breaks. Even when L is finite you have to estimate it, and being off by a factor of two can mean divergence. Tuning is a tax everyone pays.
The existing escape routes each carry a cost. Line search burns extra gradient evaluations. Adagrad and Adam are designed for the stochastic online setting. The Polyak step performs well but needs the optimal value f, which you almost never have. Barzilai-Borwein estimates the step from two consecutive gradients and is often fast, but has no convergence guarantee and can blow up on a different dataset. The stepsize problem is the oldest nuisance in optimization, and this paper attacks it head-on.
The authors propose AdGD, a minimal modification of gradient descent. Each step computes two upper bounds from gradients alone and takes the smaller as the stepsize. Rule one, do not grow too fast: λk² ≤ (1 + θ{k-1})λ{k-1}², where θk = λk/λ{k-1}. Rule two, do not overshoot the local curvature: λk ≤ 2‖xk − x{k-1}‖ / ‖∇f(xk) − ∇f(x{k-1})‖.
The ratio in rule two, ‖∇f(xk) − ∇f(x{k-1})‖ divided by ‖xk − x{k-1}‖, is a secant slope, an estimate of the local Lipschitz constant right where you are. The step therefore tracks the curvature underfoot rather than a global worst case. The whole procedure needs no function values and no line search; defaults are x0=0 and λ0=1e-10, with no problem-specific tuning.
The genuinely unconventional part is the proof. Standard convergence proofs for gradient descent rest on the descent lemma, which requires the function value to drop at every step, and that step is exactly where you need a finite global L. This paper drops the descent lemma and uses a two-step Lyapunov energy built from Cauchy-Schwarz and convexity, with a lemma that tracks three iterates at once. Because nothing assumes per-step descent, local smoothness is enough. That is the larger gift to the field: the descent lemma was a load-bearing wall, and showing it can be removed opened a line of descent-free analyses.
For convex problems the method converges even when the global L is infinite, as long as the function is locally smooth near the solution, matching gradient descent's O(1/ε) rate. For strongly convex problems it matches O(κ log 1/ε), where κ is the condition number L/μ. The stochastic variant AdSGD reaches O(κ² log 1/ε) on strongly convex finite-sum problems, one factor of κ worse than the known optimum, the price of not knowing L.
| Setting | Finding |
| Logistic regression (mushrooms/covtype/w8a) | Beats GD and Nesterov with no tuning |
| Matrix factorization (Movielens 100K, r=10/20/30) | Objective is nonconvex and not globally smooth; GD/Nesterov need near-optimal hand-tuned steps and diverge when doubled, AdGD needs none |
| ResNet-18 / DenseNet-121 (Cifar10) | AdSGD reaches higher test accuracy than SGD at equal train loss, but is slower and noisier for the first 75 epochs |
| Armijo line-search per-iteration cost | About 2x AdGD; Nesterov line search about 4x |
In the comparisons, Barzilai-Borwein diverged when the dataset changed and the Polyak step needed f. On the no-tuning axis, AdGD has essentially no peer.
Stepsize tuning is a tax every optimizer pays, and the global-smoothness assumption is routinely false outside textbook quadratics. A drop-in gradient descent that needs no L, runs on locally-smooth-only problems, and often just wins is a genuinely useful tool. More valuable is the proof technique: it shows the descent lemma can be removed and seeded a family of descent-free analyses. To be honest, this is a 2019/2020 convex-optimization result, not a new LLM trick; its value is as a clean foundational tool, and the discussion that brought it back concerns the constants in this very stepsize rule.
The authors flag three themselves. First, no theory for nonconvex objectives: they know of no generic first-order nonconvex method that avoids the descent lemma. Second, the rate they can prove only matches gradient descent, even though AdGD is often much faster in practice; the gap is unexplained. Third, extending to composite or proximal problems with nonsmooth regularizers is not straightforward. On neural networks the early epochs are noisy and slow. And the headline convergence "even when L is infinite" holds only for convex problems; the attractive wins on nonconvex matrix factorization and neural networks are empirical, not guaranteed.