A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
This work provides a theoretical explanation for the practical success of mildly over-parameterized neural networks, which is significant for researchers and practitioners seeking to understand and optimize neural network training without extreme over-parameterization.
This paper addresses the gap in understanding why mildly over-parameterized neural networks can achieve zero loss and recover teacher neuron directions, a phenomenon not fully explained by existing Neural Tangent Kernel or massively over-parameterized theories. The authors develop a local convergence theory for two-layer neural networks, demonstrating that if the loss is below a certain polynomial threshold, student neurons converge to teacher neurons, and the loss goes to zero. This holds for any number of student neurons equal to or exceeding teacher neurons, with a convergence rate independent of student neuron count.
While over-parameterization is widely believed to be crucial for the success of optimization for the neural networks, most existing theories on over-parameterization do not fully explain the reason -- they either work in the Neural Tangent Kernel regime where neurons don't move much, or require an enormous number of neurons. In practice, when the data is generated using a teacher neural network, even mildly over-parameterized neural networks can achieve 0 loss and recover the directions of teacher neurons. In this paper we develop a local convergence theory for mildly over-parameterized two-layer neural net. We show that as long as the loss is already lower than a threshold (polynomial in relevant parameters), all student neurons in an over-parameterized two-layer neural network will converge to one of teacher neurons, and the loss will go to 0. Our result holds for any number of student neurons as long as it is at least as large as the number of teacher neurons, and our convergence rate is independent of the number of student neurons. A key component of our analysis is the new characterization of local optimization landscape -- we show the gradient satisfies a special case of Lojasiewicz property which is different from local strong convexity or PL conditions used in previous work.