Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks

By Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu. 2018

454 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

Wide neural networks of any depth evolve as linear models under gradient descent (2019, background): “[22] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu.”
The large learning rate phase of deep learning: the catapult mechanism (2020, background): “…parameters (Lee et al., 2019); this becomes exact in the inﬁnite width limit, where these dynamics are sometimes called lazy training (Jacot et al., 2018; Lee et al., 2019; Du et al., 2019; Li & Liang, 2018; Zou et al., 2018; Allen-Zhu et al., 2019; Chizat et al., 2019; Dyer & Gur-Ari, 2020).”
When do neural networks outperform kernel methods? (2020, background): “A number of recent papers show that, if weights and SGD updates are suitably scaled, and the network is sufficiently wide (N sufficiently large), then SGD converges to a function f̂NN that is approximately in F RF(W ) + F NT(W ), with W determined by the SGD initialization [18, 13, 12, 3, 34, 25].”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “…multi-layer net to attain arbitrarily low training error on fairly generic datasets (Du et al., 2018a,c; Li & Liang, 2018; Allen-Zhu et al., 2018b; Zou et al., 2018), provided the amount of overparametriza-tion is a high polynomial of the relevant parameters (i.e. vastly more than the…”
On Lazy Training in Differentiable Programming (2018, background): “For the ﬁrst part, we do not claim improvements over [11, 22, 10, 2, 37], where a lot of effort is also put in dealing with the non-smoothness of h , which we do not study here.”
On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “Therefore, recent work on over-parameterization [Du et al., 2019, 2018b, Allen-Zhu et al., 2018b,a, Arora et al., 2019, Jacot et al., 2018, Zou et al., 2018] cannot fully explain the success of neural networks yet and we believe it is an interesting open problem to characterize this gap…”
Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation (2019, background): “Very recently, Du et al. (2018b;a); Allen-Zhu et al. (2018b;c); Zou et al. (2018) formally proved that GD or SGD can reduce an overparametrized DNN’s training error to 0 by showing that random initialization imbues the network with certain good properties5 and, with small learning rate, the network…”
Enhanced Convolutional Neural Tangent Kernels (2019, background): “A recent line of work studied overparameterized neural networks where all layers are trained [Allen-Zhu et al., 2018, Du et al., 2019b, 2018, Li and Liang, 2018, Zou et al., 2018].”
Wider Networks Learn Better Features (2019, background): “In the inﬁnite width limit, when the network is properly parameterized, activation vectors change by a negligible amount compared with their initial values [9, 17, 8, 2, 1, 33, 4].”
On the Inductive Bias of Neural Tangent Kernels (2019, methodology): “, [2, 20, 21, 27, 30, 54]) show that when a network is sufficiently over-parameterized, weights remain close to initialization during training.”
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks (2019, background): “Theoretically, a line of work study the optimization and generalization behavior of ultra-wide NNs (Allen-Zhu et al., 2018b,a; Arora et al., 2019b; Du et al., 2018b,a; Li & Liang, 2018; Zou et al., 2018; Yang, 2019; Cao & Gu, 2019a,b).”
Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality (2020, background): “…been a tremendous progress in understanding the "small training loss" phenomenon in standard (non-adversarial) training [Li and Liang, 2018, Du et al., 2019b, Allen-Zhu et al., 2019b,c, Du et al., 2019a, Arora et al., 2019b,a, Song and Yang, 2019, Zou et al., 2018, Oymak and Soltanolkotabi, 2019].”
Limitations of Lazy Training of Two-layers Neural Networks (2019, background): “Several papers show that SGD optimization within the original neural network is well approximated by optimization within the model NT as long as the number of neurons is large compared to a polynomial in the sample size N n0 [11, 10, 3, 27].”
On the Convergence and Robustness of Adversarial Training (2021, background): “While ReLU (Nair & Hinton, 2010) is nondifferentiable, recent studies (Allen-Zhu et al., 2018; Du et al., 2018; Zou et al., 2018; Cao & Gu, 2019) showed that the loss function of overparamterized deep neural networks is semi-smooth.”