PaperlayerView exact revision on arXiv

Source-linked AI summary

High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification

Edgar Dobriban, Stefan Wager

arXiv:1507.03003v2math.STstat.ML

TL;DR

Dense high-dimensional prediction lacks a general account when features are correlated and effects are non-sparse. The paper analyzes ridge regression and regularized discriminant analysis under a dense random-effects model using random matrix theory, deriving explicit limiting-risk expressions and showing that covariance spectra shape performance, especially for RDA.

  • Problem

    The paper addresses when dense ridge-regularized linear prediction can work well with highly correlated features, where standard sparsity, manifold, or independence hypotheses may not apply.

  • Method

    The authors use a dense random-effects model and random matrix theory to derive limiting predictive-risk formulas for ridge regression and RDA under high-dimensional asymptotics with general covariance.

  • Results

    The limiting risks depend on signal strength, aspect ratio, regularization, and covariance-spectrum transforms; for RDA, the full eigenvalue spectrum matters beyond standard condition-number or operator-norm summaries.

  • Takeaways & Limitations

    The results provide explicit tools for studying dense high-dimensional prediction and indicate that mildly regularized discriminant analysis can reproduce empirical successes qualitatively.

  • Takeaways & Limitations

    The analysis relies on a strong random-effects hypothesis and uses an LDA formula valid only for γ < 1, whereas the IR formula applies for any γ.

Abstract

from arXiv · show

We provide a unified analysis of the predictive risk of ridge regression and regularized discriminant analysis in a dense random effects model. We work in a high-dimensional asymptotic regime where $p, n \to \infty$ and $p/n \to γ\in (0, \, \infty)$, and allow for arbitrary covariance among the features. For both methods, we provide an explicit and efficiently computable expression for the limiting predictive risk, which depends only on the spectrum of the feature-covariance matrix, the signal strength, and the aspect ratio $γ$. Especially in the case of regularized discriminant analysis, we find that predictive accuracy has a nuanced dependence on the eigenvalue distribution of the covariance matrix, suggesting that analyses based on the operator norm of the covariance matrix may not be sharp. Our results also uncover several qualitative insights about both methods: for example, with ridge regression, there is an exact inverse relation between the limiting predictive risk and the limiting estimation risk given a fixed signal strength. Our analysis builds on recent advances in random matrix theory.

1 Introduction

The paper studies dense ridge-regularized prediction under a random-effects hypothesis, deriving explicit high-dimensional risk formulas for regression and classification with general feature covariance. Its results show that spectral structure materially affects predictive performance, especially for RDA, while ridge regression exhibits sharp qualitative phenomena.

  • Motivation: Dense ridge methods can predict accurately with highly correlated features even when p ≫ n, despite sparsity, manifold, or independence assumptions not being known to apply.Examples include document classification and bioinformatics, where ridge methods performed reliably or best among compared methods.
  • Random-effects hypothesis: The paper models each feature as having a small, independent random effect, providing an average-case theory for dense parameters.The authors state that this hypothesis is strong but yields a qualitatively different high-dimensional theory.
  • Theory: Random matrix theory yields explicit limiting predictive-risk formulas for ridge regression and discriminant analysis with general covariance Σ.The formulas depend on signal strength, aspect ratio, regularization, and spectral-transform quantities derived from the covariance spectrum.
  • Implications: The theory suggests that mildly regularized discriminant analysis can reproduce empirical successes of dense high-dimensional prediction under the random-effects model.The authors present this as qualitative agreement with several empirical studies and as motivation for further generalizations.
  • Ridge regression: Ridge regression has an almost-sure limiting predictive risk determined by α^2, γ, λ, and the limiting eigenvalue distribution of the sample covariance.For general λ, the limit uses both p^-1 tr((bΣ + λI_p×p)^-1) and p^-1 tr((bΣ + λI_p×p)^-2).
  • Ridge regression: At high signal-to-noise ratio, ridge accuracy undergoes a sharp phase transition at γ = 1 regardless of Σ, alongside an inverse relation between predictive and estimation risk.The inverse relation is stated for fixed signal strength, and the paper describes the simplicity of this relationship as remarkable.
  • Regularized discriminant analysis: For RDA, classification error converges to a limit governed by the limiting angle to the Bayes direction, Bayes error, and the covariance spectrum.The limiting angle remains non-trivial as α^2 →∞, and limiting regularization regimes recover known LDA and naive Bayes asymptotics.
  • Regularized discriminant analysis: RDA performance depends on the full eigenvalue spectrum rather than only the condition number, classification margin, or operator norm of Σ.Two covariance structures with similar condition numbers can produce vastly different RDA difficulty, while the asymptotic formulas remain accurate at moderate sample sizes.

2 Predictive Risk of Ridge Regression

The paper derives high-dimensional limits for ridge-regression predictive risk under random coefficients and general feature covariance. The results characterize weak- and strong-signal regimes, reveal a phase transition at γ = 1, and establish an inverse relationship between prediction and estimation risk.

  • Model and theorem: Ridge regression is analyzed under a random-design linear model with independent unit-variance noise and random coefficients having variance p−1α2Ip×p.The estimator uses regularization λ > 0, while predictive risk averages squared test error over an independent test example.
  • Model and theorem: Under high-dimensional asymptotics, predictive risk converges almost surely to a limit determined by signal strength, aspect ratio, regularization, and the limiting spectral distribution of feature covariance.The theorem assumes bounded covariance eigenvalues and expresses the limit through the Stieltjes transform.
  • Regimes of learning: For small signals, limiting risk approaches 1, with first-order excess risk determined by the average eigenvalue and independent of γ.This corresponds to strong regularization and near-zero predictions when α2 is small.
  • Regimes of learning: With identity covariance and p > n, optimally tuned ridge captures a constant fraction of signal, with explained variance tending to γ−1.For γ < 1, the strong-signal limit agrees with ordinary least squares, so ridge cannot outperform OLS in that regime.
  • Regimes of learning: For strong signals, optimal ridge risk has a phase transition at γ = 1: it scales as Θ(1) for γ < 1, Θ(α) at γ = 1, and Θ(α2) for γ > 1.With identity covariance, the corresponding log-log slopes are 0, 1/2, and 1, respectively.
  • Prediction versus estimation: At optimal tuning, the asymptotic prediction and estimation risks satisfy an exact inverse relation whose product equals the signal strength α2 for every limiting covariance spectrum.More generally, the product for arbitrary λ is bounded below by α2; feature correlation can make prediction easier while making coefficient estimation harder.

3 Regularized Discriminant Analysis

The paper analyzes regularized discriminant analysis under high-dimensional Gaussian classification with random class effects and general feature covariance. It derives limiting classification error and geometric results showing that regularization, signal strength, and the covariance spectrum jointly determine performance.

  • Setup: RDA regularizes the unstable sample-covariance inverse used by LDA through the weight vector (Σ̂c + λI)^−1δ̂.The regularization parameter λ is introduced to address the decline of LDA performance when p and n are of comparable order.
  • Setup: The analysis assumes randomly generated class means with independent coordinate effects and bounded population-covariance eigenvalues.The class means are centered around a common midpoint, with δ controlling the between-class signal.
  • High-dimensional asymptotics: RDA classification error converges almost surely to Φ(−Θ(λ)), with Θ determined by the signal strength, aspect ratio, covariance spectrum, and regularization.The relevant spectral quantities are represented through Stieltjes transforms and related parameters.
  • Geometry of RDA: The cosine between learned and Bayes hyperplanes has a deterministic limit Γ(H, γ, α^2, λ) that quantifies RDA inefficiency relative to the Bayes rule.This angle remains nontrivial in the strong-signal limit, so RDA can remain inconsistent for the Bayes hyperplane.
  • LDA versus independence rules: Worst-case margins differ sharply: LDA is minimized at identity covariance, while independence rules are most affected by highly spread eigenvalue distributions.Independence rules can outperform LDA for strong signals, while LDA may have an edge for weaker signals and poorly conditioned covariance.

4 Supplement

The supplement provides efficient computation procedures for the risk formulas and contains the proofs for ridge regression and regularized discriminant analysis.

  • Section 5 describes efficient computation of the risk formulas.
  • Sections 6 and 7 contain the proofs for ridge regression and regularized discriminant analysis, respectively.

5 Efficient computation of the risk formulas

The risk formulas are computed through the companion Stieltjes transform and its derivative, obtained from the Silverstein equation and the population spectral distribution.

  • The companion Stieltjes transform v(z) is characterized as the unique solution of the Silverstein equation with the appropriate sign condition.
  • On v ≥ 0, the functional inverse of z → v(z) has an explicit form that enables tabulation of v(z) for z < 0.
  • Differentiating the Silverstein equation yields v′ in terms of v and H, allowing convenient computation once v(z) is known.
  • The Stieltjes transform m(z) and derivative m′(z) are then computed from v(z) and v′(z), respectively.

6 Proofs for Ridge Regression

The ridge-regression proof derives finite-sample risk decompositions, establishes almost-sure convergence to explicit spectral formulas, and analyzes optimal regularization and signal-strength limits.

  • The ridge estimator decomposes into regularization bias and noise terms, whose cross-term cancels under conditional independence.
  • For λ* = γpα^-2, the finite-sample risk simplifies to the claimed expression before taking high-dimensional limits.
  • The risk converges almost surely for each fixed λ through convergence of spectral functionals and boundedness assumptions on the covariance spectrum.
  • The limiting optimal regularization parameter minimizes the limiting risk under Gaussian observations.
  • The limiting risk is Rλ = 1 + γmI(−λ; γ) + λ⋯m′I(−λ; γ), with the optimal-risk formula obtained at λ* = γα^-2.
  • Weak signals yield limα2→0 R* = 1 and slope E_H[T], whereas for γ < 1 strong signals yield limα2→∞ R* = (1 − γ)^-1.

7.1 Proof of Theorem 3.1

The proof of Theorem 3.1 reduces RDA classification error to limits of concentrated linear and quadratic forms, then expresses the error rate through the limiting margin parameter Θ.

  • The proof begins with the finite-sample Gaussian test-error formula for a linear classifier and simplifies the offset because b̂ converges almost surely to zero.
  • The remaining numerator and denominator terms converge through random-matrix limits involving the Stieltjes transform v and its derivative.
  • The limiting classification error is Φ(−Θ), where Θ has the theorem’s stated form and the denominator contribution is strictly positive.
  • Concentration of quadratic forms supplies the repeated convergence step for independent vectors and symmetric matrices with bounded eigenvalues.
  • A Gaussian representation writes δ̂ and μ̂ as their population values plus independent covariance-scaled normal perturbations.
  • The proof decomposes the offset and shows its component terms converge to zero using moment bounds, independence, and concentration lemmas.

7.2 Proof of Theorem 3.2: Unequal sampling

The proof extends the classifier analysis to unequal class probabilities and sample sizes, deriving asymptotic limits for the estimated classifier’s coefficients and error rate.

  • Unequal sampling: The Bayes classifier includes a log prior-probability correction when the class probabilities are unequal.Its discriminant function uses the shared covariance inverse and the mean difference, plus log(π+/π−).
  • Unequal sampling: The estimated classifier uses class-specific sample means, a centered sample covariance matrix, ridge regularization, and an intercept adjustment.The class proportions satisfy p/n±1 → γ±1 > 0.
  • Asymptotic expansions: Asymptotic independence causes most cross-terms in the intercept and coefficient expansions to vanish.The proof evaluates the resulting linear and quadratic forms using stochastic representations under the theorem’s regularity conditions.
  • Asymptotic limits: The ridge-estimated discriminant direction has limits involving α^2m(−λ), while the corresponding mean term has the opposite sign.These limits are obtained from quadratic forms involving the regularized covariance matrix.
  • Conclusion: Combining the coefficient, intercept, and error-rate limits yields the claimed limiting error expression in Eq. 11.The proof denotes the assembled limit by Q.

7.3 Proof of Corollary 3.3

The corollary’s error-rate limit is expressed through the Marchenko–Pastur Stieltjes transform and its derivative, with a simplification in the identity-covariance case.

  • Error-rate limit: The limiting error rate is Φ(−Θ), where Θ is determined by the signal strength and the Stieltjes-transform limit α^2m(−λ).This follows from the representation established in Theorem 3.1.
  • Identity covariance: When Σ = I_p×p, the auxiliary quantities r(λ) and q(λ) coincide.Both equal the corresponding limiting quadratic-form expression.
  • Stieltjes-transform calculation: Differentiating the Marchenko–Pastur equation gives the derivative relation used to obtain the claimed formula for Θ.For γ = 1, the required expression follows from Eq. (7) after simplification.

7.4 Note on the Ledoit-Peche result (5)

This note reconciles the paper’s covariance notation and normalization with the Ledoit–Péché result used to establish equation (5).

  • Notation: Ledoit and Péché’s Lemma 2 provides equation (5) after translating the aspect-ratio and covariance-matrix notation.The paper’s γ equals their γ−1, and its bΣ corresponds to their S_N.
  • Applicability: The cited theorem’s finite 12th-moment condition holds here, and centering does not change the limiting eigenvalue distribution.The covariance normalization can also be changed from 1/n to 1/(n−2) for regularized discriminant analysis.

7.5 Proof of Theorem 3.5

The proof of Theorem 3.5 rewrites Stieltjes-transform quantities as expectations over empirical spectral distributions and evaluates their low-regularization limits.

  • Spectral representation: Stieltjes transforms and derivatives are represented as expectations over the empirical spectral distribution and its companion distribution.The random variables Y and Ȳ are distributed according to the respective spectral distributions.
  • Low-regularization limit: For γ < 1, the relevant spectral variable is bounded away from zero, permitting dominated-convergence arguments as λ ↓ 0.This yields limits for m(−λ) and λv(−λ), including lim λv(−λ) = 1 − γ.
  • Derivative calculation: Differentiating the companion-transform relation determines the derivative ratio needed for the theorem’s limiting expression.The proof obtains v′(−λ)/v^2(−λ) − 1 → γ/(1 − γ).
  • Final expression: The resulting expression contains the inverse-spectrum moment E[Y−1] together with the aspect-ratio term γ/(1 − γ).Intermediate calculations also identify a limit involving λ^4(v′(−λ) − v^2(−λ)).
  • Large-regularization limit: At large regularization, both λm(−λ) and λv(−λ) converge to 1.These asymptotic identities provide the corresponding boundary behavior of the transforms.
  • Distribution identities: The relationship between the spectral distribution and companion distribution converts expectations under one distribution into scaled expectations under the other.The proof uses F = γF̄ + (1 − γ)δ0 and related identities.

7.6 Proof of Corollary 3.6

The proof reduces minimizing ΘLDA to minimizing EH[T −1], while minimizing ΘIR becomes maximizing EH[T 2]. Jensen’s inequality resolves the first optimization, and the second is attained by a unique unit-mean two-point distribution on {k1, k2}.

  • Minimizing ΘLDA over H ∈ H(k1, k2) is equivalent to minimizing EH[T −1].
  • EH[T −1] ≥ 1, with equality when H = δ1.The bound follows from Jensen’s inequality and the unit-mean condition.
  • Minimizing ΘIR over H ∈ H(k1, k2) amounts to maximizing EH[T 2].The proof uses k1 ≤ T ≤ k2 to derive an upper bound on EH[T 2].
  • The upper bound is achieved by distributions of the form H = w1δk1 + w2δk2.
  • A unique set of weights gives this two-point distribution unit mean, placing it in H(k1, k2).These are the weights specified in the corollary.
Loading 1507.03003v2…