Source-linked AI summary
Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
Mikhail Belkin, Daniel Hsu, Partha Mitra
TL;DR
The paper addresses the limited theory explaining why interpolating models can generalize despite label noise. It analyzes local interpolating schemes and proves consistency or near-consistency, including statistically optimal rates for weighted nearest-neighbor regression.
Problem
Existing generalization theory provides no useful risk bounds for zero-training-error functions under non-negligible label noise, despite strong empirical performance of interpolating models.
Method
The paper analyzes simplicial interpolation and singularly weighted interpolated nearest-neighbor schemes for classification and regression.
Results
The analyzed schemes achieve consistency or near-consistency, with wiNN regression attaining statistically optimal rates under a standard minimax setting.
Takeaways & Limitations
These results provide initial theoretical support for interpolated predictors and connect simplicial interpolation to minimum-norm interpolation in a Laplace-kernel space.
Takeaways & Limitations
Current theory still does not apply to interpolated kernel machines with label noise, and capacity-based generalization bounds remain open.
Abstract
from arXiv · showhide
Many modern machine learning models are trained to achieve zero or near-zero training error in order to obtain near-optimal (but non-zero) test error. This phenomenon of strong generalization performance for "overfitted" / interpolated classifiers appears to be ubiquitous in high-dimensional data, having been observed in deep networks, kernel machines, boosting and random forests. Their performance is consistently robust even when the data contain large amounts of label noise. Very little theory is available to explain these observations. The vast majority of theoretical analyses of generalization allows for interpolation only when there is little or no label noise. This paper takes a step toward a theoretical foundation for interpolated classifiers by analyzing local interpolating schemes, including geometric simplicial interpolation algorithm and singularly weighted $k$-nearest neighbor schemes. Consistency or near-consistency is proved for these schemes in classification and regression problems. Moreover, the nearest neighbor schemes exhibit optimal rates under some standard statistical assumptions. Finally, this paper suggests a way to explain the phenomenon of adversarial examples, which are seemingly ubiquitous in modern machine learning, and also discusses some connections to kernel machines and random forests in the interpolated regime.
1 Introduction
Modern models often interpolate noisy training data yet generalize well, while standard theory struggles to explain this regime. The paper studies local interpolating rules and establishes nontrivial risk, consistency, rate, and adversarial-example results.
- Motivation: Zero-training-error models can generalize well despite substantial label noise, challenging conventional views that interpolation has poor statistical properties.This behavior has been observed for deep networks, boosting, random forests, and kernel machines.
- Limits of existing theory: Capacity-based, stability-based, regularization, and smoothing analyses generally fail to provide useful bounds for noisy interpolation.Capacity bounds become uninformative with zero empirical risk and noisy labels; regularization bounds diverge at fixed-sample interpolation, while local methods usually require smoothing.
- Approach: The paper analyzes local interpolating schemes, including simplicial interpolation and singularly weighted nearest-neighbor rules, using locality rather than generalization-gap bounds.Their predictions depend primarily or entirely on nearby training values.
- Results: Simplicial interpolation approaches Bayes risk as dimension increases and can have exponentially small excess risk under an additional margin condition.The paper characterizes this as a blessing of dimensionality, while noting that the usual curse of dimensionality remains.
- Results: The weighted interpolated nearest-neighbor scheme is consistent in any dimension, and its regression rate is statistically optimal under a standard minimax setting.The analysis also gives the first known non-asymptotic convergence rates to Bayes risk for an interpolated predictor.
- Implications: The paper argues that interpolation with any label noise inevitably produces adversarial examples that have small measure but are asymptotically dense.This matches the observation that targeted optimization finds them more readily than random sampling.
2 Preliminaries
The paper studies predictors that exactly interpolate training data while targeting performance on unseen data. It formalizes the statistical setting, risk objectives, and assumptions used to analyze such methods.
- Statistical model: Interpolating predictors satisfy f̂(x_i) = y_i for every training example while being evaluated on independently sampled test data.The training and test examples are modeled as iid draws from the same distribution.
- Nearest neighbor rule: The nearest neighbor rule predicts a new point using the label of its closest training example and asymptotically has risk bounded by twice the Bayes risk.This rule motivates analyzing interpolation through local information in feature space.
- Risk objectives: The conditional mean η(x) = E(Y | X = x) is the squared-loss optimum, while the Bayes classifier f* minimizes zero-one loss.Classification analysis compares predictions with f*, whereas regression analysis compares estimates with η.
- Assumptions: The analysis uses smoothness, margin, geometric regularity, and distributional assumptions to obtain risk bounds.Uniform marginal distributions are adopted mainly for simplicity and can be replaced by measures with density bounded below, with changed constants.
3 Interpolating scheme based on multivariate triangulation
This section develops simplicial interpolation, which linearly interpolates labels over a triangulation of the training points’ convex hull. Its risk can approach optimal performance in high dimensions under stated regularity and smoothness conditions.
- Definition and basic properties: Simplicial interpolation partitions the convex hull of the training features into non-degenerate simplices and uses the vertices of the containing simplex.The prediction rule only needs to locate the containing simplex, not construct the full triangulation.
- Classification behavior: 1/d versus 1/2^d: with one noisy positive label in a d-dimensional simplex, nearest neighbor predicts 1 on a larger fraction than simplicial interpolation.This geometric difference helps explain why simplicial interpolation can be nearly optimal in high dimensions.
- Definition and basic properties: The interpolant is piecewise linear and agrees across adjacent simplices sharing a face.This makes the definition unambiguous where a point belongs to multiple adjacent simplices.
- Classification risk: The plug-in classifier f̂(x) = 1{η̂(x) > 1/2} can have risk very close to Bayes risk in high dimensions under margin and boundary conditions.The paper describes this as a blessing of dimensionality, contrasting it with nearest neighbor’s dimension-independent asymptotic bound.
4 Interpolating nearest neighbor schemes
The section introduces weighted nearest neighbor schemes that interpolate training data through singular weights. Under regularity, smoothness, and margin assumptions, these schemes are consistent and can achieve optimal convergence rates.
- Scheme: Weighted nearest neighbor schemes retain interpolation like 1-nearest neighbor while adopting convergence and consistency properties associated with k-nearest neighbor methods.The classical unweighted k-nearest neighbor rule generally interpolates only when k = 1.
- Analysis: Conditional independence of the first k nearest neighbors given the (k + 1)st neighbor enables concentration arguments for weighted local averages.With smoothness of η, the conditional expectation of the weighted average is related to η(x).
- Scheme: Singular weights force the estimator to approach each observed label as x approaches its corresponding training feature.The weights are radial, decreasing with distance, and diverge at zero.
- Mean squared error: n^-2α/(2α+d) is the minimax-optimal regression convergence rate obtained by choosing k = n^(2α/(2α+d)).The rate follows when the expected distance to the (k + 1)st nearest neighbor scales as O((k/n)^(2α/d)).
- Classification risk: The classification analysis identifies effective class interiors where local interpolated labels are likely to yield accurate predictions.The corresponding theorem analyzes the plug-in classifier for fixed γ and p > k/n.
- Classification risk: n^-αβ/(α(2+β)+d) is the classification convergence rate under the stated smoothness and margin conditions.The consistency choice is k = n^((2+β)α/((2+β)α+d)).
5 Ubiquity of adversarial examples in interpolated learning
The paper argues that adversarial examples are an inevitable feature of interpolating predictors under any nonzero label noise, even when those predictors are consistent. Their probability mass can vanish while the examples become asymptotically dense.
- Small feature perturbations can induce neural-network misclassification, motivating the paper’s analysis of adversarial examples in interpolated learning.
- Any interpolating inferential procedure has abundant adversarial examples when the labels contain any amount of noise.
- For consistent or nearly consistent schemes, incorrectly labeled training examples create small basins in which the interpolating predictor disagrees with the Bayes classifier.
- The adversarial basins have negligible total probability mass with enough data, so randomly selected points are unlikely to be misclassified.
- Despite vanishing measure, the union of adversarial basins becomes asymptotically dense, placing misclassified examples in every open set.
- The formal result assumes a compact domain with nonzero density and label noise everywhere, and states that every point lies within distance 2ϵ of the adversarial set with probability at least δ for sufficiently large n.
6 Discussion and connections
The discussion connects the paper’s local interpolating schemes to nearest-neighbor methods, kernel machines, and random forests. These connections suggest shared interpolation structures while also marking limits of existing theory.
- Nearest-neighbor schemes are direct methods, whereas simplicial interpolation uses local matrix inversion and exemplifies an inverse method.
- In one dimension, simplicial interpolation is the minimum-norm interpolant in a Laplace-kernel reproducing kernel Hilbert space as κ → 0.
- The one-dimensional Laplace-kernel interpolant reduces to linear interpolation between adjacent data points, matching the simplicial method.
- A random-forest construction similar to PERT also yields linear interpolation in one dimension when infinitely many trees are sampled.
- Current kernel-machine theory does not cover interpolation with label noise, motivating simplicial interpolation as a possible source of theoretical insight.
A.2 Proof of Theorem 3.2
The proof of Theorem 3.2 conditions on the feature sample and decomposes the interpolation error using local simplex geometry, barycentric weights, noise, and regression-function smoothness.
- The proof conditions on X1, . . . , Xn before analyzing the estimator.
- Outside the convex-hull region bC, the estimator is fixed at 1/2, giving squared error at most 1/4.
- Inside a simplex, the local interpolation points have barycentric coordinates distributed as Dirichlet(1, . . . , 1).
- The proof separates label noise ϵ(i), regression-function differences b(i), and conditional variance v(x) while applying smoothness assumptions.
- The argument invokes Proposition 3.1 and Jensen’s inequality, then takes expectations over the feature sample and query point.
A.3 Proof of Corollary 3.3
The proof of Corollary 3.3 controls simplicial interpolation through convex-hull coverage and simplex diameters. Uniform-polytope geometry and Delaunay triangulation provide the needed asymptotic bounds.
- The probability mass outside the sample convex hull bC is analyzed using stochastic-geometry results for a uniformly supported convex polytope.
- For a uniform measure on a simple polytope with r vertices in R^d, Theorem A.1 supplies an expectation bound for the mass outside bC.
- The expected mass outside bC converges to zero as n → ∞.
- The maximum simplex diameter is expected to vanish for natural triangulation schemes, including Delaunay triangulation.
- An ϵ-dense sample makes every Delaunay simplex have diameter at most 2ϵ.
A.4 Proof of Theorem 3.5
The proof combines a tail bound for interpolated labels with geometric control of Delaunay simplices to obtain exponentially small classification error away from the class boundary.
- Geometric reduction: The maximum Delaunay-simplex diameter tends to zero almost surely as n →∞.This localizes simplices intersecting both classes near the class boundary.
- Geometric reduction: Simplices not fully contained in a class interior lie in a shrinking neighborhood of the class boundary.The proof therefore reduces the bound to simplices contained entirely within one class interior.
- Simplex analysis: Within an interior simplex, the test point has Dirichlet(1, . . . , 1) barycentric coordinates conditional on the training inputs.The vertex labels are analyzed through the resulting random interpolation weights.
- Conclusion: P( ˆf (X) , f ∗(X)) ≤ c1P( f ∗(X) , Y) · e−c2(d+1).The constants are absolute, and the exponential dependence is on the simplex dimension plus one.
A.6 Proof of Corollary 4.6
The proof of Corollary 4.6 bounds the relevant boundary mass and local variability terms, then combines those bounds with Theorem 4.5.
- Radius control: The proof first bounds supx∈supp(µ) rp(x) using Rp : (Z0p/c0)1/d and the support-mass assumption.The argument uses Rp ≤r0 and a lower bound on the measure of intersected balls.
- Local class separation: Smoothness yields ¯ηx0,r ≥1/2 + γ or ¯ηx0,r ≤1/2 −γ for sufficiently small r.The relevant inequality depends on whether η(x0) is above or below the class threshold.
- Local class separation: Since rp(x0) ≤Rp, the local averaged regression function preserves the corresponding class-side separation.This transfers the small-radius bounds to the data-dependent neighborhood radius.
- Margin control: The claim follows by using the (B, β)-margin condition.The margin condition supplies the remaining control needed for the corollary.
- Conclusion: Corollary 4.6 follows by combining the bounds on µ(∂p,γ) and κp from Lemma A.4 with Theorem 4.5.The corollary is assembled from the boundary-mass and variability estimates.
A.7 Proof of Theorem 4.3
The proof analyzes nearest-neighbor regression through a conditional sampling process, controls the neighbor radius and weighted noise, and combines the resulting bounds.
- Sampling construction: The nearest-neighbor sample is generated by first selecting Xk+1, then k points inside its radius, followed by points outside that radius.Labels are then sampled independently from their conditional distributions with means η(Xi).
- Estimator decomposition: The k nearest neighbors of x0 are X1, . . . , Xk, so the regression estimate uses their labels and interpolation weights.The proof decomposes each label into conditional mean and noise components.
- Conclusion: Combining inequalities (6) and (7) completes the proof.The final step invokes Claim A.5 to control the remaining conditional term.
- Error control: Under the theorem assumptions, the weighted-neighbor error is bounded by e−k/4 + d c0(d −2δ)k2.The bound is obtained through Claim A.5 and the preceding radius analysis.
- Radius control: P(E1) ≥1 −e−k/4 under the radius and sample-size condition.This follows from a multiplicative Chernoff bound after establishing µ(B(x0, Rp)) ≥p.
B.2 Connections to semi-supervised learning
The paper connects minimum-norm kernel interpolation and graph-based semi-supervised learning to local interpolation, showing how their interpolating solutions relate to linear interpolation, label propagation, and Bayes classification.
- Graph formulation: Graph interpolation imposes Laplacian equations on unlabeled vertices while matching the labeled values exactly.The resulting finite-dimensional RKHS formulation uses the graph Laplacian and prescribed labels.
- Scope: The paper does not theoretically analyze these kernel and semi-supervised connections.The discussion is explicitly informal and may require new theoretical insights.
- Label propagation: When κ →0, the graph-based scheme becomes label propagation.Classification is obtained by thresholding the interpolating regression function.
- Local averaging: At an unlabeled vertex, the inferred value is proportional to the weighted average of neighboring labels.This property resembles the interpolated nearest-neighbor algorithms analyzed in the paper.
- Fully connected graph: For the fully connected graph, the interpolating solution is constant across unlabeled points and the classifier output is sign(n+ −n−).When p > 1/2 and k is large, the classifier recovers the Bayes classifier with high probability and has exponentially small excess risk.