Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate

Introduction

The central problem of supervised inference is to predict labels of unseen data points from a set of labeled training data. The literature on this subject is vast, ranging from classical parametric and non-parametric statistics to more recent machine learning methods, such as kernel machines , boosting , random forests , and deep neural networks . There is a wealth of theoretical analyses for these methods based on a spectrum of techniques including non-parametric estimation , capacity control such as VC-dimension or Rademacher complexity , and regularization theory . In nearly all of these results, theoretical analysis of generalization requires “what you see is what you get” setup, where prediction performance on unseen test data is close to the performance on the training data, achieved by carefully managing the bias-variance trade-off. Furthermore, it is widely accepted in the literature that interpolation has poor statistical properties and should be dismissed out-of-hand. For example, in their book on non-parametric statistics, Györfi et al. [25, page 21] say that a certain procedure “may lead to a function which interpolates the data and hence is not a reasonable estimate”.

Yet, this is not how many modern machine learning methods are used in practice. For instance, the best practice for training deep neural networks is to first perfectly fit the training data . The resulting (zero training loss) neural networks after this first step can already have good performance on test data . Similar observations about models that perfectly fit training data have been made for other machine learning methods, including boosting , random forests , and kernel machines . These methods return good classifiers even when the training data have high levels of label noise .

An important effort to show that fitting the training data exactly can under certain conditions be theoretically justified is the margins theory for boosting and other margin-based methods . However, this theory lacks explanatory power for the performance of classifiers that perfectly fit noisy labels, when it is known that no margin is present in the data . Moreover, margins theory does not apply to regression and to functions (for regression or classification) that interpolate the data in the classical sense .

In this paper, we identify the challenge of providing a rigorous understanding of generalization in machine learning models that interpolate training data. We take first steps towards such a theory by proposing and analyzing interpolating methods for classification and regression with non-trivial risk and consistency guarantees.

Many existing forms of generalization analyses face significant analytical and conceptual barriers to being able to explain the success of interpolating methods.

Existing capacity-based bounds (e.g., VC dimension, fat-shattering dimension, Rademacher complexity) for empirical risk minimization do not give useful risk bounds for functions with zero empirical risk whenever there is non-negligible label noise. This is because function classes rich enough to perfectly fit noisy training labels generally have capacity measures that grow quickly with the number of training data, at least with the existing notions of capacity . Note that since the training risk is zero for the functions of interest, the generalization bound must bound their true risk, as it equals the generalization gap (difference between the true and empirical risk). Whether such capacity-based generalization bounds exist is open for debate.

Generalization analyses based on algorithmic stability control the difference between the true risk and the training risk, assuming bounded sensitivity of an algorithm’s output to small changes in training data. Like standard uses of capacity-based bounds, these approaches are not well-suited to settings when training risk is identically zero but true risk is non-zero.

Many analyses are available for regularization approaches to statistical inverse problems, ranging from Tikhonov regularization to early stopping . To obtain a risk bound, these analyses require the regularization parameter $\lambda$ (or some analogous quantity) to approach zero as the number of data $n$ tends to infinity. However, to get (the minimum norm) interpolation, we need $\lambda\to 0$ while $n$ is fixed, causing the bounds to diverge.

There is an extensive literature on local prediction rules in non-parametric statistics . Nearly all of these analyses require local smoothing (to explicitly balance bias and variance) and thus do not apply to interpolation. (Two exceptions are discussed below.)

Recently, Wyner et al. proposed a thought-provoking explanation for the performance of AdaBoost and random forests in the interpolation regime, based on ideas related to “self-averaging” and localization. However, a theoretical basis for these ideas is not developed in their work.

The analyses of the nearest neighbor rule and Hilbert kernel regression estimate are not based on bounding generalization gap, the difference between the true risk and the empirical risk. Rather, the true risk is analyzed directly by exploiting locality properties of the prediction rules. In particular, the prediction at a point depends primarily or entirely on the values of the function at nearby points. This inductive bias favors functions where local information in a neighborhood can be aggregated to give an accurate representation of the underlying regression function.

What we do.

Our approach to understanding the generalization properties of interpolation methods is to understand and isolate the key properties of local classification, particularly the nearest neighbor rule. First, we construct and analyze an interpolating function based on multivariate triangulation and linear interpolation on each simplex (Section 3), which results in a geometrically intuitive and theoretically tractable prediction rule. Like nearest neighbor, this method is not statistically consistent, but, unlike nearest neighbor, its asymptotic risk approaches the Bayes risk as the dimension becomes large, even when the Bayes risk is far from zero—a kind of “blessing of dimensionality”This does not remove the usual curse of dimensionality, which is similar to the standard analyses of $k$-NN and other non-parametric methods.. Moreover, under an additional margin condition the difference between the Bayes risk and our classifier is exponentially small in the dimension.

A similar finding holds for regression, as the method is nearly consistent when the dimension is high.

Next, we propose a weighted & interpolated nearest neighbor (wiNN) scheme based on singular weight functions (Section 4). The resulting function is somewhat less natural than that obtained by simplicial interpolation, but like the Hilbert kernel regression estimate, the prediction rule is statistically consistent in any dimension. Interestingly, conditions on the weights to ensure consistency become less restrictive in higher dimension—another “blessing of dimensionality”. Our analysis provides the first known non-asymptotic rates of convergence to the Bayes risk for an interpolated predictor, as well as tighter bounds under margin conditions for classification. In fact, the rate achieved by wiNN regression is statistically optimal under a standard minimax settingAn earlier version of this article paper contained a bound with a worse rate of convergence based on a loose analysis. The subsequent work found that a different Nadaraya-Watson kernel regression estimate (with a singular kernel) could achieve the optimal convergence rate; this inspired us to seek a tighter analysis of our wiNN scheme..

Our results also suggest an explanation for the phenomenon of adversarial examples , which are seemingly ubiquitous in modern machine learning. In Section 5, we argue that interpolation inevitably results in adversarial examples in the presence of any amount of label noise. When these schemes are consistent or nearly consistent, the set of adversarial examples (where the interpolating classifier disagrees with the Bayes optimal) has small measure but is asymptotically dense. Our analysis is consistent with the empirical observations that such examples are difficult to find by random sampling , but are easily discovered using targeted optimization procedures, such as Projected Gradient Descent .

Finally, we discuss the difference between direct and inverse interpolation schemes; and make some connections to kernel machines, and random forests in (Section 6).

All proofs are given in Appendix A. We informally discuss some connections to graph-based semi-supervised learning in Appendix B.

Preliminaries

In this paper, we analyze two interpolating schemes, one based on triangulating and constructing the simplicial interpolant for the data, and another, based on weighted nearest neighbors with singular weight function.

2 Smoothness, margin, and regularity conditions

Below we list some standard conditions needed for further development.

For all $x,x^{\prime}$ in the support of $\mu$,

There exist $c_{0}>0$ and $r_{0}>0$ such that

The regularity condition from Audibert and Tsybakov is not very restrictive. For example, if $\operatorname{supp}(\mu)=\operatorname{B}(0,1)$, then $c_{0}\approx 1/2$ and $r_{0}\geq 1$.

In what follows, we mostly assume uniform marginal distribution $\mu$ over a certain domain. This is done for the sake of simplicity and is not an essential condition. For example, in every statement the uniform measure can be substituted (with a potential change of constants) by an arbitrary measure with density bounded from below.

Interpolating scheme based on multivariate triangulation

In this section, we describe and analyze an interpolating scheme based on multivariate triangulation. Our main interest in this scheme is in its natural geometric properties and the risk bounds for regression and classification which compare favorably to those of the original nearest neighbor rule (despite the fact that neither is statistically consistent in general).

The predictions of the plug-in classifier based on simplicial interpolation are qualitatively very different from those of the nearest neighbor rule. This is true even when restricting attention to a single simplex. Suppose, for example, that $\eta(x)<1/2$ for all $x\in\operatorname{conv}(x_{1},\dotsc,x_{d+1})$, so the Bayes classifier predicts for all $x$ in the simplex. On the other hand, due to label noise, we may have some $y_{i}=1$. Suppose in fact that only $y_{d+1}=1$, while $y_{i}=0$ for all $i=1,\dotsc,d$. In this scenario (depicted in Figure 1 for $d=2$), the nearest neighbor rule (erroneously) predicts $1$ on a larger fraction of the simplex than the plug-in classifier based on $\hat{\eta}$. The difference can be striking in high dimensions: $1/d$ for nearest neighbor versus $1/2^{d}$ for simplicial interpolation in $d$-dimensional version of Figure 1. This provides an intuition why, in contrast to the nearest neighbor rule, simplicial interpolation can yield to classifiers that are nearly optimal in high dimensions.

One consequence of Proposition 3.1 for $\hat{\eta}$ is that if $x$ is contained in two adjacent simplices (that share a ${<}d$-dimensional face), then it does not matter which simplex is used to define $U_{T}(x)$; the value of $\hat{\eta}(x)$ is the same in any case. Geometrically, we see that the restriction of the interpolating linear function to a face of the simplex coincides with the interpolating linear function constructed on a sub-simplex formed by that face. Therefore, we deduce that $\hat{\eta}$ is a piecewise linear and continuous interpolation of the data $(x_{1},y_{1}),\dotsc,(x_{n},y_{n})$ on $\operatorname{conv}(x_{1},\dotsc,x_{n})$.

We note that our prediction rule requires only locating the vertices of the simplex containing a given point, rather than the considerably harder problem of constructing a full triangulation. In fact, locating the containing simplex in a Delaunay triangulation reduces to solving polynomial-size linear programs ; in contrast, computing the full Delaunay triangulation has complexity exponential in the (intrinsic) dimension .

2 Mean squared error

In general, each $Y_{i}$ may deviate from its conditional mean $\eta(X_{i})$ by a non-negligible amount, and hence any function that interpolates the training data is “fitting noise”. Nevertheless, in high dimension, the mean squared error of such a function will be quite close to that of the (optimal) conditional mean function.

3 Classification risk

We now analyze the statistical risk of the plug-in classifier based on $\hat{\eta}$, given by

We first state an easy consequence of Corollary 3.3 using known properties of plug-in classifiers.

Under the same conditions as Corollary 3.3,

When the conditional mean function satisfies a margin condition, the $1/\sqrt{d}$ in Corollary 3.4 can be replaced with a quantity that is exponentially small in $d$, as we show next.

Both Corollary 3.4 and Theorem 3.5 show that the risk of $\hat{f}$ can be very close to the Bayes risk in high dimensions, thus exhibiting a certain “blessing of dimensionality". This stands in contrast to the nearest neighbor rule, whose asymptotic risk does not diminish with the dimension and is bounded by twice the Bayes risk, $2\mathcal{R}_{0/1}(f^{*})$.

Interpolating nearest neighbor schemes

In this section, we describe a weighted nearest neighbor scheme that, like the $1$-nearest neighbor rule, interpolates the training data, but is similar to the classical (unweighted) $k$-nearest neighbor rule in terms of other properties, including convergence and consistency. (The classical $k$-nearest neighbor rule is not generally an interpolating method except when $k=1$.)

In what follows, we investigate the properties of interpolating schemes of this type.

We will need two key observations for the analyses of these algorithms.

The second key point is that $\hat{\eta}(x)$ is an interpolating scheme, provided that $w(x,z)$ has a singularity when $z=x$. Indeed, it is easily seen that if $\lim_{z\to x}w(x,z)=\infty$, then $\lim_{x\to x_{i}}\hat{\eta}(x)=y_{i}$. Extending $\hat{\eta}$ continuously to the data points yields a weighted & interpolated nearest neighbor (wiNN) scheme.

Concretely, we will consider $\phi$ that diverge near $t=0$ as $t\mapsto-\log(t)$ or $t\mapsto t^{-\delta}$, $\delta>0$.

The denominator $\|x-x_{(k+1)}\|$ in the argument of $\phi$ is not strictly necessary, but it allows for convenient normalization in view of the conditional independence of $k$-nearest neighbors given $x_{(k+1)}$. Note that the weights depend on the sample and are thus data-adaptive.

Although $w(x,x_{(i)})$ are unbounded for singular weight functions, concentration only requires certain bounded moments. Geometrically, the volume of the region around the singularity needs to be small enough. For radial weight functions that we consider, this condition is more easily satisfied in high dimension. Indeed, the volume around the singularity becomes exponentially small in high dimension.

Our wiNN schemes are related to Nadaraya-Watson kernel regression . The use of singular kernels in the context of interpolation was originally proposed by Shepard ; they do not appear to be commonly used in machine learning and statistics, perhaps due to a view that interpolating schemes are unlikely to generalize or even be consistent; the non-adaptive Hilbert kernel regression estimate (essentially, $k=n$ and $\delta=d$) is the only exception we know of.

2 Mean squared error

Let $\hat{\eta}$ be a wiNN scheme with singular weight function $\phi$. Assume the following conditions:

$\eta$ satisfies the $(A,\alpha)$-smoothness for some $A{>}0$ and $\alpha{>}0$.

$\phi(t)=t^{-\delta}$ for some $0<\delta<d/2$.

Let $Z_{0}\mathrel{\mathop{\mathchar 58\relax}}=\lambda(\operatorname{supp}(\mu))/\lambda(\operatorname{B}(0,1))$, and assume $n>2Z_{0}k/(c_{0}r_{0}^{d})$. For any $x_{0}\in\operatorname{supp}(\mu)$, let $r_{k+1,n}(x_{0})$ be the distance from $x_{0}$ to its $(k+1)$st nearest neighbor among $X_{1},\dotsc,X_{n}$. Then

The bound in Theorem 4.3 is stated in terms of the expected distance to the $(k+1)$st nearest neighbor raised to the $2\alpha$ power; this is typically bounded by $O((k/n)^{2\alpha/d})$. Choosing $k=n^{2\alpha/(2\alpha+d)}$ leads to a convergence rate of $n^{-2\alpha/(2\alpha+d)}$, which is minimax optimal.

3 Classification risk

We now analyze the statistical risk of the plug-in classifier $\hat{f}(x)=\mathds{1}_{\{\hat{\eta}(x)>1/2\}}$ based on $\hat{\eta}$.

As in Section 3.3, we obtain the following easy consequence of Theorem 4.3 using known properties of plug-in classifiers.

Under the same conditions as Theorem 4.3,

Choosing $k=n^{2\alpha/(2\alpha+d)}$ leads to a convergence rate of $n^{-\alpha/(2\alpha+d)}$.

We now give a more direct analysis, largely based on that of Chaudhuri and Dasgupta for the standard $k$-nearest neighbor rule, that leads to improved rates under favorable conditions.

For $0<\gamma<1/2$, define the effective interiors of the two classes by

Points away from the boundary, i.e., in $\mathcal{X}_{p,\gamma}^{-}$ or $\mathcal{X}_{p,\gamma}^{+}$ for $p\approx k/n$, are likely to have $k$ nearest neighbors in $\mathcal{X}_{p,\gamma}^{-}$ or $\mathcal{X}_{p,\gamma}^{+}$, respectively, so that interpolating their labels yields accurate predictions.

Let $\hat{\eta}$ be a wiNN scheme with singular weight function $\phi$, and let $\hat{f}$ be the corresponding plug-in classifier. Fix any $0<\gamma<1/2$ and $p>k/n$. Then

While Theorem 4.5 is quite general, the values of quantities involved can be non-trivial to express in terms of $n$. The following corollary leads to explicit rates under certain conditions.

$\eta$ satisfies the $(A,\alpha)$-smoothness and $(B,\beta)$-margin conditions for some $A{>}0$, $\alpha{>}0$, $B{>}0$, $\beta{\geq 0}$.

$\phi(t)=t^{-\delta}$ for some $0<\delta<d/2$.

Let $Z_{0}\mathrel{\mathop{\mathchar 58\relax}}=\lambda(\operatorname{supp}(\mu))/\lambda(\operatorname{B}(0,1))$, and assume

