Learning in High Dimension Always Amounts to Extrapolation — part 2/2

Cleaned-text code points [15518, 20285). Bibliography omitted here; source.md includes it.

The probability p ⁡ ( n , K ) p(n,K) for a parallelogram or a triangle is given by p ⁡ ( n , parallelogram ⏟ extrapolation ) = ( ( 2 ​ n − 2 n − 1 ) / n ! ) 2 and p ⁡ ( n , triangle ⏟ extrapolation ) = 2 n ​ ( 3 ​ n − 3 ) ! ( n − 1 ) ! 3 ( 2 n ) ! . \displaystyle p(\underbrace{n,{\rm parallelogram}}_{\text{extrapolation}})=\left(\begin{pmatrix}2n-2\\ n-1\end{pmatrix}/n!\right)^{2}\hskip 14.22636pt\text{ and }\hskip 14.22636ptp(\underbrace{n,{\rm triangle}}_{\text{extrapolation}})=\frac{2^{n}(3n-3)!}{(n-1)!^{3}(2n)!}.

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

###### Theorem 3 ( Buchta, (1986) ) .

The probability p ⁡ ( n , K ) p(n,K) for K K a d d -dimensional hyperball B d B^{d} and n n growing linearly with d d has the following limit behavior , ∀ m > 3 , lim d → ∞ p ⁡ ( d + m , B d ⏟ extrapolation ) = 1 \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 1 when the number of samples grows linearly with the dimension, even when adding an arbitrary constant number of samples m 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 ) p(n,K) when the samples are obtained from Gaussian distributions.

###### Theorem 4 ( Kabluchko and Zaporozhets, (2020) ) .

Let 𝑿 \boldsymbol{X} consist of N N i.i.d. d d -dimensional samples from 𝒩 ⁡ ( 0 , I d ) \mathcal{N}(0,I_{d}) with N ≥ d + 1 N\geq d+1 , then for every σ ≥ 0 \sigma\geq 0 the probability that a new sample 𝒙 ∼ 𝒩 ⁡ ( 0 , σ 2 ​ I ​ d ) \boldsymbol{x}\sim\mathcal{N}(0,\sigma^{2}Id) is in extrapolation regime is given by p ⁡ ( 𝒙 ∉ Hull ​ ( 𝑿 ) ⏟ extrapolation ) = 2 ​ ( b N , d − 1 ​ ( σ 2 ) + b N , d − 3 ​ ( σ 2 ) + … ) \displaystyle p(\underbrace{\boldsymbol{x}\not\in\text{Hull}(\boldsymbol{X})}_{\text{extrapolation}})=2(b_{N,d-1}(\sigma^{2})+b_{N,d-3}(\sigma^{2})+\dots) with b n , k ( σ 2 ) = ( n k ) g k ( − σ 2 1 + k ​ σ 2 ) g n − k ( σ 2 1 + k ​ σ 2 ) , g n ( r ) = 1 2 ​ π ∫ − ∞ ∞ Φ n ( r x ) e − x 2 / 2 d x \displaystyle b_{n,k}(\sigma^{2})=\begin{pmatrix}n\\ k\end{pmatrix}g_{k}\left(-\frac{\sigma^{2}}{1+k\sigma^{2}}\right)g_{n-k}\left(\frac{\sigma^{2}}{1+k\sigma^{2}}\right),\;\;g_{n}(r)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\Phi^{n}\left(\sqrt{r}x\right)e^{-x^{2}/2}dx where r = i ​ − r \sqrt{r}=i\sqrt{-r} if r < 0 r<0 and b N , k = 0 b_{N,k}=0 for k ∉ { 0 , 1 , … , N } 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.

## 4 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.