Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
arXiv:1902.01384
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.
arXiv comment27 pages. This version simplifies the proof and improves the presentation in Version 3. In AAAI 2020
References in corpus (39)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- A Mean Field View of the Landscape of Two-Layers Neural Networks
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
- The loss surface of deep and wide neural networks
- Characterizing Implicit Bias in Terms of Optimization Geometry
- 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
- On the Power of Over-parametrization in Neural Networks with Quadratic Activation
- Why Deep Neural Networks for Function Approximation?
- No bad local minima: Data independent training error guarantees for multilayer neural networks
- Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
- ResNet with one-neuron hidden layers is a Universal Approximator
- Optimal approximation of continuous functions by very deep ReLU networks
- Approximating Continuous Functions by ReLU Nets of Minimal Width
- Recovery Guarantees for One-hidden-layer Neural Networks
- Representation Benefits of Deep Feedforward Networks
- Global Optimality in Tensor Factorization, Deep Learning, and Beyond
- Learning ReLUs via Gradient Descent
- Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
- Norm-Based Capacity Control in Neural Networks
- Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
- SGD Learns the Conjugate Kernel Class of the Network
- Identity Matters in Deep Learning
- An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
- Diverse Neural Network Learns True Target Functions
- Risk and parameter convergence of logistic regression
- When is a Convolutional Filter Easy To Learn?
- Exponentially vanishing sub-optimal local minima in multilayer neural networks
- Learning One-hidden-layer ReLU Networks via Gradient Descent
- Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
- Critical Points of Neural Networks: Analytical Forms and Landscape Properties
- Topology and Geometry of Half-Rectified Network Optimization
- Small nonlinearities in activation functions create bad local minima in neural networks
- Learning One-hidden-layer Neural Networks under General Input Distributions
- 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