Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data

By Yuanzhi Li, Yingyu Liang. 2018

687 citations recorded by the source corpus.

Neural networks have many successful applications, while much less theoretical understanding has been gained. Towards bridging this gap, we study the problem of learning a two-layer overparameterized ReLU neural network for multi-class classification via stochastic gradient descent (SGD) from random initialization. In the overparameterized setting, when the data comes from mixtures of well-separated distributions, we prove that SGD learns a network with a small generalization error, albeit the network has enough capacity to fit arbitrary labels. Furthermore, the analysis provides interesting insights into several aspects of learning neural networks and can be verified based on empirical studies on synthetic data and on the MNIST dataset.

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

In Scaling & Learning Theory

Citations in the corpus

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).”
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 Purification: How Adversarial Training Performs Robust Deep Learning (2020, neutral): “[4, 7, 8, 13, 14, 26–29, 38, 45, 50, 57, 61, 104, 115]).”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, methodology): “rror bound are well-established in theory. Recently, there is a line of work studying the convergence of neural networks in the PAClearning language, especially for over-parameterized neural networks [1, 4{8, 13{15, 21, 26, 45], putting neural network theory back to the distribution-free setting. Mo”
A Convergence Theory for Deep Learning via Over-Parameterization (2018, methodology): “The result of [20] claims to have adopted a learning rate m times larger than [34], but that is unfair because they have re-scaled the network by a factor of √ m.”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “Notably, our choice of step size is independent of number of hidden nodes m in contrast to the previous work [Li and Liang, 2018].”
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): “To 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, background): “Li & Liang (2018); Allen-Zhu et al. (2018b); Zou et al. (2018) analyzed the trajectory of parameters and showed that on the trajectory, the objective function satisﬁes certain gradient dominance property.”
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): “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.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Y. Liang would also like to acknowledge that support for this research was provided by the Office of the Vice Chancellor for Research and Graduate Education at the University of Wisconsin-Madison with funding from the Wisconsin Alumni Research Foundation.”
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, methodology): “Assumption 3.6 is inspired by the assumption made in Li and Liang (2018), where they assumed that the training data in each class are supported on a mixture of components, and any two components are separated by a certain distance.”
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).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Li and Liang [31] showed that, for two-layer networks with the cross-entropy loss, in the over-parametrization regime, gradient descent (GD) is capable of ﬁnding nearly-global optimal solutions on the training data.”
Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks (2019, methodology): “Finally, our proof techniques and intuitions are related to recent literature on global convergence of gradient descent for over-parametrized networks [6, 12, 13, 1, 5, 7, 4, 26, 2].”
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].”