For consistency, we set $k\mathrel{\mathop{\mathchar 58\relax}}=n^{(2+\beta)\alpha/((2+\beta)\alpha+d)}$, and in the bound, we plug-in $p\mathrel{\mathop{\mathchar 58\relax}}=2k/n$ and $\gamma\mathrel{\mathop{\mathchar 58\relax}}=A(Z_{0}p/c_{0})^{\alpha/d}$. This leads to a convergence rate of $n^{-\alpha\beta/(\alpha(2+\beta)+d)}$.

The factor $1/k$ in the final term in Corollary 4.6 results from an application of Chebyshev inequality. Under additional moment conditions, which are satisfied for certain functions $\phi$ (e.g., $\phi(t)=-\log(t)$) with better-behaved singularity at zero than $t^{-\delta}$, it can be replaced by $e^{-\Omega(\gamma^{2}k)}$. Additionally, while the condition $\phi(t)=t^{-\delta}$ is convenient for analysis, it is sufficient to assume that $\phi$ approaches infinity no faster than $t^{-\delta}$.

Ubiquity of adversarial examples in interpolated learning

The recently observed phenomenon of adversarial examples in modern machine learning has drawn a significant degree of interest. It turns out that by introducing a small perturbation to the features of a correctly classified example (e.g., by changing an image in a visually imperceptible way or even by modifying a single pixel ) it is nearly always possible to induce neural networks to mis-classify a given input in a seemingly arbitrary and often bewildering way.

We will now discuss how our analyses, showing that Bayes optimality is compatible with interpolating the data, provide a possible mechanism for these adversarial examples to arise. Indeed, such examples are seemingly unavoidable in interpolated learning and, thus, in much of the modern practice. As we show below, any interpolating inferential procedure must have abundant adversarial examples in the presence of any amount of label noise. In particular, in consistent on nearly consistent schemes, like those considered in this paper, while the predictor agrees with the Bayes classifier on the bulk of the probability distribution, every “incorrectly labeled” training example (i.e., an example whose label is different from the output of the Bayes optimal classifier) has a small “basin of attraction” with every point in the basin misclassified by the predictor. The total probability mass of these “adversarial” basins is negligible given enough training data, so that a probability of misclassifying a randomly chosen point is low. However, assuming non-zero label noise, the union of these adversarial basins asymptotically is a dense subset of the support for the underlying probability measure and hence there are misclassified examples in every open set. This is indeed consistent with the extensive empirical evidence for neural networks. While their output is observed to be robust to random feature noise , adversarial examples turn out to be quite difficult to avoid and can be easily found by targeted optimization methods such as PCG . We conjecture that it may be a general property or perhaps a weakness of interpolating methods, as some non-interpolating local classification rules can be robust against certain forms of adversarial examples .

Let ${\cal A}_{n}=\{x\in\Omega\mathrel{\mathop{\mathchar 58\relax}}\hat{f}_{n}(x)\neq f^{*}(x)\}$ be the set of points at which $\hat{f}_{n}$ disagrees with the Bayes optimal classifier $f^{*}$; in other words, ${\cal A}_{n}$ is the set of “adversarial examples” for $\hat{f}_{n}$. Consistency of $\hat{f}$ implies that, with probability one, $\lim_{n\to\infty}\mu({\cal A}_{n})=0$ or, equivalently, $\lim_{n\to\infty}\|\hat{f}_{n}-f^{*}\|_{L^{2}_{\mu}}=0$. On the other hand, the following result shows that the sets ${\cal A}_{n}$ are asymptotically dense in $\Omega$, so that there is an adversarial example arbitrarily close to any $x$.

Let $(X_{1},Y_{1}),\dotsc,(X_{n},Y_{n})$ be the training data used to construct $\hat{f}_{n}$. Fix a finite $\epsilon$-cover of $\Omega$ with respect to the Euclidean distance. Since $\hat{f}_{n}$ is interpolating and $\eta$ is never zero nor one, for every $i$, there is a non-zero probability (over the outcome of the label $Y_{i}$) that $\hat{f}_{n}(X_{i})=Y_{i}\neq f^{*}(X_{i})$; in this case, the training point $X_{i}$ is an adversarial example for $\hat{f}_{n}$. By choosing $n=n(\mu,\epsilon,\delta)$ large enough, we can ensure that with probability at least $\delta$ over the random draw of the training data, every element of the cover is within distance $\epsilon$ of at least one adversarial example, upon which every point in $\Omega$ is within distance $2\epsilon$ (by triangle inequality) of the same. ∎

A similar argument for regression shows that while an interpolating $\hat{\eta}$ may converge to $\eta$ in $L^{2}_{\mu}$, it is generally impossible for it to converge in $L_{\infty}$ unless there is no label noise. An even more striking result is that for the Hilbert scheme of Devroye et al., the regression estimator almost surely does not converge at any fixed point, even for the simple case of a constant function corrupted by label noise . This means that with increasing sample size $n$, at any given point $x$ misclassification will occur an infinite number of times with probability one. We expect similar behavior to hold for the interpolation schemes presented in this paper.

Discussion and connections

In this paper, we considered two types of algorithms, one based on simplicial interpolation and another based on interpolation by weighted nearest neighbor schemes. It may be useful to think of nearest neighbor schemes as direct methods, not requiring optimization, while our simplicial scheme is a simple example of an inverse method, using (local) matrix inversion to fit the data. Most popular machine learning methods, such as kernel machines, neural networks, and boosting, are inverse schemes. While nearest neighbor and Nadaraya-Watson methods often show adequate performance, they are rarely best-performing algorithms in practice. We conjecture that the simplicial interpolation scheme may provide insights into the properties of interpolating kernel machines and neural networks.

