Yann LeCun Team Challenges Current Beliefs on Interpolation and Extrapolation Regarding DL Model Generalization Performance

In the new paper Learning in High Dimension Always Amounts to Extrapolation, a team from Facebook AI Research and New York University that includes Yann LeCun theoretically and empirically challenges the machine learning (ML) community’s conventional wisdom regarding interpolation, demonstrating that it almost never happens on high-dimensional (>100) datasets.

Interpolation and extrapolation are foundational concepts that function as estimation methods in numerical analysis. Interpolation is used to find new data points based on the range of a given set of known data points; while extrapolation involves going beyond the original range and estimating a variable’s value based on its relationship with other variables. These terms have been ported as-is to ML, where the definitions have been formalized as: Interpolation occurs for a sample x whenever this sample belongs to the convex hull of a set of samples X , {x1, . . . , xN }, if not, extrapolation occurs.

ML researchers have developed various intuitions and theories based on the assumption that the strong performance of state-of-the-art deep learning algorithms is largely due to their ability to correctly interpolate training data, and that interpolation occurs across tasks and datasets. An increasing number of deep learning papers have proposed results based on data interpolation, reflecting the adage “as an algorithm transitions from interpolation to extrapolation, its performance decreases.”

The Facebook and NYU researchers reject these ideas and argue that interpolation/extrapolation and generalization performances do not have the intimate relationships researchers previously thought. They conclude that interpolation almost surely never occurs in high-dimensional spaces (> 100) regardless of the underlying intrinsic dimensions of the data manifold, specifically:

1. Currently employed/deployed models are extrapolating.
2. Given the superhuman performances achieved by those models, the extrapolation regime is not necessarily to be avoided, and is not an indicator of generalization performances.

The team proposes various experiments supporting the need for exponentially large datasets to maintain interpolation for non-Gaussian data. Based on the results, they conclude that to increase the probability of a sample being in an interpolation regime it is necessary to control the dimension of the smallest affine subspace that includes all the data manifold, i.e. the convex hull of the data, and not the manifold underlying dimension nor the ambient space dimension.

They then extend this insight to real datasets, and summarize their observations as:

1. Despite the data manifold geometry held by natural images, finding samples in an interpolation regime becomes exponentially difficult with respect to the considered data dimension.
2. 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.
3. Dimensionality reduction methods lose the interpolation/extrapolation information and lead to visual misconceptions significantly skewed towards interpolation.
4. The JLL low-distortion embedding can only be used to reduce the dimension of datasets in which samples are almost surely in extrapolation regime from all others.

Overall, the researchers provide solid evidence to challenge the use of interpolation and extrapolation as indicators of generalization performance; and confidently claim that the behaviour of a model within a training set’s convex hull barely impacts that model’s generalization performance, since new samples almost surely lie outside of that convex hull.

The paper Learning in High Dimension Always Amounts to Extrapolation is on arXiv.

---

Author: Hecate He | Editor: Michael Sarazen

---

We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.