SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data

Abstract

Neural networks exhibit good generalization behavior in the over-parameterized regime, where the number of network parameters exceeds the number of observations. Nonetheless, current generalization bounds for neural networks fail to explain this phenomenon. In an attempt to bridge this gap, we study the problem of learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks. Specifically, we prove convergence rates of SGD to a global minimum and provide generalization guarantees for this global minimum that are independent of the network size. Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers.

References in corpus (8)

• Understanding deep learning requires rethinking generalization
• Exploring Generalization in Deep Learning
• Practical recommendations for gradient-based training of deep architectures
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Spectrally-normalized margin bounds for neural networks
• Gradient Descent Learns Linear Dynamical Systems
• Recovery Guarantees for One-hidden-layer Neural Networks
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis

Cited by in corpus (21)

• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Data augmentation instead of explicit regularization
• The Pitfalls of Simplicity Bias in Neural Networks
• On the Decision Boundary of Deep Neural Networks
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
• Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
• A Provably Correct Algorithm for Deep Learning that Actually Works
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?
• Minnorm training: an algorithm for training over-parameterized deep neural networks
• Neural Entropic Estimation: A faster path to mutual information estimation
• The Multilinear Structure of ReLU Networks
• Implicit Regularization in Over-parameterized Neural Networks
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Hardness of Learning Neural Networks with Natural Weights
• Learning Sparse Neural Networks via Sensitivity-Driven Regularization
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results