Source-linked AI summary
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
Rachel Ward, Xiaoxia Wu, Leon Bottou
TL;DR
The paper addresses the lack of convergence guarantees for AdaGrad on smooth, nonconvex functions and develops an analysis of AdaGrad-Norm. It proves stochastic and deterministic convergence rates with robustness to algorithm hyperparameters, while experiments suggest this robustness extends to deep-learning models without sacrificing generalization.
Problem
Existing AdaGrad theory covered online and convex optimization, leaving convergence for smooth, nonconvex functions insufficiently established.
Method
The paper analyzes AdaGrad-Norm, which adapts a single stepsize using cumulative information from observed stochastic gradient norms.
Results
AdaGrad-Norm converges at O(log(N)/sqrt(N)) in stochastic settings and O(1/N) in deterministic settings.
Takeaways & Limitations
The convergence guarantees are robust to η and b0, and experiments suggest robustness extends to deep-learning models without sacrificing generalization.
Takeaways & Limitations
The stochastic rate requires uniformly bounded gradients, and ImageNet experiments did not remove the need to tune b0 while achieving lower test accuracy than reported literature results.
Abstract
from arXiv · showhide
Adaptive gradient methods such as AdaGrad and its variants update the stepsize in stochastic gradient descent on the fly according to the gradients received along the way; such methods have gained widespread use in large-scale optimization for their ability to converge robustly, without the need to fine-tune the stepsize schedule. Yet, the theoretical guarantees to date for AdaGrad are for online and convex optimization. We bridge this gap by providing theoretical guarantees for the convergence of AdaGrad for smooth, nonconvex functions. We show that the norm version of AdaGrad (AdaGrad-Norm) converges to a stationary point at the $\mathcal{O}(\log(N)/\sqrt{N})$ rate in the stochastic setting, and at the optimal $\mathcal{O}(1/N)$ rate in the batch (non-stochastic) setting -- in this sense, our convergence guarantees are 'sharp'. In particular, the convergence of AdaGrad-Norm is robust to the choice of all hyper-parameters of the algorithm, in contrast to stochastic gradient descent whose convergence depends crucially on tuning the step-size to the (generally unknown) Lipschitz smoothness constant and level of stochastic noise on the gradient. Extensive numerical experiments are provided to corroborate our theory; moreover, the experiments suggest that the robustness of AdaGrad-Norm extends to state-of-the-art models in deep learning, without sacrificing generalization.
1. Introduction
The paper studies adaptive stepsizes for stochastic optimization of smooth, nonconvex functions, addressing practical and theoretical limits of fixed-step SGD. It analyzes AdaGrad-Norm and establishes convergence guarantees that are robust to hyperparameter choices.
- SGD minimizes differentiable nonconvex functions using stochastic gradients whose expectation equals the true gradient and whose variance is bounded.
- Fixed-step gradient descent achieves O(1/N) convergence only when its stepsize is chosen below the unknown smoothness threshold 1/L.
- Finite-iteration convergence bounds provide limited guidance for selecting practical SGD stepsize schedules, often requiring costly manual experimentation.
- AdaGrad adapts stepsizes from previously observed gradients; AdaGrad-Norm uses one scalar stepsize based on cumulative gradient-norm information.
- The paper proves AdaGrad-Norm convergence for smooth, nonconvex functions, including O(log(N)/sqrt(N)) in stochastic settings and O(1/N) when noise is absent.
- The convergence guarantees hold for any η > 0 and b0 > 0, while the stochastic rate constant requires a uniformly bounded gradient assumption.
2. AdaGrad-Norm convergence
AdaGrad-Norm provides convergence guarantees for smooth nonconvex optimization in stochastic and deterministic settings, with robustness to its hyperparameters. The stochastic result requires bounded gradients, while the deterministic result achieves an O(1/N) rate without that assumption.
- Algorithm and assumptions: AdaGrad-Norm updates a single scalar adaptive stepsize from observed gradient norms and uses unbiased stochastic gradients under independence assumptions.The analysis assumes conditional unbiasedness, independent random variables, and additional assumptions including bounded gradient noise variance.
- Stochastic convergence: Theorem 2.1 establishes high-probability convergence in the stochastic setting for any η > 0 and any initial b0 > 0.The guarantee applies under the stated smoothness, lower-bounded objective, stochastic-gradient, and bounded-gradient assumptions.
- Stochastic convergence: Compared with well-tuned fixed-step SGD, AdaGrad-Norm avoids a priori knowledge of L and σ but has a worse convergence constant, scaling with σ2 or γσ up to logarithmic factors.The additional logarithmic factor arises from the squared-gradient-norm update, while another factor reflects correlation between the adaptive stepsize and gradient norm.
- Deterministic convergence: In the deterministic setting, AdaGrad-Norm converges at the optimal O(1/N) rate for any choices of b0 and η.The adaptive denominator grows when the initial stepsize is too large, after which smoothness forces the effective stepsize toward a finite scale related to L.
- Deterministic convergence: Unlike fixed-step gradient descent, AdaGrad-Norm remains convergent when the initial parameter is below ηL, whereas fixed-step descent can fail when b0 ≤ ηL/2.The resulting rate remains close to the optimal fixed-step gradient-descent rate, with extra factors in the constant.
3. Proof of Theorem 2.1
The proof of Theorem 2.1 combines descent inequalities, conditional expectations, sequence bounds, and concentration arguments. A central difficulty is the dependence between the adaptive stepsize and the current stochastic gradient.
- Proof ingredients: The proof begins with the Descent Lemma and auxiliary bounds for sums of nonnegative sequences.These lemmas provide the basic function-decrease and summation controls used throughout the argument.
- Recursion and bound: Summing the recursion over iterations and solving the resulting quadratic inequality bounds the average squared gradient norm.The proof subsequently replaces the auxiliary quantity with the sum of squared true gradients and divides by N.
- Correlation difficulty: The adaptive denominator and stochastic gradient are correlated, so the standard SGD conditional-expectation argument cannot be applied directly.The proof therefore lacks a closed-form expression for the relevant reciprocal expectation and introduces an estimate instead.
- Recursion and bound: Markov’s inequality converts the expectation bound into a high-probability convergence statement.Jensen’s inequality is also used when bounding the relevant concave minimum function.
- Recursion and bound: The final result expresses the bound after substituting the auxiliary sum with the accumulated squared gradient norms.This yields the stated probabilistic guarantee for an ε-approximate stationary point.
4. Proof of Theorem 2.2
The deterministic proof shows that AdaGrad-Norm either reaches an ε-stationary point quickly or its adaptive accumulator grows to a threshold tied to ηL. This growth enables a convergence bound despite arbitrary initialization.
- Accumulator growth: A sequence lemma guarantees that after a prescribed number of steps, either some gradient norm is at most ε or the accumulator reaches ηL.The argument applies to a nonnegative dynamical system and uses a contradiction based on persistently large gradient values.
- Accumulator growth: The auxiliary sequence is bounded for every positive initial value b0.This establishes that the accumulator does not grow without bound under the sequence dynamics used in the proof.
- Initial phase: Before the accumulator reaches ηL, the proof controls the objective decrease using the smoothness and lower-bound assumptions.The first index k0 with bk0 ≥ ηL separates the initial phase from the later convergence analysis.
- Final bound: The remaining proof solves a quadratic inequality and handles separately the cases k0 = 1 and k0 > 1.The resulting estimates combine the initial-phase control with the accumulator-growth lemma.
5. Numerical experiments
Experiments across synthetic regression and image-classification models show that AdaGrad-Norm is broadly robust to initialization and often maintains accuracy comparable to well-tuned SGD, while some settings retain practical limitations.
- Synthetic data: AdaGrad-Norm and AdaGrad-Coordinate adapt learning rates to unknown smoothness and stochastic noise, converging across a wider b0 range than the SGD baselines.When b0 is too small, both adaptive methods can converge while SGD-Constant and SGD-DecaySqrt diverge; when b0 is too large, AdaGrad-Norm matches SGD-Constant's speed.
- Synthetic data: GD-LineSearch performs best in the batch experiment, but its significantly longer computational time makes it impractical for large-scale machine learning.The comparison includes AdaGrad-Norm, AdaGrad-Coordinate, GD-Constant, and GD-DecaySqrt.
- Image data: AdaGrad-Norm is more robust to b0 than the alternatives and reaches accuracy as good as the best performance across MNIST and CIFAR10 experiments.SGD methods and AdaGrad-Coordinate are described as highly sensitive to b0, whereas AdaGrad-Norm remains robust even for small initial values.
- Image data: Batch normalization and AdaGrad-Norm together give good performance, while the experiments also adapt stepsizes per neuron or convolutional channel rather than using a strict norm-only implementation.The neural-network implementation therefore includes a limited adaptive metric component.
- Image data: With momentum, AdaGrad-Norm remains highly robust to initialization, while SGD with momentum performs better when b0 exceeds the Lipschitz smoothness constant.For smaller b0, AdaGrad-Norm performs as well as SGD with the best stepsize, 0.1.
Appendix A. Tables
The appendix provides tables summarizing dataset statistics and the architecture of a four-layer convolutional neural network.
- Table 1 reports statistics for the datasets used in the experiments.Its caption identifies DIM as the dimension of a sample.
- Table 2 describes the architecture of a four-layer convolutional neural network.
Appendix B. Implementing Algorithm 1 in a neural network
The appendix explains how Algorithm 1 is adapted to neural-network layers, associating adaptive learning rates with neurons or convolutional channels.
- In a standard neuron, the computation applies an elementwise nonlinearity to a linear transform of input features.The weight vector, bias, input features, output, and nonlinearity define the neuron computation.
- For fully connected layers, AdaGrad-Norm associates one learning rate with each neuron, whereas SGD uses one learning rate for all neurons.
- For convolutional layers, AdaGrad-Norm associates one learning rate with each channel.The appendix gives six learning rates for the first layer of the LeNet architecture as an example.
- Figure 7 illustrates backpropagation through two hidden layers, with green edges representing the stochastic gradient G in Algorithm 1.
- The appendix includes implementations of AdaGrad-Norm, its momentum variant, and gradient descent with line search.The listed algorithms include AdaGrad-Norm with momentum and gradient descent with line search.