Source-linked AI summary

Benign overfitting in ridge regression

A. Tsigler, P. L. Bartlett

arXiv:2009.14286v2math.STstat.ML

TL;DR

Overparameterized ridge regression can interpolate noisy observations while still controlling excess risk, but prior theory relied on independent components and sharply analyzed variance alone. This paper replaces that assumption with broader tail-spectrum control, derives sharp bias bounds, and extends the analysis to ridge regression, including sufficient conditions for negative optimal regularization.

  • Problem

    Overparameterized ridge regression remains incompletely understood because classical theory expects substantial regularization when n < p, despite interpolation sometimes generalizing with little, zero, or negative regularization.

  • Method

    The paper separates leading covariance eigendirections from the tail and analyzes excess-risk bias and variance using tail Gram-matrix condition-number control instead of component independence.

  • Results

    The analysis characterizes which signal components are learned and how noise is damped, and gives sufficient conditions for negative regularization to be optimal.

  • Takeaways & Limitations

    Learning can decompose into classical ridge regression on a low-dimensional component and zero-estimator behavior on an essentially high-dimensional component.

  • Takeaways & Limitations

    The lower and upper bounds use different assumptions, so a gap can remain when condition-number control holds without independent components.

Abstract

from arXiv · show

In many modern applications of deep learning the neural network has many more parameters than the data points used for its training. Motivated by those practices, a large body of recent theoretical research has been devoted to studying overparameterized models. One of the central phenomena in this regime is the ability of the model to interpolate noisy data, but still have test error lower than the amount of noise in that data. arXiv:1906.11300 characterized for which covariance structure of the data such a phenomenon can happen in linear regression if one considers the interpolating solution with minimum $\ell_2$-norm and the data has independent components: they gave a sharp bound on the variance term and showed that it can be small if and only if the data covariance has high effective rank in a subspace of small co-dimension. We strengthen and complete their results by eliminating the independence assumption and providing sharp bounds for the bias term. Thus, our results apply in a much more general setting than those of arXiv:1906.11300, e.g., kernel regression, and not only characterize how the noise is damped but also which part of the true signal is learned. Moreover, we extend the result to the setting of ridge regression, which allows us to explain another interesting phenomenon: we give general sufficient conditions under which the optimal regularization is negative.

1. Introduction

The paper studies why overparameterized ridge regression can interpolate noisy data while generalizing, focusing on excess-risk bounds in the n < p regime. It builds on prior variance-only results by broadening the assumptions, analyzing bias, and extending the theory to ridge regression.

  • Motivation: Overparameterized models can interpolate training data yet generalize with little, zero, or even negative regularization.This motivates a theoretical analysis of ridge regression when p > n.
  • Prior work: Prior work showed that ridgeless variance can be small when the covariance tail has high effective rank after removing few leading eigendirections.That work assumed independent data-vector components and focused on the variance term.
  • Contributions: The paper replaces component independence with a weaker condition on the tail Gram matrix's condition number.The resulting framework targets non-asymptotic bounds for covariance structures with arbitrary spectral organization.
  • Contributions: The same eigendirection separation yields tight bounds for the bias term as well as the variance term.This addresses which signal components are learned, not only how noise is damped.
  • Positioning: The paper belongs to the category of non-asymptotic results that depend on arbitrary covariance structure.It contrasts with asymptotic analyses and results relying on specialized data distributions or kernels.

2. Ridge regression setup

The setup analyzes ridge regression on n independent noisy observations in R^p with p > n. Its excess risk decomposes into noiseless bias and noise-induced variance, which the paper aims to bound sharply.

  • Data and model: The learning problem is ridge regression for an unknown linear function in the overparameterized regime p > n.The data consist of n i.i.d. vectors with zero mean and noisy responses.
  • Covariance assumptions: The covariance matrix Σ determines the analysis through its ordered eigenvalues and associated eigenbasis.The data matrix is whitened to form isotropic, centered, i.i.d. sub-Gaussian rows.
  • Estimator: Ridge regression estimates θ∗ from X and y using a regularization parameter λ, with A = λI_n + XX⊤ central to the analysis.In the ridgeless case λ = 0, A is the data Gram matrix and regularization shifts its eigenvalues.
  • Risk decomposition: Excess risk is the population average squared prediction error on an independent data point.Because the estimator is linear in y, the risk can be separated into contributions from noiseless estimation and pure noise.
  • Analysis goal: The paper seeks sharp non-asymptotic bounds for the bias and variance terms, whose noise contribution scales with the noise variance v²_ε.The stated high-probability control uses sub-Gaussian noise when that assumption is imposed.

