Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data

Abstract

Neural networks have many successful applications, while much less theoretical understanding has been gained. Towards bridging this gap, we study the problem of learning a two-layer overparameterized ReLU neural network for multi-class classification via stochastic gradient descent (SGD) from random initialization. In the overparameterized setting, when the data comes from mixtures of well-separated distributions, we prove that SGD learns a network with a small generalization error, albeit the network has enough capacity to fit arbitrary labels. Furthermore, the analysis provides interesting insights into several aspects of learning neural networks and can be verified based on empirical studies on synthetic data and on the MNIST dataset.

arXiv commentNeurIPS'18 version. Appendix updated, additional experimental results added

Cited by in corpus (188)

• LoRA: Low-Rank Adaptation of Large Language Models
• A Convergence Theory for Deep Learning via Over-Parameterization
• Benign Overfitting in Linear Regression
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Optimization for deep learning: theory and algorithms
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies
• On the Convergence Rate of Training Recurrent Neural Networks
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Overlearning Reveals Sensitive Attributes
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Towards Understanding the Spectral Bias of Deep Learning
• The large learning rate phase of deep learning: the catapult mechanism
• Neural Tangents: Fast and Easy Infinite Neural Networks in Python
• Analyzing Upper Bounds on Mean Absolute Errors for Deep Neural Network Based Vector-to-Vector Regression
• Kernel and Rich Regimes in Overparametrized Models
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Strong error analysis for stochastic gradient descent optimization algorithms
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• SGD on Neural Networks Learns Functions of Increasing Complexity
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• A Priori Estimates of the Population Risk for Residual Networks
• Finite Versus Infinite Neural Networks: an Empirical Study
• Stochastic AUC Maximization with Deep Neural Networks
• Orthogonal Gradient Descent for Continual Learning
• Generalization Bounds for Sparse Random Feature Expansions
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Distillation $\approx$ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• Feature Space Singularity for Out-of-Distribution Detection
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Mathematical Models of Overparameterized Neural Networks
• A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions
• HYDRA: Hypergradient Data Relevance Analysis for Interpreting Deep Neural Networks
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
• Memorization in Overparameterized Autoencoders
• Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
• Network size and weights size for memorization with two-layers neural networks
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• Failures of model-dependent generalization bounds for least-norm interpolation
• On Convergence and Generalization of Dropout Training
• Towards NNGP-guided Neural Architecture Search
• On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers
• On the geometry of generalization and memorization in deep neural networks
• Memory capacity of neural networks with threshold and ReLU activations
• Taylorized Training: Towards Better Approximation of Neural Network Training at Finite Width
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Depth creates no more spurious local minima
• Gradients as Features for Deep Representation Learning
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• Computational Separation Between Convolutional and Fully-Connected Networks
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• The Local Elasticity of Neural Networks
• Early-stopped neural networks are consistent
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• Deep Equals Shallow for ReLU Networks in Kernel Regimes
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Deep Learning is Singular, and That's Good
• On the Global Convergence of Training Deep Linear ResNets
• Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting
• Symmetry & critical points for a model shallow neural network
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Generalized Leverage Score Sampling for Neural Networks
• Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
• Generalisation dynamics of online learning in over-parameterised neural networks
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality
• A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
• Enhancing Adversarial Defense by k-Winners-Take-All
• Understanding the Generalization of Adam in Learning Neural Networks with Proper Regularization
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• A Theory-Driven Self-Labeling Refinement Method for Contrastive Representation Learning
• Theory III: Dynamics and Generalization in Deep Networks
• Max-Affine Spline Insights into Deep Generative Networks
• On the Principle of Least Symmetry Breaking in Shallow ReLU Models
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• A global convergence theory for deep ReLU implicit networks via over-parameterization
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• When does gradient descent with logistic loss find interpolating two-layer networks?
• RSO: A Gradient Free Sampling Based Approach For Training Deep Neural Networks
• Implicit Gradient Regularization
• Neural Tangent Kernel Maximum Mean Discrepancy
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• A Deep Conditioning Treatment of Neural Networks
• Challenges for cognitive decoding using deep learning methods
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Distinguishing rule- and exemplar-based generalization in learning systems
• 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
• Which Minimizer Does My Neural Network Converge To?
• Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Understanding the Effects of Data Parallelism and Sparsity on Neural Network Training
• Label-Aware Neural Tangent Kernel: Toward Better Generalization and Local Elasticity
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime
• A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• Extreme Memorization via Scale of Initialization
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• PAC-Bayesian Generalization Bounds for MultiLayer Perceptrons
• Fundamental Tradeoffs in Distributionally Adversarial Training
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• Training Learned Optimizers with Randomly Initialized Learned Optimizers
• Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Shallow Neural Network can Perfectly Classify an Object following Separable Probability Distribution
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees
• A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensing
• On the validity of kernel approximations for orthogonally-initialized neural networks
• Experiments with Rich Regime Training for Deep Learning
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Implicit Bias of Linear RNNs
• Phases of learning dynamics in artificial neural networks: with or without mislabeled data
• Explaining generalization in deep learning: progress and fundamental limits
• Imitating Deep Learning Dynamics via Locally Elastic Stochastic Differential Equations
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Learning and Generalization in RNNs
• Stochastic Thermodynamics of Learning Parametric Probabilistic Models
• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets
• Theoretical Exploration of Flexible Transmitter Model
• Quantifying Epistemic Uncertainty in Deep Learning
• On the Provable Generalization of Recurrent Neural Networks
• Properties of the After Kernel
• Deep Residual Networks Learn the Geodesic Curve in the Wasserstein Space
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Dimension Independent Generalization Error by Stochastic Gradient Descent
• On the convergence of gradient descent for two layer neural networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Information Theoretic Lower Bounds for Feed-Forward Fully-Connected Deep Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• On Symmetry and Initialization for Neural Networks
• Reservoir Transformers
• Towards Understanding Learning in Neural Networks with Linear Teachers
• WGAN with an Infinitely Wide Generator Has No Spurious Stationary Points
• Painless step size adaptation for SGD
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Directional Convergence Analysis under Spherically Symmetric Distribution
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Rapid training of deep neural networks without skip connections or normalization layers using Deep Kernel Shaping
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Non-Convex Compressed Sensing with Training Data
• Layer-Wise Interpretation of Deep Neural Networks Using Identity Initialization
• Asymptotics of Ridge Regression in Convolutional Models
• Neurons learn slower than they think
• Large-Dimensional Random Matrix Theory and Its Applications in Deep Learning and Wireless Communications
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks
• Universality of Gradient Descent Neural Network Training
• A Revision of Neural Tangent Kernel-based Approaches for Neural Networks
• Why to "grow" and "harvest" deep learning models?
• Parallel Stochastic Optimization Framework for Large-Scale Non-Convex Stochastic Problems
• Nearly Minimal Over-Parametrization of Shallow Neural Networks