Achieving Small Test Error in Mildly Overparameterized Neural Networks

Abstract

Recent theoretical works on over-parameterized neural nets have focused on two aspects: optimization and generalization. Many existing works that study optimization and generalization together are based on neural tangent kernel and require a very large width. In this work, we are interested in the following question: for a binary classification problem with two-layer mildly over-parameterized ReLU network, can we find a point with small test error in polynomial time? We first show that the landscape of loss functions with explicit regularization has the following property: all local minima and certain other points which are only stationary in certain directions achieve small test error. We then prove that for convolutional neural nets, there is an algorithm which finds one of these points in polynomial time (in the input dimension and the number of data points). In addition, we prove that for a fully connected neural net, with an additional assumption on the data distribution, there is a polynomial time algorithm.

References in corpus (5)

• The Loss Surfaces of Multilayer Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Spectrally-normalized margin bounds for neural networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity

Cited by in corpus (1)

• Early-stopped neural networks are consistent