Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks

Abstract

We study the training and generalization of deep neural networks (DNNs) in the over-parameterized regime, where the network width (i.e., number of hidden nodes per layer) is much larger than the number of training data points. We show that, the expected $0$-$1$ loss of a wide enough ReLU network trained with stochastic gradient descent (SGD) and random initialization can be bounded by the training loss of a random feature model induced by the network gradient at initialization, which we call a neural tangent random feature (NTRF) model. For data distributions that can be classified by NTRF model with sufficiently small error, our result yields a generalization error bound in the order of $\tilde{\mathcal{O}}(n^{-1/2})$ that is independent of the network width. Our result is more general and sharper than many existing generalization error bounds for over-parameterized neural networks. In addition, we establish a strong connection between our generalization error bound and the neural tangent kernel (NTK) proposed in recent work.

25 pages, 1 figure. In NeurIPS 2019

References in corpus (8)

• On Exact Computation with an Infinitely Wide Neural Net
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Norm-Based Capacity Control in Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Generalization bounds for deep convolutional neural networks

Cited by in corpus (78)

• Deep Network Approximation for Smooth Functions
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• The Random Feature Model for Input-Output Maps between Banach Spaces
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• Review: Deep Learning in Electron Microscopy
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Towards Understanding the Spectral Bias of Deep Learning
• Deep Network with Approximation Error Being Reciprocal of Width to Power of Square Root of Depth
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Do Wider Neural Networks Really Help Adversarial Robustness?
• Neural Thompson Sampling
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• Multiple Descent: Design Your Own Generalization Curve
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Mathematical Models of Overparameterized Neural Networks
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Failures of model-dependent generalization bounds for least-norm interpolation
• Neural-BO: A Black-box Optimization Algorithm using Deep Neural Networks
• On Convergence and Generalization of Dropout Training
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Speedy Performance Estimation for Neural Architecture Search
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• Learning Parities with Neural Networks
• Graph Neural Bandits
• EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits
• Early-stopped neural networks are consistent
• Deep Learning is Singular, and That's Good
• Knowledge Distillation in Wide Neural Networks: Risk Bound, Data Efficiency and Imperfect Teacher
• Deep Active Learning by Leveraging Training Dynamics
• Hardness of Learning Neural Networks with Natural Weights
• For self-supervised learning, Rationality implies generalization, provably
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• On generalization bounds for deep networks based on loss surface implicit regularization
• Implicit Gradient Regularization
• Norm-based generalisation bounds for multi-class convolutional neural networks
• Learning with Gradient Descent and Weakly Convex Losses
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• ROMO: Retrieval-enhanced Offline Model-based Optimization
• Analysis of Knowledge Transfer in Kernel Regime
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets
• Neural Combinatorial Clustered Bandits for Recommendation Systems
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Scaling Neural Tangent Kernels via Sketching and Random Features
• Provable Regret Bounds for Deep Online Learning and Control
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Adversarial Robustness Guarantees for Random Deep Neural Networks
• On the Robustness and Generalization of Deep Learning Driven Full Waveform Inversion
• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets
• Properties of the After Kernel
• Pure Exploration in Kernel and Neural Bandits
• Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
• On the Provable Generalization of Recurrent Neural Networks
• Quantifying Epistemic Uncertainty in Deep Learning
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Neural Path Features and Neural Path Kernel : Understanding the role of gates in deep learning
• Neural Contextual Bandits without Regret
• Directional Convergence Analysis under Spherically Symmetric Distribution
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Neural Active Learning with Performance Guarantees
• Tangent Space Sensitivity and Distribution of Linear Regions in ReLU Networks
• One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks