Source-linked AI summary
Two models of double descent for weak features
Mikhail Belkin, Daniel Hsu, Ji Xu
TL;DR
The paper asks how double descent arises when models use many potentially weak features rather than features selected in an informed order. It analyzes least squares/least norm prediction in two random-feature models and proves that risk can peak near p = n before decreasing beyond that threshold. The results support using abundant weak features in the analyzed setting, while the conclusions remain dependent on the application regime and assumptions about feature selection.
Problem
Double descent describes out-of-sample prediction as model parameterization varies, but its behavior with plentiful, individually weak features requires precise analysis.
Method
The paper mathematically analyzes least squares/least norm predictors in Gaussian and Fourier random-feature models with randomly selected features.
Results
Risk becomes infinite around p = n and decreases as p increases beyond n in both models; at high signal-to-noise ratio, minimum risk occurs in the p > n regime.
Takeaways & Limitations
With uninformed weak-feature selection, choosing as many features as possible may outperform limiting p to the classical bias-variance balance, though processing many parameters can be costly.
Takeaways & Limitations
The conclusions distinguish weak-but-plentiful interpolating settings from classical p < n analyses, and best practices depend on the application's regime.
Abstract
from arXiv · showhide
The "double descent" risk curve was proposed to qualitatively describe the out-of-sample prediction accuracy of variably-parameterized machine learning models. This article provides a precise mathematical analysis for the shape of this curve in two simple data models with the least squares/least norm predictor. Specifically, it is shown that the risk peaks when the number of features $p$ is close to the sample size $n$, but also that the risk decreases towards its minimum as $p$ increases beyond $n$. This behavior is contrasted with that of "prescient" models that select features in an a priori optimal order.
1 Introduction
The paper places double descent in the context of over-parameterized prediction and analyzes it mathematically using least squares/least norm predictors in two random-feature models. It distinguishes randomly selected weak features from prescient feature selection and relates the analysis to prior explanations of the phenomenon.
- Motivation: The double descent curve describes out-of-sample prediction performance as the number of model parameters varies, extending classical bias-variance analysis to interpolating models.Prior observations include several model families, including neural networks, across varied applications.
- Approach: The paper analyzes key aspects of double descent with least squares/least norm predictors in Gaussian and Fourier random-feature models.The Gaussian model concerns the classical p ≤ n regime, while the Fourier model concerns functions on the circle.
- Feature selection: The models use randomly selected features that may be individually weak, unlike prescient models that include features known a priori to be most useful.The paper presents prescient selection as a comparison with informed feature ordering.
- Related perspectives: Prior work connects double descent to variance reduction from increasing neural-network width and to jamming-like transitions between under- and over-parameterized regimes.This paper makes these ideas explicit in simple regression models.
- Related work: The paper's analysis is situated alongside concurrent studies of least squares/least norm prediction in over-parameterized linear regression.Those studies include work focused on well-specified settings and risk bounds that vanish as p increases.
2 Gaussian model
The Gaussian model gives an explicit risk analysis for least squares/least norm prediction under arbitrary and random feature subsets. Under random selection, risk rises to the interpolation threshold p = n, then falls beyond it; at sufficiently high signal-to-noise ratio, the minimum occurs with p > n, unlike prescient selection.
- Model and risk formula: Theorem 1 derives the prediction risk for least squares/least norm coefficients using any subset T of p features in a Gaussian linear model.The model assumes standard normal features, independent standard normal noise, and y = x*β + σϵ.
- Random feature selection: For uniformly random feature subsets, the risk increases with p up to the interpolation threshold p = n and decreases afterward.This conclusion assumes D > n + 1.
- Random feature selection: When the signal-to-noise ratio ∥β∥2/σ2 exceeds D/(D − n − 1), the risk is smallest at p = D and is lower than at every p ≤ n.The resulting first descent is degenerate, with the bias-variance sweet spot at p = 0.
- Risk near interpolation: The risk becomes infinite at p = n and p = n + 1, while for p ≥ n + 2 the noise contribution contains the factor n/(p − n − 1).This behavior follows from inverse-Wishart properties of the design matrix.
- Proof and concentration: The over-parameterized error decomposes into squared projection bias and a Gaussian noise quadratic form controlled by the Wishart design matrix.The projection term measures distance from βT to a random n-dimensional subspace of Rp.
- Proof and concentration: The parameter µ is small when signal is spread across many weak features and large when β is concentrated on a sparse subset.This parameter is used in concentration analysis of ∥β − β̂∥2.
3 Fourier series model
The Fourier series model studies least-norm regression with randomly selected rows and features of a discrete Fourier transform matrix. In the high-dimensional limit, its risk diverges when feature and sample proportions are close, then decreases as the feature proportion approaches one.
- The model uses a noise-free Fourier series setting, a one-dimensional analogue of random Fourier features for functions on the unit circle.
- Random subsets S and T independently select rows and columns, with expected proportions ρn = n/D and ρp = p/D.The observed design is the submatrix F S,T, paired with the response subvector µS.
- The fitted coefficients use the pseudoinverse of F S,T applied to µS, with coefficients outside T set to zero.
- The discrete Fourier matrix property rank(F A,B) = min{|A|, |B|} underpins the risk analysis for every row and column subset.This rank identity follows from the Vandermonde structure of F.
- Theorem 3 analyzes the asymptotic risk as D, n, and p grow while ρn and ρp remain fixed, in the regime ρp > ρn.
- The risk diverges when ρp is close to ρn and decreases as ρp approaches 1, matching the Gaussian model's random-feature behavior.Figure 3 gives a non-asymptotic example using D = 1024, n = 256, and averages over 10 random choices of S and T.
4 Discussion
The analysis finds that uninformed feature selection can favor using many features, including more than the sample size, whereas prescient selection can favor balancing bias and variance. It also emphasizes that model and feature-selection practices depend on the application's regime.
- Feature-selection regimes: Uninformed feature selection may make using as many features as possible—even more than the number of data—preferable to classical bias-variance balancing.This simple strategy may incur computational costs and avoids precise control of regularization parameters.
- Feature-selection regimes: Prescient selection of the best features can make choosing a feature count that balances bias and variance better than using all features.
- Regime dependence: Best practices for model and feature selection depend crucially on the application's regime, including classical p < n and weak-but-plentiful interpolating settings.The paper describes understanding of the latter setting as only beginning to emerge.
A Proof of Theorem 2
The proof treats the cases p > n and p < n separately, using projection geometry, quadratic-form bounds, singular-value conditioning, and symmetry between the two regimes.
- p > n: For p > n, the proof combines a decomposition with probability inequalities and concentration-based bounds to complete the argument.The bounds use Gaussian comparison inequalities and concentration of measure, with conditions such as p > (1 + t)^2n.
- Projection geometry: The projection term is interpreted as the squared distance from βT to a uniformly random n-dimensional subspace of R^p.This distributional interpretation invokes the same argument used in a proof of the Johnson-Lindenstrauss lemma.
- Quadratic-form control: The noise term is handled as a random quadratic form in η, with bounds conditioned on the nonsingularity of KT.KT is defined from XT and X*T, while η is Gaussian and independent of XT.
- p < n: For p < n, the proof repeats the preceding strategy after switching the roles of p and n and replacing α with α^-1.
B Confidence bounds
The appendix derives fixed-level confidence bounds from probability inequalities, including a high-probability result for p < n under positivity conditions on denominators.
- Confidence bounds: Fixed-level confidence bounds follow immediately from the probability inequalities in Appendix A.
- Proposition 2: For p < n, Proposition 2 gives a bound holding with probability at least 1 − δ.
- Assumptions: The displayed bounds assume n and p are sufficiently large for all denominators to be positive.
C Proof of Proposition 1
The proof analyzes a uniformly sampled subset of squared signal coefficients, using its mean and variance and a complementary-sample argument when the subset exceeds half the population.
- Sampling without replacement: The selected squared coefficients are modeled as a sample drawn without replacement from the finite population (β_1^2, …, β_D^2).This gives ∥βT∥^2 as the sum over the sampled coefficients.
- Moment calculation: The finite-population sample has mean 1/D∥β∥^2 and a variance determined by the population's squared coefficients.
- Concentration: A concentration result and union bound yield a high-probability control for the sampled signal quantity.
- Complementary sampling: When p/D exceeds 1/2, the argument can instead use the complementary sample of cardinality D − p.