Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

Abstract

The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized? In this work, we prove that overparameterized neural networks can learn some notable concept classes, including two and three-layer networks with fewer parameters and smooth activations. Moreover, the learning can be simply done by SGD (stochastic gradient descent) or its variants in polynomial time using polynomially many samples. The sample complexity can also be almost independent of the number of parameters in the network. On the technique side, our analysis goes beyond the so-called NTK (neural tangent kernel) linearization of neural networks in prior works. We establish a new notion of quadratic approximation of the neural network (that can be viewed as a second-order variant of NTK), and connect it to the SGD theory of escaping saddle points.

arXiv commentV1/V2/V3/V4 polish writing, V5 adds experiments, V6 reflects our camera ready version

References in corpus (24)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Spectrally-normalized margin bounds for neural networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• On the Convergence Rate of Training Recurrent Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Stronger generalization bounds for deep nets via a compression approach
• 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
• Reliably Learning the ReLU in Polynomial Time
• An Alternative View: When Does SGD Escape Local Minima?
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Theoretical properties of the global optimizer of two layer neural network
• Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations
• Learning Two Layer Rectified Neural Networks in Polynomial Time

Cited by in corpus (78)

• Knowledge Distillation: A Survey
• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Overfitting Mechanism and Avoidance in Deep Neural Networks
• Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP
• 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
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Analyzing Upper Bounds on Mean Absolute Errors for Deep Neural Network Based Vector-to-Vector Regression
• Environmental drivers of systematicity and generalization in a situated agent
• A Constructive Prediction of the Generalization Error Across Scales
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Identity Crisis: Memorization and Generalization under Extreme Overparameterization
• Progress toward favorable landscapes in quantum combinatorial optimization
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• A Priori Estimates of the Population Risk for Residual Networks
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Non-Structured DNN Weight Pruning -- Is It Beneficial in Any Platform?
• Scaling Laws for Deep Learning
• Mathematical Models of Overparameterized Neural Networks
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Greedy Layerwise Learning Can Scale to ImageNet
• Learning with invariances in random features and kernel models
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Tensor Programs III: Neural Matrix Laws
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Visualizing the PHATE of Neural Networks
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Decoupling Gating from Linearity
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Learning Parities with Neural Networks
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• Depth creates no more spurious local minima
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Early-stopped neural networks are consistent
• Towards Task and Architecture-Independent Generalization Gap Predictors
• The Local Elasticity of Neural Networks
• Hardness of Learning Neural Networks with Natural Weights
• Implicit Rugosity Regularization via Data Augmentation
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Auxiliary Learning for Deep Multi-task Learning
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• CNN Acceleration by Low-rank Approximation with Quantized Factors
• Theory III: Dynamics and Generalization in Deep Networks
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Training Neural Networks with Fixed Sparse Masks
• BINet: Learning to Solve Partial Differential Equations with Boundary Integral Networks
• Consensus-based Interpretable Deep Neural Networks with Application to Mortality Prediction
• The Dynamics of Gradient Descent for Overparametrized Neural Networks
• For Manifold Learning, Deep Neural Networks can be Locality Sensitive Hash Functions
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Learning Boolean Circuits with Neural Networks
• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• On Assessing the Quantum Advantage for MaxCut Provided by Quantum Neural Network Ansätze
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Accelerated Target Updates for Q-learning
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks
• Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Data