On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels

Tengyuan Liang; Alexander Rakhlin; Xiyu Zhai

Source-linked AI summary

On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels

Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai

arXiv:1908.10292v2Aug 27, 2019math.STcs.LGstat.MLstat.TH

TL;DR

The paper asks how minimum-norm RKHS interpolants generalize across dimension–sample scalings where classical regularized analyses do not address the non-regularized solution. It derives spectral risk bounds, finds multiple-descent behavior with empirically aligned peaks, and extends guarantees to wide neural networks through the neural-tangent-kernel connection.

Problem
The paper investigates the generalization and consistency of minimum-norm RKHS interpolants across scaling regimes d ≍ n^α, beyond classical analyses requiring tuned regularization.
Source: §1 · pp. 1–2
Method
The analysis studies random kernel matrices restricted to filtration eigenspaces of the population covariance operator and proves a restricted lower isometry property.
Source: §1 · p. 4, §8.1 · p. 15
Results
Risk upper bounds exhibit multiple descent across d ≍ n^α, with empirical peak locations matching theoretical predictions and no consistency at α = 0.
Source: §1 · p. 2, §7 · p. 12
Takeaways & Limitations
The results provide generalization guarantees for minimum-norm RKHS interpolants and, through the NTK connection, for appropriately initialized wide neural networks.
Source: §7 · p. 12
A lower bound exhibiting multiple-descent behavior remains open, and the results rely on assumptions including independent coordinates.
Source: §1 · p. 3, §7 · p. 12

Abstract

from arXiv · show

We study the risk of minimum-norm interpolants of data in Reproducing Kernel Hilbert Spaces. Our upper bounds on the risk are of a multiple-descent shape for the various scalings of $d = n^{\alpha}$, $\alpha\in(0,1)$, for the input dimension $d$ and sample size $n$. Empirical evidence supports our finding that minimum-norm interpolants in RKHS can exhibit this unusual non-monotonicity in sample size; furthermore, locations of the peaks in our experiments match our theoretical predictions. Since gradient flow on appropriately initialized wide neural networks converges to a minimum-norm interpolant with respect to a certain kernel, our analysis also yields novel estimation and generalization guarantees for these over-parametrized models. At the heart of our analysis is a study of spectral properties of the random kernel matrix restricted to a filtration of eigen-spaces of the population covariance operator, and may be of independent interest.

1 Introduction

The paper studies minimum-norm RKHS interpolants across d ≍ n^α and derives risk bounds with multiple-descent behavior, supported by experiments whose peaks match theoretical predictions. Its analysis combines generalization bounds with spectral control of random kernel matrices on population-covariance eigenspaces.

The paper studies minimum-norm interpolants in RKHS across the general scaling regime d ≍ n^α, α ∈ (0, 1), to characterize their risk and consistency.Source: §1 · pp. 1–2
For α approaching 0, even the fastest rate worsens, with no consistency at α = 0, matching the lower bound of Rakhlin and Zhai (2018).Source: §1 · p. 2
At fixed d, increasing n can alternate between better and worse performance because empirical kernel matrices estimate increasingly complex subspaces tied to smaller population eigenvalues.Source: §1 · pp. 2, 4
A lower bound exhibiting multiple descent remains open, although the interpolating solution has diminishing out-of-sample error for most scalings of d and n.Source: §1 · p. 3
Experiments at n = 5000 confirm multiple peaks in the variance of the minimum-norm interpolant, with peak locations aligning with theoretical predictions.Source: §1 · p. 2, Figure 2 · p. 3
Theorem 1 gives risk upper bounds with non-monotone multiple-descent behavior as the dimension-to-sample scaling changes.Source: §1 · pp. 2–3, Figure 1 · p. 2
The analysis studies spectral properties of random kernel matrices through a restricted lower isometry property on filtration eigenspaces of the population covariance operator.Source: §1 · pp. 3–4

2 Restricted Lower Isometry of High-Dimensional Kernels

The paper establishes restricted lower isometry for empirical kernel matrices on degree-indexed polynomial feature spaces in a growing-dimensional regime. This spectral control supports the later risk guarantees for kernel interpolation and wide neural networks.

2 Restricted Lower Isometry of High-Dimensional Kernels

The proposition is the key ingredient for bounding kernel ridgeless-regression generalization error and deriving guarantees for converged, randomly initialized wide neural networks.The paper also relates its least-eigenvalue control to concurrent random Fourier feature work under different assumptions.Source: §2 · p. 4, §2.3 · p. 7

2.1 Setup

The setup uses i.i.d. product-distributed coordinates, smooth kernels with nonnegative Taylor coefficients, and normalized kernel matrices K = k(X, X)/n.The coordinate distribution is centered, polynomially tailed, and non-atomic.Source: §2.1 · p. 4

2.2 Main Technical Result

Restricted lower isometry holds on a filtration of spaces indexed by increasing polynomial degree, under d^ι0 log d = o(n) and positive initial Taylor coefficients.The result holds with probability at least 1 − e^−Ω(n/d^ι0).Source: §2.2 · p. 5

2.3 Proof Outline.

The restricted lower isometry is equivalent to lower-bounding sample covariance eigenvalues by d^−ι on the corresponding polynomial feature spaces.Nonzero eigenvalues of the truncated kernel matrix correspond to those of the associated covariance operator.Source: §2.3 · p. 6
The proof orthogonalizes correlated monomials into polynomial features, then uses weak correlation and a small-ball argument to control the smallest eigenvalue.Standard concentration is insufficient at the target d^−ι scale, motivating the small-ball method and Paley–Zygmund inequality.Source: §2.3 · pp. 6–7

3 Application to Kernel Ridgeless Regression

This section decomposes ridgeless-regression risk into variance and squared bias, then bounds both using restricted lower isometry and structural assumptions on the target function. The resulting analysis covers polynomial and non-polynomial kernel regimes.

3 Application to Kernel Ridgeless Regression

Risk analysis begins from a conditional bias–variance decomposition, with expectation taken over the response vector Y while conditioning on the design X.The two terms are identified as variance and squared bias.Source: §3 · p. 7

3.1 Variance

The variance bound applies in regimes d^ι log d ≲ n ≲ d^(ι+1), with high-probability control under sub-Gaussian inputs.For polynomial kernels, the stated condition becomes d^ι log d ≲ n.Source: §3.1 · p. 8
The variance proof splits contributions by polynomial degree, applying restricted lower isometry to one part and nK ⪰ Ω(1)I_n to the other.This connects the risk bound directly to the spectral proposition from Section 2.Source: §3.1 · p. 8

3.2 Bias

Under a suitable representation of f*, the squared bias is upper bounded by a multiple of the variance bound.The theorem assumes bounded kernel diagonals and ℓ2-bounded coefficient-related random variables.Source: §3.2 · p. 8
The bias statement also holds in probability, with a δ^−1/2 factor independent of dimension d.Relaxing one target-function assumption increases this factor to δ^−1.Source: §3.2 · p. 9

4 Applications to Wide Neural Networks

The paper extends its kernel analysis to Neural-Tangent-type kernels, including the Neural Tangent Kernel. Because wide-network gradient flow converges to an NTK minimum-norm interpolant, the kernel risk bounds yield estimation and generalization guarantees for these models.

4 Applications to Wide Neural Networks

Theorem 1’s risk bound generalizes to Neural-Tangent-type kernels, including kernels with infinitely many positive Taylor coefficients, when d^ι log d ≲ n ≲ d^(ι+1)/log d.The inner-product kernel is recovered when data lie on a fixed-radius sphere.Source: §4 · p. 9
Sufficiently wide, appropriately initialized neural networks converge to the minimum-norm interpolating solution associated with the Neural Tangent Kernel.This connection transfers the kernel analysis to estimation and generalization guarantees for over-parameterized networks.Source: §4 · p. 9
The infinitely wide one-hidden-layer network’s kernel converges pointwise to an analytic kernel of the required form as width m tends to infinity.The paper verifies that multilayer fully connected NTKs also have positive Taylor coefficients in the relevant angular parameterization.Source: §4 · pp. 9–10

5 Proof of Theorem 2

The proof of the variance theorem first establishes kernel-matrix invertibility and a uniform spectral lower bound, then analyzes the variance through restricted spectral control on population-defined eigenspaces.

