Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

Alexander Rakhlin; Xiyu Zhai

Source-linked AI summary

Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

Alexander Rakhlin, Xiyu Zhai

arXiv:1812.11167v1Dec 28, 2018stat.MLcs.LGmath.STstat.TH

TL;DR

The conditions under which exact interpolation generalizes well remain poorly understood. The paper analyzes minimum-norm interpolation with the Laplace kernel and shows it is inconsistent at constant input dimension, even when bandwidth is chosen from the data.

Problem
The conditions under which interpolation can generalize well remain poorly understood, despite evidence that procedures with zero training error can generalize well.
Source: §1 · p. 1
Method
The paper proves a lower bound for the estimation error of the minimum-norm interpolant in the Laplace-kernel RKHS.
Source: §1 · p. 2
Results
At constant input dimension, the Laplace-kernel minimum-norm interpolant is inconsistent for any data-dependent bandwidth choice.
Source: §1 · p. 2
Takeaways & Limitations
The result supports the empirical observation that minimum-norm interpolation can generalize well in some high-dimensional datasets but not in low-dimensional ones.
Source: §1 · pp. 1–2
The theorem assumes odd dimension and binary noise, with the authors describing these as technical simplicity and brevity assumptions, respectively.
Source: §2 · p. 3

Abstract

from arXiv · show

We show that minimum-norm interpolation in the Reproducing Kernel Hilbert Space corresponding to the Laplace kernel is not consistent if input dimension is constant. The lower bound holds for any choice of kernel bandwidth, even if selected based on data. The result supports the empirical observation that minimum-norm interpolation (that is, exact fit to training data) in RKHS generalizes well for some high-dimensional datasets, but not for low-dimensional ones.

1 Introduction

Although exact-fit procedures can generalize well, the conditions for successful interpolation remain poorly understood. This paper shows that minimum-norm interpolation with the Laplace kernel is inconsistent at constant input dimension, regardless of bandwidth choice.

1 Introduction

Kernel Ridge Regression can fit the training data exactly when λ = 0, so the paper considers the minimum-norm interpolating solution among the non-unique minimizers.The setting concerns training pairs in Rd × R and an RKHS associated with a kernel.Source: §1 · p. 1
Conditions under which interpolation generalizes well remain poorly understood, despite experiments showing that zero-training-error procedures can generalize well.Prior work studied high-dimensional interpolation and related its implicit regularization to high dimensionality and favorable geometric properties.Source: §1 · pp. 1–2
The Laplace-kernel minimum-norm interpolant is inconsistent when input dimension is constant, even with data-dependent bandwidth selection.The paper presents this as a theoretical justification for experiments suggesting poor performance in low dimensions.Source: §1 · p. 2
The paper studies the Laplace kernel because its minimum-norm interpolant relates to simplicial interpolation in one dimension and its RKHS norm relates to a Sobolev norm.The authors also note its reported similarity to ReLU networks and use of Laplace-kernel upper bounds under high-dimensional scaling.Source: §1 · p. 2

2 Main Theorem

The main theorem concerns noisy observations and the minimum-norm Laplace-kernel interpolant. Its lower bound rules out consistency at constant dimension for any data-dependent bandwidth, while the proof relates estimation error to random quantities controlling local spacing and derivatives.

2 Main Theorem

The theorem's setting uses i.i.d. sampled inputs, noisy responses, and a minimum-norm interpolant for the Laplace kernel.The supplied theorem statement is incomplete, so no numerical bound is reported here.Source: §2 · p. 3
The lower bound applies to every data-dependent bandwidth choice, and the authors state that odd dimension is a technical requirement while binary noise is assumed for brevity.They believe the result extends to even dimensions using more complicated harmonic-analysis tools; noise magnitude can be changed by rescaling.Source: §2 · p. 3
Without explicit regularization, controlling the interpolant's complexity is harder; noisy values at nearby data points suggest large derivatives.The paper relates the interpolating solution's norm to distances between datapoints.Source: §2 · p. 3
The proof relates estimation error to random quantities through Gagliardo-Nirenberg interpolation inequalities and control of higher-order derivatives.It requires tail control for powers of these quantities beyond the known expectation bound.Source: §2 · p. 3

3 Proof

The proof combines two distinct lower bounds to cover all choices of kernel width c. One controls smoothness for smaller c, while the other uses the L2 norm for large c.

3.1 Outline

In odd dimensions, the RKHS norm has an explicit form equal to a Sobolev norm.This supplies the smoothness control used in the first method.Source: §3.1 · pp. 3–4
The first method uses the RKHS norm to control smoothness and lower-bound squared loss near training points, but that bound becomes vacuous as c grows.The large-c method is therefore needed.Source: §3.1 · p. 4
For large c, the RKHS norm approximates the L2 norm, and the interpolant's L2 norm falls below a constant fraction of the target norm.This yields a lower bound on total squared loss.Source: §3.1 · p. 4
The two distinct lower bounds cover all choices of c, though this coverage is not immediately evident.The large-c argument uses an L2-norm bound; the other method controls smoothness.Source: §3.1 · p. 4

3.2 Notation

The notation Hc denotes the Laplace-kernel RKHS with width c, and its inner product and squared norm are written ⟨f, g⟩Hc and ∥f∥²Hc.The paper notes that its scaling convention does not change the algorithm's output.Source: §3.2 · p. 4

3.3 First Method: Control of H¨older Continuity; 3.4 Second Method: Control of L2 norm

