PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotics of Ridge (less) Regression under General Source Condition

Dominic Richards, Jaouad Mourtada, Lorenzo Rosasco

arXiv:2006.06386v3math.STstat.MLstat.TH

TL;DR

The paper asks whether the structure of the true parameter and data covariance affects ridge regression’s predictive performance and optimal regularization. It analyzes this structure through source conditions and characterizes asymptotic test error. In a strong- and weak-feature setting, it finds that interpolation can be optimal at finite SNR when signal is sufficiently concentrated on strong features.

  • Problem

    Prior studies of least squares beyond interpolation focused on isotropic true parameters, leaving open whether data-generating structure helps determine when interpolation is optimal.

    Source: §1 · p. 2

  • Method

    The paper uses a source condition to encode parameter alignment with covariance eigenspaces, reduce expected test error for a deterministic parameter to a structured prior, and characterize asymptotic ridge risk.

    Source: §1 · pp. 2–3

  • Results

    Ridgeless regression can be optimal among ridge estimators when strong features carry sufficiently more signal than weak ones and SNR is large; unlike isotropic priors, this can occur at finite SNR [15].

    Source: §1 · p. 3, §4 · p. 13

  • Takeaways & Limitations

    The framework extends isotropic-parameter analyses to study how mismatch between the signal structure and ridge’s implicit assumptions affects ideal regularization.

    Source: §4 · p. 13

    Integrating conditional-risk convergence requires suitable domination assumptions, for instance a positive ridge parameter.

    Source: §2.2 · p. 6

Abstract

from arXiv · show

We analyze the prediction error of ridge regression in an asymptotic regime where the sample size and dimension go to infinity at a proportional rate. In particular, we consider the role played by the structure of the true regression parameter. We observe that the case of a general deterministic parameter can be reduced to the case of a random parameter from a structured prior. The latter assumption is a natural adaptation of classic smoothness assumptions in nonparametric regression, which are known as source conditions in the the context of regularization theory for inverse problems. Roughly speaking, we assume the large coefficients of the parameter are in correspondence to the principal components. In this setting a precise characterisation of the test error is obtained, depending on the inputs covariance and regression parameter structure. We illustrate this characterisation in a simplified setting to investigate the influence of the true parameter on optimal regularisation for overparameterized models. We show that interpolation (no regularisation) can be optimal even with bounded signal-to-noise ratio (SNR), provided that the parameter coefficients are larger on high-variance directions of the data, corresponding to a more regular function than posited by the regularization term. This contrasts with previous work considering ridge regression with isotropic prior, in which case interpolation is only optimal in the limit of infinite SNR.

1 Introduction

This paper studies how covariance structure and the true parameter’s alignment affect ridge regression beyond the interpolation threshold. It develops a source-condition framework and shows that, under favorable alignment and sufficiently large but finite signal-to-noise ratio, interpolation can be optimal.

1 Introduction

  • Prior least-squares studies beyond interpolation largely assumed an isotropic true parameter, leaving open whether data-generating structure determines when interpolation is optimal.The paper situates this question alongside double-descent work on test error past the interpolation threshold.Source: §1 · p. 2
  • The paper characterizes asymptotic test error under a general source condition, reducing a deterministic parameter to a structured prior encoding its alignment with covariance principal components.The analysis takes sample size and dimension to infinity proportionally and uses asymptotic random matrix theory.Source: §1 · pp. 2–3
  • In the overparameterized regime, interpolation can have smaller risk than every positively regularized choice when signal is larger on high-variance directions and SNR is sufficiently large but finite.For isotropic-prior least squares, zero regularization was previously optimal only in the infinite-SNR limit [15].Source: §1 · p. 3
  • The strong- and weak-feature analysis also characterizes noisy-coordinate augmentation as implicit regularization and predicts an additional ridgeless bias-and-variance peak beyond interpolation [45].The paper presents these results in Sections 3.2 and 3.3, respectively.Source: §1 · p. 3

1.1 Related Literature

  • Unlike prior asymptotic work on isotropic or autoregressive features, random features, and sparse recovery, this paper imposes structural assumptions on the ground truth through the population covariance basis.The paper also reports that theory verifies empirical observations of additional test-error peaks beyond interpolation [45].Source: §1.1 · p. 4

2 Dense Regression with General Source Condition

The section defines source conditions to represent how signal aligns with covariance eigenvectors, reduces deterministic-parameter expected risk to a structured-prior analysis, and derives asymptotic ridge risk as sample size and dimension grow proportionally.

2.1 Problem Setting

  • A source function Φ describes how parameter coefficients vary across covariance eigenvectors, and the expected risk of a linear estimator depends only on the prior’s first two moments.Under the stated Gaussian prior, the parameter coordinate along eigenvector v_j has standard deviation proportional to √Φ(τ_j).Source: §2.1 · p. 5

2.2 Reduction to Source Condition

  • For any deterministic parameter, its expected test error equals the average error under a matching source prior, and this equality holds at finite sample size.The asymptotic analysis uses a fixed source function for simplicity rather than tracking dimension-dependent source functions.Source: §2.2 · pp. 6–7

2.3 Random Matrix Theory

  • The analysis takes sample size and dimension to infinity with d/n→γ and uses random-matrix limits for covariance-related quantities.The limiting covariance spectrum is assumed to converge to a distribution supported on a positive bounded interval.Source: §2.3 · p. 7

2.4 Main Theorem: Asymptotic Risk under General Source Condition

  • Theorem 1 characterizes limiting expected ridge excess risk as a function of the sample-size ratio, limiting covariance spectrum, and source function.It assumes a bounded source function with finitely many discontinuities and proportional growth of sample size and dimension.Source: §2.4 · p. 8
  • For Φ=1, Φ=x, and Φ=x^-1, asymptotic bias is expressible using the companion transform and its first derivative; for Φ=1, combining bias and variance yields optimal λ=σ²γ/r².Φ=x^-1 is a “harder” case with no favoured direction; Φ=x is an “easier” case with faster coefficient decay.Source: §2.4 · p. 8

3 Strong and Weak Features Model

The strong-and-weak-features model tracks how signal is distributed across high- and low-variance directions, then uses it to study ridge and ridgeless prediction in overparameterized settings. Its results include conditions for optimal interpolation, implicit regularization from noisy features, and additional peaks in ridgeless bias and variance.

3 Strong and Weak Features Model

  • The model separates strong and weak feature subspaces by their covariance eigenvalues, with source-condition coefficients encoding the ground-truth signal in each group.The strong and weak subspaces correspond to eigenvalues ρ1 and ρ2, respectively; the coefficient ratio describes whether the problem is easy or hard.Source: §3 · p. 9

3.1 Interpolating can be optimal in the presence of noise

  • When signal is sufficiently concentrated on strong features and the signal-to-noise ratio is sufficiently large, zero regularization can minimize asymptotic test error among ridge estimators.As the coefficient ratio φ1/φ2 increases, optimal regularization decreases; interpolation can be optimal because ridge is misspecified for the signal structure.Source: §3.1 · pp. 10–11

3.2 The Special Case of Noisy Weak Features

  • Adding and tuning many pure-noise weak features can make ridgeless performance converge to optimally tuned ridge regression using only the strong features.This noisy-feature regularization is an active approach to implicit regularization.Source: §3.2 · p. 11

3.3 Ridgeless Bias and Variance

  • Ridgeless bias and variance can have an additional peak beyond the interpolation threshold, with peak behavior depending on feature structure and dimension.The reported bias peak occurs in the hard setting when n = d1; a variance peak occurs when n = d1 and ρ1 > ρ2.Source: §3.3 · pp. 11–12

4 Conclusion

The conclusion presents a framework for characterizing high-dimensional ridge risk using covariance structure and the true parameter's coefficients in the covariance basis. In a strong-and-weak-features example, it identifies when ridgeless regression can be optimal and describes noisy-feature regularization and additional ridgeless bias and variance peaks.

4 Conclusion

  • The framework characterizes limiting ridge risk through the dimension-to-sample-size ratio, covariance spectrum, and true-parameter coefficients in the covariance basis.This extends prior work on isotropic ground truth and permits analysis of prior misspecification and its effect on ideal regularization.Source: §4 · pp. 12–13
  • In the strong-and-weak-features model, ridgeless regression can be optimal when signal-to-noise ratio is large and strong features carry sufficiently more signal than weak ones.The conclusion also reports that noisy weak features can act as regularization and that additional peaks can occur in ridgeless bias and variance.Source: §4 · p. 13
  • The authors identify non-Gaussian covariates and other ground-truth and data-generating structures as directions for further investigation.They expect extension to independent-coordinate random vectors and linear transformations based on random matrix theory universality results.Source: §4 · p. 13

A Proofs for Ridge Regression

The appendix collects calculations and proofs supporting the paper's ridge-regression results.

A Proofs for Ridge Regression

A.1 Proof of Proposition 1

The proof randomizes the true parameter by independent rotations within the covariance eigenspaces. Invariance and quadratic risk then reduce its expected risk to that of a zero-mean prior with covariance Φ(Σ)/d.

A.1 Proof of Proposition 1

  • Independent Haar rotations within each covariance eigenspace preserve the covariate distribution and ridge risk while producing a randomized version of the true parameter.The transformed data have the same distribution as the original data, and the corresponding ridge estimator transforms with the parameter.Source: §A.1 · p. 19
  • The randomized parameter has mean zero and covariance Φ(Σ)/d, with each eigenspace block contributing its projected signal energy divided by that block’s dimension.Rotational invariance gives an identity covariance within each eigenspace; independence makes cross-eigenspace covariance terms vanish.Source: §A.1 · p. 19
  • Because ridge risk is quadratic in the parameter, any zero-mean prior with covariance Φ(Σ)/d yields the same expected risk as the fixed true parameter.The proof applies this moment match to replace the deterministic-parameter risk with an average over the constructed prior.Source: §A.1 · p. 19

A.2 Proof of Oracle Estimator (Remark 1)

For the oracle estimator, quadratic risk lets the proof replace the structured prior by a Gaussian with the same covariance and identify the Bayes estimator. The random-matrix preliminaries characterize the companion transform used to simplify limiting functions.

A.2 Proof of Oracle Estimator (Remark 1)

  • For linear-in-Y estimators under quadratic risk, the prior can be replaced without loss by a Gaussian with covariance r^2Φ(Σ)/d.The posterior is Gaussian, and its mean is the estimator defined in equation (4), hence the Bayes-optimal estimator.Source: §A.2 · p. 20

A.3 Random Matrix Theory Preliminaries

  • The companion transform is characterized as the unique solution to the Silverstein equation that preserves the sign of the imaginary part.The proof differentiates this equation to obtain a formula for the transform’s derivative.Source: §A.3 · p. 20
  • The relation between the Stieltjes transform and companion transform supplies identities used to rewrite and simplify limiting functions.The proof notes γ(m(z) + 1/z) = v(z) + 1/z before applying the resulting equalities.Source: §A.3 · p. 20

A.4 Proof of Theorem 1

The proof of Theorem 1 decomposes ridge risk into bias and variance and establishes limits for three functionals. Computing the source-condition-dependent functional is identified as a main technical contribution.

A.4 Proof of Theorem 1

  • The proof decomposes the ridge-parameter difference into bias and variance terms before taking expectation over observation noise.This sets up the quantities whose high-dimensional limits are needed for the theorem.Source: §A.4 · pp. 20–21
  • The asymptotic analysis requires almost-sure convergence of three functionals as n and d grow proportionally.The stated regime is d/n = γ.Source: §A.4 · p. 21
  • Among the three limits, the source-condition-dependent trace is the main technical contribution; the proof derives it in Lemma 2.The other two trace limits follow from prior results, and companion-transform identities are used to plug the limits into the theorem.Source: §A.4 · pp. 21–22

A.5 Proof of Corollary 1

The appendix derives limiting-risk expressions for three source functions and the strong-and-weak-features model. It also treats ridgeless limits separately for underparameterized and overparameterized regimes.

A.5.1 Case: Φ(x) = x

  • The Φ(x) = x case rewrites the functional in terms of the Stieltjes transform and differentiates it to obtain the limiting expression.The calculation is repeated for completeness and is aligned with earlier asymptotics in and.Source: §A.5.1 · p. 22

A.5.2 Case: Φ(x) = 1

  • For Φ(x) = 1, the functional matches the one calculated in, and the proof obtains its limiting risk from Theorem 1.The limit is formed after dividing by v(−λ)^2 and adding asymptotic variance.Source: §A.5.2 · p. 23

A.5.3 Case: Φ(x) = 1/x

  • For Φ(x) = 1/x, the proof expresses the functional using the companion transform and derives the limiting risk from Theorem 1.It divides by v(−λ)^2 and adds the limiting variance.Source: §A.5.3 · pp. 23–24

A.6 Strong and Weak Features Model

  • In the strong-and-weak-features model, the source function takes separate values at the two covariance eigenvalues, yielding an explicit functional and limiting-risk form.The model uses a two-bulk covariance spectrum with masses ψ1 and 1 − ψ1.Source: §A.6 · pp. 24–25
  • For the companion transform, the two-bulk model yields a cubic equation that simplifies to a quadratic in the overparameterized ridgeless limit.The cubic can be solved computationally for t; the ridgeless simplification applies as t approaches zero with γ > 1.Source: §A.6 · p. 24

A.6.1 Ridgeless Limit

  • In the ridgeless limit, the underparameterized case has lim t→0 −t v(t) = 1 − γ, while the overparameterized case obtains v(0) from a quadratic.The overparameterized root is selected with the negative sign so that the quantity is non-negative for γ > 1.Source: §A.6.1 · pp. 25–26

A.6.2 Proof of Corollary 2

The proof evaluates the companion transform and its first two derivatives at zero, then uses them to determine the sign of the asymptotic-risk derivative at zero.

A.6.2 Proof of Corollary 2

  • The proof’s stated strategy is to compute the companion transform for this case and check the sign of the asymptotic-risk derivative at zero.It uses the second derivative v′′(0) in the calculation.Source: §A.6.2 · pp. 26–27
  • At γ = 2 and ψ1 = ψ2 = 1/2, the companion transform at zero is v(0) = 1/√ρ1ρ2.The proof obtains derivative expressions from the Silverstein equations and evaluates them at zero.Source: §A.6.2 · p. 26
  • For the strong and weak features model, the proof differentiates asymptotic risk, combining its bias and variance terms and then taking λ → 0.The calculation divides by σ^2 and substitutes ψ1 = ψ2 = 1/2, ψ1φ1 + ψ2φ2 = 1, φ1 + φ2 = 2, and v(0).Source: §A.6.2 · p. 27
  • The sign of the asymptotic-risk derivative at zero is governed by a quantity in square brackets, yielding Corollary 2.The supplied passage does not specify that quantity's formula.Source: §A.6.2 · p. 27

B Proof of Lemma 2

The proof of Lemma 2 establishes a limiting expression by combining analytic-function convergence with a Gaussian decomposition and bounds on error terms.

B Proof of Lemma 2

  • The proof combines techniques from and to establish limit (15), while using previously computed limits and results from and.It states that the four error terms δ1, δ2, δ3, and δ4 vanish almost surely in section B.1.Source: B Proof of Lemma 2 · pp. 28–29
  • Writing the Gaussian covariates as X = ZΣ^1/2 expresses X⊤X as a sum over independent standard-normal rows.Each row is Xi = ZiΣ^1/2.Source: B Proof of Lemma 2 · p. 28
  • Vitali’s theorem supplies convergence of derivatives when analytic functions converge pointwise and are uniformly bounded on the domain.The proof checks analyticity and boundedness for fd(λ) on S, then invokes Morera’s theorem to establish analyticity of the limit.Source: B Proof of Lemma 2 · pp. 29–30
  • The proof targets limit (15) by taking the limit of (20), using δ → 0 and combining (21), (22), and (13).It also applies (13) to the square of 1 + (1/n)Tr.Source: B Proof of Lemma 2 · p. 30

B.1 Showing δ →0

The section proves that the error terms δ1, δ2, δ3, and δ4 vanish almost surely, using trace bounds and a Gaussian concentration argument.

B.1 Showing δ →0

  • A Gaussian-vector concentration inequality is introduced to bound the quantities used in the error analysis.It applies to y ∼ N(0, I) and a symmetric matrix C with bounded norm.Source: §B.1 · p. 30
  • The proof uses upper bounds on the maximal eigenvalues and traces, including a bound that tends to zero as n → ∞.It also uses |(1 + a)^−2 − (1 + b)^−2| ≤ 2|b − a| for nonnegative a and b.Source: §B.1 · pp. 30–32
  • The section’s goal is to show that each of δ1, δ2, δ3, and δ4 converges to zero almost surely.For δ1, the proof uses a decomposition and trace bounds; δ1 vanishes as n, d → ∞ with d/n → γ.Source: §B.1 · pp. 30–31
  • Vn,d → 0 almost surely, established through a threshold-probability bound and the Borel–Cantelli lemma.For each t > 0, Vn,d ≥ t occurs for only finitely many n almost surely.Source: §B.1 · p. 32

Related papers

Loading 2006.06386v3…