Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
arXiv:1909.12292
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 , the (inverse) target error , and the (inverse) failure probability . This work shows that iterations of gradient descent with training examples on two-layer ReLU networks of any width exceeding suffice to achieve a test misclassification error of . We also prove that stochastic gradient descent can achieve test error with polylogarithmic width and 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 (18)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
- On the Convergence Rate of Training Recurrent Neural Networks
- What Can ResNet Learn Efficiently, Going Beyond Kernels?
- Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
- Risk and parameter convergence of logistic regression
- Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
- Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
- An Improved Analysis of Training Over-parameterized Deep Neural Networks
- Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
- Can SGD Learn Recurrent Neural Networks with Provable Generalization?
Cited by in corpus (44)
- 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
- On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
- Learning with Density Matrices and Random Features
- How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
- Mathematical Models of Overparameterized Neural Networks
- Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
- Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
- 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
- Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
- Hardness of Learning Neural Networks with Natural Weights
- When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
- Train simultaneously, generalize better: Stability of gradient-based minimax learners
- 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
- Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
- Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
- Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
- An Optimization and Generalization Analysis for Max-Pooling Networks
- Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
- The Dynamics of Gradient Descent for Overparametrized Neural Networks
- Provable Regret Bounds for Deep Online Learning and Control
- Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
- On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Models
- Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
- Deep Networks Provably Classify Data on Curves
- Properties of the After Kernel
- On the Provable Generalization of Recurrent Neural Networks
- Achieving Small Test Error in Mildly Overparameterized Neural Networks
- Actor-critic is implicitly biased towards high entropy optimal policies
- 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