Gradient Descent Finds Global Minima of Deep Neural Networks

By Simon Shaolei Du, Jason D. Lee, Haochuan Li, Liwei Wang, Xiyu Zhai. 2018

1,268 citations recorded by the source corpus.

Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.

Subfields: Artificial Intelligence, Computational Mechanics, Model Architectures, 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 Computational Mechanics

In Model Architectures

In Optimization & Training

Citations in the corpus

Wide neural networks of any depth evolve as linear models under gradient descent (2019, background): “It has already been adopted in several recent works (van Laarhoven, 2017; Karras et al., 2018; Jacot et al., 2018; Du et al., 2018; Park et al., 2018).”
The large learning rate phase of deep learning: the catapult mechanism (2020, background): “, 2019); this becomes exact in the infinite 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].”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, neutral): “These works build on global convergence results of randomly initialized neural networks [21, 20, 2, 17, 60, 46, 47, 61] which study the gradient descent trajectory via comparisons to a a linearized Neural Tangent Kernel (NTK) learning problem.”
A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “[18] has two main results, one for fully-connected networks and the other for residual networks (ResNet).”
Wide Neural Networks Forget Less Catastrophically (2021, background): “Based on the NTK framework, other works (Allen-Zhu et al., 2019; Du et al., 2019; Zou et al., 2020) have proved the convergence of the SGD on various other settings and proved the NTK to be a powerful framework to study neural networks training dynamics.”
New Insights and Perspectives on the Natural Gradient Method (2014, methodology): “This happens both for gradient descent (Du et al., 2018; Jacot et al., 2018; Lee et al., 2019), and natural gradient descent / GGN-based methods (Zhang et al., 2019; Cai et al., 2019), applied to certain choices for L.”
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 Lazy Training in Differentiable Programming (2018, background): “While the lazy training regime provides some of the first optimization-related theoretical insights for deep neural networks [10, 2, 37, 17], we believe that it does not explain yet the many successes of neural networks that have been observed in various challenging, high-dimensional tasks in machin”
On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “Comparing with recent results on over-parameterized neural nets [Arora et al., 2019, Allen-Zhu et al., 2018b,a, Du et al., 2019, 2018b, Li and Liang, 2018, Zou et al., 2018], our theorem is a more precise characterization of the learned neural network.”
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).”
Benign overfitting in linear regression (2019, background): “Very wide neural networks, trained with gradient descent from a suitable random initialization, can be accurately approximated by linear functions in an appropriate Hilbert space, and in this case gradient descent finds an interpolating solution quickly; see [29, 21, 20, 40, 26, 1].”
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].”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “As we mentioned earlier, it has been argued in a number of recent papers that for highly overparameterized models, any random initial point is, whp, close to the solution set W (Azizan & Hassibi, 2019; Li & Liang, 2018; Du et al., 2018; Allen-Zhu et al., 2019; Cao & Gu, 2019).”