The first method controls Hölder continuity, while the second method controls the interpolant's L2 norm.The proof outline combines the two methods' propositions.Source: §3.1 · p. 4, §3.3 · pp. 5–6, §3.4 · p. 6

A Explicit Form of RKHS norm

The appendix gives an expression, up to constant factors, for the Laplace-kernel RKHS norm and describes the associated eigenfunctions and eigenvalues. It obtains the norm expression through the kernel's integral operator and its eigenspace decomposition.

A Explicit Form of RKHS norm

For odd dimension d, Proposition A.1 gives an expression for the Laplace-kernel RKHS norm.The appendix describes the expression up to constant factors and provides associated eigenfunctions and eigenvalues.Source: A Explicit Form of RKHS norm · p. 7
The paper chooses a Fourier-transform convention and notes that scaling does not change the algorithm's output.Source: A Explicit Form of RKHS norm · p. 7
The Laplace kernel's integral operator has eigenfunctions hp(x) = e^(ip·x), whose eigenspace decomposition yields the RKHS inner product.The passage then rewrites that inner product and points to an explicit computation of the eigenvalues.Source: A Explicit Form of RKHS norm · pp. 7–8

B.1 Main Claims

The appendix states two propositions with high-probability claims and constants depending on dimension, and in one case on α. It also selects subsets of indices by ordering the associated radii.

B.1 Main Claims

Proposition B.1 states constants C1 and C2 depending on d and a probability bound, but the supplied passage does not include the full claim.Source: §B.1 · p. 8
Proposition B.2 states constants depending on α and d and a probability bound, but the supplied passage does not include the full claim.Source: §B.1 · p. 9
The proof selects a subset I1 of size ceil(βn) whose radii are at least those of indices outside I1, then introduces another subset I2.The passage states that |I1 ∩ I2| is at least αn.Source: §B.1 · p. 9

B.2 Average of rd

This appendix section establishes an average-radius claim and develops a covariance argument for dependent radii. It approximates the radii with pair-specific independent versions, bounds covariance differences, and applies Chebyshev's inequality.

B.2 Average of rd

The section states an average-of-rd result and says the result follows after establishing an intermediate claim.Source: §B.2 · p. 9

B.3.1 Strategy

The strategy addresses the dependence between ri and rj by defining pair-specific approximations that are independent of the other point's sample variable.It then bounds the covariance of the approximations and the difference from the original covariance before applying Chebyshev's inequality.Source: §B.3.1 · p. 10

B.3.3 Estimate of Cov( 1

The covariance estimate compares probabilities for individual balls with the probability for their union, using bounds assembled across three cases.The excerpt identifies the common upper bounds and differing lower bounds but does not provide the full expressions.Source: §B.3.3 · pp. 14–16

B.3.4 Estimate for the difference between Cov( 1

Conditioning on Xi makes ∥Xi − Xj∥ and the approximation r̃i independent, supporting the estimate of the difference between covariance terms.Source: §B.3.4 · p. 17

B.3.10 Final Step: Chebyshev’s inequality

The proof applies Chebyshev's inequality in its final step.Source: §B.3.10 · p. 18

C.1 Gagliardo-Nirenberg interpolation inequalities

The appendix states Gagliardo–Nirenberg inequalities for general spaces and domains, then presents a Morrey inequality. It identifies two odd-dimensional cases needed for the paper’s purposes.

C.1 Gagliardo-Nirenberg interpolation inequalities

The general Gagliardo–Nirenberg statement gives an inequality with a parameter-dependent constant and specifies exceptional cases, including restrictions when q = ∞ or when m−k−N/p is a nonnegative integer.Source: §C.1 · p. 19
The domain version assumes a uniformly Lipschitz boundary; when p < q, the domain is additionally required to be bounded.Source: §C.1 · p. 19
For the paper’s applications, the inequalities are needed on R^d and on the unit ball supp P, with d odd and specified derivative orders.The listed cases use r = q = 2 on R^d and r = q = p = 2 on the unit ball.Source: §C.1 · p. 20

C.2 Morrey’s inequality

The appendix presents a Morrey inequality and combines it with the Gagliardo–Nirenberg inequality when u also belongs to Lq(R^d).Source: §C.2 · p. 21

C.3 Local H¨older Continuity around Samples

This section introduces a measure of local Hölder continuity around samples and develops inequalities used to establish a proposition for subsets of samples.

C.3 Local H¨older Continuity around Samples

The section introduces a measure of local Hölder continuity around a sample set S and an index subset I.Source: §C.3 · p. 22
The proof proceeds through inequalities using Morrey’s inequality, the Leibniz rule, and the domain Gagliardo–Nirenberg inequality.Source: §C.3 · pp. 23–24
Proposition C.7 states a result for any subset I and any f in L2(Ω).Source: §C.3 · p. 25

C.4 Upper Bound of ⟨bfc⟩Hc

The section constructs an interpolating function for each positive c and uses the minimum-RKHS-norm property of bfc to compare it with that function.

C.4 Upper Bound of ⟨bfc⟩Hc

For any c > 0, the section asserts the existence of a function g interpolating S.Source: §C.4 · p. 26
Because bfc has the smallest RKHS norm among interpolating functions, its norm is compared with that of g.Source: §C.4 · p. 26
The argument then states a result for odd d and gives a further conclusion with the same probability.Source: §C.4 · p. 27