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 (5)

• The Loss Surfaces of Multilayer Networks
• Spectrally-normalized margin bounds for neural networks
• The Expressive Power of Neural Networks: A View from the Width
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data

Cited by in corpus (40)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• On the Convergence and Robustness of Adversarial Training
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Optimization for deep learning: theory and algorithms
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Enhanced Convolutional Neural Tangent Kernels
• The large learning rate phase of deep learning: the catapult mechanism
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Mathematical Models of Overparameterized Neural Networks
• Learning with invariances in random features and kernel models
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Limitations of Lazy Training of Two-layers Neural Networks
• The Local Elasticity of Neural Networks
• Early-stopped neural networks are consistent
• On the Global Convergence of Training Deep Linear ResNets
• On Connected Sublevel Sets in Deep Learning
• Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• Predicting Training Time Without Training
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Noether: The More Things Change, the More Stay the Same
• Global Convergence of Gradient Descent for Deep Linear Residual Networks
• Wider Networks Learn Better Features
• Implicit bias of deep linear networks in the large learning rate phase
• Plateau Phenomenon in Gradient Descent Training of ReLU networks: Explanation, Quantification and Avoidance
• Subquadratic Overparameterization for Shallow Neural Networks
• Implicit Bias of Linear RNNs
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks