PaperlayerView exact revision on arXiv

Source-linked AI summary

Benign Overfitting in Linear Regression

Peter L. Bartlett, Philip M. Long, Gábor Lugosi, Alexander Tsigler

arXiv:1906.11300v3stat.MLcs.LGmath.ST

TL;DR

The paper asks when exact fitting of noisy data can still yield accurate prediction in linear regression. It analyzes the minimum-norm interpolator through covariance effective ranks and shows that benign overfitting requires substantial overparameterization, with broader support in large finite dimensions than in infinite-dimensional spaces.

  • Problem

    The paper addresses when perfect fitting of noisy training data can remain compatible with accurate prediction, a question motivated by successful interpolation in deep learning.

  • Method

    The paper studies the minimum-norm interpolating rule for overparameterized linear regression and characterizes its prediction risk using two effective-rank notions of the covariance.

  • Results

    Benign overfitting requires many low-variance directions relative to sample size and slowly decaying smallest covariance eigenvalues.

  • Takeaways & Limitations

    Large finite-dimensional spaces permit benign overfitting across a wider range of covariance properties than infinite-dimensional spaces.

  • Takeaways & Limitations

    The stated results do not directly apply to a neural-network setting whose random Hilbert-space elements lack the assumed independent-component representation.

Abstract

from arXiv · show

The phenomenon of benign overfitting is one of the key mysteries uncovered by deep learning methodology: deep neural networks seem to predict well, even with a perfect fit to noisy training data. Motivated by this phenomenon, we consider when a perfect fit to training data in linear regression is compatible with accurate prediction. We give a characterization of linear regression problems for which the minimum norm interpolating prediction rule has near-optimal prediction accuracy. The characterization is in terms of two notions of the effective rank of the data covariance. It shows that overparameterization is essential for benign overfitting in this setting: the number of directions in parameter space that are unimportant for prediction must significantly exceed the sample size. By studying examples of data covariance properties that this characterization shows are required for benign overfitting, we find an important role for finite-dimensional data: the accuracy of the minimum norm interpolating prediction rule approaches the best possible accuracy for a much narrower range of properties of the data distribution when the data lies in an infinite dimensional space versus when the data lies in a finite dimensional space whose dimension grows faster than the sample size.

1 Introduction

The paper studies when linear predictors can interpolate noisy training data yet retain near-optimal prediction accuracy. It characterizes this benign overfitting through covariance effective ranks and highlights the role of large finite dimensions.

  • Deep networks can achieve essentially zero training loss while retaining respectable prediction performance despite label noise, challenging classical overfitting intuitions.
  • The paper studies quadratic-loss linear regression in a sufficiently overparameterized setting where perfect fitting is guaranteed.
  • The estimator is the smallest-norm parameter vector among all exact interpolators, embedding label noise into the parameter estimate without necessarily harming prediction accuracy.
  • The main result gives a finite-sample characterization: noise-induced excess error is small if and only if low-variance directions have effective rank large compared with n.
  • Benign overfitting requires slowly decaying smallest covariance eigenvalues, with two effective-rank notions governing the relevant spectral split and low-variance subspace.
  • Infinite-dimensional data permits benign overfitting only for a narrow eigenvalue-decay range, whereas finite dimensions growing faster than sample size allow any suitably slowly decaying sequence.

2 Definitions and Notation

This section defines linear regression in a separable Hilbert space, its excess risk, and the minimum-norm interpolating estimator. It introduces covariance eigenvalues and effective-rank quantities used to bound that estimator’s risk.

  • A linear regression problem uses covariates x in a potentially infinite-dimensional Hilbert space H to predict a real-valued response y.
  • The optimal parameter θ∗ minimizes expected squared prediction error, E(y − x⊤θ∗)^2, over θ in H.
  • The model assumes mean-zero variables, a spectral covariance representation with independent components, lower-bounded conditional noise variance, and conditionally subgaussian regression noise.
  • The data are assumed to span n dimensions after projection orthogonally to any covariance eigenvector, supporting exact interpolation under the stated setup.
  • Excess risk evaluates an estimator’s prediction error relative to the optimal parameter, using a fresh covariate-response pair conditional on the estimate.
  • The minimum-norm estimator fits Xθ = y and selects the smallest Hilbert-space norm among potentially many exact interpolators.
  • The estimator is equivalently characterized through least-squares normal equations and the pseudoinverse, while the paper bounds its excess risk using covariance effective ranks.
  • Effective-rank definitions are based on the descending eigenvalues of the covariance operator and its operator norm.

3 Main Results

The paper characterizes benign overfitting for minimum-norm linear interpolants using effective ranks of the covariance, showing that substantial overparameterization is required. Examples further show that benign overfitting permits a much broader range of covariance spectra in high finite dimensions than in infinite dimensions.

  • Nearly matching upper and lower risk bounds characterize when the minimum-norm interpolating estimator has near-optimal prediction accuracy.
  • Effective Ranks and Overparameterization: The effective-rank conditions require r0(Σ) small relative to n while rk*(Σ) and Rk*(Σ) are large relative to n.These are the covariance-spectrum conditions controlling the estimator’s excess risk.
  • Effective Ranks and Overparameterization: Benign overfitting therefore requires many low-variance directions, with their number significantly exceeding the sample size.When there are not many more such directions than samples, they must be roughly equal; with many more, greater asymmetry is allowed.
  • Effective Ranks and Overparameterization: For infinite-dimensional covariance with eigenvalues µk(Σ)=k^-α ln^-β(k+1), benign overfitting occurs if and only if α=1 and β>1.
  • Effective Ranks and Overparameterization: In finite dimensions growing faster than n, benign overfitting occurs for much broader spectra, including constant or slowly decaying eigenvalues with sufficiently small isotropic noise.The finite-dimensional setting resolves the tension between slow eigenvalue decay and summability.

4 Deep neural networks

The paper relates its linear-regression analysis to neural tangent kernel views of deep networks, while emphasizing that its assumptions do not directly cover this setting.

  • The neural tangent kernel viewpoint approximates deep neural networks as linear functions of their parameters.
  • Neural tangent kernel covariance eigenvalues can have heavy tails, and the dimension can be very large but finite.
  • The paper’s assumptions do not apply directly because neural tangent kernel covariates need not be linear transformations of independent components.
  • The linear analysis suggests that finite-dimensional truncation might matter for statistical performance in the overfitting regime.

5 Proof

The proof decomposes excess risk and controls its noise-sensitive term through covariance effective-rank conditions, using concentration bounds for weighted subgaussian random matrices.

  • Proof strategy: The excess risk splits into finite-sample distortion and label-noise distortion, with covariance weighting errors across parameter directions.
  • Proof strategy: The noise contribution is controlled through tr(C), whose behavior depends on effective rank in low-variance covariance directions.
  • Lower bounds: For identity covariance with p = n, random matrix theory yields a constant lower bound on tr(C), so the least-norm interpolant has constant excess risk.
  • Concentration: The proof applies concentration lemmas to independent subgaussian vectors and combines the resulting bounds with union bounds.
  • Concentration: When effective rank is sufficiently large, eigenvalues of the relevant weighted outer-product matrices concentrate within constant factors.
  • Technical results: Lemma 11 provides a high-probability bound under k ≤ n/c, effective rank at least bn, and l ≤ k.

6 Conclusions and Further Work

The paper characterizes benign overfitting through covariance effective ranks and concludes that many low-variance directions and sufficiently large finite dimension broaden the conditions for near-optimal interpolation.

  • The results give finite-sample excess-risk bounds for minimum-norm interpolation in terms of two effective-rank notions of covariance.
  • Benign overfitting requires many low-variance, prediction-unimportant parameter directions, making significant overparameterization essential.
  • Further work: The assumptions require a linear conditional mean and covariates generated as linear transformations of independent random variables.
  • Further work: The latter covariate assumption excludes examples such as infinite-dimensional reproducing kernel Hilbert spaces with continuous kernels on finite-dimensional spaces.
  • Further work: Extending the results to other losses, other interpolators, and nonlinear neural-network parameterizations remains future work.

A Proof of Lemma 7

The proof of Lemma 7 begins with an excess-risk decomposition and uses conditional noise concentration plus matrix identities to control its two components.

  • The excess risk of the minimum-norm estimator is first decomposed into terms involving the estimator’s finite-sample and noise distortions.
  • Conditional mean-zero independent noise permits the noise-dependent term to be analyzed separately from the design matrix.
  • A subgaussian quadratic-form bound controls εᵀCε through the trace of C.
  • The Sherman–Morrison–Woodbury formula is used to manipulate inverse matrices involving ZᵀA^-1Z and ZᵀA^-2Z.

C Proof of concentration inequalities

This section assembles concentration tools for subgaussian and subexponential variables, then applies an epsilon-net argument to control random quadratic forms and matrix norms.

  • C Proof of concentration inequalities: Standard subgaussian and subexponential concentration results provide the probabilistic ingredients for the appendix’s matrix bounds.The section invokes Bernstein-type inequalities and consequences for weighted sums and quadratic forms.
  • C Proof of concentration inequalities: If ξ is centered, σ^2-subgaussian, and unit variance, then ξ^2 − 1 is centered subexponential with controlled moment generating function.The stated bound is E exp(λ(ξ^2 −1)) ≤ exp(c2σ^4λ^2) for sufficiently small |λ|.
  • C Proof of concentration inequalities: An epsilon-net argument transfers quadratic-form bounds from a finite net on the sphere to a bound on the full symmetric matrix norm.For an epsilon-net with ε < 1, the proof approximates a leading eigenvector and controls the resulting approximation error.
  • C Proof of concentration inequalities: The resulting union-bound construction uses a 1/4-net with cardinality at most 9^n and probability bounds of the form 1 − 2e^−t.The net estimate is combined with the quadratic-form concentration bound and a norm-conversion factor.

D Proof of Lemma 14

The proof of Lemma 14 combines high-probability bounds for fixed indices with Cauchy–Schwarz to obtain a uniform conclusion on a shared event.

  • D Proof of Lemma 14: Lemma 14 is established by intersecting events whose failure probabilities are bounded exponentially in n.The proof records intermediate probabilities at least 1 − 2e^−n/c1 and 1 − 5e^−n/c3 before choosing constants.
  • D Proof of Lemma 14: Cauchy–Schwarz and Corollary 13 supply the final comparison on the same high-probability event.The argument concludes after selecting a sufficiently large universal constant.

E Proof of Lemma 15

This section proves eigenvalue and effective-rank properties using variational characterizations, monotonicity, and an optimization over an index threshold.

  • E Proof of Lemma 15: The Courant–Fischer–Weyl characterization expresses μ_i(A) through a minimum over subspaces of dimension n − i and a maximum Rayleigh quotient.This variational form is then used to compare eigenvalues of ordered symmetric matrices.
  • E Proof of Lemma 15: Loewner ordering A ⪯ B implies μ_i(A) ≤ μ_i(B) for every index i.The proof applies the variational characterization to the minimizing subspace for A and the analogous subspace for B.
  • E Proof of Lemma 15: The quantity r0(Σ) is identified as an effective-rank complexity parameter, with related terminology including stable rank and numerical rank.The section distinguishes the historical terminology from the different meaning of numerical rank in computational linear algebra.
  • E Proof of Lemma 15: The proof compares R_k(Σ) and r_k(Σ), then studies monotonicity of φ(k) = k/(b^2n) + n/R_k.The minimizing index is characterized through the point where the effective-rank condition crosses the threshold b n.

I Conditions on eigenvalues

This section derives eigenvalue-decay conditions governing benign overfitting through effective-rank thresholds and applies them to infinite- and finite-dimensional covariance sequences.

  • I Conditions on eigenvalues: For λ_k,n = k^−α log^−β(k + 1), benign overfitting holds if and only if α = 1 and β > 1.This result identifies a specific polynomial-logarithmic decay boundary for the infinite-dimensional sequence.
  • I Conditions on eigenvalues: For λ_k,n = k^−(1+α_n), benign overfitting holds if and only if α_n = ω(1/n) and α_n = o(1).The theorem describes a shrinking exponent regime in which α_n vanishes but remains asymptotically larger than 1/n.
  • I Conditions on eigenvalues: k*(n)/n → 0 if and only if r_n/n → ∞ when the effective-rank sequence is increasing.Theorem 33 links the fraction of retained directions to the growth rate of the effective rank.
  • I Conditions on eigenvalues: n/R_k*(n) → 0 follows under a sufficient growth condition on the increasing effective-rank sequence.Theorem 34 gives the condition and notes that r_n = n log n satisfies it.
  • I Conditions on eigenvalues: For finite-dimensional power-law spectra λ_i,n = i^−α up to p_n, benign overfitting requires p_n = ω(n), with additional conditions depending on α and p_n.For α > 1, k* = Ω_α(n), ruling out benign overfitting; for α ≤ 1, k* = o(n), while further effective-rank conditions remain necessary.
  • I Conditions on eigenvalues: For spectra with a flat component and exponential tail, benign overfitting holds iff p_n = ω(n) and n e^−o(n) = ε_n p_n = o(n).The result also states that this regime includes p_n = Ω(n) with ε_n p_n = n e^−o(n).

K Another lower bound

The section develops a lower-bound argument by constructing Algorithm C from the least-norm interpolation algorithm and then showing that quantized, noiseless regression remains difficult. The contradiction relies on producing many separated parameter sets and establishing that their number grows as Ω(n log n).

  • Packing construction: The covariance construction partitions coordinates into sets and maps vectors in R^d into the Hilbert space by assigning a common weight within each set.The mapping φ preserves separation sufficiently: ρ(φ(u), φ(v)) ≥ ||u−v||.
  • Packing construction: Definition 36 produces Ω(n log n) sets, providing enough separated directions for the lower-bound packing argument.The proof reaches a contradiction because d = Θ(s) and d = Ω(n log n) for large enough n and small enough τ.
  • Construction of Algorithm C: Algorithm C feeds the least-norm interpolation algorithm responses modified by quantized Gaussian noise and additional uniform noise.For each response y, it supplies y + Q_α(ε) + ζ, with ε distributed as N(0,1) and ζ uniform on (−α/2, α/2).
  • Construction of Algorithm C: If least-norm interpolation learns noisy Gaussian-design problems with error τ, Algorithm C learns corresponding quantized noiseless problems with error at most τ.The success probability changes from 1−δ to 1−2δ.
  • Lower bound: Combining the reduction with the quantized-data lower bound shows that the least-norm interpolant cannot achieve sufficiently small error in the corresponding noisy setting.The proof applies Lemma 41 and Lemma 45 to obtain failure for a small enough constant τ0.
  • Lower bound: When 1/α = O(n), every regression algorithm given n quantized noiseless examples has error exceeding a constant τ with probability at least 1/2.This is the lower bound established for data with rows independently drawn from N(0,Σ).
Loading 1906.11300v3…