Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network

Abstract

Adaptive gradient methods like AdaGrad are widely used in optimizing neural networks. Yet, existing convergence guarantees for adaptive gradient methods require either convexity or smoothness, and, in the smooth setting, only guarantee convergence to a stationary point. We propose an adaptive gradient method and show that for two-layer over-parameterized neural networks -- if the width is sufficiently large (polynomially) -- then the proposed method converges \emph{to the global minimum} in polynomial time, and convergence is robust, \emph{ without the need to fine-tune hyper-parameters such as the step-size schedule and with the level of over-parametrization independent of the training error}. Our analysis indicates in particular that over-parametrization is crucial for the harnessing the full potential of adaptive gradient methods in the setting of neural networks.

References in corpus (11)

• ADADELTA: An Adaptive Learning Rate Method
• A Convergence Theory for Deep Learning via Over-Parameterization
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Adaptive Bound Optimization for Online Convex Optimization
• Barzilai-Borwein Step Size for Stochastic Gradient Descent
• 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
• Online Adaptive Methods, Universality and Acceleration
• Online to Offline Conversions, Universality and Adaptive Minibatch Sizes
• AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods

Cited by in corpus (25)

• Adaptive Federated Optimization
• Towards Understanding the Spectral Bias of Deep Learning
• Overparameterized Neural Networks Implement Associative Memory
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• The Low-Rank Simplicity Bias in Deep Networks
• Linear Convergence of Adaptive Stochastic Gradient Descent
• Gradient descent with momentum --- to accelerate or to super-accelerate?
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Global Convergence of SGD On Two Layer Neural Nets
• Provable Regret Bounds for Deep Online Learning and Control
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• On Alignment in Deep Linear Neural Networks
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• On Generalization of Adaptive Methods for Over-parameterized Linear Regression
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Ghosts in Neural Networks: Existence, Structure and Role of Infinite-Dimensional Null Space