Is Interpolation Overrated?

Interpolation and extrapolation are fundamental concepts in fields like machine learning and deep learning. The difference between the two is that interpolation occurs for a sample x when it falls inside or on the boundary of the given dataset’s convex hull, while extrapolation happens outside this convex hull. 

In a recent paper, the authors Yann Lecun, Randall Balestriero and J´erˆome Pesenti aim to dispel two major misconceptions. The first misconception is that state-of-the-art algorithms work well since they can correctly interpolate training data. The second misconception is that interpolation happens throughout tasks and datasets. 

The authors argue that on any high-dimensional (>100) dataset, interpolation almost never happens. They also claim that their results challenge the validity of the current interpolation/extrapolation definition.

Interpolation & Extrapolation

In the earliest recorded versions (Kolmogoroff, 1941 and Wiener, 1949), extrapolation was defined as the method for future prediction of a stationary Gaussian process based on past and current realisation. Interpolation was defined as predicting the possible realisation of a Gaussian process at a time position that lies between observation; one can even say that interpolation resamples the past.

Currently, the most accepted definition of interpolation is that it happens for a sample x when this sample resides in the convex hull of a set of samples X. In cases it does not, extrapolation occurs. This definition indicates that extrapolation is a more intricate task than interpolation -- the latter guarantees that the sample lies within the dataset’s convex hull, and the former leaves the entire remaining space as a valid sample position. This definition has been used in fields like function approximation, machine learning, and deep learning. Interestingly, such a definition has also given rise to an assumption that the algorithm transitions from interpolation to extrapolation as the performance decreases. 

The authors of this paper argue that interpolation/extrapolation and generalisation performances are not as tightly linked as previously believed. They have attempted to demonstrate theoretically and empirically that for synthetic and real data, interpolation almost never occurs in high dimensional spaces, regardless of the underlying intrinsic dimension of the data manifold. They claim that:

• Current models are extrapolating.
• Given the super-human performance of those models, the extrapolation regime is not an indicator of generalisation performances.

Interpolation & Curse of Dimensionality

In the first stage of the study, the authors carefully studied the dimensions of the space in which data is placed, the number of variables needed for the minimal representation of the data, and the dimension of the smallest subspace that includes all the data manifolds.

The commonly held belief for data such as images is that they lie on a low-dimension manifold and that interpolation occurs regardless of the high-dimensional ambient space. This study showed that such intuition could be misleading. In fact, the underlying manifold dimension does not help even in the case of having a 1-dimensional manifold. Instead, the parameter which matters the most is the dimension d* of the smallest affine subspace that includes the dimension of the convex hull of the data.

Credit: Research paper

It was observed that the increasing ambient space dimension has no impact on the number of samples required for maintaining the interpolation regime. The authors concluded that to increase the probability of being seen in the interpolation regime, the dimension d* needs to be controlled, not the manifold underlying dimension and ambient space dimension.

Experiments also demonstrated that even with real datasets and various popular embeddings, interpolation remains an elusive goal, and it becomes exponentially difficult to reach with growth dimension.

Wrapping Up

“In particular, we opposed the use of interpolation and extrapolation as indicators of generalisation 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,” the authors write.

The behaviour of the model within the convex of the training set barely impacts the model’s generalisation performance since new samples most often lie outside the convex hull. This observation is true for both original data space and embeddings. The authors believe that these observations will help in constructing better suited geometrical definitions of interpolation extrapolation that are more suited for generalised performances in high-dimensional data.

Read the full paper here.