AdaGrad stepsizes: Sharp convergence over nonconvex landscapes

Abstract

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.

Cited by in corpus (55)

• A Decentralized Federated Learning Framework via Committee Mechanism with Convergence Guarantee
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• WNGrad: Learn the Learning Rate in Gradient Descent
• Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization
• A stochastic version of Stein Variational Gradient Descent for efficient sampling
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• A Simple Convergence Proof of Adam and Adagrad
• Momentum-Based Variance Reduction in Non-Convex SGD
• Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning
• Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability
• Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Adaptive Gradient Descent without Descent
• A Knowledge Graph-Enhanced Tensor Factorisation Model for Discovering Drug Targets
• Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
• Adam${}^{+}$: A Stochastic Method with Adaptive Variance Reduction
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• On the Convergence of Decentralized Adaptive Gradient Methods
• Implicit Regularization and Convergence for Weight Normalization
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
• Convergence of adaptive algorithms for weakly convex constrained optimization
• Generalized Left-Localized Cayley Parametrization for Optimization with Orthogonality Constraints
• Explicit Regularization of Stochastic Gradient Methods through Duality
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails
• Asymptotic study of stochastic adaptive algorithm in non-convex landscape
• Efficient Projection-Free Online Convex Optimization with Membership Oracle
• Improving the convergence of SGD through adaptive batch sizes
• Quantized Adam with Error Feedback
• Acceleration via Fractal Learning Rate Schedules
• Low Rank Saddle Free Newton: A Scalable Method for Stochastic Nonconvex Optimization
• Adaptive Differentially Private Empirical Risk Minimization
• On Faster Convergence of Scaled Sign Gradient Descent
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization
• CADA: Communication-Adaptive Distributed Adam
• Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors
• No-regret Non-convex Online Meta-Learning
• On the Last Iterate Convergence of Momentum Methods
• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• Toward Communication Efficient Adaptive Gradient Method
• Adaptive Gradient Descent for Optimal Control of Parabolic Equations with Random Parameters
• Robust Online Convex Optimization in the Presence of Outliers
• A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization
• Momentum Improves Normalized SGD