Harmless interpolation of noisy data in regression

Vidya Muthukumar; Kailas Vodrahalli; Vignesh Subramanian; Anant Sahai

Source-linked AI summary

Harmless interpolation of noisy data in regression

Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, Anant Sahai

arXiv:1903.09139v2Mar 21, 2019cs.LGstat.ML

TL;DR

The paper asks whether noisy training data can be interpolated without sacrificing generalization, using overparameterized linear regression as an analyzable setting. It characterizes the fundamental error of interpolators, identifies signal bleeding and noise overfitting, and constructs hybrid interpolators. The resulting analysis shows that interpolation noise can become harmless with sufficiently many features, while hybrid methods achieve order-optimal MSE in the sparse model.

Problem
The paper investigates how solutions that interpolate noisy training data can nevertheless generalize well in overparameterized settings.
Method
The paper analyzes all interpolating solutions in overparameterized linear regression and constructs two-step hybrid interpolators for sparse signals.
Results
The fundamental excess MSE of interpolation can converge to zero with increasing features, and sparse hybrid interpolators achieve the order-optimal MSE among interpolators.
Takeaways & Limitations
Overparameterization can make fitting noise harmless when enough aliased features absorb and dissipate training noise, while signal preservation requires a complementary strategy.
Takeaways & Limitations
Harmless interpolation is established with matching upper and lower bounds only for Gaussian features and independent sub-Gaussian feature vectors, not under the weaker general assumptions.

Abstract

from arXiv · show

A continuing mystery in understanding the empirical success of deep neural networks is their ability to achieve zero training error and generalize well, even when the training data is noisy and there are more parameters than data points. We investigate this overparameterized regime in linear regression, where all solutions that minimize training error interpolate the data, including noise. We characterize the fundamental generalization (mean-squared) error of any interpolating solution in the presence of noise, and show that this error decays to zero with the number of features. Thus, overparameterization can be explicitly beneficial in ensuring harmless interpolation of noise. We discuss two root causes for poor generalization that are complementary in nature -- signal "bleeding" into a large number of alias features, and overfitting of noise by parsimonious feature selectors. For the sparse linear model with noise, we provide a hybrid interpolating scheme that mitigates both these issues and achieves order-optimal MSE over all possible interpolating solutions.

1 Introduction

Overparameterized interpolation challenges classical expectations that excess model complexity causes poor generalization. This paper studies the phenomenon in noisy linear regression, characterizes when interpolation is harmless, and develops interpolators that preserve signal while absorbing noise.

Overparameterized neural networks can fit noisy data to zero training error while still generalizing well, challenging classical bias-variance expectations.
The analysis addresses overparameterized linear regression as a simpler, classically studied setting for understanding interpolation and generalization.
The paper gives a fundamental limit on the excess MSE of every noisy-data interpolator and shows it converges to zero as feature count grows under mild conditions.
The authors interpret minimum-ℓ2 interpolation through Fourier analysis and study how feature transformations can mitigate signal bleeding.
Minimum-ℓ2 interpolation can cause signal “bleed,” while parsimonious interpolators can overfit pure noise.
Two-step hybrid interpolators recover signal, harmlessly fit noise, and achieve the order-optimal rate among all interpolators.

2 Problem Setting

The paper studies noisy, overparameterized linear regression under a correctly specified feature model. Estimators interpolate all training responses, and performance is measured by expected test MSE after removing irreducible noise.

Data follow Y = ⟨a(X), α∗⟩ + W, with Gaussian noise W ∼ N(0, σ2) independent of X.
The feature covariance Σ = E[a(X)a(X)⊤] is assumed invertible, and covariates are generally iid random samples.
The primary regime is d > n, where the full-row-rank training matrix makes interpolation feasible.
Test MSE is the expected fresh-sample squared error minus irreducible noise σ2.

3 The fundamental price of interpolation

The paper defines the minimum test MSE attainable by any interpolating solution and establishes when interpolation can be harmless despite fitting noise. The fundamental price depends on whitened feature geometry, decreases with extreme overparameterization, and is achievable under Gaussian or independent sub-Gaussian features.

The fundamental price: The ideal interpolator minimizes test MSE among all coefficients satisfying the interpolation constraint A_trainα = Y_train.Its test MSE is therefore a lower bound on every interpolating solution.
The fundamental price: Theorem 1 gives an explicit lower bound on the best possible test MSE for any interpolating solution, for arbitrary joint distributions and training realizations.The bound can be evaluated for different feature families through the whitened training matrix B_train = A_trainΣ^-1/2.
Examples: Figure 1 shows the beneficial behavior for whitened Legendre features and Gaussian features, but not for unwhitened Vandermonde features.The comparison illustrates the importance of whitening for these polynomial features.
Feature geometry: The fundamental price depends on the singular-value spectrum of the whitened feature matrix B_train.Whitening is expected to improve conditioning and reduce error arising solely from fitting noise.
Harmless interpolation: For Gaussian and independent sub-Gaussian features, upper bounds match the general lower bound, showing that harmless interpolation is attainable under these feature families.The corresponding results hold with explicitly stated high probability, while the general lower-bound result also covers heavy-tailed features.
Overparameterization: As d grows much faster than n, the noise-fitting contribution to test MSE decays to zero; this regime is essential for harmless interpolation.The conclusion applies to extreme overparameterization, whereas d approximately equal to n produces a peak that Corollary 2 does not explain.
Technical scope: The analysis uses non-asymptotic random matrix theory, sharply characterizing dependence on n and d but not constant factors.For Gaussian features, the probability statements are obtained using a union bound over the relevant events.

4 The minimum-ℓ2-norm interpolator through the Fourier lens

The Fourier lens explains when minimum-ℓ2-norm interpolation generalizes: aliases can dissipate noise but also dilute signal, so appropriate feature weighting must balance both effects.

For large d, Fourier-feature interpolation achieves the same scaling as the ideal MSE bound, because aliases dissipate noise energy across unfavored directions.This provides a mechanism for harmless noise fitting in sufficiently overparameterized settings.
The minimum-ℓ2-norm interpolator generalizes well with double descent for Example 5 but extremely poorly for Example 4.Example 5’s random Gaussian features increasingly approximate the constant true signal through a dominant covariance eigenvector, whereas Example 4 lacks that favorable prior structure.
Avoiding signal “bleed”: Minimum-ℓ2-norm interpolation divides each coefficient across aliased features, reducing signal survival in true features and increasing contamination by spurious ones.The same energy-dispersion mechanism helps noise but harms recovery of genuine signal.
Avoiding signal “bleed”: A strong prior on a low-dimensional subspace can prevent signal bleeding when the true signal is well represented there.The transformed feature family reweights features so true directions are favored over their aliases.
Avoiding signal contamination: Preventing bleeding alone is insufficient: higher-frequency features must retain enough weight to keep noise contamination from remaining nonvanishing.Consistency requires balancing signal preservation against noise dissipation; avoiding contamination is a separate condition.

5 Interpolation in the noisy sparse linear model

In the noisy sparse linear model, sparsity-seeking interpolators can fit noise poorly, while hybrid interpolators separate signal recovery from noise fitting and achieve order-optimal test MSE.

Model: The noisy sparse linear model assumes whitened features, k-sparse signal α∗, and Gaussian noise with variance σ2.The model uses E=I_d and support size |S∗|≤k.
Sparsity-seeking interpolators: OMP run to completion and minimum-ℓ1-norm interpolation are substantially better than minimum-ℓ2 interpolation for sparse recovery with noise.These methods are evaluated on Gaussian features in Figure 7.
Sparsity-seeking interpolators: Parsimonious interpolators overfit pure noise because they use O(n) features to interpolate it, causing test MSE to decrease extremely slowly.The decrease is negligible compared with the ideal test MSE across the studied high-dimensional regimes.
Sparsity-seeking interpolators: In polynomially high-dimensional regimes, consistency of parsimonious interpolators may be possible only at an extremely slow logarithmic rate.With d=n^q for q>1, the relevant quantity goes to zero slowly; exponentially overparameterized regimes have faster rates but make signal recovery impossible.
Order-optimal hybrid methods: A two-step hybrid interpolator first estimates the sparse signal and then fits the residual noise, thereby addressing signal recovery and noise fitting separately.The construction is motivated by the tradeoff between signal contamination and harmless interpolation of noise.
Order-optimal hybrid methods: Hybrid interpolators achieve order-optimal test MSE among all interpolating solutions, with suitable first-stage choices including Lasso, OMP, and square-root-Lasso.The guarantee applies when d>4n, and SLOPE is cited as one order-optimal estimator.
Order-optimal hybrid methods: Increasing d reduces noise-fitting error as 1/d but increases signal-recovery error logarithmically through false discovery of fake features.The resulting logarithmic-linear tradeoff favors substantial, rather than infinite, overparameterization; hybrid test MSE closely tracks the ideal MSE in Figure 7.

6 Conclusions for high-dimensional generative model

Overparameterization can make noise interpolation harmless, but generalization depends on balancing noise absorption with signal preservation. The paper favors hybrid interpolators while stressing that denoising regularization remains practically preferable and important nonlinear extensions remain unresolved.

Overparameterization is necessary for harmless interpolation, because aliased features can absorb and dissipate training-noise energy as their number grows.The interpolation price decays to zero as the level of overparameterization increases.
The ℓ2-minimizing interpolator absorbs noise effectively but can bleed signal across aliases unless the true signal lies in a known subspace.Reliable learning requires a strong bias toward predetermined feature directions and measuring error along those directions.
The ℓ1-minimizing interpolator preserves sparse signal more successfully but fails to absorb training noise harmlessly.This is the complementary failure mode to signal bleeding by ℓ2 minimization.
Two-step hybrid interpolators combine sparse signal preservation with noise spreading and achieve asymptotically order-optimal rates among interpolating solutions.They first fit the signal and then interpolate the residual in a way that disperses noise.
Despite harmless interpolation being possible, it is practically suboptimal to optimal denoising regularization, including because noise variance need not be known for regularization.The discussion describes the additional noise-fitting step as artificial and unnecessary.
6.1 Future Directions: The analysis leaves model misspecification and nonlinear, deep-neural-network overparameterization for future work.The effects of non-quadratic losses and substantial nonlinearity remain unclear.

A Supplemental proofs

The supplemental proofs begin by stating the matrix-concentration tools needed to establish the main corollaries. They organize the arguments around sub-Gaussian and heavy-tailed row distributions.

The supplement starts by formally stating matrix concentration results used in proving Corollaries 1 and 2.
The concentration lemmas provide the probabilistic controls required for the supplemental derivations.
The proof framework first treats matrices with sub-Gaussian rows and then considers matrices with heavy-tailed rows.These correspond to Assumptions 2 and 1, respectively.

A.1.1 Supplemental lemmas for sub-Gaussian case

The sub-Gaussian supplement uses matrix concentration to control singular values and prove Corollary 1, while Corollary 2 requires stronger iid-entry assumptions. General sub-Gaussianity alone does not sufficiently control the minimum singular value.

Sub-Gaussian random variables and vectors are defined before applying concentration lemmas to the training matrix.The lemmas assume independent sub-Gaussian isotropic rows and provide high-probability spectral bounds.
The sub-Gaussian concentration bound controls σmax(Btrain) and, with a chi-squared tail bound, proves Corollary 1.
Corollary 2 cannot generally be proved from sub-Gaussian feature vectors alone because available minimum-singular-value bounds may be vacuous.The supplement notes that suitable results impose restrictive normalization and incoherence conditions.
For independent unit-variance sub-Gaussian entries, a dedicated lemma supplies the minimum-singular-value concentration needed for Corollary 2.The entries must be independent, centered, unit variance, and have bounded sub-Gaussian parameter.

A.1.2 Supplemental lemmas for heavy-tailed case

The heavy-tailed supplement applies a concentration lemma for bounded-norm isotropic rows to establish the relevant test-MSE bound. Its multiplicative deviation form weakens both the scaling and the high-probability guarantee.

The heavy-tailed proof uses concentration for independent isotropic rows whose norms are almost surely bounded by √n.
The heavy-tailed concentration result holds with probability at least 1 − 2ne−ct^2.
Because the deviation parameter enters multiplicatively, the resulting ideal-test-MSE scaling and high-probability strength are weaker than in the sub-Gaussian case.The proof also notes that the minimum singular value remains delicate and may require incoherence conditions.

A.2 Proof of Corollary 4

The proof establishes equivalence between basis pursuit and a linear program, then uses this equivalence to characterize optimal solutions under non-degeneracy assumptions. With Gaussian noise, the BP solution is unique and has support size exactly n with probability 1.

BP–LP equivalence: Any optimal LP solution has disjoint supports for u and v, because overlapping positive entries can be replaced by a feasible solution with lower objective value.The proof handles both signs of u_j − v_j by retaining only the larger component at the overlapping index.
BP–LP equivalence: BP and the LP are equivalent through α = u − v, with optimal solutions corresponding under this transformation.The equivalence also preserves the support of corresponding optimal solutions.
Support size: An optimal BP solution exists with support size at most n, since an optimal basic feasible solution of the equivalent LP has at most n nonzero variables.The LP optimum is attained at an extreme point, and the BP transformation preserves optimality.
Uniqueness: Under Assumptions 4–6, the BP solution is unique with probability 1 over Gaussian noise.Distinct basic feasible solutions have equal ℓ1 objective value with probability zero because the relevant matrix ratio is not a generalized permutation matrix.
Support size: Under the same assumptions, the unique BP solution has support size exactly n with probability 1.Solutions supported on fewer than n columns require Gaussian noise to lie in a lower-dimensional column span, an event of probability zero.

A.3 Proof of Proposition 1

The proposition’s proof expresses the hybrid estimator’s test error relative to a suitable sparse estimator. The resulting decomposition connects hybrid performance to the sparse estimator’s prediction error.

Error decomposition: The hybrid estimator is compared with a suitable sparse estimator through their difference, denoted by Δ.The difference is expressed using the pseudoinverse of the training design matrix.
Error decomposition: Substituting this difference into the test-error expression completes the proof of Equation (29).The proof explicitly uses the prediction error Eest(α1) of the sparse estimator.
Estimator choice: The sparse estimator α1 may be obtained by methods such as Lasso or OMP when the sparsity level or noise variance is available.The proof treats α1 as any suitable sparse-recovery estimator rather than requiring one specific procedure.

A.3.1 Proof of Corollary 5 (order-optimality)

The order-optimality proof substitutes the conditions in Equations (30a) and (30b) into the test-error expression and verifies the required dimensional scaling.

Order-optimality: Substituting the order-optimality conditions from Equations (30a) and (30b) into Equation (29) yields the desired error bound.The derivation uses the stated high-probability inequalities.
Order-optimality: The dimensional requirement d ≥ cn for c > 4 implies d − 2√n ≥ c′√n for some c′ > 0.This inequality is identified as matching the statement of Equation (31).

A.3.2 Recovery guarantees for Lasso (Corollary 6) and square-root-Lasso (Corollary 7)

The section gives recovery and prediction guarantees for Lagrangian Lasso and square-root-Lasso hybrid interpolators under a restricted eigenvalue condition. Both achieve bounds scaling with σ²k ln d/n, while square-root-Lasso does not require knowing σ.

Definitions and assumptions: The Lagrangian Lasso and square-root-Lasso are defined as alternative sparse estimators used in hybrid interpolators.Their guarantees require k-sparsity together with a restricted eigenvalue condition on the training design.
Design condition: An iid Gaussian training matrix satisfies the restricted eigenvalue condition with probability at least 1 − 2e^(−cn) when n ≥ Ck ln d.This supplies a high-probability design condition for the recovery guarantees.
Lagrangian Lasso: Under the restricted eigenvalue condition, Lagrangian Lasso solutions satisfy the stated estimation and prediction-error bounds for an appropriate regularization parameter.The theorem assumes restricted eigenvalue parameters (κ, β = 3).
Lagrangian Lasso: Eest ∼ Epred ≤ C′′ σ²k ln d/n with high probability for the Lagrangian Lasso.The bound follows for the regularization choice specified in the corollary.
Square-root-Lasso: Square-root-Lasso satisfies analogous estimation and prediction guarantees under the same restricted eigenvalue framework.Its theorem provides bounds for solutions using an appropriate γ_n regularization parameter.
Square-root-Lasso: Eest ∼ Epred ≤ C′′ σ²k ln d/n with high probability for square-root-Lasso, whose regularization choice does not depend on σ.Thus the method can achieve the stated rates without requiring prior knowledge of the noise variance.

A.3.3 Recovery guarantee for OMP (Corollary 6)