To provide some evidence for this line of thought, we show that in one dimension simplicial interpolation is indeed a special case of interpolating kernel machine. We will briefly sketch the argument without going into the details. Consider the space $\mathcal{H}$ of real-valued functions $f$ with the norm $\|f\|_{\mathcal{H}}^{2}=\int(\operatorname{d\!}f/\operatorname{d\!}x)^{2}+\kappa^{2}f^{2}\operatorname{d\!}x$. This space is a reproducing kernel Hilbert Space corresponding to the Laplace kernel $e^{-\kappa|x-z|}$. It can be seen that as $\kappa\to 0$ the minimum norm interpolant $f^{*}=\operatorname*{\arg\min}_{f\in\mathcal{H},\forall_{i}f(x_{i})=y_{i}}\|f\|_{\mathcal{H}}$ is simply linear interpolation between adjacent points on the line. Note that this is the same as our simplicial interpolating method.

Finally, we note that while kernel machines (which can be viewed as two-layer neural networks) are much more theoretically tractable than general neural networks, none of the current theory applies in the interpolated regime in the presence of label noise . We hope that simplicial interpolation can shed light on their properties and lead to better understanding of modern inferential methods.

Acknowledgements

We would like to thank Raef Bassily, Luis Rademacher, Sasha Rakhlin, and Yusu Wang for conversations and valuable comments. We acknowledge funding from NSF. DH acknowledges support from NSF grants CCF-1740833 and DMR-1534910. PPM acknowledges support from the Crick-Clay Professorship (CSHL) and H N Mahabala Chair (IITM). This work grew out of discussions originating at the Simons Institute for the Theory of Computing in 2017, and we thank the Institute for the hospitality. PPM and MB thank ICTS (Bangalore) for their hospitality at the 2017 workshop on Statistical Physics Methods in Machine Learning.

References

Appendix A Proofs

A.2 Proof of Theorem 3.2

Throughout we condition on $X_{1},\dotsc,X_{n}$, and write

For the first term, observe that if $X\notin\widehat{C}$, then $\hat{\eta}(X)=1/2$ and hence $(\hat{\eta}(X)-\eta(X))^{2}\leq 1/4$.

We now consider the second term, conditional on $Z\mathrel{\mathop{\mathchar 58\relax}}=(X_{1},\dotsc,X_{n})$ and $X\in\widehat{C}$. Let $L_{T}(X)=\mathrel{\mathop{\mathchar 58\relax}}\{(X_{(1)},Y_{(1)}),\dotsc,(X_{(d+1)},Y_{(d+1)})\}$. Since $X\in\operatorname{conv}(U_{T}(X))$, its barycentric coordinates $W\mathrel{\mathop{\mathchar 58\relax}}=(W_{1},\dotsc,W_{d+1})$ in $\operatorname{conv}(U_{T}(X))$ are distributed as $\operatorname{Dirichlet}(1,\dotsc,1)$. Let $\epsilon_{(i)}\mathrel{\mathop{\mathchar 58\relax}}=Y_{(i)}-\eta(X_{(i)})$ and $b_{(i)}\mathrel{\mathop{\mathchar 58\relax}}=\eta(X_{(i)})-\eta(X)$ for $i=1,\dotsc,d+1$. Also, let $v(x)\mathrel{\mathop{\mathchar 58\relax}}=\operatorname{var}(Y\mid X=x)$ be the conditional variance function. By the smoothness assumptions, we have

by Jensen’s inequality and the bound on $|b_{(i)}|$. For the second term, we have

by the bound on $|v(X_{(i)})-v(X)|$. Therefore

The conclusion follows by taking expectation with respect to $Z$ and $X$. ∎

A.3 Proof of Corollary 3.3

Recall that $\mu$ is supported uniformly on a convex polytope, and that $\widehat{C}$ is the convex hull of $X_{1},\dotsc,X_{n}$. Consider the probability mass outside of $\widehat{C}$. This quantity has been intensely studied in the context of stochastic geometry [see 37, for a review]. The following exemplifies the kind of result one may expect.

Next we consider $\hat{\delta}_{T}$, the maximum diameter of any simplex in the triangulation $T$ (defined in Theorem 3.2). For many natural triangulation schemes, we expect $\hat{\delta}_{T}\to 0$ as $n\to\infty$. This is indeed the case with Delaunay triangulation, in which the edges of each simplex in $T$ are obtained by connecting the centroids of neighboring cells in the Voronoi tessellation for the given point set $x_{1},\dotsc,x_{n}$.

Consider the Voronoi tessellation corresponding to the set $x_{1},\ldots,x_{n}$. The Voronoi cell corresponding to $x_{i}$ is defined simply as $\{x\in C\mathrel{\mathop{\mathchar 58\relax}}\forall j\neq i\centerdot\|x-x_{i}\|\leq\|x-x_{j}\|\}$, the set of points closest to $x_{i}$ than any other $x_{j}$. It is easy to see that each Voronoi cell is a convex set. Moreover, the distance from $x_{i}$ to any $x$ in its corresponding cell cannot exceed $\epsilon$, as the set $x_{1},\ldots,x_{n}$ is $\epsilon$-dense for $C$. The edges of Delaunay triangulation connect the centroids of neighboring elements of Voronoi tessellation and thus are bounded by $2\epsilon$ by the triangle inequality. The diameter of the simplex is the length of the longest edge, so the claim is proved. ∎

vanish as $n\to\infty$. This follows by applying Theorem A.1 and Lemma A.2. ∎

A.4 Proof of Theorem 3.5

The proof of Theorem 3.5 relies on the following tail bound.

for some absolute constants $c_{1},c_{2}>0$ (which may depend on $\delta$ but not $\bar{p}$ nor $k$).

Recall that $W$ has the same distribution as $(G_{1},\dotsc,G_{k})/\sum_{i=1}^{k}G_{i}$, where $G_{1},\dotsc,G_{k}$ are independent Gamma random variables, each with unit shape and scale parameters. Let $S\mathrel{\mathop{\mathchar 58\relax}}=\sum_{i=1}^{k}G_{i}(Y_{i}-1/2)$. Then, by Proposition 3.1,

Set $\lambda^{*}\mathrel{\mathop{\mathchar 58\relax}}=\delta$, so we obtain

which is of the form $c_{1}\bar{p}\cdot e^{-c_{2}k}$ for $c_{1}=8$ and $c_{2}=\delta^{2}/(4-\delta^{2})$.

Now, we prove the right tail bound for $S$ under the assumption that $\bar{p}\leq 1/8$. Fix any $y\in\{0,1\}^{k}$, and let $t\mathrel{\mathop{\mathchar 58\relax}}=\sum_{i=1}^{k}y_{i}$ denote be the number of $1$’s in $y$. If $t=0$, then we have

If $0<t<k/2$, then by the summation property of the Gamma distribution, the conditional distribution of $S$ given $Y=y$ is the same as that of $(H_{t}-H_{k-t})/2$, where $H_{t}$ and $H_{k-t}$ are independent Gamma random variables with unit scale, $H_{t}$ has shape parameter $t$, and $H_{k-t}$ has shape parameter $k-t$. The moment generating function for $H_{t}-H_{k-t}$ is

Since $0<t<k/2$, the minimizer of the moment generating function is achieved at $\lambda^{*}\mathrel{\mathop{\mathchar 58\relax}}=1-2t/k$. So

where $\operatorname{RE}(p,q)\mathrel{\mathop{\mathchar 58\relax}}=p\ln\frac{p}{q}+(1-p)\ln\frac{1-p}{1-q}$ is the binary relative entropy. Therefore, using Equation 1 and Equation 2,

where $|Y|\mathrel{\mathop{\mathchar 58\relax}}=Y_{1}+\dotsb+Y_{k}$.

To put Equation 3 into the desired form, first observe that

Moreover, by a standard coupling argument, if $B$ is a binomial random variable with $k$ trials and success probability $\bar{p}$, then

where the second-to-last inequality uses the assumption $\bar{p}\leq 1/8$, and the last inequality uses a standard Chernoff bound for binomial random variables. Therefore, combining Equation 3, Equation 4, and Equation 5,

Therefore, it is sufficient to prove our bound for the union of the simplices contained entirely within in the interior of one class. Moreover, since our bound is preserved under taking unions of sets, it is sufficient to prove the bound for the interior of a single simplex.

Let $L_{T}(X)=\mathrel{\mathop{\mathchar 58\relax}}\{(X_{(1)},Y_{(1)}),\dotsc,(X_{(d+1)},Y_{(d+1)})\}$ be the training examples defining one such simplex $\Delta\mathrel{\mathop{\mathchar 58\relax}}=\operatorname{conv}(X_{(1)},\dotsc,X_{(d+1)})$. Without loss of generality we can assume that $\eta(X_{(i)})\leq 1/2-h$ for all $i$ (the analysis for $\eta(X_{(i)})\geq 1/2+h$ is the same). Conditional on $X_{1},\dotsc,X_{n}$, the random vector $X$ is uniformly distributed in $\Delta$. Therefore, the barycentric coordinates $(W_{1},\dotsc,W_{d+1})$ of $X$ within $\Delta$ are distributed as $\operatorname{Dirichlet}(1,\dotsc,1)$. Since $X$ is independent of $(X_{1},Y_{1}),\dotsc,(X_{n},Y_{n})$, it follows that $(W_{1},\dotsc,W_{d+1})$ is independent of $Y_{(1)},\dotsc,Y_{(d+1)}$. Therefore, by Lemma A.3, we have

for some absolute constants $c_{1},c_{2}>0$ (depending only on $h$). Since $\eta$ is Lipschitz on the class interior, we have for any $x\in\Delta$,

Since the above argument holds for any simplex $\Delta$ contained entirely within a class interior, we conclude

A.5 Proof of Theorem 4.5

Following Chaudhuri and Dasgupta (and in particular, the proof of their Theorem 5), we bound the probability of the event $\hat{f}(X)\neq f^{*}(X)$ by the sum of probabilities of three events:

the $(k+1)$st nearest neighbor of $X$ is more than distance $r_{p}(X)$ from $X$;

$\neg(E_{1}\cup E_{2})$ and yet $\hat{f}(X)\neq f^{*}(X)$.

by a multiplicative Chernoff bound; here $X_{(k+1)}$ denotes the $(k+1)$st nearest neighbor of $x_{0}$.

Now assume $x_{0}\notin\partial_{p,\gamma}$. To bound the probability of $E_{3}$, we consider the following sampling process for $(X_{1},Y_{1}),\dotsc,(X_{n},Y_{n})$ relative to $x_{0}$:

Pick $X_{k+1}$ from the marginal distribution of the $(k+1)$st nearest neighbor of $x_{0}$.

Pick $k$ points $X_{1},\dotsc,X_{k}$ independently from $\mu$ restricted to $\operatorname{B}(x_{0},\|x_{0}-X_{k+1}\|)$.

For each $X_{i}$, independently pick the label $Y_{i}$ from the corresponding conditional distribution with mean $\eta(X_{i})$.

The distance from $x_{0}$ to its $(k+1)$st nearest neighbor is determined in the first step of this process, from the choice of $X_{k+1}$. The $k$ nearest neighbors of $x_{0}$ are the points $X_{1},\dotsc,X_{k}$ picked in the second step; their corresponding labels are $Y_{1},\dotsc,Y_{k}$.

Suppose without loss of generality that $x_{0}\in\mathcal{X}_{p,\gamma}^{-}$. It suffices to prove that, conditional on the event $r\mathrel{\mathop{\mathchar 58\relax}}=\|x_{0}-X_{k+1}\|\leq r_{p}(x_{0})$,

Observe that by definition of $\bar{\eta}_{x_{0},r}$ and the assumption $x_{0}\in\mathcal{X}_{p,\gamma}^{-}$,

for each $i=1,\dotsc,k$. Define $Z_{i}\mathrel{\mathop{\mathchar 58\relax}}=\phi(\|x_{0}-X_{i}\|/r)(Y_{i}-1/2)$ for $i=1,\dotsc,k$. Since $Z_{1},\dotsc,Z_{k}$ are iid, the following bound holds by Chebyshev’s inequality:

The conclusion follows now from the definition of $\kappa_{p}$. ∎

A.6 Proof of Corollary 4.6

First, we bound $\sup_{x\in\operatorname{supp}(\mu)}r_{p}(x)$. Let $R_{p}\mathrel{\mathop{\mathchar 58\relax}}=(Z_{0}p/c_{0})^{1/d}$, and fix any $x\in\operatorname{supp}(\mu)$. By assumption, $R_{p}\leq r_{0}$, so $\lambda(\operatorname{B}(x,R_{p})\cap\operatorname{supp}(\mu))\geq c_{0}\lambda(\operatorname{B}(x,R_{p}))$. Consequently,

Next, we bound $\mu(\partial_{p,\gamma})$. Pick any $x_{0}\in\operatorname{supp}(\mu)$. If $\eta(x_{0})\geq 1/2+\gamma+AR_{p}^{\alpha}$, then by the smoothness condition,

Hence $\bar{\eta}_{x_{0},r}\geq 1/2+\gamma$ for all $r\leq R_{p}$. Similarly, if $\eta(x_{0})\leq 1/2-\gamma-AR_{p}^{\alpha}$, then

which implies $\bar{\eta}_{x_{0},r}\leq 1/2-\gamma$ for all $r\leq R_{p}$. Since $r_{p}(x_{0})\leq R_{p}$ for all $x_{0}\in\operatorname{supp}(\mu)$, we conclude that

The claim now follows by using the $(B,\beta)$-margin condition.

Finally, we bound $\kappa_{p}$. Fix any $x_{0}\in\operatorname{supp}(\mu)$ and $0\leq r\leq r_{p}(x_{0})$ (so $r\leq R_{p}\leq r_{0}$). Then

The proof of Corollary 4.6 follows by combining the bounds on $\mu(\partial_{p,\gamma})$ and $\kappa_{p}$ from Lemma A.4 with Theorem 4.5.

A.7 Proof of Theorem 4.3

Fix $x_{0}\in\operatorname{supp}(\mu)$. As in the proof of Theorem 4.5, we sample $(X_{1},Y_{1}),\dotsc,(X_{n},Y_{n})$ as follows:

Pick $X_{k+1}$ from the marginal distribution of the $(k+1)$st nearest neighbor of $x_{0}$.

Pick $k$ points $X_{1},\dotsc,X_{k}$ independently from $\mu$ restricted to $\operatorname{B}(x_{0},\|x_{0}-X_{k+1}\|)$.

For each $X_{i}$, independently pick the label $Y_{i}$ from the corresponding conditional distribution with mean $\eta(X_{i})$.

The distance from $x_{0}$ to its $(k+1)$st nearest neighbor is determined in the first step of this process, from the choice of $X_{k+1}$. The $k$ nearest neighbors of $x_{0}$ are the points $X_{1},\dotsc,X_{k}$ picked in the second step; their corresponding labels are $Y_{1},\dotsc,Y_{k}$, so the regression estimate at $x_{0}$ is $\hat{\eta}(x_{0})=\sum_{i=1}^{k}W_{i}Y_{i}$, where

Define $\epsilon_{i}\mathrel{\mathop{\mathchar 58\relax}}=Y_{i}-\eta(X_{i})$ and $b_{i}\mathrel{\mathop{\mathchar 58\relax}}=\eta(X_{i})-\eta(x_{0})$ for $i=1,\dotsc,k$. Then

where the last inequality follows from A.5 (below). Combining (6) and (7) concludes the proof. ∎

Fix $X=x_{0}\in\operatorname{supp}(\mu)$, and consider the sampling process for $X_{1},\dotsc,X_{k+1}$ in the proof of Theorem 4.3 to define

Appendix B Interpolating kernel regression and semi-supervised learning

In this section we make some informal observations and notes on kernel regression in Reproducing Kernel Hilbert Space and semi-supervised learning. Full and rigorous exploration of these theoretically rich and practically significant topics is well beyond the scope of this paper and, likely, requires new theoretical insights. Still, we feel that some comments and observations may be of interest and could help connect our treatment of interpolation to other related ideas.

We start by discussing a simple setting already mentioned in Section 6. Consider the space $\mathcal{H}$ of real-valued functions $f$ with the norm defined as

This space is a reproducing kernel Hilbert Space corresponding to the Laplace kernel $e^{-\kappa|x-z|}$. We can now define the minimum norm interpolant as

It is well-known that the $\hat{\eta}$ can be written as a linear combination of kernel functions:

The coefficient $\alpha_{i}$ can be obtained by solving a system of linear equations given by $\hat{\eta}(x_{i})=y_{i}$.

It is however not necessary to solve this system to find the interpolating solution. Minimizing the norm directly, from the calculus of variations it follows that $\hat{\eta}$ satisfies the following differential equation:

This equation should be solved in each interval $(x_{i},x_{i+1})$ separately (here, assuming $x_{1}<\dotsb<x_{n}$). The boundary conditions $g(x_{i})=y_{i}$ and $g(x_{i+1})=y_{i+1}$ uniquely determine the solution of this second order ODE inside the interval.

Importantly, note that as $\kappa\rightarrow 0$, the solution tends to a linear interpolation between the sample points, since the differential equation becomes $\dfrac{\operatorname{d\!}{{}^{2}}\hat{\eta}}{\operatorname{d\!}{x^{2}}}=0$, i.e., $\hat{\eta}(x)=a+bx$ in each interval with the line passing through the samples at the ends of the interval. This observation connects RKHS interpolation in one dimension to simplicial interpolation analyzed in some detail in this paper. Higher dimensional RKHS kernel interpolation is significantly harder to analyze but some insight may be gained by considering a special case below.

B.2 Connections to semi-supervised learning

We will now discuss a discrete version of (9) on a graph and its connection to semi-supervised learning. We do not attempt any theoretical analyses of these methods here. Let $G=(V,E)$ be a (potentially weighted) graph with vertices $x_{i},i=1,\ldots,n$. Let $W$ be its adjacency matrix and $L$ the corresponding graph Laplacian. We can now consider the (finite-dimensional) space of functions $f$ defined on the vertices of the graph $G$. The following definition of the norm is the discrete analogue of (8):

This norm defines a finite dimensional RKHS on the vertices of the graph $G$. In the semi-supervised setting, where some of the vertices, $x_{1},\ldots,x_{k}$ have labels $y_{1},\ldots,y_{k}$, the interpolation problem becomes almost the same as before

Considering $\hat{\eta}$ as a vector, we see that the analogue of the differential equation in (9) is the system of linear equations

The set of linear equations determining the minimum norm interpolating solution on the unlabelled points $i$ can be recast into a somewhat more intuitive form:

Here ${\cal N}_{i}$ is the set of neighbors of $i$ (i.e., nodes connected to $i$ by edges of the graph) and $z_{i}=\sum_{i\in{\cal N}_{i}}w_{ij}$ is the weighted degree of the $i$th vertex.

The classifier for semi-supervised classification can be obtained by thresholding $\hat{\eta}(x_{i})$. This provides a graph-based interpolated semi-supervised learning algorithm similar to label propagation or interpolated graph regularization . Indeed, when $\kappa\to 0$, this scheme becomes label propagation. Interestingly, and consistently with the main story of this paper, it has been observed empirically in various works including the references above that interpolated semi-supervised learning typically provides optimal or near-optimal results compared to regularization.

If the graph corresponded to a (unweighted) hypercubic lattice in $d$-dimensions, then the degree of each vertex is $z_{i}=2d$. Thus, the interpolating solution has the property that at each unlabeled vertex, the inferred label value is proportional to the average of the assigned labels in the neighboring vertices. This is reminiscent of the interpolated nearest neighbor algorithms discussed in this paper.

While the solution of these equations generally depends on the structure of the neighborhood graph, there is a particularly simple case for which a closed form solution is easily obtained. This corresponds to the fully connected (unweighted) graph. The fully connected graph can be viewed as a local model for high-dimensional data. Similarly, it is used in the physics literature to mimic an infinite dimensional lattice.

It is easy to see with the above assumptions that the semi-supervised learning algorithm described above recovers the Bayes classifier when $k\rightarrow\infty$. Since each unlabeled vertex is equivalent, the solution $\eta_{i}^{U}=\eta^{U}$ does not depend on $i$. Thus, the minimum norm interpolating solution is constant on all the unlabeled points and is given by

The value of the interpolating regression function in this example is a constant and is independent of the number of unlabeled points. The plug-in classifier output is given at every site by $\hat{f}=\operatorname{sign}(\hat{\eta}^{U})=\operatorname{sign}(n_{+}-n_{-})$. Notice, as in $d=1$, the classifier output does not depend on $\kappa$.

If $p>\frac{1}{2}$ and $k$ is large, then $\hat{f}$ is therefore $+1$ with high probability, and for $k\rightarrow\infty$ one recovers the Bayes classifier. Using Hoeffding’s inequality for the Binomially distributed $n_{+}$, the excess risk is exponentially small: