Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks

Abstract

We study the problem of training deep neural networks with Rectified Linear Unit (ReLU) activation function using gradient descent and stochastic gradient descent. In particular, we study the binary classification problem and show that for a broad family of loss functions, with proper random weight initialization, both gradient descent and stochastic gradient descent can find the global minima of the training loss for an over-parameterized deep ReLU network, under mild assumption on the training data. The key idea of our proof is that Gaussian random initialization followed by (stochastic) gradient descent produces a sequence of iterates that stay inside a small perturbation region centering around the initial weights, in which the empirical loss function of deep ReLU networks enjoys nice local curvature properties that ensure the global convergence of (stochastic) gradient descent. Our theoretical results shed light on understanding the optimization for deep learning, and pave the way for studying the optimization dynamics of training modern deep neural networks.

54 pages. This version relaxes the assumptions on the loss functions and data distribution, and improves the dependency on the problem-specific parameters in the main theory

References in corpus (18)

• The Loss Surfaces of Multilayer Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Spectrally-normalized margin bounds for neural networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Optimal approximation of continuous functions by very deep ReLU networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• The Expressive Power of Neural Networks: A View from the Width
• Representation Benefits of Deep Feedforward Networks
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Benefits of depth in neural networks
• Stronger generalization bounds for deep nets via a compression approach
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate

Cited by in corpus (128)

• Benign Overfitting in Linear Regression
• On Exact Computation with an Infinitely Wide Neural Net
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• On the Convergence and Robustness of Adversarial Training
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• 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
• Optimization for deep learning: theory and algorithms
• A Theoretical Analysis of Deep Q-Learning
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• Review: Deep Learning in Electron Microscopy
• Are All Layers Created Equal?
• Gradient Descent Maximizes the Margin of Homogeneous 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?
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Enhanced Convolutional Neural Tangent Kernels
• When Do Neural Networks Outperform Kernel Methods?
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• The large learning rate phase of deep learning: the catapult mechanism
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Tensor Programs II: Neural Tangent Kernel for Any Architecture
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Elimination of All Bad Local Minima in Deep Learning
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Stochastic AUC Maximization with Deep Neural Networks
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Mathematical Models of Overparameterized Neural Networks
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Learning with invariances in random features and kernel models
• A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Tensor Programs III: Neural Matrix Laws
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• LaProp: Separating Momentum and Adaptivity in Adam
• On Convergence and Generalization of Dropout Training
• Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics
• Memory capacity of neural networks with threshold and ReLU activations
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Depth creates no more spurious local minima
• Limitations of Lazy Training of Two-layers Neural Networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Early-stopped neural networks are consistent
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• The Local Elasticity of Neural Networks
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• On the Global Convergence of Training Deep Linear ResNets
• Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
• Linear Convergence of Adaptive Stochastic Gradient Descent
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• On Connected Sublevel Sets in Deep Learning
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Approximation power of random neural networks
• Scaling Limit of Neural Networks with the Xavier Initialization and Convergence to a Global Minimum
• The Recurrent Neural Tangent Kernel
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
• Almost Sure Convergence of Dropout Algorithms for Neural Networks
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Predicting Training Time Without Training
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Noether: The More Things Change, the More Stay the Same
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Global Convergence of Three-layer Neural Networks in the Mean Field Regime
• Norm-based generalisation bounds for multi-class convolutional neural networks
• Global Convergence of Gradient Descent for Deep Linear Residual Networks
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Implicit bias of deep linear networks in the large learning rate phase
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Temporal-difference learning with nonlinear function approximation: lazy training and mean field regimes
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Plateau Phenomenon in Gradient Descent Training of ReLU networks: Explanation, Quantification and Avoidance
• Wider Networks Learn Better Features
• Prediction intervals for Deep Neural Networks
• Learning with convolution and pooling operations in kernel methods
• Embedding Principle of Loss Landscape of Deep Neural Networks
• Scaling Neural Tangent Kernels via Sketching and Random Features
• Provable Regret Bounds for Deep Online Learning and Control
• Subquadratic Overparameterization for Shallow Neural Networks
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• On Alignment in Deep Linear Neural Networks
• Blind Adversarial Pruning: Balance Accuracy, Efficiency and Robustness
• Fast Approximation and Estimation Bounds of Kernel Quadrature for Infinitely Wide Models
• Implicit Bias of Linear RNNs
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• SGD Through the Lens of Kolmogorov Complexity
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Normalization effects on shallow neural networks and related asymptotic expansions
• Embedding Principle: a hierarchical structure of loss landscape of deep neural networks
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• Training Deep Neural Networks via Branch-and-Bound
• Nearly Minimal Over-Parametrization of Shallow Neural Networks