This section formalizes noisy orthogonal matching pursuit (OMP) and states support-recovery guarantees under two stopping conditions. The guarantees require incoherence and sufficiently strong nonzero coefficients, with overparameterization making the signal-to-noise requirement more stringent.

Algorithm: OMP iteratively selects the variable most correlated with the residual, projects onto the selected columns, updates the residual, and stops using either of two conditions.Condition a) compares the maximum residual correlation with a noise-based threshold; Condition b) stops after a known upper bound on sparsity.
Recovery guarantees: Under Condition a), OMP recovers the true support S = supp(α∗) with the stated high probability.This condition uses knowledge of the noise variance.
Recovery guarantees: Under Condition b), OMP recovers a superset S ⊃ supp(α∗) with the stated high probability.This condition uses a guaranteed upper bound k0 on the true sparsity level k.
Interpretation: The noisy OMP guarantees concern support recovery, which is stronger than directly bounding the ℓ2 coefficient error.Their coefficient requirements can be viewed as requiring sufficiently high SNR for signal recovery.
Limitations and side information: As d increases, the coefficient or SNR requirement becomes more stringent, while the two stopping conditions rely on different side information.Condition a) uses the noise variance; Condition b) uses an upper bound on sparsity.

B The interpolation threshold: Regularity vs randomness of training data

The interpolation-threshold experiments show that training-point regularity substantially affects generalization. Regular spacing approximately preserves feature orthogonality, whereas random sampling produces lower and heavy-tailed test-MSE behavior and requires stronger overparameterization for harmless noise fitting.

Scope: Corollary 2 is primarily meaningful when d >> n and does not mathematically explain the interpolation peak near d ∼ n.That peak reflects the mean minimum possible test MSE arising purely from fitting noise at the interpolation threshold.
Regularity versus randomness: Regularly spaced training points approximately preserve the orthogonality of the design matrix because they appropriately approximate the feature-space integral.Legendre and Fourier features are orthogonal in function space over [−1, 1].
Experimental setup: Figure 9 compares test MSE for ideal and practical interpolators using Legendre and Fourier features with regularly spaced or randomly drawn training points.The true fit is a 2-degree polynomial, and the figure reports results for both sampling schemes.
Regularity versus randomness: Randomly drawn training data produces lower, heavy-tailed test MSE, reflected by large confidence intervals and a much lower median than the mean.The median remains higher than the test MSE for regularly spaced training data.
Implication: Randomly drawn training data requires overparameterization to ensure harmless fitting of noise, unlike logistic regression.The analysis attributes the heavy-tailed behavior intuitively to the non-uniformity of random spacings and its connection to the minimum singular value.

D Calculations for the regularly spaced Fourier case

For regularly spaced Fourier features, exact aliases create multiple interpolating representations of the same training signal. The analysis shows how weighted minimum-norm interpolation distributes signal across aliases, attenuating the true component and introducing contamination at test points.

Alias structure: With regularly spaced samples, Fourier features have exact aliases of a true feature k∗ at indices S(k∗) = {k∗ + n, k∗ + 2n, …, k∗ + Mn}.The analysis assumes d = (M + 1)n and reduces the problem to the true feature and its aliases.
Weighted interpolation: The minimum weighted ℓ2-norm interpolating solution is obtained by scaling Fourier features with weights and minimizing the coefficient norm subject to the interpolation constraint.The weighted formulation is equivalent to minimum ℓ2 interpolation for the weighted features.
Weighted interpolation: The optimization can be restricted to the true feature and its alias set because coefficients outside those indices are zero at the optimum.The reduced problem is solved using the Cauchy–Schwarz equality condition.
Test-time effect: At a test point, prediction decomposes into an attenuated true signal and a contamination term caused by signal bleeding into features orthogonal to the true signal.The surviving signal fraction and contamination standard deviation quantify these two components.
Test-time effect: For uniformly spaced test inputs, Fourier-feature orthogonality simplifies evaluation of the surviving signal and contamination components.The relevant feature inner products are zero for distinct indices and one for identical indices.
Weighting schemes: Spiked weights place a fraction of energy on a favored set of s < n low-frequency features, providing an example of a nonuniform weighting scheme.The analysis also compares this scheme with uniform weights wj = 1.