3. The story of separating the first k eigendirections and our contribution

Separating leading eigendirections from the covariance tail explains how overparameterized interpolation can learn some signal while damping noise in other directions. The paper extends this picture from ridgeless variance to bias and ridge regularization.

  • Essentially low-dimensional: In essentially low-dimensional regression, OLS approximates the population covariance uniformly and yields the classical k/n error rate.The model can fit signal well, while increasing model size increases noise-related error.
  • Essentially high-dimensional: In essentially high-dimensional isotropic regression, the data span preserves only about an n/p fraction of signal energy.The projection X⊤(XX⊤)^−1X is onto a random n-dimensional subspace of p-dimensional space.
  • Essentially high-dimensional: The high-dimensional regime nearly fails to learn the signal but damps the noise by a factor p/n.Geometrically, new data are nearly orthogonal to the old sample span, so interpolation noise has little out-of-sample influence.
  • Geometric intuition: With many cosine features, minimum-norm interpolation predicts nearly zero out of sample; frequency weights can instead assign low-frequency signal to the low-frequency components and noise to high frequencies.This illustrates how feature geometry can separate learned structure from interpolated noise.
  • Prior work and extension: Prior ridgeless theory identifies k∗ as the point after which the covariance tail is effectively high-dimensional, but sharply bounds only variance.The present paper completes that picture by deriving sharp bias bounds and extending the analysis to nonzero λ.
  • Main contribution: The paper controls the tail through the condition number of A_k rather than requiring independent components and high effective rank directly.This broader condition supports the essentially high-dimensional interpretation without the independence assumption.
  • Bias: The bias bound assigns nearly all signal energy in the high-dimensional tail to error, while the low-dimensional part behaves like ridge regression with explicit plus implicit regularization.The implicit regularization equals the energy of the tail.
  • Ridge extension: Negative λ can be optimal when tail noise and signal energy are small but the tail effective rank abruptly becomes much larger than n.In this case, the essentially high-dimensional part supplies too much regularization and negative λ can compensate.

4. Main results

The paper develops sharp excess-risk bounds for ridge regression through spectral quantities A_k and ρ_k, with tightness under condition-number and coordinate-distribution assumptions. Its results cover upper and lower bounds, including a theorem that selects k=min(k̄,k*) and establishes high-probability control.

  • Proof strategy: A_k and ρ_k are the central proof objects, and bounds become tight when A_k has constant condition number and k is chosen appropriately.The relevant choice is either a k with constant ρ_k or the smallest k* for which ρ_k exceeds a constant.
  • Scope: The analysis focuses on models satisfying NoncritReg(γ) for γ<1, while a rare third spectral regime receives only an upper-bound treatment and may lack sharp bounds.In that regime, negative regularization can improve rates over all non-negative choices, but the bounds are not expected to be uniformly sharp.
  • Assumptions: The condition-number assumption requires A_k to be positive-definite with condition number at most L, holding with probability at least 1−δ.The paper uses this explicit assumption because A_k is central to the argument and sub-Gaussianity is not considered essential.
  • Upper bounds: Theorem 1 chooses k=min(k̄,k*) under NoncritReg(k̄,γ) and CondNum(k̄,δ,L), yielding high-probability preservation of these conditions and a constant lower bound on ρ_k.The theorem assumes k̄<n/c and δ<1−ce^(−n/c), with probability at least 1−ce^(−n/c)−δ.
  • Limitations: Because the lower-bound arguments use assumptions different from the upper-bound analysis, they do not establish that the upper bound is always tight.The paper states that sharper bounds require specific knowledge about the data and signal distributions.
  • Lower bounds: Theorem 2 gives lower bounds for variance and bias under different distributional assumptions, including independent coordinates for variance and exchangeability plus random sign priors for bias.These bounds apply for k≤k* when ρ_k>a and hold with probability at least 1−2δ−ce^(−c/n).

5. Effective ranks and control of the spectrum of Ak

The paper characterizes when the spectrum of A_k is controlled through effective-rank and norm-concentration conditions. These conditions extend from sub-Gaussian to heavy-tailed data and explain when negative regularization creates a distinct spectral regime.

  • Spectral control: CondNum(k,δ,L) is controlled by bounding the spectrum of the projected-tail Gram matrix and choosing λ to regularize its singular values.The paper identifies three strategies: positive shifts, shifts near a negative lower spectral bound, and a near-critical negative shift.
  • Negative regularization: When tail singular values are very well concentrated, a near-critical negative regularizer can make the shifted spectrum scale with the smaller gap term ♦.This regime differs from ordinary negative shifting when the gap between upper and lower tail spectra is of smaller order than the lower spectral scale.
  • Effective rank: For λ=0, constant-factor spectral control requires the tail effective-rank condition Σ_i>k λ_i ≥ cλ_{k+1}n, equivalently ρ_k>c.This links the condition number of A_k to high effective rank after removing the first k components.
  • Sub-Gaussian data: Sub-Gaussianity controls the largest eigenvalue but not the smallest, so an additional norm-concentration or small-ball condition is needed to lower-bound μ_n(A_k).A sub-Gaussian distribution can share a covariance with a degenerate sampled Gram matrix, demonstrating why an extra lower-tail assumption is necessary.
  • Sub-Gaussian data: Under sub-Gaussianity, necessary and sufficient conditions for bounded eigenvalue ratios are constant lower-bounded ρ_k and regularized squared-norm concentration, up to a gap in constants.Lemma 3 provides the corresponding high-probability control under NoncritReg(k,γ).
  • Heavy-tailed data: For heavy-tailed data, norm concentration and a large heavy-tailed effective rank r_h,k yield high-probability spectral control.Theorem 4 assumes h>4 and gives probability at least 1−cn^(1−h/4)−nδ.

6. Structure of the proof and role of sub-Gaussianity

The proof separates the first k eigendirections from the tail, decomposes excess risk into bias and variance contributions, and combines algebraic bounds with probabilistic concentration. Sub-Gaussianity supports the concentration steps and tight control at the appropriate k, while several bounds remain valid under broader assumptions.

  • Probabilistic control: Theorem 5 requires sub-Gaussianity and positive semidefiniteness of A_k, with its proof splitting into algebraic and probabilistic parts.For non-negative λ, positive semidefiniteness holds with probability 1.
  • Proof strategy: The proof separates the first k eigendirections from the remaining tail, matching the distinction between essentially low-dimensional and high-dimensional parts.This separation supports separate bounds for spiked-part and tail errors.
  • Proof strategy: The algebraic argument decomposes excess risk into four terms: spiked-part bias and variance, and tail bias and variance.The inequalities are established on the event that A_k is positive definite.
  • Probabilistic control: The probabilistic argument controls the algebraic quantities using concentration of k-dimensional sample covariance and norms or sums involving i.i.d. components.The final theorem follows by plugging these high-probability bounds into the algebraic inequalities.
  • Role of sub-Gaussianity: Sub-Gaussianity is not essential for Corollary 6's bound in principle, because weaker moment assumptions can supply analogous concentration, though tightness may require selecting the appropriate k.The shift to k* additionally uses an upper bound on ||A_k*|| derived from sub-Gaussianity.
  • Scope and tightness: The bounds need not be tight when A_k has an unbounded condition number, and oracle control at the wrong k can miss the transition point.Under suitable condition-number control, Corollary 6 and related results provide high-probability bounds; Theorem 10 identifies the relevant k relative to k*.

7. Alternative forms of the bounds and effect of increasing regularization

The bounds admit an alternative form resembling classical in-sample ridge bias and variance, with an increased effective regularization level. This form clarifies how bounds change with λ and when they match results from prior work.

  • 7.1 Alternative form of the bound and its relation to classical in-sample analysis: When ρ_k is bounded by constants or k=k*, the bias and variance bounds match simplified expressions up to constant factors.The alternative form is introduced through Theorem 10.
  • 7.1 Alternative form of the bound and its relation to classical in-sample analysis: The alternative expressions resemble classical in-sample ridge formulas after replacing empirical eigenvalues with population eigenvalues and increasing λ by the tail energy.The tail energy is represented by the sum of eigenvalues beyond k.
  • 7.1 Alternative form of the bound and its relation to classical in-sample analysis: The alternative bias bound can also be interpreted as the bias of population ridge regression with an effective regularization level.The paper defines a population ridge solution to motivate this interpretation.
  • 7.2 Dependence on λ: For larger λ, any k between k* and n/c yields the same bounds up to a constant factor, so k need not decrease as regularization increases.This removes much of the dependence on the changing definition of k*.
  • 7.2 Dependence on λ: The resulting λ-dependence follows by substituting the definition of ρ_k into the alternative bounds.The proof outline controls eigenvalues, applies the main theorem, converts forms, and replaces k* where needed.
  • 7.2 Dependence on λ: When λ dominates the tail eigenvalue sum and equalizes the eigenvalues of A_k up to constants, Corollary 13 gives a corresponding simplified result.The corollary applies under a stated positive-constant condition on λ.
  • 7.3 Comparison with other results: Compared with Hsu et al., Corollary 13 has the same form with different constants and applies over a wider λ range when n is sufficiently large.The wider range follows because one condition allows d(λ/n)=O(n), whereas the comparison restricts it to O(n/log n).
  • 7.3 Comparison with other results: The bounds coincide up to constants with Hastie et al. when ˜V≤1−1/c and ρ_kλ_{k+1} is comparable to ˜λ.This comparison concerns the interpolating regime λ=0 in the prior work.

8. Negative regularization

The paper identifies sufficient conditions under which negative ridge regularization is optimal. The mechanism depends on the balance among noise, tail signal, and an abrupt effective-rank increase.

  • 8. Negative regularization: The tail acts as additional regularization for the first k components, and a jump in ρ_k(0) can make that regularization too large.This motivates considering negative λ.
  • 8. Negative regularization: Negative regularization cannot damp noise relative to non-negative regularization, so noise must be sufficiently small for it to be beneficial.The variance term decreases as λ increases.
  • 8. Negative regularization: Tail signal contributes both unestimated tail error and additional noise for estimating the first k components, with negative λ potentially amplifying the latter.For non-negative λ, the first error type dominates; negative λ can reverse this balance.
  • 8. Negative regularization: Negative regularization can improve excess risk by more than a constant factor only in the critical regime λ=−sum_{i>k}λ_i.At this value, the tail-induced regularization is compensated by negative λ.
  • 8. Negative regularization: Under independent components and prior-sign assumptions, Lemma 17 lower-bounds expected excess risk uniformly over all λ≥0.The bound holds with high probability when k is selected from the first effective-rank threshold.
  • 8. Negative regularization: Under related assumptions, Lemma 18 supplies an upper bound achieved by some negative λ, allowing comparison with the non-negative lower bound.The required concentration control uses the independent-components assumption.
  • 8. Negative regularization: Theorem 19 makes the optimizer negative with high probability when the stated conditions combine small variance, small tail signal, and an abrupt effective-rank jump.The theorem combines Lemmas 17 and 18.
  • 8. Negative regularization: The conditions are sufficient but not known to be necessary when the critical-regime noncriticality assumption fails.Matching lower bounds are unavailable in that regime.

9. Comparison to other works

The paper belongs to the non-asymptotic covariance-structure category and compares its results with asymptotic, distribution-specific, and other arbitrary-covariance analyses. Its bounds generalize prior results while differing in norms and assumptions.

  • 9. Comparison to other works: Prior work is grouped into asymptotic spectral-limit analyses, distribution-specific bounds, and non-asymptotic bounds for arbitrary covariance structure.This paper belongs to the third category.
  • 9. Comparison to other works: Limiting spectral distributions make many asymptotic regimes effectively isotropic from this paper’s perspective because almost all eigenvalues are within constant factors.Some prior works explicitly assume spectra bounded above and below by constants.
  • 9. Comparison to other works: Unlike feature-generation or kernel-specific analyses, this approach makes assumptions directly on feature vectors and can apply after computing the population covariance spectrum.It does not require a particular data-generation mechanism or feature-construction process.
  • 9. Comparison to other works: The paper generalizes Bartlett et al.’s framework, while its bias bound can remain finite when Chinot and Lerasle’s norm-dependent bound becomes arbitrarily large.The paper’s bound scales with ||θ*||_Σ rather than ||θ*||.
  • 9. Comparison to other works: Kobak et al.’s negative-regularization result is a one-spike special case, whereas this paper gives sufficient conditions for a richer set of covariance structures.The special case corresponds to k=1.
  • 9. Comparison to other works: Dereziński et al.’s projector bounds do not translate directly because their Loewner-order analysis uses a different norm from the paper’s Σ-norm bias.The bias here is a projected signal measured in ||·||_Σ.

10. Conclusions

The paper connects data geometry to both signal learning and noise damping in overparameterized ridge regression. It decomposes learning across low- and high-dimensional eigendirections and gives sufficient conditions for negative regularization.

  • 10. Conclusions: Data geometry determines both which signal components are learned and how noise is damped.This is the paper’s central conclusion about excess risk.
  • 10. Conclusions: Learning decomposes into classical ridge regression on the first k components and zero-estimator behavior on the remaining essentially high-dimensional components.The decomposition explains the distinct treatment of low- and high-dimensional directions.
  • 10. Conclusions: The paper provides a general essential-high-dimensionality assumption and geometric sufficient conditions for satisfying it.These conditions support the paper’s geometric interpretation.
  • 10. Conclusions: Negative regularization is sufficient under small noise, small low-dimensional-part signal energy, and an abrupt effective-rank jump.These conditions concern the regime where the high-dimensional part provides excessive regularization.
  • 10. Conclusions: The proof separates an algebraic component from a probabilistic concentration component, making the contributions of estimator terms easier to trace.The algebraic part holds with probability 1 for non-negative regularization.
  • 10. Conclusions: The paper identifies a unified treatment of different overparameterized linear-regression regimes as a promising direction for future work.This follows from similarities between results that remain theoretically unexplained.

A.3 Data and the learning procedure

The paper studies ridge regression with overparameterized data, decomposing prediction error into bias and variance and analyzing both under covariance eigendirection separation and sub-Gaussian concentration.

  • Data model: The model uses responses y = Xθ* + ε, with an unknown signal θ* and noise ε, and evaluates prediction on an independent draw x.The covariance is diagonal, and the data-related assumptions include isotropic sub-Gaussian coordinates or rows.
  • Eigendirection split: The covariance coordinates are split into the first k components and the remaining components to separate low- and high-dimensional eigendirections.Matrix and vector block notation, including Σ_0:k and Σ_k:∞, formalizes this decomposition.
  • Ridge procedure: The ridge estimator is extended beyond positive regularization through θ^(y) = X^T(λI_n + XX^T)^−1y whenever the matrix remains positive definite.At λ = 0, this expression equals the minimum-norm interpolating solution; λ < 0 is considered by continuity while λI_n + XX^T stays positive definite.
  • Error decomposition: Because the estimator is linear in y, its error separates into a noiseless contribution defining bias and a pure-noise contribution defining variance.The full mean-squared error is organized through these two terms.
  • Concentration tools: The study seeks sharp non-asymptotic bounds for both B and V, using concentration tools for sub-Gaussian quadratic forms, covariance sums, and Gram-matrix norms.Sub-Gaussian noise makes the realized variance concentrate around its expectation, whose scale is linear in the noise variance.

D. Controlling the singular values

The singular-value analysis controls the condition number of the high-dimensional Gram matrix A_k through concentration and an explicit effective-rank-type ratio. It establishes sufficient and necessary conditions for this control and shows that k can be reduced to k* up to adjusted constants and failure probabilities.

  • Gram-matrix concentration: Lemma 23 bounds the non-diagonal part of the Gram matrix, while norm concentration controls its diagonal and total operator norm.These ingredients combine through ∥A∥ ≤ max_i ∥X_i,*∥ + ∥˚A∥.
  • Sufficient control: A sufficient condition for condition number at most L is obtained by comparing the tail covariance mass with λ, nλ_{k+1}, and concentration terms.The argument derives explicit inequalities involving the separated tail coordinates and the ratio ρ_k.
  • Effective-rank criterion: The ratio ρ_k summarizes the tail covariance relative to λ and nλ_{k+1}, and its size governs whether the singular values can be controlled.The analysis also gives a converse under a high-probability condition-number assumption.
  • High-probability bounds: Under NoncritReg(k, γ) and CondNum(k, δ, L), Lemma 25 provides high-probability bounds for the spectrum of A_k.The probability includes the condition-number failure probability δ and an exponential concentration term.
  • Reduction to k*: If the assumptions hold for some k ≥ k*, Lemma 11 transfers them to k* with adjusted constants and failure probability δ + ce^−n/c.Thus, the distinguished index k* is sufficient for the subsequent analysis.

E.1 Variance term

The variance analysis expresses the noise contribution as a sum of nonnegative terms and lower-bounds it by separating the leading k directions from the remaining spectrum. Concentration and eigenvalue control yield high-probability lower bounds under the stated structural assumptions.

  • Variance lower bound: Lemma 7 gives a high-probability lower bound for the variance term when k < n/c under NoncritReg(k, γ) and independent coordinates.The proof combines projection arguments, Hanson–Wright concentration, and lower bounds for the separate nonnegative summands.
  • Variance representation: The variance term is written as a sum of nonnegative contributions involving the columns of Z and matrices A_{−i}.Replacing A_{−i} by its positive-semidefinite magnitude preserves a form suitable for lower bounds.
  • Proof strategy: The lower-bound argument separates the first k coordinates, then controls the associated projectors and eigenvalues using sub-Gaussian concentration.This mirrors the eigendirection split used to analyze the singular values of A_k.
  • Spectral structure: With high probability, A_{−i} has at least n − k eigenvalues whose magnitudes are bounded by a constant.This spectral structure supports lower bounds for the noise contribution in the remaining directions.
  • Connection to MSE: The paper’s bias and variance bounds are organized through the same spectral decomposition, with Lemmas 27 and 28 providing corresponding termwise controls when A_k is positive definite.The variance analysis therefore forms one component of a joint MSE treatment.

I. Main results

The main results give sharp high-probability bounds for ridge-regression bias and variance, characterize when upper and lower bounds match, and recover the effective-rank criterion governing noise damping.

  • Upper bound: Theorem 5 gives a high-probability upper bound for the combined bias and variance terms when k < n/c and A_k is positive definite.Its bound is evaluated using concentration of the separated low-dimensional sample covariance and high-dimensional tail quantities.
  • Effective-rank implication: Corollary 6 shows that under NoncritReg(k, γ) and CondNum(k, δ, L), ρ_k is bounded below by a constant and the resulting bound holds with probability at least 1 − δ − ce^−n/c.This connects spectral conditioning to the effective-rank-type criterion.
  • Sharpness: Theorem 10 states that the lower bound matches the upper bound when ρ_k lies in a specified interval or k is the first index where ρ_k exceeds a threshold.The result is formulated for constants a > 0 and b > 1/n.
  • Role of k*: Lemma 12 transfers the bounds between k* and another admissible index, enabling the theorem to use the distinguished split point k*.The transfer relies on k − k* < n/c and the condition ρ_{k*} > b.

J. Negative regularization

The section establishes a lower bound on bias for all non-negative regularization and proves that sufficiently large effective rank can make some negative regularization achieve a controlled excess-risk bound.

  • Non-negative regularization: Lemma 17 lower-bounds the bias for every λ ≥ 0 under IndepCoord and PriorSigns(θ̄), when k is defined by ρ_k(0) > b and k > 0.The bound holds with probability at least 1 − c e^(-n/c).
  • Proof strategy: The proof reduces the non-negative case to λ = 0 because the relevant lower bound is non-decreasing in λ ≥ 0.This monotonicity follows from the stated behavior of the right-hand side of (27).
  • Proof strategy: For the matrix lower bound, the proof rescales and swaps columns, drops the first k columns, and applies Lemma 16 to the resulting matrix.The transformed matrix preserves the assumptions needed for the Lemma 16 application.
  • Negative regularization: Lemma 18 assumes ρ_k(0) > c for some k < n/c and guarantees a λ < 0 with a high-probability excess-risk bound.The assumptions include PriorSigns(θ̄) and IndepCoord.
  • Proof strategy: Combining eigenvalue bounds with Theorem 5 yields the claimed result with explicit high-probability bounds in both noise regimes.The argument invokes concentration and combines the resulting constants to obtain the final bound.
  • Proof strategy: The tuning quantity ♦ balances bias in the first k components against tail bias and variance, with separate small-noise and large-noise cases.In the large-noise case, the proof lower-bounds μ_n(A_−i) separately for each index i.
Loading 2009.14286v2…