Gradient Descent Provably Optimizes Over-parameterized Neural Networks

By Simon Shaolei Du, Xiyu Zhai, Barnab'as P'oczos, Aarti Singh. 2018

1,387 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Train Large, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers (2020, background): “, 2017), and bounds the neural network generalization error (Du et al., 2019; Arora et al., 2018b).”
Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model (2019, background): “Indeed, recent theoretical works [Jacot et al., 2018, Du et al., 2019, Zhang et al., 2019a] show that for wide enough networks, the weights stay close enough to the initialization for the linearized approximation to remain accurate.”
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].”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, positive): “This is in stark contrast to related works [4, 21, 2, 15] where network size grows inversely proportional to the distance between the input samples or other notions of margin.”
Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains (2020, methodology): “To analyze the effects of applying a Fourier feature mapping to input coordinates before passing them through an MLP, we rely on recent theoretical work that models neural networks in the limits of inﬁnite width and inﬁnitesimal learning rate as kernel regression using the NTK [2, 5, 11, 16, 20].”
A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix (2020, background): “Recent advances towards understanding neural networks behavior [Jacot et al., 2018] has enabled a better understanding through Neural Tangent Kernel (NTK) [Du et al., 2018, Arora et al., 2019].”
Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, background): “In their seminal work, Du et al. (2018) prove that Gradient Descent on multilayer overparametrised RELU neural networks achieve zero training error at the limit.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Given { x i } ni =1 , we deﬁne the following Gram matrix H ∞ ∈ R n × n as follows: (3) This matrix can be viewed as a Gram matrix from a kernel associated with the ReLU function, and has been studied in (Xie et al., 2017; Tsuchida et al., 2017; Du et al., 2018c).”
On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “Lastly, with these lemmas at hand, using an argument similar to [Du et al., 2019], we can show during training, weight matrices do not move by much.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “In contrast, in the two-layer case the optimization landscape with overparameterization is almost convex [17, 32]; and in previous studies on the multi-layer case, researchers have weakened the network by applying the socalled NTK (neural tangent kernel) linearization to remove all non-convex intera”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, methodology): “Theoretically, Hardt and Ma [2016] showed that residual links in linear networks prevent gradient vanishing in a large neighborhood of zero, but for neural networks with non-linear activations, the advantages of using residual connections are not well understood.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, methodology): “However, both Li and Liang (2018) and Du et al. (2018b) only characterized the behavior of gradient-based method on one-hidden-layer shallow neural networks rather than on deep neural networks that are widely used in practice.”
Neural Tangents: Fast and Easy Infinite Neural Networks in Python (2019, methodology): “…characterized by a distribution that is related to the NNGP, and is described by the so-called Neural Tangent Kernel (NTK) (Jacot et al., 2018; Lee et al., 2019; Chizat et al., 2019), a kernel which was implicit in some earlier papers (Li & Liang, 2018; Allen-Zhu et al., 2018; Du et al., 2018a;b).”