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

Abstract

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