A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network

2020/10/04 by Jun-Kun Wang, Wang, Jun-Kun, Chi-Heng Lin +3 · 2 citations
Computer Science · Mathematics · #Acceleration #Advanced Neural Network Applications #Artificial intelligence #Classical mechanics #Computer science #Economics #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Modular design #Momentum (technical analysis) #Operating system #Optimization and Control (math.OC) #Physics #Stochastic Gradient Optimization Techniques #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.2010.01618

published in arXiv (Cornell University) (Cornell University) · Accepted at ICML 2021

openalex publication_date 2020/10/04 · arxiv created 2021/06/10 · arxiv updated 2021/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Incorporating a so-called "momentum" dynamic in gradient descent methods is widely used in neural net training as it has been broadly observed that, at least empirically, it often leads to significantly faster convergence. At the same time, there are very few theoretical guarantees in the literature to explain this apparent acceleration effect. Even for the classical strongly convex quadratic problems, several existing results only show Polyak's momentum has an accelerated linear rate asymptotically. In this paper, we first revisit the quadratic problems and show a non-asymptotic accelerated linear rate of Polyak's momentum. Then, we provably show that Polyak's momentum achieves acceleration for training a one-layer wide ReLU network and a deep linear network, which are perhaps the two most popular canonical models for studying optimization and deep learning in the literature. Prior work Du at al. 2019 and Wu et al. 2019 showed that using vanilla gradient descent, and with an use of over-parameterization, the error decays as (1- Θ((1)/( κ')))^t after t iterations, where κ' is the condition number of a Gram Matrix. Our result shows that with the appropriate choice of parameters Polyak's momentum has a rate of (1-Θ((1)/(√(κ'))))^t. For the deep linear network, prior work Hu et al. 2020 showed that vanilla gradient descent has a rate of (1-Θ(\frac1κ))^t, where κ is the condition number of a data matrix. Our result shows an acceleration rate (1- Θ((1)/(√κ)))^t is achievable by Polyak's momentum. All the results in this work are obtained from a modular analysis, which can be of independent interest. This work establishes that momentum does indeed speed up neural net training.

Citations

• Some methods of speeding up the convergence of iteration methods
• ImageNet classification with deep convolutional neural networks
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Depth Creates No Bad Local Minima
• An Analytical Formula of Population Gradient for two-layered ReLU\n network and its Applications in Convergence and Critical Point Analysis
• Recovery Guarantees for One-hidden-layer Neural Networks
• Global optimality conditions for deep neural networks
• On the Convergence of Adam and Beyond
• Parametrized Accelerated Methods Free of Condition Number
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning Overparameterized Neural Networks via Stochastic Gradient\n Descent on Structured Data
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• A Convergence Theory for Deep Learning via Over-Parameterization
• Decoupled Weight Decay Regularization
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Understanding the Role of Momentum in Stochastic Gradient Methods
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Learning a Single Neuron with Gradient Methods
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• Global Convergence of Second-order Dynamics in Two-layer Neural Networks
• Generalized Leverage Score Sampling for Neural Networks
• On the linearity of large non-linear models: when and why the tangent kernel is constant

Cited by

• Provable local acceleration in HbNet-GIANT: an accelerated Newton-type distributed optimization algorithm
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum

Related

• Provable Accelerated Convergence of Nesterov's Momentum for Deep ReLU Neural Networks
• Gradient Descent with Polyak's Momentum Finds Flatter Minima via Large Catapults
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• A Convergence Analysis of Nesterov's Accelerated Gradient Method in Training Deep Linear Neural Networks
• Gradient descent with momentum --- to accelerate or to super-accelerate?