5 Proof of Theorem 2

The proof first shows that K is invertible and that its normalized form satisfies nK ⪰ cI_n with high probability.This supplies the baseline spectral control needed for the variance analysis.Source: §5 · pp. 10–11
The proof combines bounds on diagonal and off-diagonal terms with matrix norm inequalities and concentration estimates.These intermediate estimates control the deviation needed for the lower spectral bound.Source: §5 · pp. 10–11
The resulting intermediate quantity is bounded using Proposition 1, completing the variance-theorem argument.The proof concludes after applying the proposition’s restricted spectral control.Source: §5 · p. 11
The spectral argument restricts the sample kernel operator to the column space generated by lower-degree components and compares it with the corresponding truncated kernel matrix.The restriction is justified because the relevant vector lies in that column space.Source: §5 · p. 11

6 Proof of Theorem 3

The proof analyzes the bias term through a surrogate function and bounds its population error using auxiliary propositions.

The proof introduces a surrogate function to analyze the bias term of the minimum-norm interpolant.Source: §6 · p. 11
The surrogate is evaluated on the sample points through the kernel matrix and coefficient vector.Source: §6 · p. 12
Auxiliary propositions provide bounds for the resulting population squared error.Source: §6 · p. 12

7 Discussion

The discussion concludes that minimum-norm RKHS interpolants can have vanishing risk across many dimension–sample scalings, while their risk may exhibit multiple descent peaks and remains difficult to characterize precisely.

Risk vanishes in n for a wide range of scalings d ≍ n^α, α ∈ (0, 1), under the paper’s assumptions.Source: §7 · p. 12
The upper bound becomes vacuous at fractions α = 1/i, where empirical evidence supports non-monotone peaks generalizing double descent.Source: §7 · p. 12
The paper leaves precise risk-curve characterization and regularization effects on the peaks as open directions.Source: §7 · p. 12
In the noiseless case yi = f∗(xi), the variance term is zero and known lower-isometry results can simplify the analysis.Source: §7 · p. 12
The noisy case is harder because the kernel matrix K is not easily controlled.Source: §7 · p. 12

8 Proof of Main Proposition

The proof establishes restricted lower isometry by transforming polynomial features, proving a small-ball property, and controlling the resulting empirical spectrum.

8 Proof of Main Proposition

The main proposition proves restricted lower isometry for the empirical kernel matrix on population covariance eigenspaces indexed by increasing polynomial degree.Source: §8 · p. 14

8.2 Gram-Schimdt Process

The Gram-Schmidt construction uses polynomial bases and multi-indexed monomials to organize the relevant eigenspaces.Source: §8.1 · p. 14, §8.2 · p. 15

8.1 Preparation

A transformed matrix Ψ replaces the correlated feature matrix Φ, with a bounded invertible linear map Λ relating the two representations.Source: §8.1 · p. 15

8.3 Small Ball Property

The small-ball argument shows that normalized polynomial combinations have a nontrivial probability of exceeding a d^-ι-scale threshold.Source: §8.3 · p. 19, §8.4 · p. 22

8.4 Lower Isometry

A covering-net and Lipschitz argument yields a high-probability lower bound on the smallest eigenvalue of n^-1 Ψ^TΨ, larger than C d^-ι.Source: §8.4 · pp. 22, 24

9 Technical Proofs

The technical proofs establish moment and probability bounds for the variance analysis and approximate the kernel using truncated polynomial-type components.

9.1 Proofs in Section 3

The Section 3 proofs derive second-moment bounds for the terms used in the variance analysis.Source: §9.1 · pp. 25–26
The calculations identify which index configurations yield nonzero contributions and bound their number using O(n) and O(n^2) counts.Source: §9.1 · pp. 26–27
Chebyshev and second-moment arguments convert the calculations into probability bounds for the relevant error terms.Source: §9.1 · pp. 26–27

9.2 Proofs in Section 4

The Section 4 proof approximates the kernel by a weighted sum of polynomial-type inner-product kernels and controls the truncation remainder.Source: §9.2 · p. 27
The truncation degree is selected large enough to make the approximation error small while preserving the required uniform bounds.Source: §9.2 · p. 28