Achieving Small Test Error in Mildly Overparameterized Neural Networks
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 38 of its 42 references that are in the map. First posted on arXiv 24 Apr 2021.
Builds on
38 of 42 references.
References · 38
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2017Spectrally-normalized margin bounds for neural networkscited by 681
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
- 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
- 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
- 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
- 2017Implicit Regularization in Matrix Factorizationcited by 318
- 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
- 2014The Loss Surfaces of Multilayer Networkscited by 278
- 2016Deep Learning without Poor Local Minimacited by 233
- 2018Gradient descent aligns the layers of deep linear networkscited by 182
26 more
- 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
- 2020Directional convergence and alignment in deep learningcited by 172
- 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
- 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
- 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
- 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
- 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
- 2016Topology and Geometry of Half-Rectified Network Optimizationcited by 102
- 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
- 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
- 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
- 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
- 2017The loss surface of deep and wide neural networkscited by 74
- 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
- 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
- 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
- 2020A law of robustness for two-layers neural networkscited by 54
- 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
- 2018On the loss landscape of a class of deep neural networks with no bad local valleyscited by 38
- 2018Understanding the Loss Surface of Neural Networks for Binary Classificationcited by 27
- 2018Adding One Neuron Can Eliminate All Bad Local Minimacited by 21
- 2018Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalizationcited by 21
- 2018On the Connection Between Learning Two-Layers Neural Networks and Tensor Decompositioncited by 14
- 2017The Multilinear Structure of ReLU Networkscited by 9
- 2017Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activationscited by 8
- 2019Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinitycited by 6
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 1.
3 papers.