Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks

Abstract

Recent theoretical work has guaranteed that overparameterized networks trained by gradient descent achieve arbitrarily low training error, and sometimes even low test error. The required width, however, is always polynomial in at least one of the sample size $n$, the (inverse) target error $1/\epsilon$, and the (inverse) failure probability $1/\delta$. This work shows that $\tilde{\Theta }(1/\epsilon )$ iterations of gradient descent with $\tilde{\Omega }(1/{\epsilon }^2)$ training examples on two-layer ReLU networks of any width exceeding $\mathrm{polylog}(n,1/\epsilon ,1/\delta )$ suffice to achieve a test misclassification error of $\epsilon$. We also prove that stochastic gradient descent can achieve $\epsilon$ test error with polylogarithmic width and $\tilde{\Theta }(1/\epsilon )$ samples. The analysis relies upon the separation margin of the limiting kernel, which is guaranteed positive, can distinguish between true labels and random labels, and can give a tight sample-complexity analysis in the infinite-width setting

References in corpus (5)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?

Cited by in corpus (42)

• Towards Understanding the Spectral Bias of Deep Learning
• Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth
• On the linearity of large non-linear models: when and why the tangent kernel is constant
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Learning with Density Matrices and Random Features
• Mathematical Models of Overparameterized Neural Networks
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Network size and weights size for memorization with two-layers neural networks
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• On Convergence and Generalization of Dropout Training
• Memory capacity of neural networks with threshold and ReLU activations
• Distributional Generalization: A New Kind of Generalization
• Learning Parities with Neural Networks
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Hardness of Learning Neural Networks with Natural Weights
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Learning with Gradient Descent and Weakly Convex Losses
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Is deeper better? It depends on locality of relevant features
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
• An Optimization and Generalization Analysis for Max-Pooling Networks
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Provable Regret Bounds for Deep Online Learning and Control
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• The Dynamics of Gradient Descent for Overparametrized Neural Networks
• On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Models
• Deep Networks Provably Classify Data on Curves
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
• On the Provable Generalization of Recurrent Neural Networks
• Actor-critic is implicitly biased towards high entropy optimal policies
• Properties of the After Kernel
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network