Source-linked AI summary
Learning in High Dimension Always Amounts to Extrapolation
Randall Balestriero, Jerome Pesenti, Yann LeCun
TL;DR
The paper questions the assumption that interpolation is common and that it predicts generalization. It combines theoretical results and experiments to argue that high-dimensional data are almost surely outside the training set’s convex hull, challenging interpolation and extrapolation as performance indicators.
Problem
Method
The paper combines theoretical results with experiments on synthetic and real data to examine interpolation probabilities across dimensions and data representations.
Source: §1 · pp. 1–2, §2.1 · p. 2, §2.2 · p. 4Results
For dimensions above 100, interpolation almost surely never occurs regardless of intrinsic data-manifold dimension, and current deployed models therefore extrapolate under the paper’s definition.
Source: §1 · pp. 1–2Takeaways & Limitations
The paper argues that interpolation and extrapolation should not be used as indicators of generalization performance.
Source: §1 · p. 2, §4 · p. 8The paper identifies further work on specific probability results for lower-dimensional manifolds and anisotropic distributions.
Source: §3 · p. 8
Abstract
from arXiv · showhide
The notion of interpolation and extrapolation is fundamental in various fields from deep learning to function approximation. Interpolation occurs for a sample $x$ whenever this sample falls inside or on the boundary of the given dataset's convex hull. Extrapolation occurs when $x$ falls outside of that convex hull. One fundamental (mis)conception is that state-of-the-art algorithms work so well because of their ability to correctly interpolate training data. A second (mis)conception is that interpolation happens throughout tasks and datasets, in fact, many intuitions and theories rely on that assumption. We empirically and theoretically argue against those two points and demonstrate that on any high-dimensional ($>$100) dataset, interpolation almost surely never happens. Those results challenge the validity of our current interpolation/extrapolation definition as an indicator of generalization performances.
1 Introduction
The paper defines interpolation geometrically as membership in a dataset’s convex hull, but challenges the assumption that interpolation is common or that it tracks generalization. It argues that in high dimensions interpolation is almost surely absent at realistic dataset sizes, regardless of the data manifold’s intrinsic dimension.
1 Introduction
- The paper distinguishes geometric interpolation from the model “interpolation regime,” which means zero training loss, and questions whether either notion indicates generalization performance.The common adage that performance decreases as an algorithm transitions from interpolation to extrapolation motivates this distinction.Source: §1 · p. 1
- For dimensions above 100, interpolation almost surely never occurs regardless of the data manifold’s intrinsic dimension.At realistic dataset sizes, a newly observed sample is extremely unlikely to lie in the dataset’s convex hull.Source: §1 · pp. 1–2
- The paper claims that current deployed models extrapolate, and that extrapolation need not be avoided or indicate poor generalization.The paper uses interpolation to mean convex-hull membership, not the model’s zero-training-loss “interpolation regime.”Source: §1 · pp. 1–2
- Under the uniform hyperball result, interpolation probability tends to zero as dimension grows unless dataset size grows exponentially with dimension.The introduction previews empirical evidence that interpolation probability also decreases exponentially with the number of considered dimensions on standard datasets.Source: §1 · p. 2
2 Interpolation is Doomed by the Curse of Dimensionality
Across synthetic and real data, interpolation becomes increasingly unlikely as the dimension of the data’s convex hull grows. Image test samples remain in extrapolation in pixel and embedding spaces, while dimensionality-reduction methods can obscure that distinction.
2.1 The Role of the Intrinsic, Ambient and Convex Hull Dimensions
- For synthetic data, the sample size needed to maintain a constant interpolation probability grows exponentially with convex-hull dimension d*, regardless of intrinsic manifold dimension.At fixed d*, increasing ambient dimension does not affect the sample size needed to maintain interpolation.Source: §2.1 · pp. 2–3, Figure 1 · p. 3
2.2 Real Datasets and Embeddings are no Exception
- Across MNIST, CIFAR, and ImageNet, interpolation becomes exponentially harder as pixel dimensions grow and remains elusive in embeddings as small as 30 dimensions.The experiments consider both central image patches and smoothed subsamples, as well as several embedding spaces.Source: §2.2 · p. 4
- Dimensionality-reduction methods lose interpolation/extrapolation information on hypercube vertices that are all in extrapolation, producing visualizations skewed toward interpolation.The paper tests eight methods on vertices of hypercubes with dimensions 8 and 12.Source: §2.2 · p. 4
- When interpolation requires dataset sizes exponential in dimension d, the Johnson–Lindenstrauss bound implies dJLL > d, so it provides no dimensionality reduction.This conclusion follows from the stated bound on the output dimension of the projection.Source: §2.2 · pp. 5–6
3 Theoretical Quantification of Interpolation Probabilities
The section frames interpolation and extrapolation probabilities as properties of convex polytopes and reviews theoretical results for several sampling settings. It also identifies lower-dimensional manifolds and anisotropic distributions as open cases for more specific results.
- Figure 5 shows that nonlinear dimensionality-reduction methods lose the interpolation/extrapolation distinction for hypercube vertices that are all in extrapolation from one another.The figure depicts hypercubes of dimensions 8 and 10.Source: Figure 5 · p. 7
- The section names the probability that no sampled point lies in the convex hull of the others the convex position problem.It uses this formulation to quantify interpolation and extrapolation probabilities.Source: §3 · p. 7
- Valtr (1995, 1996) gives formulas for the convex-position probability p(n, K) for parallelograms and triangles.Source: §3 · p. 7
- For uniform samples from a hyperballs, the probability that all points are in convex position tends to 1 when sample size grows linearly with dimension, even with a fixed number of extra samples.Convex position means every point lies outside the convex hull of the others.Source: §3 · p. 7
- For Gaussian training samples and a new Gaussian sample, Kabluchko and Zaporozhets (2020) give a formula for the probability of extrapolation.The stated setting has N ≥ d + 1 training samples and varies the new sample's scale σ.Source: §3 · p. 8
- The section leaves specific results for lower-dimensional manifolds and anisotropic distributions as open directions.Source: §3 · p. 8
4 Conclusion
The conclusion argues that convex-hull interpolation is an unreliable proxy for generalization in high-dimensional settings. It reports that maintaining interpolation requires exponentially growing datasets and calls for geometric definitions better aligned with generalization.
- Maintaining interpolation for new samples requires dataset size to grow exponentially with data dimension, so new samples almost surely lie outside the training set's convex hull.Source: §4 · p. 8
- The authors argue that a model's behavior within the training convex hull barely impacts generalization because new samples usually lie outside it.Source: §4 · p. 8
- The conclusion says this observation holds in both the original data space and embeddings.Source: §4 · p. 8
- The authors call for geometric definitions of interpolation and extrapolation that align better with generalization, especially for high-dimensional data.Source: §4 · p. 8
Related papers
Cited by
- AI Finds A Way2026