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

2019/01/24 by Sanjeev Arora, Simon S. Du, Arora, Sanjeev +7 · 68 citations
Computer Science · #Advanced Neural Network Applications #Stochastic Gradient Optimization Techniques #Machine Learning and ELM

paper · pdf · doi:10.48550/arxiv.1901.08584

Abstract

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

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

• Understanding Scaling Laws in Deep Neural Networks via Feature Learning Dynamics
• 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\n Networks
• A Dynamical View on Optimization Algorithms of Overparameterized Neural\n 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\n 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 Kernels: 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\n 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

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