Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

By Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang. 2018

841 citations recorded by the source corpus.

The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized? In this work, we prove that overparameterized neural networks can learn some notable concept classes, including two and three-layer networks with fewer parameters and smooth activations. Moreover, the learning can be simply done by SGD (stochastic gradient descent) or its variants in polynomial time using polynomially many samples. The sample complexity can also be almost independent of the number of parameters in the network. On the technique side, our analysis goes beyond the so-called NTK (neural tangent kernel) linearization of neural networks in prior works. We establish a new notion of quadratic approximation of the neural network (that can be viewed as a second-order variant of NTK), and connect it to the SGD theory of escaping saddle points.

Subfields: Artificial Intelligence, 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

In Scaling & Learning Theory

Citations in the corpus

A Constructive Prediction of the Generalization Error Across Scales (2019, background): “Theoretical error bounds: Much attention has been given to theoretical explanations of the generalization capabilities of deep neural networks (Neyshabur et al., 2017a;b; Allen-Zhu et al., 2018a;b; Arora et al., 2018).”
Environmental drivers of systematicity and generalization in a situated agent (2019, background): “Depending on the desired level of analysis, such an explanation may ultimately come from theoretical work on neural network generalisation (Arora et al., 2018; Lampinen & Ganguli, 2018; Allen-Zhu et al., 2018; Arora et al., 2019).”
Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “Since a poly-sized NTK kernel is known to be powerful enough to incorporate any low complexity functions (such as constant-degree polynomials) [6], we have the following corollary.”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “This is in stark contrast to recent literature on optimization and generalization of neural networks [4, 21, 2, 15, 40, 1, 14] where guarantees only hold for very wide networks with the width of the network growing inversely proportional to the distance between the input samples or class margins or ”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, methodology): “The following notions introduced in [3] measure the complexity of any infinite-order smooth function φ : R→ R.”
Training Neural Networks with Fixed Sparse Masks (2021, methodology): “In practice, minimizing a large neural network’s training loss using SGD often results in models that generalize well to new data [3, 17, 27], making SGD an invaluable tool.”
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.”
Knowledge Distillation: A Survey (2020, background): “…with good performance, especially in the real-world scenarios with large-scale data, because the over parameterization improves the generalization performance when new data is considered (Zhang et al. 2018; Brutzkus and Glober-son 2019; Allen-Zhu et al. 2019; Arora et al. 2018; Tu et al. 2020).”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Researchers have proposed norm-based generalization bounds (Bartlett & Mendelson, 2002; Bartlett et al., 2017a; Neyshabur et al., 2015, 2017, 2019; Konstantinos et al., 2017; Golowich et al., 2017; Li et al., 2018a) and compression-based bounds (Arora et al., 2018).”
On Lazy Training in Differentiable Programming (2018, background): “This work is motivated by a series of recent articles [14, 26, 13, 2, 3, 47] where it is shown that over-parameterized neural networks could converge linearly to zero training loss with their parameters hardly varying.”
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…”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Finally, in concurrent work, Allen-Zhu et al. (2018c) also analyze gradient descent on deep neural networks. The primary difference between the two papers is that we analyze general smooth activations, and Allen-Zhu et al. (2018c) develop specific analysis for ReLU activation.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “, 2018a; Allen-Zhu et al., 2018c; Du et al., 2018b; Li and Liang, 2018). More specifically, Safran and Shamir (2017) showed that over-parameterization can help reduce the spurious local minima in one-hidden-layer neural networks with Rectified Linear Unit (ReLU) activation function. Du and Lee (2018”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “In the lazy regime, generalization guarantees can be derived from the distance traveled by the parameters (Neyshabur et al., 2018; Nagarajan and Kolter, 2019), which may decrease as the model capacity increases (Arora et al., 2019b; Li and Liang, 2018; Allen-Zhu et al., 2018a; Oymak et al., 2019).”