Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks

Abstract

Empirical studies show that gradient-based methods can learn deep neural networks (DNNs) with very good generalization performance in the over-parameterization regime, where DNNs can easily fit a random labeling of the training data. Very recently, a line of work explains in theory that with over-parameterization and proper random initialization, gradient-based methods can find the global minima of the training loss for DNNs. However, existing generalization error bounds are unable to explain the good generalization performance of over-parameterized DNNs. The major limitation of most existing generalization bounds is that they are based on uniform convergence and are independent of the training algorithm. In this work, we derive an algorithm-dependent generalization error bound for deep ReLU networks, and show that under certain assumptions on the data distribution, gradient descent (GD) with proper random initialization is able to train a sufficiently over-parameterized DNN to achieve arbitrarily small generalization error. Our work sheds light on explaining the good generalization performance of over-parameterized deep neural networks.

27 pages. This version simplifies the proof and improves the presentation in Version 3. In AAAI 2020

References in corpus (10)

• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Why Deep Neural Networks for Function Approximation?
• Recovery Guarantees for One-hidden-layer Neural Networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Norm-Based Capacity Control in Neural Networks
• Diverse Neural Network Learns True Target Functions
• Critical Points of Neural Networks: Analytical Forms and Landscape Properties
• Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks

Cited by in corpus (45)

• On Exact Computation with an Infinitely Wide Neural Net
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• A Theoretical Analysis of Deep Q-Learning
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Towards Understanding the Spectral Bias of Deep Learning
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Consensus-Based Optimization on the Sphere: Convergence to Global Minimizers and Machine Learning
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Integrating Deep Neural Networks with Full-waveform Inversion: Reparametrization, Regularization, and Uncertainty Quantification
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Learning a Single Neuron with Gradient Methods
• Neural tangent kernels, transportation mappings, and universal approximation
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• Knowledge Distillation in Wide Neural Networks: Risk Bound, Data Efficiency and Imperfect Teacher
• Coresets for Robust Training of Neural Networks against Noisy Labels
• Distributionally Robust Deep Learning using Hardness Weighted Sampling
• Approximation power of random neural networks
• Implicit Rugosity Regularization via Data Augmentation
• De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Estimating linear response statistics using orthogonal polynomials: An RKHS formulation
• Directional Convergence Analysis under Spherically Symmetric Distribution
• A Revision of Neural Tangent Kernel-based Approaches for Neural Networks
• Regularized OFU: an Efficient UCB Estimator forNon-linear Contextual Bandit
• Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise