Gradient Descent Provably Optimizes Over-parameterized Neural Networks

Abstract

One of the mysteries in the success of neural networks is randomly initialized first order methods like gradient descent can achieve zero training loss even though the objective function is non-convex and non-smooth. This paper demystifies this surprising phenomenon for two-layer fully connected ReLU activated neural networks. For an $m$ hidden node shallow neural network with ReLU activation and $n$ training data, we show as long as $m$ is large enough and no two inputs are parallel, randomly initialized gradient descent converges to a globally optimal solution at a linear convergence rate for the quadratic loss function. Our analysis relies on the following observation: over-parameterization and random initialization jointly restrict every weight vector to be close to its initialization for all iterations, which allows us to exploit a strong convexity-like property to show that gradient descent converges at a global linear rate to the global optimum. We believe these insights are also useful in analyzing deep models and other first order methods.

arXiv commentICLR 2019

References in corpus (17)

• Understanding deep learning requires rethinking generalization
• The loss surface of deep and wide neural networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• Learning One-hidden-layer Neural Networks with Landscape Design
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Learning ReLUs via Gradient Descent
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Diverse Neural Network Learns True Target Functions
• Gradient Descent Can Take Exponential Time to Escape Saddle Points
• When is a Convolutional Filter Easy To Learn?
• Optimization Landscape and Expressivity of Deep CNNs
• Critical Points of Neural Networks: Analytical Forms and Landscape Properties
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Invariance of Weight Distributions in Rectified MLPs

Cited by in corpus (228)

• Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains
• FedBN: Federated Learning on Non-IID Features via Local Batch Normalization
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Scaling description of generalization with number of parameters in deep learning
• Compressed Sensing with Deep Image Prior and Learned Regularization
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Neural Network Approximation: Three Hidden Layers Are Enough
• A Theoretical Analysis of Deep Q-Learning
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• On the Convergence Rate of Training Recurrent Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Generalisation error in learning with random features and the hidden manifold model
• Training BatchNorm and Only BatchNorm: On the Expressive Power of Random Features in CNNs
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• Overparameterized Neural Networks Implement Associative Memory
• Neural Tangents: Fast and Easy Infinite Neural Networks in Python
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Stiffness: A New Perspective on Generalization in Neural Networks
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• On the linearity of large non-linear models: when and why the tangent kernel is constant
• Asymptotics of Wide Networks from Feynman Diagrams
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• A Priori Estimates of the Population Risk for Residual Networks
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Stochastic AUC Maximization with Deep Neural Networks
• Finite Versus Infinite Neural Networks: an Empirical Study
• A mean-field limit for certain deep neural networks
• Banach Space Representer Theorems for Neural Networks and Ridge Splines
• A Fine-Grained Spectral Perspective on Neural Networks
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Generalization Bounds for Sparse Random Feature Expansions
• Neural Kernels Without Tangents
• Neural Thompson Sampling
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Rethinking Positional Encoding
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Distillation $\approx$ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Theory-Inspired Path-Regularized Differential Network Architecture Search
• Dynamical Isometry and a Mean Field Theory of LSTMs and GRUs
• Convergence analysis for gradient flows in the training of artificial neural networks with ReLU activation
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Minimax Estimation of Conditional Moment Models
• How does Weight Correlation Affect the Generalisation Ability of Deep Neural Networks
• On the Banach spaces associated with multi-layer ReLU networks: Function representation, approximation theory and gradient descent dynamics
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Tensor Programs III: Neural Matrix Laws
• Structure Probing Neural Network Deflation
• Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Can Shallow Neural Networks Beat the Curse of Dimensionality? A mean field training perspective
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• Accelerated replica exchange stochastic gradient Langevin diffusion enhanced Bayesian DeepONet for solving noisy parametric PDEs
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
• Towards NNGP-guided Neural Architecture Search
• Asymptotics of Wide Convolutional Neural Networks
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• On the Neural Tangent Kernel of Deep Networks with Orthogonal Initialization
• Taylorized Training: Towards Better Approximation of Neural Network Training at Finite Width
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• WeMix: How to Better Utilize Data Augmentation
• Memory capacity of neural networks with threshold and ReLU activations
• Robust Pruning at Initialization
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
• Supervised Learning and the Finite-Temperature String Method for Computing Committor Functions and Reaction Rates
• Decoupling Gating from Linearity
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Path Length Bounds for Gradient Descent and Flow
• Computational Separation Between Convolutional and Fully-Connected Networks
• Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent
• Learning Parities with Neural Networks
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Limitations of Lazy Training of Two-layers Neural Networks
• Efficient and Private Federated Learning with Partially Trainable Networks
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• The Low-Rank Simplicity Bias in Deep Networks
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• On the Generalization Properties of Adversarial Training
• Order and Chaos: NTK views on DNN Normalization, Checkerboard and Boundary Artifacts
• Reproducing Activation Function for Deep Learning
• Neural tangent kernels, transportation mappings, and universal approximation
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• The Local Elasticity of Neural Networks
• An Investigation of how Label Smoothing Affects Generalization
• On the Convergence and Calibration of Deep Learning with Differential Privacy
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• On the Global Convergence of Training Deep Linear ResNets
• Solving PDEs on Unknown Manifolds with Machine Learning
• Approximation power of random neural networks
• Compound Probabilistic Context-Free Grammars for Grammar Induction
• Linear Convergence of Adaptive Stochastic Gradient Descent
• Generalized Leverage Score Sampling for Neural Networks
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Symmetry & critical points for a model shallow neural network
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networks
• Hardness of Learning Neural Networks with Natural Weights
• Adaptive Dense-to-Sparse Paradigm for Pruning Online Recommendation System with Non-Stationary Data
• Predicting Training Time Without Training
• Enhancing Adversarial Defense by k-Winners-Take-All
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Unbiased deep solvers for linear parametric PDEs
• Implicit Regularization via Neural Feature Alignment
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Noether: The More Things Change, the More Stay the Same
• Machine-learning-based methods for output only structural modal identification
• Implicit Regularization and Convergence for Weight Normalization
• A Theory-Driven Self-Labeling Refinement Method for Contrastive Representation Learning
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Convergence and Alignment of Gradient Descent with Random Backpropagation Weights
• Distributed Optimization for Over-Parameterized Learning
• On Iterative Neural Network Pruning, Reinitialization, and the Similarity of Masks
• RSO: A Gradient Free Sampling Based Approach For Training Deep Neural Networks
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
• A Generalized Lottery Ticket Hypothesis
• Surfing: Iterative optimization over incrementally trained deep networks
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Plateau Phenomenon in Gradient Descent Training of ReLU networks: Explanation, Quantification and Avoidance
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Distinguishing rule- and exemplar-based generalization in learning systems
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Correlation Congruence for Knowledge Distillation
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Understanding over-parameterized deep networks by geometrization
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• BINet: Learning to Solve Partial Differential Equations with Boundary Integral Networks
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Understanding the Effects of Data Parallelism and Sparsity on Neural Network Training
• Wider Networks Learn Better Features
• Bespoke vs. Prêt-à-Porter Lottery Tickets: Exploiting Mask Similarity for Trainable Sub-Network Finding
• Provable Regret Bounds for Deep Online Learning and Control
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• Pro-KD: Progressive Distillation by Following the Footsteps of the Teacher
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• On the Bias-Variance Tradeoff: Textbooks Need an Update
• Optimization Landscapes of Wide Deep Neural Networks Are Benign
• When and how epochwise double descent happens
• Generalization Error of Generalized Linear Models in High Dimensions
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Revisiting minimum description length complexity in overparameterized models
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Strong overall error analysis for the training of artificial neural networks via random initializations
• Neural Networks with Complex-Valued Weights Have No Spurious Local Minima
• On the Provable Generalization of Recurrent Neural Networks
• Making Method of Moments Great Again? -- How can GANs learn distributions
• On Alignment in Deep Linear Neural Networks
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Global Convergence and Geometric Characterization of Slow to Fast Weight Evolution in Neural Network Training for Classifying Linearly Non-Separable Data
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Deep Networks Provably Classify Data on Curves
• Competition analysis on the over-the-counter credit default swap market
• Implicit Bias of Linear RNNs
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Experiments with Rich Regime Training for Deep Learning
• On the validity of kernel approximations for orthogonally-initialized neural networks
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models
• Learning Boolean Circuits with Neural Networks
• On the Anomalous Generalization of GANs
• Second-order Information in First-order Optimization Methods
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Generalization error of minimum weighted norm and kernel interpolation
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• On Generalization of Adaptive Methods for Over-parameterized Linear Regression
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• Notes on Deep Learning Theory
• On the Stability and Generalization of Learning with Kernel Activation Functions
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Quadratic number of nodes is sufficient to learn a dataset via gradient descent
• Minimum complexity interpolation in random features models
• A Theoretical Analysis of Learning with Noisily Labeled Data
• On Symmetry and Initialization for Neural Networks
• WGAN with an Infinitely Wide Generator Has No Spurious Stationary Points
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• Tangent Space Sensitivity and Distribution of Linear Regions in ReLU Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Statistical Mechanical Analysis of Neural Network Pruning
• A Revision of Neural Tangent Kernel-based Approaches for Neural Networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversion
• Constraining Logits by Bounded Function for Adversarial Robustness
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Regularized OFU: an Efficient UCB Estimator forNon-linear Contextual Bandit
• Offline Contextual Bandits with Overparameterized Models
• Neural Optimization Kernel: Towards Robust Deep Learning
• On the convergence of gradient descent for two layer neural networks
• Stationary Density Estimation of Itô Diffusions Using Deep Learning
• Volumization as a Natural Generalization of Weight Decay
• Rapid training of deep neural networks without skip connections or normalization layers using Deep Kernel Shaping
• Why Does Multi-Epoch Training Help?
• Over-parametrized neural networks as under-determined linear systems