Source-linked AI summary
Adaptive Gradient Descent without Descent
Yura Malitsky, Konstantin Mishchenko
TL;DR
The paper addresses the need for gradient methods with automated stepsizes that do not rely on function values, line search, or global smoothness. It proposes stepsize adaptation from local curvature and proves convergence for convex functions under local smoothness, including cases where global smoothness is infinite. The analysis establishes convergence of iterates and complexity results, while experiments compare the method across convex and nonconvex problems.
Problem
Gradient descent’s stepsize requires manual tuning, can be non-robust, and may be poorly matched to local smoothness.
Method
The method chooses λk as an approximation of the inverse local Lipschitz constant using gradient information, and its proof uses boundedness followed by convergence of the whole sequence.
Results
The method converges for convex functions with locally Lipschitz gradients, with the paper also stating convergence and complexity guarantees in locally strongly convex settings.
Takeaways & Limitations
Adaptive stepsizes can provide convergence guarantees based on local smoothness rather than requiring a global smoothness constant.
Takeaways & Limitations
The theoretical rate shown for Algorithm 1 coincides with gradient descent’s rate despite better empirical performance often being observed.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper targets gradient descent’s persistent stepsize-selection problems by proposing an adaptive rule based on local geometry, without requiring function values or line search. It establishes convergence under local smoothness and convexity, while motivating the approach through limitations of standard and related methods.
- Motivation: Gradient descent requires a user-chosen stepsize, and robust selection rules remain elusive even for smooth convex optimization.The paper frames automated stepsize selection as the central deficiency it aims to remedy.
- Limitations of gradient descent: Standard gradient descent may fail globally because many functions do not satisfy the required smoothness condition.This limits the generality of analyses based on a global smoothness constant.
- Limitations of gradient descent: Gradient descent requires guessing λ, can diverge when λ is not below 2/L, and may be slow when L greatly exceeds local smoothness.These three issues respectively concern tuning effort, robustness, and mismatch between global and local geometry.
- Related approaches: Line search addresses stepsize issues through additional gradient or function evaluations, making each iteration more expensive.The paper presents line search as practical but not cost-free.
- Related approaches: Polyak’s stepsize uses gradient information and avoids the global smoothness constant, but requires a sufficiently accurate value of f∗.The method therefore replaces one tuning requirement with another.
- Contribution: The proposed method chooses λk as an approximation of the inverse local Lipschitz constant and proves O(1/k) convergence for f(xk) − f∗ under convexity and local smoothness.The paper also distinguishes its analysis from line-search approaches by requiring convergence in the end rather than monotonic decrease at every step.
2 Main part
The method adapts gradient descent stepsizes to local curvature and proves convergence using a two-step Lyapunov analysis rather than descent of function values. For convex locally smooth objectives it converges with O(1/k) function-value complexity, while local strong convexity yields a linear-rate guarantee based on local constants.
- Adaptive gradient descent: The algorithm chooses each λ_k as an approximation of the inverse local Lipschitz constant, using only gradient information.Its convergence conditions constrain stepsize growth and prevent overstepping local curvature.
- Analysis without descent: The analysis is two-step: gradient differences control the next-step displacement, while convexity and Cauchy-Schwarz produce a decreasing Lyapunov energy.Including x_{k−1} allows the proof to capture changes in gradients and establish bounded iterates.
- Convex convergence: The proof first establishes boundedness and complexity, then proves convergence of the whole sequence to a solution.Bounded iterates make local Lipschitzness sufficient on the relevant convex hull.
- Convex convergence: For convex f with locally Lipschitz ∇f, the iterates converge to a solution and achieve O(1/k) complexity for f(x_k) − f*.The theorem requires local smoothness rather than global smoothness.
- Convex convergence: The theoretical bound is f(ˆx_k) − f* ≤ D L/k, while practical stepsizes can exceed 1/(2L) and yield faster convergence.D depends explicitly on the initial data and solution set.
- Locally strongly convex objectives: Under local strong convexity and local Lipschitz gradients, the method converges with O(κ log(1/ε)) complexity using local L and μ.The condition number κ is formed from smoothness and strong-convexity constants on the convex hull of the iterates and solution.
3 Heuristics
The paper extends adaptive stepsize ideas to acceleration and stochastic gradients, but explicitly distinguishes heuristic extensions from results with theoretical guarantees. The stochastic analysis gives complexity guarantees under stated sampling and curvature assumptions, while the accelerated scheme lacks guarantees.
- 3.1 Acceleration: The proposed accelerated extension estimates both smoothness and strong convexity through dual-space quantities, using p_k = ∇f(x_k).The construction relies on the conjugate relationship between strong convexity and inverse smoothness.
- 3.1 Acceleration: Algorithm 2 has no theoretical guarantees, although related restarting methods have guarantees but require more complicated procedures and tuning.The paper presents acceleration as an application of interest rather than a fully established extension.
- 3.2 Uniting our steps with stochastic gradients: For stochastic gradients, the method can reuse the current sample or use an extra sample to estimate curvature, with different bias and assumption trade-offs.Reusing the current gradient makes λ_k∇f_{ξ_k}(x_k) biased; an extra sample estimates L_k more directly.
- 3.2 Uniting our steps with stochastic gradients: In overparameterized models with ∇f_ξ(x*) = 0 almost surely, L_k can be estimated using the same sample ξ_k.This is the setting associated with the second stated stochastic complexity result.
- 3.2 Uniting our steps with stochastic gradients: Adaptive stepsize estimation matches the known ε-dependence up to logarithmic terms but incurs an extra κ factor.The factor is identified as the price of adapting the stepsize.
- 3.2 Uniting our steps with stochastic gradients: A decreasing-stepsize SGD application is proposed, but rigorous proofs for those schemes are left for future work.The proposed rates require estimates of both smoothness and strong convexity.
4 Experiments
The experiments evaluate the adaptive method against gradient-based baselines on logistic regression, matrix factorization, cubic regularization, and neural-network training. Results emphasize reduced tuning requirements, local nonsmoothness handling, and trade-offs in iteration cost and early-stage performance.
- Logistic regression: Logistic-regression experiments compare the adaptive method with GD, acceleration, line search, Polyak, and Barzilai-Borwein methods.The study uses the mushrooms, covtype, and w8a datasets, with GD stepsizes based on an estimated smoothness constant.
- Matrix factorization: Matrix-factorization experiments use Movielens 100K with ranks r = 10, 20, 30, where tuned GD and Nesterov steps were nearly optimal but required manual tuning.Doubling the selected steps caused nonconvergence, whereas the adaptive methods required no tuning.
- Cubic regularization: Cubic-regularization subproblems with M = 10, 20, 100 produced similar results but required different iteration counts.The objective is smooth only locally because of its cubic term.
- Logistic regression: Barzilai-Borwein can be very fast but diverges after changing datasets, while Polyak performs consistently only when supplied with f∗.The experiments report no way to guess f∗ beforehand for logistic regression.
- Logistic regression: Armijo line search costs approximately 2 times more per iteration than AdGD, while Nesterov line search costs 4 times more in logistic-regression experiments.Both line-search variants remove the need to know the stepsize but require additional per-iteration work.
- Neural networks: The method achieved better test accuracy than SGD at the same train loss, but was significantly slower initially and noisy during the first 75 epochs.The neural-network experiments use ResNet-18 and DenseNet-121 on Cifar10.
5 Perspectives
The paper identifies open challenges in extending its adaptive method beyond the established convex setting and in explaining its empirical performance. Experiments include neural-network training on Cifar10, while several theoretical and practical directions remain unresolved.
- Nonconvex case: The proposed method lacks theoretical guarantees for generic nonconvex optimization because existing analysis relies on the descent lemma or a generalization of it.The authors identify nonconvex guarantees as a major challenge.
- Performance estimation: Theoretical rates match gradient descent even though Algorithm 1 often performs much better empirically than gradient descent or accelerated gradient descent.The authors call for performance-estimation techniques to bridge this theory–experiment gap.
- Composite minimization: The proof of Algorithm 1 does not appear to provide a route toward general composite minimization.The authors leave open how to resolve this limitation.
- Experiments: Figures 5 and 6 report results for training ResNet-18 and DenseNet-121, respectively, on Cifar10.The captions identify the two neural-network training experiments but state no numerical comparison.
- Stochastic optimization: Stochastic extensions have unsatisfactory bounds with suboptimal dependence on κ, and it is unclear whether deterministic techniques can improve the rate.This is presented as an unresolved extension of the analysis.
- Heuristics: The authors also seek a more solid understanding of the performance of their proposed heuristics.This is listed as a separate direction for future work.
6 Missing proofs
The missing-proof discussion completes convergence arguments by combining boundedness, local smoothness, convexity, and a cluster-point lemma. The resulting analysis establishes convergence of the iterates to a solution.
- Convergence of (xk): The proof first establishes bounded iterates and complexity, then uses an Opial-type argument to show that the entire sequence converges to a solution.The cluster-point argument is needed because boundedness alone does not imply convergence of the sequence.
- Convergence of (xk): Lemma 2 proves that a bounded sequence whose cluster points lie in the solution set has only one cluster point under the stated energy condition.Applying the lemma yields convergence to an element of the solution set.
- Convergence of (xk): All cluster points are solutions because the analysis shows ∇f(xk) → 0 and invokes local Lipschitzness of the gradient on the bounded iterate set.The set C is the convex hull of the solution and iterates, where the gradient is Lipschitz by the analysis.
- Strongly convex case: Under local strong convexity, the stepsizes satisfy λk ≤ 1/(2µ), and the strengthened analysis obtains contraction in every term.The condition is used to tighten the convergence bound.
- Strongly convex case: The proof derives a geometric contraction bound for the energy using κ = L/µ and lower bounds on the component contraction factors.The argument uses the monotonicity of θ/(1+θ) to obtain a uniform κ-dependent estimate.
7 Extensions
The paper extends adaptive gradient descent through a more general stepsize rule and a variant for known smoothness, retaining convergence guarantees under local or global smoothness assumptions.
- More general update: Algorithm 4 generalizes the adaptive stepsize update using parameters α and β, while Algorithm 1 is recovered by setting α = 1/2.The general rule controls stepsize growth and limits it using observed gradient changes.
- More general update: For convex functions with locally Lipschitz gradients, Algorithm 4 converges to a solution.The theorem also provides a bound involving a constant D determined by the initial data and solution set.
- More general update: The analysis proves bounded iterates and local Lipschitz control by combining the adaptive rule with a telescoping energy inequality.A bounded-set Lipschitz constant is then used in the convergence argument.
- More general update: The generalized rule guarantees that at least one stepsize among every m + n + 1 consecutive elements is at least α/L.This lower-bound property supports the complexity analysis.
- f is L-smooth: When L is known, Algorithm 5 uses the stronger smoothness inequality to permit larger steps than the basic convexity-based analysis.The resulting theorem preserves inequality (5) and yields an ergodic convergence rate.
- f is L-smooth: The known-L variant obtains f(ˆxk) − f∗ = O(...) for some ergodic vector ˆxk.The supplied theorem passage states the rate form but does not include its completed expression.
8 Stochastic analysis
The stochastic analysis establishes stepsize bounds and convergence results under almost-sure smoothness and strong convexity, including a same-sample update for overparameterized models.
- Stochastic update: The stochastic method uses two samples at each iteration in the analyzed version.The supplied passage introduces this as a version of SGD.
- Stochastic stepsizes: For almost-surely L-smooth and µ-strongly convex component functions, Lemma 4 provides bounds on the stepsizes generated by the stochastic rule.The proof uses strong convexity for the upper bound and iterates a lower-bound inequality.
- Stochastic convergence: Choosing α ≤ µ/(2L) yields the stochastic convergence guarantee stated in Theorem 6 under almost-sure smoothness and strong convexity.The condition also implies λk ≤ α/µ ≤ 1/(2L).
- Same sample: overparameterized models: In overparameterized models satisfying ∇fξ(x∗) = 0 almost surely, the same stochastic sample can estimate the stepsize and update the iterate.This assumption removes the issue that stepsize dependence would otherwise make the update biased.
- Same sample: overparameterized models: The overparameterized setting also permits a better bound based on ∥∇fξ0(x0)∥ ≤ L∥x0 − x∗∥.The improved estimate follows from the component gradient vanishing at the solution.
9 Experiments details
The experiments used standard neural-network implementations and specified training procedures for ResNet-18, while the proposed method used a biased adaptive-stepsize SGD variant with untested alternatives.
- The neural-network experiments used a publicly available implementation, standard data augmentation, and no weight decay.Confidence intervals used 5 random seeds for ResNet-18 and 3 for DenseNet-121.
- ResNet-18 experiments used default Adam parameters and tuned SGD’s initial stepsize by log-grid search, selecting 0.2.SGD reduced its stepsize by 10 at epochs 120 and 160 when the loss plateaued; tuning compared average test accuracy at epoch 200 across three runs.
- The proposed method used a biased SGD variant whose stepsize was computed using the sampled gradient index ξ_k.Only stepsizes based on 1/L_k and 1/(2L_k) were tested, and the momentum coefficient may also be suboptimal.