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

2019/01/24 by Sanjeev Arora, Simon S. Du, Arora, Sanjeev +7 · 145 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #Machine Learning and ELM #Stochastic Gradient Optimization Techniques #cs.LG #cs.NE #stat.ML

paper · pdf · doi:10.48550/arxiv.1901.08584

In ICML 2019

arxiv created 2019/05/27 · arxiv updated 2019/05/28

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.

Citations

• Gradient-based learning applied to document recognition
• When is a Convolutional Filter Easy To Learn?
• A Convergence Theory for Deep Learning via Over-Parameterization

Cited by

• Feature Learning Dynamics in Infinite-Depth Neural Networks
• Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention
• Teleportation-Based Defenses for Privacy in Approximate Machine Unlearning
• Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
• Scalable Data Attribution via Forward-Only Test-Time Inference
• On the Inductive Bias of Neural Tangent Kernels
• PAS-Net: Physics-informed Adaptive Scale Deep Operator Network
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• Reproducing Activation Function for Deep Learning
• Speedy Performance Estimation for Neural Architecture Search
• Revisiting the Neural Tangent Kernel: the role of large width and depth
• Depth-induced NTK: Bridging Over-parameterized Neural Networks and Deep Neural Kernels
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning
• Disentangling Adaptive Gradient Methods from Learning Rates
• A Theoretical Analysis of Deep Q-Learning
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• A Theory of Generalization in Deep Learning
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective
• Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels
• Block Coordinate Descent for Neural Networks Provably Finds Global Minima
• NTKMTL: Mitigating Task Imbalance in Multi-Task Learning from Neural Tangent Kernel Perspective
• Position: Many generalization measures for deep learning are fragile
• Generalization Below the Edge of Stability: The Role of Data Geometry
• Local properties of neural networks through the lens of layer-wise Hessians
• FedBN: Federated Learning on Non-IID Features via Local Batch Normalization
• On the Generalization Properties of Learning the Random Feature Models with Learnable Activation Functions
• Spectral Analysis of Molecular Features: When Richer Features Do Not Guarantee Better Generalization
• How Well Can Preference Optimization Generalize Under Noisy Feedback?
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Hardness of Learning Neural Networks with Natural Weights
• INR-Bench: A Unified Benchmark for Implicit Neural Representations in Multi-Domain Regression and Reconstruction
• Learning Boolean Circuits with Neural Networks
• Theoretical Guarantees of Variational Quantum Algorithm with Guiding States
• Generalization of Gibbs and Langevin Monte Carlo Algorithms in the Interpolation Regime
• Directional Sheaf Hypergraph Networks: Unifying Learning on Directed and Undirected Hypergraphs
• Early-stopped neural networks are consistent
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
• A type of generalization error induced by initialization in deep neural networks
• Low Rank Gradients and Where to Find Them
• Growing Winning Subnetworks, Not Pruning Them: A Paradigm for Density Discovery in Sparse Neural Networks
• Quantitative convergence of trained single layer neural networks to Gaussian processes
• Sobolev acceleration for neural networks
• A Unified Paths Perspective for Pruning at Initialization
• Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods
• When Does Preconditioning Help or Hurt Generalization?
• Theoretical Foundations of Representation Learning using Unlabeled Data: Statistics and Optimization
• Achilles' Heel of Mamba: Essential difficulties of the Mamba architecture demonstrated by synthetic data
• Neural tangent kernels, transportation mappings, and universal approximation
• Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks
• SBS: Enhancing Parameter-Efficiency of Neural Representations for Neural Networks via Spectral Bias Suppression
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Memorization in Graph Neural Networks
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• Theory III: Dynamics and Generalization in Deep Networks
• Analytic expressions for the output evolution of a deep neural network
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Approximation power of random neural networks
• On Symmetry and Initialization for Neural Networks
• Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Neural Thompson Sampling
• Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains
• Gathering and Exploiting Higher-Order Information when Training Large Structured Models
• Why Does Multi-Epoch Training Help?
• Compact Vision Transformer by Reduction of Kernel Complexity
• Understanding the Evolution of the Neural Tangent Kernel at the Edge of Stability
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers
• Distillation ≈ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• The Riemannian Geometry associated to Gradient Flows of Linear Convolutional Networks
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Directional Convergence Analysis under Spherically Symmetric Distribution
• Balancing structure and randomness: maximum entropy networks for context-dependent computations
• Learning the gravitational force law and other analytic functions
• A Theoretical Analysis of Learning with Noisily Labeled Data
• Doubly Robust Off-Policy Learning on Low-Dimensional Manifolds by Deep Neural Networks
• The Recurrent Neural Tangent Kernel
• On the Similarity between the Laplace and Neural Tangent Kernels
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Asymptotics of Wide Networks from Feynman Diagrams
• When does gradient descent with logistic loss find interpolating two-layer networks?
• KCES: Training-Free Defense for Robust Graph Neural Networks via Kernel Complexity
• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Finite Versus Infinite Neural Networks: an Empirical Study
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Provable Regret Bounds for Deep Online Learning and Control
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Implicit Regularization of the Deep Inverse Prior Trained with Inertia
• On a spherically lifted spin model at finite temperature
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Model Reprogramming Demystified: A Neural Tangent Kernel Perspective
• Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks
• A priori generalization error for two-layer ReLU neural network through minimum norm solution
• Favorability of Loss Landscape with Weight Decay Requires Both Large Overparametrization and Initialization
• On Learning Verifiers and Implications to Chain-of-Thought Reasoning
• Mallows-type model averaging: Non-asymptotic analysis and all-subset combination
• A ZeNN architecture to avoid the Gaussian trap
• A Bayesian Perspective on Training Speed and Model Selection
• On the Role of Label Noise in the Feature Learning Process
• Learning a Single Neuron with Gradient Methods
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• Directional Convergence, Benign Overfitting of Gradient Descent in leaky ReLU two-layer Neural Networks
• Continuous Representation Methods, Theories, and Applications: An Overview and Perspectives
• A Selective Overview of Deep Learning
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• Learning Robust Spectral Dynamics for Temporal Domain Generalization
• Neural Multivariate Regression: Qualitative Insights from the Unconstrained Feature Model
• Block-Biased Mamba for Long-Range Sequence Processing
• Geometry of the Loss Landscape in Overparameterized Neural Networks:\n Symmetries and Invariances
• Asymptotics of Wide Convolutional Neural Networks
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Generalization Error of Generalized Linear Models in High Dimensions
• Dynamically Stable Infinite-Width Limits of Neural Classifiers
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Global Attention Improves Graph Networks Generalization
• Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network
• No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems
• A Group-Theoretic Framework for Data Augmentation
• An Effective Gram Matrix Characterizes Generalization in Deep Networks
• A Comprehensive Survey of Synthetic Tabular Data Generation
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU\n Networks with Linear Widths
• A Recipe for Global Convergence Guarantee in Deep Neural Networks

Related

• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Quantizes ReLU Network Features