Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
By Sanjeev Arora, Simon Shaolei Du, Wei Hu, Zhiyuan Li, Ruosong Wang. 2019
1,081 citations recorded by the source corpus.
Recent works have cast some light on the mystery of why deep nets fit any data and generalize despite being very overparametrized. This paper analyzes training and generalization for a simple 2-layer ReLU net with random initialization, and provides the following improvements over recent works: (i) Using a tighter characterization of training speed than recent papers, an explanation for why training a neural net with random labels leads to slower training, as originally observed in [Zhang et al. ICLR'17]. (ii) Generalization bound independent of network size, using a data-dependent complexity measure. Our measure distinguishes clearly between random labels and true labels on MNIST and CIFAR, as shown by experiments. Moreover, recent papers require sample complexity to increase (slowly) with the size, while our sample complexity is completely independent of the network size. (iii) Learnability of a broad class of smooth functions by 2-layer ReLU nets trained via gradient descent. The key idea is to track dynamics of training and generalization via properties of a related kernel.
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
- Yoshua Bengio
- Ruslan Salakhutdinov
- Percy Liang
- Sergey Levine
- Tengyu Ma
- Mohit Bansal
- Quoc V. Le
- Jianfeng Gao
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Jitendra Malik
- Xiaogang Wang
- Andrew Zisserman
- Andrea Vedaldi
In Scaling & Learning Theory
Citations in the corpus
- Environmental drivers of systematicity and generalization in a situated agent (2019, background): “…be resolved by promising theoretical analyses of neural net generalization (Arora et al., 2018; Lampinen & Ganguli, 2018; Allen-Zhu et al., 2018; Arora et al., 2019), and some more general intuitions can be gleaned from developmental psychology (Clerkin et al., 2017; Kell-man & Arterberry,…”
- The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “Another line of work has identified that deep linear networks gradually increase the rank during training [Arora et al., 2019a, Saxe et al., 2014, Lampinen and Ganguli, 2018, Gidel et al., 2019].”
- Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “operty of a random initialization; or (2) only consider the neural tangent kernel regime, where the neural networks are linearized so the features are not learned (they stay at random initialization) [4, 6{8, 13, 14, 26, 26{29, 38, 45, 50, 57, 61, 104, 114, 115]. 1 Cleaning Training global feature l”
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, methodology): “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.”
- Continual Learning in Low-rank Orthogonal Subspaces (2020, neutral): “For a ReLU nonlinearity and assuming that the non-linearity remains in the linear region during the training [Serra et al., 2017, Arora et al., 2019], we assume the Jacobian matrix to be an identity.”
- Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent (2020, methodology): “linear model when trained on certain losses under gradient descent. In addition to these findings, recent works on the convergence of Stochastic Gradient Descent for overparameterized neural networks (Arora et al., 2019) have unlocked multiple mathematical tools to study the training dynamics of over”
- On Lazy Training in Differentiable Programming (2018, background): “Other works in this line of research have appeared since the first version of this article was communicated, studying the optimization and statistical properties of various neural networks architectures in what we refer to as the lazy regime [5, 33, 32, 29, 46, 8, 27, 16, 4, 43].”
- On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “For the perturbation during training, we use high level proof idea from Du et al. [2018b], Arora et al. [2019] to reduce the perturbation on the kernel value to the perturbation on the gradient of each prediction with respect to weight matrices.”
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “[8] showed that neural networks can provably learn two-layer networks with a slightly weaker class of smooth activation functions.”
- 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].”
- Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “aining to arrive at a good nal solution. On the other hand, unlike in supervised training where the training objective involving a (over-parameterized) deep neural network can be approximately convex [9, 48, 4, 10, 31, 15, 14, 80, 30, 27, 42, 36, 52, 40, 74, 26, 81, 26], to the best of our knowledge”
- Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot (2020, background): “Deep neural networks have achieved great success in the overparameterized regime [44, 35, 8, 7, 2].”