A Framework for Overparameterized Learning
This work addresses the fundamental problem of explaining the success of deep learning for researchers and practitioners, offering a theoretical framework that is incremental but builds on existing insights into overparameterized models.
The paper tackles the challenge of understanding why deep neural networks perform well by proving that sufficiently wide multilayer perceptrons converge to a global optimum with a linear rate and exhibit implicit regularization, leading to improved generalization bounds and learning rate transfer. It provides theoretical guarantees with coefficients that depend on data distribution moments and supports these with empirical evidence.
A candidate explanation of the good empirical performance of deep neural networks is the implicit regularization effect of first order optimization methods. Inspired by this, we prove a convergence theorem for nonconvex composite optimization, and apply it to a general learning problem covering many machine learning applications, including supervised learning. We then present a deep multilayer perceptron model and prove that, when sufficiently wide, it $(i)$ leads to the convergence of gradient descent to a global optimum with a linear rate, $(ii)$ benefits from the implicit regularization effect of gradient descent, $(iii)$ is subject to novel bounds on the generalization error, $(iv)$ exhibits the lazy training phenomenon and $(v)$ enjoys learning rate transfer across different widths. The corresponding coefficients, such as the convergence rate, improve as width is further increased, and depend on the even order moments of the data generating distribution up to an order depending on the number of layers. The only non-mild assumption we make is the concentration of the smallest eigenvalue of the neural tangent kernel at initialization away from zero, which has been shown to hold for a number of less general models in contemporary works. We present empirical evidence supporting this assumption as well as our theoretical claims.