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

2019/05/30 by Yuan Cao, Quanquan Gu, Cao, Yuan +1 · 10 citations
Computer Science · #Advanced Neural Network Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Neural Networks and Applications #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1905.13210

openalex publication_date 2019/05/30 · openalex created_date 2019/06/07 · openalex updated_date 2026/07/28

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 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.

Citations

• Gradient-based learning applied to document recognition
• Deep Neural Networks for Acoustic Modeling in Speech Recognition: The Shared Views of Four Research Groups
• ImageNet classification with deep convolutional neural networks
• Learning Overparameterized Neural Networks via Stochastic Gradient\n Descent on Structured Data
• A Convergence Theory for Deep Learning via Over-Parameterization
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks

Cited by

• Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention
• Data Value in the Age of Scaling: Understanding LLM Scaling Dynamics Under Real-Synthetic Data Mixtures
• Selecting Auxiliary Data via Neural Tangent Kernels for Low-Resource Domains
• On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functions
• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
• Can Mamba Learn In Context with Outliers? A Theoretical Generalization Analysis
• Faster, Smaller, and Smarter: Task-Aware Expert Merging for Online MoE Inference
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• MER-Inspector: Assessing model extraction risks from an attack-agnostic perspective
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature

Related

• A Convergence Theory for Deep Learning via Over-Parameterization
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Generalization Error Bounds for Deep Neural Networks Trained by SGD