A Convergence Theory for Deep Learning via Over-Parameterization
By Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song. 2018
1,651 citations recorded by the source corpus.
Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a long line of works has been focusing on training neural networks with one hidden layer. The theory of multi-layer networks remains largely unsettled. In this work, we prove why stochastic gradient descent (SGD) can find $\textit{global minima}$ on the training objective of DNNs in $\textit{polynomial time}$. We only make two assumptions: the inputs are non-degenerate and the network is over-parameterized. The latter means the network width is sufficiently large: $\textit{polynomial}$ in $L$, the number of layers and in $n$, the number of samples. Our key technique is to derive that, in a sufficiently large neighborhood of the random initialization, the optimization landscape is almost-convex and semi-smooth even with ReLU activations. This implies an equivalence between over-parameterized neural networks and neural tangent kernel (NTK) in the finite (and polynomial) width setting. As concrete examples, starting from randomly initialized weights, we prove that SGD can attain 100% training accuracy in classification tasks, or minimize regression loss in linear convergence speed, with running time polynomial in $n,L$. Our theory applies to the widely-used but non-smooth ReLU activation, and to any smooth and possibly non-convex loss functions. In terms of network architectures, our theory at least applies to fully-connected neural networks, convolutional neural networks (CNN), and residual neural networks (ResNet).
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Optimization & Training, Scaling & Learning Theory
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
- Yoshua Bengio
- Percy Liang
- Ruslan Salakhutdinov
- Mohit Bansal
- Quoc V. Le
- Jianfeng Gao
- Dacheng Tao
- Tengyu Ma
In Statistical and Nonlinear Physics
- Greg Yang
- Yuanzhi Li
- Zeyuan Allen-Zhu
- Jason D. Lee
- Simon Shaolei Du
- Quanquan Gu
- Sam Schoenholz
- Zhao Song
In Optimization & Training
- Zeyuan Allen-Zhu
- Francis R. Bach
- Jason D. Lee
- Yuanzhi Li
- Peter Richtárik
- Tengyu Ma
- Simon Lacoste-Julien
- Nati Srebro
In Scaling & Learning Theory
Citations in the corpus
- Scaling description of generalization with number of parameters in deep learning (2019, background): “In particular, recent works on the over-parametrized regime of DNNs [20, 21, 22, 23] have shown that the landscape around a typical initialization point becomes essentially convex, allowing for convergence to a global minimum during training.”
- The large learning rate phase of deep learning: the catapult mechanism (2020, background): “…dynamics of deep networks in the limit of infinite width (Daniely, 2017; Jacot et al., 2018; Lee et al., 2019; Du et al., 2019; Zou et al., 2018; Allen-Zhu et al., 2019; Li & Liang, 2018; Chizat et al., 2019; Mei et al., 2018; Rotskoff & Vanden-Eijnden, 2018; Sirignano & Spiliopoulos, 2018;…”
- LoRA: Low-Rank Adaptation of Large Language Models (2021, background): “In theory literature, it is known that neural networks outperform other classical learning methods, including the corresponding (finite-width) neural tangent kernels [5, 22] when the underlying concept class has certain low-rank structure [2, 3, 11].”
- Feature Learning in Infinite-Width Neural Networks (2020, background): “Our abc framework encapsulates all such parametrizations, and can easily tell when two ostensibly different parametrizations (e.g. (Du et al., 2018; Zou et al., 2018)) are actually equivalent or when they are really different (e.g. (Allen-Zhu et al., 2018; Du et al., 2018)) via Eq.”
- 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): “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.”
- What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, methodology): “We prove such properties using techniques from prior works [3, 5].”
- One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares (2022, neutral): “are many parameter vectors in the vicinity of the current solution that perfectly fit the new datapoint [1], [2], [12].”
- Orthogonal Gradient Descent for Continual Learning (2019, background): “…tackle this issue note that the neural networks are often overparameterized, which implies that in a close vicinity of the optimum parameter for task A, there lies optimum parameters for both tasks A and B (Azizan and Hassibi, 2018; Li and Liang, 2018; Allen-Zhu et al., 2018; Azizan et al., 2019).”
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…an over-parametrized 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…”
- 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): “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…”
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Also, for the results [3, 4] and our two-layer Theorem 1 to hold, it suffices to analyze a regime where the “sign pattern” of ReLUs can be replaced with that of the random initialization.”
- Gradient Descent Finds Global Minima of Deep Neural Networks (2018, neutral): “The dependency on n and the least eigenvalue λ0 is only polynomial, which is the same as previous work on shallow neural networks [Du et al., 2018b, Li and Liang, 2018, Allen-Zhu et al., 2018a].”
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…Anthony and Bartlett, 2009), a vast literature have recently studied the connection between the generalization performance of deep neural networks and their architectures (Neyshabur et al., 2015, 2017a,b; Bartlett et al., 2017; Golowich et al., 2017; Arora et al., 2018c; Allen-Zhu et al., 2018a).”