The generalization error of random features regression: Precise asymptotics and double descent curve

Abstract

Deep learning methods operate in regimes that defy the traditional statistical mindset. Neural network architectures often contain more parameters than training samples, and are so rich that they can interpolate the observed labels, even if the latter are replaced by pure noise. Despite their huge complexity, the same architectures achieve small generalization error on real data. This phenomenon has been rationalized in terms of a so-called `double descent' curve. As the model complexity increases, the test error follows the usual U-shaped curve at the beginning, first decreasing and then peaking around the interpolation threshold (when the model achieves vanishing training error). However, it descends again as model complexity exceeds this threshold. The global minimum of the test error is found above the interpolation threshold, often in the extreme overparametrization regime in which the number of parameters is much larger than the number of samples. Far from being a peculiar property of deep neural networks, elements of this behavior have been demonstrated in much simpler settings, including linear regression with random covariates. In this paper we consider the problem of learning an unknown function over the $d$-dimensional sphere ${\mathbb{S}}^{d-1}$, from $n$ i.i.d. samples $({\mathbf{x}}_i,y_i)\in {\mathbb{S}}^{d-1}\times \mathbb{R}$, $i\le n$. We perform ridge regression on $N$ random features of the form $\sigma ({\mathbf{w}}_a^{\mathsf{T}}\mathbf{x})$, $a\le N$. This can be equivalently described as a two-layers neural network with random first-layer weights. We compute the precise asymptotics of the test error, in the limit $N,n,d\to \infty$ with $N/d$ and $n/d$ fixed. This provides the first analytically tractable model that captures all the features of the double descent phenomenon without assuming ad hoc misspecification structures.

arXiv commentWe reorganized the proofs of the main theorem

References in corpus (13)

• A Convergence Theory for Deep Learning via Over-Parameterization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Properties of Learning with Random Features
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• To understand deep learning we need to understand kernel learning
• Deep Convolutional Networks as shallow Gaussian Processes
• Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• SGD Learns the Conjugate Kernel Class of the Network
• Steps Toward Deep Kernel Methods from Infinite Neural Networks

Cited by in corpus (149)

• Underspecification Presents Challenges for Credibility in Modern Machine Learning
• Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
• Scaling description of generalization with number of parameters in deep learning
• Explaining Neural Scaling Laws
• Think Locally, Act Globally: Federated Learning with Local and Global Representations
• Optimization for deep learning: theory and algorithms
• The Modern Mathematics of Deep Learning
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Benign overfitting in ridge regression
• An Investigation of Why Overparameterization Exacerbates Spurious Correlations
• Generalisation error in learning with random features and the hidden manifold model
• Rethinking Bias-Variance Trade-off for Generalization of Neural Networks
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime
• Optimal Regularization Can Mitigate Double Descent
• The Gaussian equivalence of generative models for learning with shallow neural networks
• On Interpretability of Artificial Neural Networks: A Survey
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• More Data Can Hurt for Linear Regression: Sample-wise Double Descent
• Gradient Starvation: A Learning Proclivity in Neural Networks
• Generalization Bounds for Sparse Random Feature Expansions
• Exact expressions for double descent and implicit regularization via surrogate random design
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Triple descent and the two kinds of overfitting: Where & why do they appear?
• Rethinking Parameter Counting in Deep Models: Effective Dimensionality Revisited
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Multiple Descent: Design Your Own Generalization Curve
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Quantifying Relevance in Learning and Inference
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• A Precise Performance Analysis of Learning with Random Features
• Probing transfer learning with a model of synthetic correlated datasets
• Universality Laws for High-Dimensional Learning with Random Features
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Asymptotics of Ridge (less) Regression under General Source Condition
• What causes the test error? Going beyond bias-variance via ANOVA
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
• Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Gaussian Universality of Perceptrons with Random Labels
• A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Asymptotics of Wide Convolutional Neural Networks
• On the Inherent Regularization Effects of Noise Injection During Training
• Mean-Field Neural ODEs via Relaxed Optimal Control
• Double descent in the condition number
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• Distributional Generalization: A New Kind of Generalization
• A Study of Gradient Variance in Deep Learning
• Reservoir Computing meets Recurrent Kernels and Structured Transforms
• Precise Tradeoffs in Adversarial Training for Linear Regression
• When Does Preconditioning Help or Hurt Generalization?
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• High Dimensional Classification via Regularized and Unregularized Empirical Risk Minimization: Precise Error and Optimal Loss
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• Dimensionality reduction, regularization, and generalization in overparameterized regressions
• Towards an Understanding of Benign Overfitting in Neural Networks
• Implicit Regularization of Random Feature Models
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Disentangling Adaptive Gradient Methods from Learning Rates
• Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree
• Early Stopping in Deep Networks: Double Descent and How to Eliminate it
• On Sparsity in Overparametrised Shallow ReLU Networks
• Interpolating Predictors in High-Dimensional Factor Regression
• Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networks
• On the interplay between data structure and loss function in classification problems
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionality
• Benign Overfitting and Noisy Features
• The role of regularization in classification of high-dimensional noisy Gaussian mixture
• On Uniform Convergence and Low-Norm Interpolation Learning
• 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?
• Provable More Data Hurt in High Dimensional Least Squares Estimator
• Generalization Guarantees for Neural Architecture Search with Train-Validation Split
• Exploring Weight Importance and Hessian Bias in Model Pruning
• On the proliferation of support vectors in high dimensions
• The Slow Deterioration of the Generalization Error of the Random Feature Model
• Theory III: Dynamics and Generalization in Deep Networks
• A Deep Conditioning Treatment of Neural Networks
• Optimal Learning with Excitatory and Inhibitory synapses
• For interpolating kernel machines, minimizing the norm of the ERM solution minimizes stability
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• On the Universality of the Double Descent Peak in Ridgeless Regression
• When does gradient descent with logistic loss find interpolating two-layer networks?
• On the Double Descent of Random Features Models Trained with SGD
• Support vector machines and linear regression coincide with very high-dimensional features
• Recovery and Generalization in Over-Realized Dictionary Learning
• Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
• On the Role of Optimization in Double Descent: A Least Squares Study
• CoordiQ : Coordinated Q-learning for Electric Vehicle Charging Recommendation
• On the best choice of Lasso program given data parameters
• Avoiding The Double Descent Phenomenon of Random Feature Models Using Hybrid Regularization
• Removing Spurious Features can Hurt Accuracy and Affect Groups Disproportionately
• The Geometry of Over-parameterized Regression and Adversarial Perturbations
• Tight bounds for minimum l1-norm interpolation of noisy data
• On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Models
• Solvable Model for Inheriting the Regularization through Knowledge Distillation
• When and how epochwise double descent happens
• Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model
• A finite sample analysis of the benign overfitting phenomenon for ridge function estimation
• The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data
• Nonasymptotic Guarantees for Spiked Matrix Recovery with Generative Priors
• Fundamental Tradeoffs in Distributionally Adversarial Training
• Subspace Fitting Meets Regression: The Effects of Supervision and Orthonormality Constraints on Double Descent of Generalization Errors
• Generalization Error of Generalized Linear Models in High Dimensions
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• Adversarially Robust Kernel Smoothing
• Random Network Distillation as a Diversity Metric for Both Image and Text Generation
• Sparse sketches with small inversion bias
• Explaining generalization in deep learning: progress and fundamental limits
• Interpolation can hurt robust generalization even when there is no noise
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models
• Asymptotic Risk of Overparameterized Likelihood Models: Double Descent Theory for Deep Neural Networks
• Learning Curves for SGD on Structured Features
• Risk-Monotonicity in Statistical Learning
• Phases of learning dynamics in artificial neural networks: with or without mislabeled data
• Generalization error of minimum weighted norm and kernel interpolation
• Minimum complexity interpolation in random features models
• Training Efficiency and Robustness in Deep Learning
• Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models
• Double Descent Optimization Pattern and Aliasing: Caveats of Noisy Labels
• On Generalization of Adaptive Methods for Over-parameterized Linear Regression
• Benign overfitting without concentration
• Over-parametrized neural networks as under-determined linear systems
• Asymptotics of Ridge Regression in Convolutional Models
• Large-Dimensional Random Matrix Theory and Its Applications in Deep Learning and Wireless Communications
• Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective
• `Basic' Generalization Error Bounds for Least Squares Regression with Well-specified Models
• How rotational invariance of common kernels prevents generalization in high dimensions
• Generalization Properties of hyper-RKHS and its Applications
• What needles do sparse neural networks find in nonlinear haystacks
• Is Feature Diversity Necessary in Neural Network Initialization?
• Mitigating deep double descent by concatenating inputs
• Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamics