Source-linked AI summary
Surprises in High-Dimensional Ridgeless Least Squares Interpolation
Trevor Hastie, Andrea Montanari, Saharon Rosset, Ryan J. Tibshirani
TL;DR
The paper asks how zero-training-error interpolation behaves in high-dimensional regression, motivated by interpolation in modern neural networks. It analyzes minimum-ℓ2-norm regression under linear and random-neural-network feature models, finding double descent and settings where overparameterization helps. These findings are robust across feature-distribution details, but their neural-network correspondence is limited to lazy training and does not address fully nonlinear training bias.
Problem
The paper studies how ridgeless interpolation behaves in high-dimensional regression, where interpolation is relevant to modern neural networks but its statistical consequences remain challenging to understand.
Method
The paper analyzes minimum-ℓ2-norm and ridge regression under linear features and under features generated by a random one-layer neural network, using linearization and universality arguments for the neural-network connection.
Results
The analysis formally verifies double descent in least squares, constructs cases where risk is minimized at p > n, and shows robustness to the distributional details of (y_i, x_i).
Takeaways & Limitations
Overparameterization can be beneficial, while optimally tuned ridge regression uses non-vanishing regularization and dominates min-norm regression in risk across the studied settings.
Takeaways & Limitations
The correspondence to overparameterized neural networks holds only in a lazy-training regime, while fully nonlinear models learn features and remain an open problem for gradient-induced bias.
Abstract
from arXiv · showhide
Interpolators -- estimators that achieve zero training error -- have attracted growing attention in machine learning, mainly because state-of-the art neural networks appear to be models of this type. In this paper, we study minimum $\ell_2$ norm ("ridgeless") interpolation in high-dimensional least squares regression. We consider two different models for the feature distribution: a linear model, where the feature vectors $x_i \in {\mathbb R}^p$ are obtained by applying a linear transform to a vector of i.i.d. entries, $x_i = Σ^{1/2} z_i$ (with $z_i \in {\mathbb R}^p$); and a nonlinear model, where the feature vectors are obtained by passing the input through a random one-layer neural network, $x_i = \varphi(W z_i)$ (with $z_i \in {\mathbb R}^d$, $W \in {\mathbb R}^{p \times d}$ a matrix of i.i.d. entries, and $\varphi$ an activation function acting componentwise on $W z_i$). We recover -- in a precise quantitative way -- several phenomena that have been observed in large-scale neural networks and kernel machines, including the "double descent" behavior of the prediction risk, and the potential benefits of overparametrization.
1 Introduction
The paper examines why interpolation can generalize well in high dimensions, despite its conventional association with overfitting, and studies this using overparametrized linear regression models.
- Modern deep networks often have enough parameters to interpolate training data, even when labels are replaced by random ones.
- Interpolation is traditionally associated with overfitting and poor generalization, yet high-dimensional settings can make interpolation nearly optimal.
- The paper studies i.i.d. feature-response data in a linear regression model with centered features, covariance Σ, and centered noise of variance σ2.
- Because p > n makes the least-squares minimizer nonunique, the paper compares minimum-ℓ2-norm interpolation with ridge regression.
2. We denote these
The paper studies high-dimensional min-norm interpolation across linear and nonlinear feature distributions, showing that feature geometry reproduces double descent, overparameterization benefits, and contrasting regularization behavior. Its results identify when risk is minimized beyond interpolation and show robustness of these phenomena across models.
- Scope and approach: The study analyzes proportional high-dimensional regression, emphasizing overparameterized settings and varying feature distributions to reproduce phenomena observed in deep learning.The analysis covers linear and nonlinear feature models, with prediction risk evaluated through asymptotic and non-asymptotic results.
- Contributions: The paper contributes more accurate non-asymptotic risk approximations for linear models, novel results for general covariance-coefficient geometry and nonlinear features, and a new block-matrix resolvent result.These results extend the analysis beyond isotropic settings and provide explicit, nearly optimal error bounds under weaker geometric assumptions than cited prior work.
- Risk around interpolation: The asymptotic risk diverges as the aspect ratio γ approaches the interpolation boundary from below, while overparameterized risk contains both bias and variance.Below the boundary, min-norm regression coincides with ordinary least squares and has purely variance risk; above it, dependence on β and Σ enters through bias and variance.
- Double descent and overparameterization: For well-specified models, risk can decrease after interpolation or exhibit a local minimum, whereas misspecification can place the global minimum in the overparameterized regime.With sufficient approximation bias and SNR > 1, the misspecified risk may attain its global minimum for γ > 1, although it eventually increases for large γ.
- Interpolation versus regularization: Optimally tuned ridge regression uses non-vanishing regularization and dominates min-norm least squares across γ and SNR in both well-specified and misspecified settings.For misspecified models, optimally tuned ridge reaches its global minimum around γ = 1, and leave-one-out cross-validation is asymptotically equivalent to optimal tuning.
- Feature geometry: Coefficient alignment with covariance eigenvectors changes the overparameterization picture: latent-space models can have risk decreasing toward its minimum as γ →∞, where min-norm interpolation is optimal.Equidistributed coefficients behave qualitatively like isotropic features, while alignment with top eigenvectors yields the contrasting latent-space behavior.
- Nonlinear features: The nonlinear random-feature model with a purely nonlinear activation has the same limiting min-norm risk as a Gaussian linear feature model, supporting broader robustness of the linear-model results.Theorem 8 predicts convergence to the linear risk with p features regardless of the input dimension d.
- Double descent and overparameterization: The double-descent shape reflects decreasing overparameterized variance, while misspecification can also make bias decrease as γ grows moderately beyond the interpolation boundary.Increasing the number of features can distribute the minimum-norm solution across more columns, lowering its norm and variance; additional features can also improve approximation capacity under misspecification.
2 Preliminaries
The section defines out-of-sample risk and the minimum-ℓ2-norm least-squares estimator, including its pseudoinverse and ridge-limit forms. It then states the proportional asymptotic setting and shows that overparametrization introduces bias, while underparametrized risk is variance alone.
- The out-of-sample prediction risk evaluates an estimator on an independent test point and admits a bias-variance decomposition.
- The min-norm estimator is the least-squares solution with minimum ℓ2 norm and can be written using the pseudoinverse.
- Ridgeless least squares is the zero-regularization limit of ridge regression, with ˆβ = limλ→0+ ˆβλ and ˆβλ = (XT X + nλI)−1XT y.
- When X has rank n, the min-norm estimator interpolates the training data; gradient descent initialized at zero converges to this same solution.
- As n,p→∞ with p/n→γ, γ<1 is underparametrized and γ>1 overparametrized; underparametrized risk is σ2γ/(1−γ), while overparametrization creates nonzero bias.
3 Isotropic features
For isotropic features, asymptotic risk depends on β only through its squared norm, and the overparametrized bias increases with γ while variance decreases. Depending on SNR, risk may improve over the null estimator after interpolation, producing a second descent.
- Isotropic features: For isotropic features, the asymptotic risk depends on β only through its squared norm, a consequence of rotational invariance.
- Limiting risk: The overparametrized bias concentrates at r2(1−1/γ), so it increases with γ, while variance decreases with γ.
- Limiting risk: On (0,1), risk has no bias and increases with γ; on (1,∞), bias increases and variance decreases.
- Limiting risk: For SNR≤1, overparametrized risk remains above the null risk, decreases monotonically, and approaches it from above as γ→∞.
- Limiting risk: For SNR>1, overparametrized risk beats the null risk if and only if γ>SNR/(SNR−1), with a local minimum beyond interpolation.
- Estimator norm: The limiting estimator norm increases below γ=1, diverges at the interpolation boundary, and decreases above γ=1.
4 Correlated features
The correlated-feature analysis characterizes min-norm regression through the joint geometry of Σ and β, with finite-sample deterministic approximations and asymptotic limits under weak convergence assumptions.
- Model and assumptions: The feature model is x = Σ^1/2z, with independent standardized entries in z and deterministic positive-definite covariance Σ.The analysis imposes tail, eigenvalue, and interpolation-ratio conditions; min-norm interpolation additionally requires the smallest eigenvalue of Σ to be bounded away from zero.
- Geometry of Σ and β: Prediction risk depends on the eigenvalues of Σ and the coefficients of β in its eigenvector basis, encoded by distributions bHn and bGn.These distributions capture covariance geometry and signal alignment.
- Finite-sample characterization: Theorem 2 gives deterministic finite-n, p approximations for min-norm bias and variance, uniformly over the overparametrization ratio γ = p/n.The theorem applies under the stated covariance and moment assumptions and provides high-probability risk control.
- Asymptotic characterization: If bHn and bGn converge weakly, normalized bias and variance converge almost surely to functions B(H, G, γ) and V(H, γ).The same asymptotic predictions hold under weaker finite-moment conditions in Theorem 3.
- Special geometries: When β is equidistributed across Σ’s eigenvectors, G = H; in the isotropic case, Bequi(H, γ) = 1 − γ^-1 and Vequi(H, γ) = 1/(γ − 1).The equidistributed setting has no special relation between β and Σ and is qualitatively similar to isotropic features.
- Special geometries: A latent-space model aligns β with the top eigenspace of Σ, providing a distinct geometry from the equidistributed case.The paper treats this as a misspecified model and analyzes it separately.
5 Misspecified model
The misspecified model studies interpolation when observed features omit signal-bearing variables, decomposing risk into irreducible bias, approximation bias, misspecification variance, and noise variance. Increasing overparametrization can reduce both bias and variance, and in some settings the best risk occurs beyond interpolation.
- Polynomial approximation bias: Because adding features can improve approximation, increasing γ beyond 1 can decrease both bias and variance in the misspecified model.The paper models the approximation bias as decreasing polynomially with γ and studies the resulting risk curves.
- Model setup: The model observes X but omits W, while responses depend on both feature blocks; min-norm regression fits y using X alone.Prediction risk integrates over training noise and the unobserved test features.
- Risk decomposition: The risk decomposition separates the well-specified prediction risk from an additional misspecification bias caused by unobserved features.For jointly Gaussian features, the misspecification bias is M(β, θ) = θ^TΣw|xθ.
- Isotropic misspecification: Theorem 4 assumes independent standardized observed and unobserved features, finite moments of order 8 + η, and a fixed captured-signal fraction κ.The resulting limiting risk is derived as p/n → γ.
- Risk components: The limiting risk comprises irreducible misspecification bias, approximation bias, misspecification variance, and ordinary variance, with separate formulas for γ < 1 and γ > 1.The misspecification variance reflects inflation from unobserved features, while ordinary variance reflects noise.
- Polynomial approximation bias: For SNR > 1, the min-norm risk can outperform the null risk after a threshold, and sufficiently small approximation-bias exponents place the global minimum at γ > 1.For SNR ≤ 1, the overparametrized risk remains above the null risk and decreases toward it as γ grows.
- Latent-space model: In the latent-space model, β aligns with the top eigenspace, and the risk can decrease throughout the overparametrized regime, reaching its global minimum as γ → ∞.Increasing p averages out feature noise, making observed features approach ideal latent covariates.
6 Ridge regularization
The section develops deterministic and asymptotic risk formulas for ridge regression, compares optimally tuned ridge with min-norm interpolation, and studies how regularization interacts with overparametrization in latent-space models.
- Risk approximation: Theorem 5 gives non-asymptotic deterministic approximations for ridge bias and variance, uniformly over covariance matrices with nearly optimal dependence on n.The risk decomposes as prediction bias plus variance.
- Isotropic features: In isotropic features, the limiting ridge risk has an explicit formula and is minimized at λ*=σ2γ/r2.The corresponding minimum risk is σ2γm(−λ*).
- Ridge versus interpolation: Optimally tuned ridge has strictly lower asymptotic risk than min-norm least squares across r2, γ, and κ in both well-specified and misspecified settings.Figures 7 and 8 compare the two estimators in these settings.
- Latent-space model: In the latent-space model, risk is minimized at large overparametrization γ≫1 largely independently of λ in the probed range.The curves use δ=n/d=20 and compare several regularization values, including the ridgeless limit.
- Latent-space model: Regularization smooths the risk divergence at γ=1, while the optimally regularized risk decreases monotonically with γ and λ→0 is optimal at large overparametrization.The λ→0 optimum persists even when observation noise is strictly positive.
7 Cross-validation
The section shows that leave-one-out cross-validation consistently estimates ridge prediction risk and that CV- or GCV-tuned ridge achieves the asymptotic performance of optimally tuned ridge.
- Cross-validation formulas: The leave-one-out shortcut formula expresses CV error through training errors and the ridge smoother matrix, avoiding separate refits for each observation.The identity follows from the Sherman–Morrison–Woodbury formula.
- Limiting behavior: For isotropic features, CV error converges almost surely to ridge prediction error under proportional asymptotics.The result assumes an isotropic prior and finite moments of order 4+η.
- Limiting behavior: CV tuning achieves the same asymptotic risk as optimally tuned ridge, and the same conclusion holds for generalized cross-validation.The tuning result is stated for parameter intervals containing the asymptotically optimal value.
- Implication: Thus the optimally tuned ridge curves can also be interpreted as the asymptotic risk under CV or GCV tuning.This connects the theoretical optimum to a data-driven tuning procedure.
- Extensions: The leave-one-out shortcut extends to min-norm least squares at λ=0+ and to kernel ridgeless regression with a positive definite kernel matrix.The extension assumes rank(X)=n in the min-norm case.
8 Nonlinear model
The nonlinear feature model uses random neural features whose asymptotic min-norm risk matches the linear isotropic model despite dependent coordinates, supporting a universality result.
- Model: The nonlinear model sets xi=ϕ(Wzi), with Gaussian inputs, random W, and componentwise activation ϕ.The analysis focuses on purely nonlinear activations satisfying the stated standardization conditions.
- Second-order statistics: The nonlinear model’s population covariance is asymptotically close to the identity, with off-diagonal entries of order O(1/d).This approximate second-order matching helps explain comparison with the isotropic model but does not remove coordinate dependence.
- Universality: Although nonlinear feature coordinates are highly dependent when d≪p, Theorem 8 shows their asymptotic bias and variance equal those of linear isotropic features.The dependence arises because features are functions of only d latent variables.
- Empirical comparison: For the purely nonlinear activation ϕabs, finite-sample risks agree closely with the asymptotic curve.The plotted asymptotic risk depends on p/n rather than d/n.
- Proof outline: The empirical covariance spectrum converges to the Marchenko–Pastur law, and the ridgeless variance limit is represented by D0.The limiting statements hold as n, p, d diverge with p/n→γ and d/p→ψ.
A.2 Proof of Theorem 5, bias term
The proof of Theorem 5 controls ridge bias through resolvent-based deterministic approximations, truncation, analytic continuation, and uniform high-probability bounds.
- Resolvent representation: The proof represents the bias through resolvent quantities and studies analytic functions over a domain where the covariance spectrum remains controlled.The argument uses bounds on the covariance operator and resolvent norm.
- Local-law control: An anisotropic local law supplies uniform high-probability control of resolvent entries for regularization parameters above the stated n-dependent threshold.The bound is established over a complex domain and then extended to the relevant real parameters.
- Bias approximation: Differentiating the analytic resolvent representation yields the deterministic approximation for the bias term.The proof uses differentiability of rn and Fn with respect to the auxiliary parameter η.
- Conclusion: Combining the approximation bounds and taking the truncation limit establishes convergence to the deterministic bias formula.The final step uses Borel–Cantelli and convergence of the empirical spectral measures.
- Truncation: Truncation replaces heavy-tailed coordinates by bounded variables, applies Theorem 5 to the truncated model, and controls the approximation error as the truncation level grows.The bounded model has moments of all orders, enabling direct use of the theorem.
B.1 Proof of Theorem 2
The proof approximates min-norm regression by ridge regression with a small penalty, then separately controls bias and variance to establish the claimed bounds.
- Proof strategy: The proof approximates min-norm regression with ridge regression using a small regularization parameter λ.The argument assumes λ ≤ 1 and transfers bounds from ridge regression to the min-norm estimator.
- Bias and variance: The bias is analyzed through the eigendecomposition of the sample covariance matrix, while the variance is treated separately.The bias expression uses the eigenvalues and eigenvectors of S_X = X^T X/n.
- Error control: The resulting bias and variance differences between ridge and min-norm regression are bounded by quantities proportional to λ.The bias bound is stated as B_X(β̂_λ; β)^{1/2} − B_X(β̂; β)^{1/2} ≤ C(M)λ, with analogous variance control.
- Overparametrized regime: For γ > 1, the proof defines a fixed-point quantity c*(λ) through the companion Stieltjes transform and bounds its dependence on λ.Monotonicity and spectral-support bounds imply |c*(λ) − c0| ≤ C(M)λ on bounded λ intervals.
- Conclusion: Choosing λ = n^-1/7 and ε sufficiently small yields the desired high-probability bound.The preceding approximation bounds are combined with Theorem 5 to complete the argument.
C.1 Proof of Proposition 2
This section derives Proposition 2 using random-matrix limits, including Marchenko–Pastur and Silverstein equations, and specializes the result to isotropic, equicorrelated, and autoregressive features.
- Isotropic features: When γ is separated from one, the sample covariance is almost surely invertible, so the min-norm estimator has zero bias.The argument uses lower bounds on the smallest eigenvalue and the Bai–Yin theorem.
- Isotropic features: Marchenko–Pastur convergence and Stieltjes-transform calculations provide the asymptotic bias and variance formulas for isotropic features.The proof exchanges limits using uniform convergence and evaluates the resulting transform explicitly.
- Equicorrelated features: For equicorrelated covariance, the limiting spectral distribution is a point mass at 1 − ρ, despite one eigenvalue diverging with p.The covariance has one eigenvalue 1 + (p − 1)ρ and p − 1 eigenvalues 1 − ρ.
- Equicorrelated features: Corollary 7 obtains the overparametrized equicorrelation risk by inserting explicit limits of the companion Stieltjes transform and its derivative into Theorem 2.The relevant limits depend on ρ, γ, and 1 − ρ.
- Autoregressive features: For autoregressive covariance, the eigenvalues are known explicitly, but the required transform quantities generally must be computed numerically.Numerical integration and root finding yield v(0), v′(0), and the asymptotic risk.
C.6.1 Analysis of GCV
The GCV analysis shows that its criterion converges almost surely and uniformly to the asymptotic ridge prediction-risk expression, so GCV tuning converges to the corresponding optimal tuning.
- Criterion convergence: The GCV numerator and denominator converge almost surely through Marchenko–Pastur limits and quadratic-form arguments.The numerator uses independent-vector quadratic-form convergence, while the denominator follows directly from spectral convergence.
- Criterion convergence: The limiting GCV expression equals σ2 plus the asymptotic ridge risk at tuning parameter λ.The expression is identified using companion Stieltjes-transform identities.
- Tuning convergence: Uniform convergence on a compact interval follows by bounding the criterion and its derivative, enabling convergence of the minimizing tuning parameter.The proof applies Arzelà–Ascoli to the sequence of GCV criteria.
- Tuning convergence: The GCV-tuned ridge estimator’s risk converges almost surely to the asymptotic risk at the optimal tuning parameter.Uniform convergence of both the criterion and the risk transfers the result to the selected estimator.
C.6.2 Analysis of CV
The CV analysis replaces dependent leave-one-out terms with asymptotic limits, controls the resulting remainders, and shows that CV and GCV share the same asymptotic criterion and risk.
- Dependence control: The CV analysis uses Sherman–Morrison–Woodbury to separate each held-out feature from the remaining design matrix.This restores the independence needed for quadratic-form convergence arguments.
- Asymptotic replacement: The leave-one-out denominators are replaced by their common asymptotic limit, (1 + γm(−λ))^-1.The replacement is organized through the diagonal matrix D̄_λ.
- Remainder control: The denominator-replacement remainders vanish almost surely after spectral bounds, moment estimates, and Borel–Cantelli arguments.The proof establishes that the maximum remainder Δ_i tends to zero.
- CV–GCV equivalence: The CV criterion has the same almost sure limit as GCV, namely the asymptotic ridge-risk expression.The comparison combines the convergent GCV numerator with the matching denominator limit.
- Simulation: Finite-sample simulations report excellent agreement among CV, GCV, and optimal tuning near their common asymptotic risk curves.CV- and GCV-tuned finite-sample risks are estimated by averaging over 20 repetitions.
D.1 A more general theorem
The section develops random-matrix results for nonlinear random-feature models, characterizing resolvents and their limiting behavior under proportional asymptotics. These results yield deterministic asymptotic descriptions relevant to min-norm least-squares variance.
- Resolvent asymptotics: The central random-matrix theorem characterizes the asymptotics of the resolvents m1,n and m2,n through a generalization of an earlier lemma.The theorem provides the limiting equations for the nonlinear model's block-structured random matrix.
- Nonlinear model: Theorem 9 analyzes x_i = ϕ(Wz_i) with Gaussian inputs and random Gaussian weights under growth ratios p/n → γ and d/p → ψ.The activation is componentwise, has polynomial growth, and is standardized under a standard Gaussian input.
- Spectral distribution: The asymptotic Stieltjes transform of the empirical spectrum of ˆΣ is characterized by a nonrandom function solving the stated equations.When c1 = 0, this function reduces to the Stieltjes transform of the Marchenko-Pastur distribution.
- Ridgeless limit: For ridge regression, the proportional high-dimensional limit followed by λ → 0+ gives a ridgeless variance limit D0 almost surely.The coefficient D0 depends on the overparametrization and nonlinear-feature parameters through the asymptotic expansion.
- Resolvent asymptotics: The resolvent limits converge almost surely, and the finite-sample quantities m1,n and m2,n converge to their limiting counterparts throughout the upper half-plane.The convergence is established first for sufficiently large imaginary parts and then extended using analyticity and the stated lemmas.
D.3 Proof of Lemma D.5
The section derives spectral and variance consequences for random-feature models by combining resolvent limits with concentration and spectral-distribution arguments. It concludes that the nonlinear model has the same asymptotic bias as random isotropic linear features.
- Spectral consequences: The empirical spectral distribution converges almost surely to a limiting probability measure obtained from convergence of the associated transform.The argument separates the spectral mass into components above and below a threshold ρ0.
- Isotropic specialization: For c1 = 0, the empirical spectral distribution of ˆΣ converges almost surely to the Marchenko-Pastur law.This isotropic-feature specialization is used to evaluate the asymptotic bias.
- Isotropic specialization: The asymptotic bias in the nonlinear analysis is the same as in the linear model with random isotropic features.The conclusion follows by combining the limiting spectral result with the earlier bias analysis.