Learning in High Dimension Always Amounts to Extrapolation

Introduction

The origin of the interpolation and extrapolation notions are hard to trace back. Kolmogoroff, (1941); Wiener, (1949) defined extrapolation as predicting the future (realization) of a stationary Gaussian process based on past and current realizations. Conversely, interpolation was defined as predicting the possible realization of such process at a time position lying in-between observations, i.e., interpolation resamples the past. Various research communities have formalized those definitions as follows.

Interpolation occurs for a sample $\boldsymbol{x}$ whenever this sample belongs to the convex hull of a set of samples $\boldsymbol{X}\triangleq\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{N}\}$, if not, extrapolation occurs.

From the above definition, it is reasonable to assume extrapolation as being a more intricate task than interpolation. After all, interpolation guarantees that the sample lies within the dataset’s convex hull, while extrapolation leaves the entire remaining space as a valid sample position. Those terms have been ported as-is to various fields such as function approximation (DeVore,, 1998) or machine learning (Bishop,, 2006), and an increasing amount of research papers in deep learning provide results and intuitions relying on data interpolation (Belkin et al.,, 2018; Bietti and Mairal,, 2019; Adlam and Pennington,, 2020). Beyond those, the following adage “as an algorithm transitions from interpolation to extrapolation, as its performance decreases” is commonly agreed upon. Before going further, we insist that throughout this manuscript, interpolation is to be understood as characterizing the data geometry as per Def. 1. This is not to be mistaken with the often employed “interpolation regime” of models which occur whenever the latter has training loss on the data (Chatterji et al.,, 2021). We shall see that interpolation/extrapolation and generalization performances do not seem as tightly related as previously thought.

Our goal in this paper is to demonstrate both theoretically and empirically for both synthetic and real data that interpolation almost surely never occurs in high-dimensional spaces ($>100$) regardless of the underlying intrinsic dimension of the data manifold. That is, given the realistic amount of data that can be carried by current computational capacities, it is extremely unlikely that a newly observed sample lies in the convex hull of that dataset. Hence, we claim that

currently employed/deployed models are extrapolating

given the super-human performances achieved by those models, extrapolation regime is not necessarily to be avoided, and is not an indicator of generalization performances

This paper is organized as follows. We first provide below (Thm. 1) an important theoretical result that has been derived in the context of Uniform samples from an hyper-ball. In that case, the probability of a new sample to be in interpolation regime from a dataset goes to as the dimension $d$ increases unless the number of dataset samples grows exponentially with $d$. This will allow to introduce notations and intuitions. We then directly provide empirical evidences in Sec. 2 using standard dataset where we demonstrate that even when considering a subset of the data dimensions, the probability to interpolate goes exponentially quickly to with the number of considered dimensions. We conclude with Sec. 3 by providing existing theoretical results describing the probability that new samples are in interpolation or extrapolation regimes in more specific scenarios.

Given a $d$-dimensional dataset $\boldsymbol{X}\triangleq\{\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{N}\}$ with i.i.d. samples uniformly drawn from an hyperball, the probability that a new sample $\boldsymbol{x}$ is in interpolation regime (recall Def. 1) has the following asymptotic behavior

Interpolation is Doomed by the Curse of Dimensionality

In this section we propose various experiments supporting the need for exponentially large dataset to maintain interpolation, as per Thm. 1, for non Gaussian data. First, we demonstrate in Sec. 2.1 the role of the underlying data manifold intrinsic dimension along with the role of the dimension of the smallest affine subspace that include the data manifold. As we will see from carefully designed datasets, only the latter has an impact on the probability of new samples being in an interpolation regime. We then move to real datasets in Sec. 2.2 and demonstrate that both in the data space or in various embedding spaces, current test set samples are all in extrapolation regime from their corresponding training set.

The first stage of our study consists in carefully understanding not only the role of the ambient dimension i.e. the dimension of the space in which the data lives, but also the role of the underlying data manifold intrinsic dimension i.e. the number of variables needed in a minimal representation of the data (Bennett,, 1965), and the dimension of the smallest affine subspace that includes all the data manifold.

In fact, one could argue that data such as images might lie on a low dimensional manifold and thus hope that interpolation occurs regardless of the high-dimensional ambient space. As we demonstrate in Fig. 1, this intuition would be misleading. In fact, the underlying manifold dimension does not help even in the extreme case of having a $1$-dimensional manifold. What matters however, is the dimension $d^{*}$ of the smallest affine subspace that includes all the data manifold, or equivalently, the dimension of the convex hull of the data. As such, in the presence of a nonlinear manifold, we can see that the exponential requirement from Thm. 1 in the number of samples required to preserve a constant probability to be in interpolation grows exponentially with $d^{*}$. In fact, with the intrinsic dimension ($d^{*}$) constant, increasing the ambient space dimension ($d$) has no impact on the number of samples needed to maintain interpolation regime as can be seen on the right of Fig. 1. We thus conclude that for one to increase the probability to be in an interpolation regime, one should control $d^{*}$, and not the manifold underlying dimension not the ambient space dimension.

We now propose to extend those insights to real data where the exact same behavior occurs across datasets.

2 Real Datasets and Embeddings are no Exception

The previous section explored the cases of synthetic data with varying ambient, intrinsic, and convex hull dimensions. This provided valuable insights e.g. the key quantity of interest lies in the dimension of the smallest affine subspace containing the data. For real dataset however, one could argue that some natural properties of such manifolds help in being in an interpolation regime. Furthermore, one could argue that once embedded in a suitable and non-degenerate latent space, e.g. from a learned deep network, interpolation occurs. As we will see through various experiments, even with real datasets and various popular embeddings, interpolation remains an elusive goal that becomes exponentially difficult to reach as the dimension grows.

Test set extrapolation in pixel-space. We first propose in Fig. 3 to study the proportion of the test set that is in interpolation regime from the train set for MNIST, CIFAR and Imagenet. To grasp the impact of the dimensionality of the data we propose to compute this proportion with varying number of dimensions obtained from two strategies. First, we only keep a specified amount of dimensions from the center of the images, second, we smooth and subsample the images. The former has the benefit of preserving the manifold geometry whilst only considering a limited amount of dimensions, the latter preserves the overall geometry of the manifold while removing the high-frequency structures (details of the image) and compressing the information on fewer dimensions. In both cases and throughout datasets, we see that despite the data manifold geometry held by natural images, finding samples in interpolation regime becomes exponentially difficult with respect to the considered data dimension.

Test set extrapolation in embedding-space. Given the above, one could argue that the key interest of machine learning is not to perform interpolation in the data space, but rather in a (learned) latent space. In fact, a DN provides a data embedding, then, in that space, a linear classifier (for example) solves the problem at hand, possibly in an interpolation regime. We thus provide in Tab. 1 the proportion of the test set that is in interpolation regime when considering different embedding spaces. We observed that embedding-spaces provide seemingly organized representations (with linear separability of the classes), yet, interpolation remains an elusive goal even for embedding-spaces of only $30$ dimensions. Hence current deep learning methods operate almost surely in an extrapolation regime in both the data space, and their embedding space.

Test set extrapolation in dimensionality-reduction-space. The last set of experiments deals with the use of (non)linear dimensionality reduction techniques to visualize high-dimensional dataset. We pose the following question: is the interpolation/extrapolation information preserved by commonly employed dimensionality reduction techniques? To unequivocally answer this question, we create a data that consists of the $2^{d}$ vertices of an hypercube in $d$ dimensions for $d=8,12$. Those dataset have the specificity that any sample is in extrapolation regime with respect to the other samples. We propose in Fig. 5 the $2$-dimensional representations of those vertices using $8$ different popular dimensionality reduction techniques: locally linear embedding (Roweis and Saul,, 2000) denoted as LLE, modified LLE (Zhang and Wang,, 2007), Hessian eigenmaps (Donoho and Grimes,, 2003) denoted as Hessian LLE, Laplacian eigenmaps (Belkin and Niyogi,, 2003) denoted as SE, isomap (Balasubramanian et al.,, 2002), t-distributed stochastic neighbor embedding (Van der Maaten and Hinton,, 2008) denoted as t-SNE, local tangent space alignment (Zhang and Zha,, 2004) referred as LTSA, Multidimensional scaling (Kruskal,, 1964) denoted as MDS. We observe that dimensionality reduction methods loose the interpolation/extrapolation information and lead to visual misconceptions significantly skewed towards interpolation.

Johnson–Lindenstrauss (di)lemma One last important setting concerns dimensionality reduction techniques that preserve -to some extent- the pairwise distances of the samples. Such techniques are often coined low-distortion embeddings, one of which follows from the Johnson–Lindenstrauss lemma (JLL) (Johnson and Lindenstrauss,, 1984). In short, the JLL guarantees the existence of a linear mapping $f$ with input dimension $d$ and output dimension $d_{\rm JLL}\geq\frac{24}{3\epsilon^{2}-2\epsilon^{3}}\log(N)$ with $N$ the size of the dataset such that the pairwise distances after projection will be within a $1\pm\epsilon$ factor of the original distances. Different bounds have emerged based on different proofs of the JLL (see Dasgupta and Gupta, (2003) for a survey). Interestingly, as per Thm. 1, the experiments from Fig. 1 and Fig. 3, the dataset size must be of order $2^{d}$ to ensure that samples in the test set be in interpolation regime. In the JLL setting, this translates into $d_{\rm JLL}>\frac{24}{3\epsilon^{2}-2\epsilon^{3}}d>d$. In other words, if a dataset size $N$ is exponential with the dimension $d$ (required to have new samples in interpolation regime) then $d_{\rm JLL}>d$ and JLL does not provide any dimensionality reduction.

We propose in the next section for the interested reader a brief collection of theoretical results that have also reached the conclusion that in high-dimensional spaces, exponentially large datasets are required to maintain the probability for a new sample to be in interpolation regimes.

Theoretical Quantification of Interpolation Probabilities

The previous section focuses on empirically evaluating the probability that a new sample falls into the convex hull of a given dataset and studied various settings concluding that interpolation suffers from the curse of dimensionality and is thus difficult to achieve in high-dimensional settings. As the convex hull is simply a polytope, we shall first refer the reader to Spielman and Teng, (2004) for a thorough study between various properties of such polytopes and their relation to the data dimension. We then provide some milestone theoretical results on computing the probability that samples are in interpolation/extrapolation regime, a problem often named as the convex position problem.

For a convex body $K$ in the space, let $p(n,K)$ denote the probability that $n$ random, independent, and uniform points from $K$ are in convex position, that is, none of the samples lies in the convex hull of the others.

Note that with this formulation, $p(n,K)$ describes the probability that any point in the set of samples is in extrapolation regime. Characterization of $p(n,K)$ for many $2$-dimensional bodies $K$ such as parallelograms and non-flat triangles are given below.

The probability $p(n,K)$ for a parallelogram or a triangle is given by

Going to higher dimensional spaces has seen more challenging progresses making many existing results only valid in the limiting setting and when considering $K$ to be an hypersphere, as given in Thm. 1 and in the following result.

The probability $p(n,K)$ for $K$ a $d$-dimensional hyperball $B^{d}$ and $n$ growing linearly with $d$ has the following limit behavior , $\forall m>3,\lim_{d\rightarrow\infty}p(\underbrace{d+m,B^{d}}_{\text{extrapolation}})=1$

The above result effectively demonstrates that when sampling uniformly from an hyperball, the probability that all the points are in convex position (any sample lies outside of the other samples’ convex hull) is $1$ when the number of samples grows linearly with the dimension, even when adding an arbitrary constant number of samples $m$. This result nicely complements the one provided in Thm. 1 which was originally conjectured by Buchta, (1986) a few years prior being proven by Bárány and Füredi, (1988). More recently, a non asymptotic result has been obtained characterizing $p(n,K)$ when the samples are obtained from Gaussian distributions.

Let $\boldsymbol{X}$ consist of $N$ i.i.d. $d$-dimensional samples from $\mathcal{N}(0,I_{d})$ with $N\geq d+1$, then for every $\sigma\geq 0$ the probability that a new sample $\boldsymbol{x}\sim\mathcal{N}(0,\sigma^{2}Id)$ is in extrapolation regime is given by

where $\sqrt{r}=i\sqrt{-r}$ if $r<0$ and $b_{N,k}=0$ for $k\not\in\{0,1,\dots,N\}$.

The above theorem provides the analytical quantities governing the probability to be in interpolation regime. Lastly, Majumdar et al., (2010) consider the case where the samples are obtained from random walks and obtain similar interpolation behaviors. There remain many avenues to provide specific results when the data belong to lower dimensional manifolds, or to consider anisotropic distributions.

Conclusion

Interpolation and extrapolation, as per Def. 1, provide an intuitive geometrical characterization on the location of new samples with respect to a given dataset. Those terms are commonly used as geometrical proxy to predict a model’s performances on unseen samples and many have reached the conclusion that a model’s generalization performance depends on how a model interpolates. In other words, how accurate is a model within a dataset’s convex-hull defines its generalization performances. In this paper, we proposed to debunk this (mis)conception. In particular, we opposed the use of interpolation and extrapolation as indicators of generalization performances by demonstrating both from existing theoretical results and from thorough experiments that, in order to maintain interpolation for new samples, the dataset size should grow exponentially with respect to the data dimension. In short, the behavior of a model within a training set’s convex hull barely impacts that model’s generalization performance since new samples lie almost surely outside of that convex hull. This observation holds whether we are considering the original data space, or embeddings. We believe that those observations open the door to constructing better suited geometrical definitions of interpolation and extrapolation that align with generalization performances, especially in the context of high-dimensional data.

References