Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks

Abstract

Recent works have cast some light on the mystery of why deep nets fit any data and generalize despite being very overparametrized. This paper analyzes training and generalization for a simple 2-layer ReLU net with random initialization, and provides the following improvements over recent works: (i) Using a tighter characterization of training speed than recent papers, an explanation for why training a neural net with random labels leads to slower training, as originally observed in [Zhang et al. ICLR'17]. (ii) Generalization bound independent of network size, using a data-dependent complexity measure. Our measure distinguishes clearly between random labels and true labels on MNIST and CIFAR, as shown by experiments. Moreover, recent papers require sample complexity to increase (slowly) with the size, while our sample complexity is completely independent of the network size. (iii) Learnability of a broad class of smooth functions by 2-layer ReLU nets trained via gradient descent. The key idea is to track dynamics of training and generalization via properties of a related kernel.

In ICML 2019

References in corpus (26)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Train faster, generalize better: Stability of stochastic gradient descent
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• The loss surface of deep and wide neural networks
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Gradient descent aligns the layers of deep linear networks
• To understand deep learning we need to understand kernel learning
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• 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
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Critical Points of Neural Networks: Analytical Forms and Landscape Properties
• Invariance of Weight Distributions in Rectified MLPs

Cited by in corpus (146)

• Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains
• On Exact Computation with an Infinitely Wide Neural Net
• FedBN: Federated Learning on Non-IID Features via Local Batch Normalization
• Deep Network Approximation for Smooth Functions
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• A Theoretical Analysis of Deep Q-Learning
• 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
• A Priori Estimates of the Population Risk for Two-layer Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• 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
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Kernel and Rich Regimes in Overparametrized Models
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Environmental drivers of systematicity and generalization in a situated agent
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Asymptotics of Wide Networks from Feynman Diagrams
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• A Selective Overview of Deep Learning
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Finite Versus Infinite Neural Networks: an Empirical Study
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Neural Thompson Sampling
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• Continual Learning in Low-rank Orthogonal Subspaces
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Frequency Bias in Neural Networks for Input of Non-Uniform Density
• Distillation $\approx$ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Recent advances in deep learning theory
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• 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
• Asymptotics of Wide Convolutional Neural Networks
• On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• On Convergence and Generalization of Dropout Training
• The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks
• Memory capacity of neural networks with threshold and ReLU activations
• WeMix: How to Better Utilize Data Augmentation
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Speedy Performance Estimation for Neural Architecture Search
• Decoupling Gating from Linearity
• On the Similarity between the Laplace and Neural Tangent Kernels
• Generalization bounds for deep learning
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• When Does Preconditioning Help or Hurt Generalization?
• Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent
• Global Attention Improves Graph Networks Generalization
• Learning Parities with Neural Networks
• Rethinking Influence Functions of Neural Networks in the Over-parameterized Regime
• Learning a Single Neuron with Gradient Methods
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Neural tangent kernels, transportation mappings, and universal approximation
• Reproducing Activation Function for Deep Learning
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• A Bayesian Perspective on Training Speed and Model Selection
• Early-stopped neural networks are consistent
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• A Unified Paths Perspective for Pruning at Initialization
• Disentangling Adaptive Gradient Methods from Learning Rates
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• On the Convergence and Calibration of Deep Learning with Differential Privacy
• NASI: Label- and Data-agnostic Neural Architecture Search at Initialization
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Hardness of Learning Neural Networks with Natural Weights
• Implicit Rugosity Regularization via Data Augmentation
• Why Unsupervised Deep Networks Generalize
• Approximation power of random neural networks
• Shallow Univariate ReLu Networks as Splines: Initialization, Loss Surface, Hessian, & Gradient Flow Dynamics
• The Recurrent Neural Tangent Kernel
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Theory III: Dynamics and Generalization in Deep Networks
• Noether: The More Things Change, the More Stay the Same
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Norm-based generalisation bounds for multi-class convolutional neural networks
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Which Minimizer Does My Neural Network Converge To?
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• The Dynamics of Gradient Descent for Overparametrized Neural Networks
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Provable Regret Bounds for Deep Online Learning and Control
• Dynamically Stable Infinite-Width Limits of Neural Classifiers
• Distribution of Classification Margins: Are All Data Equal?
• Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods
• On The Effect of Auxiliary Tasks on Representation Dynamics
• Generalization Error of Generalized Linear Models in High Dimensions
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• A Temporal Kernel Approach for Deep Learning with Continuous-time Information
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• A Dynamical Central Limit Theorem for Shallow Neural Networks
• Learning Boolean Circuits with Neural Networks
• Dimension Independent Generalization Error by Stochastic Gradient Descent
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks
• Provably Training Overparameterized Neural Network Classifiers with Non-convex Constraints
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• A priori generalization error for two-layer ReLU neural network through minimum norm solution
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Doubly Robust Off-Policy Learning on Low-Dimensional Manifolds by Deep Neural Networks
• Geometry Perspective Of Estimating Learning Capability Of Neural Networks
• On Symmetry and Initialization for Neural Networks
• Directional Convergence Analysis under Spherically Symmetric Distribution
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• A Theoretical Analysis of Learning with Noisily Labeled Data
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Learning the gravitational force law and other analytic functions
• Neural Path Features and Neural Path Kernel : Understanding the role of gates in deep learning
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Why Does Multi-Epoch Training Help?
• Analytic expressions for the output evolution of a deep neural network
• Deep Gated Networks: A framework to understand training and generalisation in deep learning