PaperlayerView exact revision on arXiv

Source-linked AI summary

The generalization error of random features regression: Precise asymptotics and double descent curve

Song Mei, Andrea Montanari

arXiv:1908.05355v5math.STstat.ML

TL;DR

The paper asks how double descent and favorable generalization can arise beyond conventional underparameterized models without imposing special misspecification assumptions. It analyzes ridge regression on random features over the sphere and derives precise proportional asymptotics, finding a natural model that captures the full double-descent phenomenology, while noting limits concerning ridgeless and minimum-norm limits.

  • Problem

    Existing random-covariate analyses capture some double-descent behavior but miss phenomena including optimal large overparameterization, while highly overparameterized neural networks remain difficult to analyze directly.

  • Method

    The paper studies ridge regression on random features over the d-dimensional sphere, equivalent to a two-layer network with random first-layer weights, in the limit N,n,d→∞ with N/d and n/d fixed.

  • Results

    The model's precise test-error asymptotics reproduce all qualitative features of double descent, including peaks in both variance and bias at the interpolation threshold.

  • Takeaways & Limitations

    Large overparameterization is necessary for optimal prediction in this natural analytically tractable model, without postulating special misspecification structure.

  • Takeaways & Limitations

    The analysis does not rigorously establish that taking λ→0 after the high-dimensional limit equals the fixed-dimension minimum-norm interpolator limit.

Abstract

from arXiv · show

Deep learning methods operate in regimes that defy the traditional statistical mindset. Neural network architectures often contain more parameters than training samples, and are so rich that they can interpolate the observed labels, even if the latter are replaced by pure noise. Despite their huge complexity, the same architectures achieve small generalization error on real data. This phenomenon has been rationalized in terms of a so-called `double descent' curve. As the model complexity increases, the test error follows the usual U-shaped curve at the beginning, first decreasing and then peaking around the interpolation threshold (when the model achieves vanishing training error). However, it descends again as model complexity exceeds this threshold. The global minimum of the test error is found above the interpolation threshold, often in the extreme overparametrization regime in which the number of parameters is much larger than the number of samples. Far from being a peculiar property of deep neural networks, elements of this behavior have been demonstrated in much simpler settings, including linear regression with random covariates. In this paper we consider the problem of learning an unknown function over the $d$-dimensional sphere $\mathbb S^{d-1}$, from $n$ i.i.d. samples $(\boldsymbol x_i, y_i)\in \mathbb S^{d-1} \times \mathbb R$, $i\le n$. We perform ridge regression on $N$ random features of the form $σ(\boldsymbol w_a^{\mathsf T} \boldsymbol x)$, $a\le N$. This can be equivalently described as a two-layers neural network with random first-layer weights. We compute the precise asymptotics of the test error, in the limit $N,n,d\to \infty$ with $N/d$ and $n/d$ fixed. This provides the first analytically tractable model that captures all the features of the double descent phenomenon without assuming ad hoc misspecification structures.

1 Introduction

The paper studies why test error can decrease again after interpolation and develops a random-features model that analytically reproduces this double-descent behavior. It derives precise prediction-error asymptotics in proportional high-dimensional limits, including effects of regularization, noise, activation, and target-function structure.

  • Traditional statistical guidance expects test error to follow a U-shaped curve and peak at the interpolation threshold because of variance explosion.
  • In contrast, highly overparameterized neural networks can interpolate even noisy labels while retaining small test error, motivating the double-descent framework.
  • The resulting model reproduces the qualitative double-descent curve and provides a complete proportional-asymptotic treatment of the nonparametric setting without ad hoc misspecification.
  • Random features ridge regression is both a finite-rank approximation to kernel ridge regression and a two-layer neural network with a fixed random first layer.
  • The paper computes precise prediction-error asymptotics as N,n,d grow with N/d and n/d fixed, explicitly accounting for dimension ratios, noise, activation, regularization, and target-function components.
  • The analysis also identifies an asymptotically equivalent Gaussian-covariates model, offering additional intuition for random-features behavior.

2 Results and insights: An informal overview

The paper's exact asymptotic formulas show that random-features regression reproduces double descent while revealing how overparameterization and regularization affect prediction error. Highly overparameterized models can be optimal, and the optimal regularization depends on signal-to-noise ratio.

  • The model exhibits a test-error peak at the interpolation threshold because both bias and variance become singular there in the ridgeless limit.Unlike simpler linear models, the double-descent behavior persists even in the noiseless setting, where error is entirely due to bias.
  • For fixed regularization, the minimum test error occurs in the highly overparameterized regime as the feature ratio ψ1 approaches infinity.In the ridgeless limit, the generalization curve decreases monotonically with ψ1 once ψ1 exceeds the sample ratio ψ2.
  • The paper presents a natural analytically tractable model in which large overparameterization is necessary for optimal prediction without imposing special misspecification.Its exact formulas depend on dimension ratios, noise, activation, regularization, and the linear or nonlinear components of the target function.
  • With optimal regularization, test error decreases monotonically as the number of parameters increases, so regularization compensates for overparameterization.The interpolation peak becomes less prominent as regularization increases, and the lower envelope of the curves is monotone decreasing.
  • The optimal regularization depends on signal-to-noise ratio: positive regularization helps at low SNR, whereas vanishing regularization is optimal at high SNR.The two regimes are separated by a critical SNR ρ⋆, and highly overparameterized near-interpolators are statistically optimal above that threshold.
  • The self-induced regularization intuition becomes essentially correct in the wide limit, although random off-diagonal kernel terms remain non-negligible at finite width.The empirical kernel's diagonal concentrates near E{σ(G)^2}, suggesting an effective regularization of order Var(σ(G)).

3 Related literature

Related work develops from empirical studies of interpolation and double descent toward analytical random-feature and kernel-matrix results. The present paper distinguishes its full-test-error analysis from prior variance-only or asymptotic-regime-specific treatments.

  • Prior work showed that deep networks and kernel methods can generalize despite interpolating all training data.
  • Earlier analyses established double descent in linear and related models, including over-specified linear regression and Fourier series models.
  • Random-feature research connects finite random-feature spaces to RKHSs and studies convergence of empirical kernels and kernel matrices.
  • The paper studies the high-dimensional regime N,n = Θ_d(d), unlike work focused on polynomial scalings or population and infinitely wide limits.
  • Its main technical advance is computing full prediction error through derivatives of a block-matrix log-determinant, rather than only the variance term.
  • The analysis models the full nonparametric target and characterizes spectral and eigenvector properties in a regime where the kernel matrix is not near-isometric.

4 Notations

The notation section defines the mathematical spaces, asymptotic conventions, matrix symbols, norms, traces, and distributions used throughout the paper.

  • The paper defines real and complex numbers, natural numbers, real and imaginary parts, the upper half-plane, spheres, and integer index sets.
  • Asymptotic notation includes O_d, o_d, Ω_d, and their in-probability versions O_d,P and o_d,P.
  • Bold lowercase and uppercase symbols denote vectors and matrices, while I, 1, and 0 denote identity, all-ones, and all-zero matrices.
  • Matrix notation covers Frobenius, nuclear, operator, and maximum norms, the Moore–Penrose inverse, entrywise functions, traces, and partial traces.
  • The paper uses ⊙ for element-wise matrix products and defines the standard Gaussian measure and uniform distribution on the sphere.
  • The distributions τ_d and ˜τ_d describe normalized inner products for Gaussian vectors and inner products for uniformly sampled spherical vectors.

5 Main results

The paper derives asymptotic prediction-error formulas for random-features ridge regression on the sphere, including linear and nonlinear regression functions. These formulas explain double descent, highly overparameterized behavior, and the effects of regularization.

  • 5 Main results: The asymptotic risk is expressed through bias and variance terms, with a formula that can be evaluated numerically and simplified in special cases.The functions defining the formula are characterized through analytic equations and a unique bounded solution.
  • 5.1 Statement of main result: Theorem 2 gives the asymptotic prediction error for random-features ridge regression when N/d and n/d converge to fixed positive ratios.The result assumes spherical covariates, admissible activations, proportional asymptotics, and a regression function with deterministic linear and random isotropic nonlinear components.
  • 5.1 Statement of main result: For nonlinear targets, the risk gains an additive F⋆^2 term and replaces τ^2 by τ^2 + F⋆^2, so the nonlinear component behaves like random noise.The result states that random-features regression in the proportional regime estimates only the linear component of the regression function.
  • 5.2 Simplifying the asymptotic risk in special cases: Above the interpolation threshold, both bias and variance decrease monotonically with the rescaled number of neurons ψ1.This differs from simpler random-covariate models, where bias can increase after interpolation; the decreasing bias helps explain why highly overparameterized models can perform best.
  • 5.2.2 Highly overparametrized regime: In the large-width limit, the risk remains bounded below by F⋆^2, even as ψ1 tends to infinity, because random features cannot learn the nonlinear component in the considered scaling.The cited result applies when the number of features is at most O(d^(2−δ)) for any δ > 0.
  • 5.2.2 Highly overparametrized regime: Regularization is not universally beneficial: vanishing regularization is optimal above a critical signal-to-noise ratio, while another positive optimum can occur below it.The large-width risk as a function of regularization is either increasing or first decreasing and then increasing.

6 Asymptotics of the training error

This section characterizes the asymptotic training error and coefficient norm for random-features ridge regression, then uses simulations to examine interpolation and double descent.

  • Asymptotic characterization: Theorem 6 gives asymptotic formulas for the regularized training error and minimizer norm when λ > 0.The formulas are defined through uniquely specified analytic functions and fixed-point conditions.
  • Numerical illustrations: The analysis tracks training error and parameter norm as functions of the overparameterization ratio N/n at fixed sample density ψ2 = n/d.The simulations use a small positive ridge parameter, λ = 10^-3.
  • Numerical illustrations: Training error decreases monotonically with N/n and becomes close to zero for N/n > 1, indicating near interpolation in the overparameterized regime.It remains nonzero because the simulations use λ > 0.
  • Numerical illustrations: The quantity ψ1||â(λ)||2 rises to the interpolation threshold, then falls for N/n > 1 and converges as ψ1 → ∞.The paper uses this quantity as a proxy for model complexity.
  • Optimal regularization: Choosing optimal ridge regularization makes test error strictly decreasing as ψ1 = N/d increases, thereby eliminating or reducing double descent.The authors expect this behavior to hold generically in other models.

7 An equivalent Gaussian covariates model

The paper constructs a Gaussian-covariates proxy for the random-features model and shows that both models have the same asymptotic prediction error under proportional scaling.

  • Model construction: The proxy represents the response as linear in Gaussian covariates with a specially chosen covariance and signal structure.Its covariate covariance is Σ = µ1^2ΘΘT/d + µ⋆^2IN.
  • Model construction: The construction draws Gaussian x, noise ε, and weights w, then defines feature covariates u using the random-feature weights and activation moments.The resulting u is Gaussian and jointly Gaussian with y.
  • Equivalence result: The Gaussian-covariates model has the same asymptotic prediction error as the nonlinear random-features model in proportional asymptotics.The shared limit is given by the same formula R as in Definition 1.
  • Equivalence result: Theorem 7 provides the explicit asymptotic prediction-error expression for the Gaussian-covariates model for any λ > 0.The expression uses R(ρ, ζ, ψ1, ψ2, λ/µ⋆^2), defined in Definition 1.
  • Numerical validation: Simulations show excellent agreement between the Gaussian-covariates predictions and numerical results.The comparison uses test error as a function of ψ1/ψ2 = N/n.

8 Proof of Theorem 2

The proof of Theorem 2 reduces random-features risk to resolvent and trace calculations, derives fixed-point equations for their asymptotic transforms, and extracts explicit bias and variance formulas.

  • Setup: The proof begins with random points on the sphere, random feature weights, fixed assumptions, and fixed positive regularization λ.The proportional parameters are ψ1 = N/d and ψ2 = n/d.
  • Risk decomposition: A decomposition expresses the risk through traces involving a block-structured matrix A and associated random matrices.The matrix has dimension M = N + n and separates feature and sample blocks.
  • Leave-one-out analysis: A leave-one-out argument handles dependence by separating components parallel and orthogonal to a selected feature direction.The parallel component is treated explicitly, while independence is exploited for the orthogonal component.
  • Leave-one-out analysis: The spherical variables are replaced by Gaussian vectors whose Stieltjes-transform asymptotics agree with those of the original model.The Gaussian decomposition isolates independent variables and a low-rank correction.
  • Asymptotic transforms: Two nonlinear fixed-point equations characterize the limiting partial Stieltjes transforms m1 and m2.The solution is selected by analytic continuation and bounds on |m1| and |m2|.
  • Risk extraction: Integrating the limiting transform yields an asymptotic log-determinant, whose derivatives provide explicit asymptotics for bias and variance.The fixed-point solution is stationary for the auxiliary function Ξ, simplifying derivatives with respect to model parameters.

9 Proof of Proposition 8.1

This proof decomposes the random-features risk by spherical-harmonic degree, controls each component with resolvent estimates, and combines the bounds to establish Proposition 8.1.

  • Harmonic decomposition: The nonlinear regression function is represented as a Gaussian process with independent spherical-harmonic coefficients across degrees.The linear component is handled separately through rotational symmetry.
  • Harmonic decomposition: Rotational invariance permits replacing a fixed linear coefficient vector by a uniformly random vector on the sphere without changing the relevant asymptotics.The proof also uses Gaussian coefficient representations for the linear component.
  • Conclusion: Combining the harmonic decomposition, trace estimates, and concentration arguments proves Proposition 8.1.The concentration step controls fluctuations around the expectation over the nonlinear coefficients and noise.
  • Error control: The proof establishes that the decomposed trace terms converge to their target quantities, including uniform control over higher-degree components.These estimates yield the required o_d(1) errors.
  • Matrix approximation: The feature Gram matrix is approximated by a term linear in ΘΘT plus an identity term, using Gegenbauer expansions and operator-norm bounds.The approximation controls the nonlinear harmonic components needed for the risk calculation.

10 Proof of Proposition 8.3

The proof establishes that Gaussian partial Stieltjes transforms approximately solve a fixed-point system, then proves the system has a unique solution and the transforms concentrate around their means.

  • Key fixed-point approximation: The Gaussian partial Stieltjes transforms m1,d and m2,d approximately satisfy fixed-point equations involving F1 and F2.The approximation error is bounded by C · err(d), with err(d) tending to zero as d grows.
  • Gaussian comparison: The analysis constructs Gaussian counterparts using iid Gaussian feature and sample vectors, a polynomial activation, and a block matrix A.The matrix A has dimension M = N + n and is compared with the corresponding spherical matrix.
  • Proof ingredients: The proof uses leave-one-out arguments, resolvent properties, and concentration results for partial Stieltjes transforms.The transforms converge almost surely and in L1 to their expectations when Im(ξ) > 0.
  • Fixed-point uniqueness: For sufficiently large Im(ξ), F maps a specified product of complex disks into itself and is 1/2-Lipschitz, yielding a unique fixed point.Uniqueness follows from the Banach fixed point theorem.
  • Transform properties: The normalized transforms are Stieltjes transforms of probability measures and therefore are analytic on C+ and map C+ into C+.Convergence on a set with an accumulation point extends analytically to C+ with uniform convergence on compact subsets.

11 Proof of Proposition 8.4

This section proves the asymptotic characterization needed for Proposition 8.4 by controlling fixed-point solutions, their large-imaginary-argument behavior, and the convergence of auxiliary functions.

  • Auxiliary-function limits: The auxiliary function Ξ2 evaluated at the fixed-point transforms approaches its value at (iψ1/K, iψ2/K) as K tends to infinity.This comparison supplies the limiting behavior used to identify the asymptotics of g.
  • Large-imaginary-argument asymptotics: As Im(ξ) tends to infinity, the fixed-point transforms satisfy ξm1(ξ; q) + ψ1 → 0 and ξm2(ξ; q) + ψ2 → 0.Equivalently, m1 and m2 have leading behavior −ψ1/ξ and −ψ2/ξ in this regime.
  • Uniform control: Uniform derivative bounds for Gd and g support the passage from pointwise estimates to uniform control over compact parameter regions.The proof combines resolvent bounds, Wishart operator-norm control, and a covering-number argument.
  • Completion of Proposition 8.4: Implicit differentiation and analytic continuation connect the limiting auxiliary function to the propositions’ formulas for arbitrary ξ in C+.The argument integrates derivative identities along compact continuous paths linking ξ and iK.
  • Conclusion: The resulting estimates establish Eqs. (75)–(77) and complete the proof of Proposition 8.4.The final step combines the preceding bounds with the asymptotic lemmas.

12 Proof of Theorem 3, 4, and 5

The proofs analyze the small-regularization behavior of the fixed-point transforms and derive explicit limiting formulas for their product, including the λ-dependent cases used in the theorems.

  • Connection to theorem formulas: These formulas identify the correspondence between the λ → 0 definition of χ and its alternative definition through the fixed-point product.The proof uses the relationship between χ and m1m2.
  • Small-u behavior: When ψ2 > ψ1, m2(iu) is of order 1/u while m1(iu) is of order u as u tends to zero.This follows from the n > N eigenvalue structure of ZZT + u2IN.
  • Limiting product: The product m1(iu)m2(iu) converges to the unique non-positive solution of a quadratic equation as u tends to zero.The limiting expression is given explicitly in terms of ψ and ζ.
  • λ-dependent formula: For λ > 0, the corresponding product has an explicit square-root expression involving ψ2, ζ, and λ.This is the formula established in Lemma 12.2.
  • Symmetric case: A symmetric expression holds for the case involving ψ1 instead of ψ2.The paper states that this result is symmetric to Lemma 12.2.

13 Proof of Proposition 5.1 and 5.2

The section characterizes how Rwide depends on λ and establishes the optimization regimes in Proposition 13.1, while also introducing spherical-harmonic and orthogonal-polynomial tools.

  • 13 Proof of Proposition 5.1 and 5.2: For fixed ζ, ψ2, and ρ, Rwide is either strictly increasing in λ or first strictly decreasing and then strictly increasing.Thus its λ-dependence has at most one interior minimum.
  • 13 Proof of Proposition 5.1 and 5.2: The function ω(λ, ψ2, ζ) is always negative and increasing in λ.The derivative ∂λω is positive in both ψ2 ≥ 1 and ψ2 < 1 cases.
  • 13 Proof of Proposition 5.1 and 5.2: When ρ < ρ⋆(ζ, ψ2), an interior λ⋆ matches the unconstrained minimizer; when ρ > ρ⋆(ζ, ψ2), the optimum is attained at λ = 0.The distinction depends on whether ω1 is above or below ω0.
  • 13 Proof of Proposition 5.1 and 5.2: Joint optimization over ζ and λ retains the λ⋆ construction whenever ζ2 ≥ ζ2⋆.In this regime, the optimized value equals Rwide evaluated at the unconstrained target ω1.
  • Technical background: The technical background decomposes functions on the sphere into spherical harmonics and expands functions on the real line in Hermite polynomials.Gegenbauer polynomials connect the spherical-harmonic and Gaussian polynomial representations.

C.2 Proof of Lemma 9.6 and Lemma 9.7

The proofs reduce the relevant quantities using Sherman–Morrison–Woodbury identities and random-matrix bounds, then combine the resulting terms to establish the lemmas. Lemma 9.6 obtains a nonnegative quantity bounded by one, while Lemma 9.7 uses analogous operator-norm controls under a singleton-set simplification.

  • Sherman–Morrison–Woodbury reformulates A1, A2, and Bα before the proofs of Lemmas 9.6 and 9.7.
  • Proof of Lemma 9.6: A = 1 − 2A1 + A2 = (K12 + 1)^2/(K11(1 − K22) + (K12 + 1)^2)^2 ≥ 0.
  • Proof of Lemma 9.6: 1/(K11(1 − K22) + (K12 + 1)^2)^2 = O_d(d^-2) · (1 + ∥J∥op^8).
  • Proof of Lemma 9.6: 0 ≤ A ≤ 1, so the high-probability bound yields an expectation bound and completes Lemma 9.6.
  • Proof of Lemma 9.7: Lemma 9.7 is proved first for A = {α}, with B = Bα; the argument extends directly to arbitrary sets A.
  • Proof of Lemma 9.7: The operator norm satisfies ∥J∥op = O_d,P(exp{C(log d)^1/2}), and deterministically bounded quantities convert high-probability bounds into expectation bounds.

D Proof of Lemma 8.1

The proof of Lemma 8.1 differentiates the stationary-point equations for m1 and m2 using implicit differentiation. The remaining algebra completes the result.

  • For fixed ξ ∈ C+ and q ∈ R^5, the fixed-point solution (m1(ξ; q), m2(ξ; q)) is a stationary point of Ξ.
  • Implicit differentiation of the stationary-point equations, followed by basic algebra, proves Lemma 8.1.

E Proof sketch for Theorem 6

The proof sketch for Theorem 6 assumes fixed feature and sample aspect ratios and uses resolvent matrices to analyze training error, minimizer norms, and log-determinant derivatives. Random-matrix estimates control the resulting expressions.

  • The proof fixes ψ1,d = N/d and ψ2,d = n/d as constants independent of d and recalls two useful resolvent matrices, Ξ and Π.
  • Theorem 6 is organized around the expectation of regularized training error, the squared norm of minimizers, and derivatives of a log determinant.
  • Step 1. The expectation of regularized training error: Random features regression supplies the regularized training-error expression through Eq. (45), whose expectation is then analyzed.
  • Step 1. The expectation of regularized training error: The coefficients before F2 are asymptotically vanishing, while Lemma C.6 controls supk≥2 ∥Qk(XXT) − In∥2.
  • Step 3. The derivatives of the log determinant: The auxiliary block matrix A is defined with dimension M = N + n for the subsequent calculations.
  • Derivatives of g follow by differentiating its defining equation and applying Daskin’s theorem; simple calculus then yields the theorem.
Loading 1908.05355v5…