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

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Limitations of Lazy Training of Two-layers Neural Networks
• On Connected Sublevel Sets in Deep Learning
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD