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

  1. Yoshua Bengio
  2. Ruslan Salakhutdinov
  3. Percy Liang
  4. Sergey Levine
  5. Tengyu Ma
  6. Mohit Bansal
  7. Quoc V. Le
  8. Jianfeng Gao

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Dacheng Tao
  3. Trevor Darrell
  4. Ming-Hsuan Yang
  5. Jitendra Malik
  6. Xiaogang Wang
  7. Andrew Zisserman
  8. Andrea Vedaldi

In Scaling & Learning Theory

  1. Yuanzhi Li
  2. Greg Yang
  3. Tengyu Ma
  4. Quanquan Gu
  5. Jason D. Lee
  6. Zeyuan Allen-Zhu
  7. Colin Wei
  8. Simon Shaolei Du

Citations in the corpus