x\rVert_{2}^{2})$ $\displaystyle=-(1-2\nu^{-1})\lVert x\rVert^{2}+D.$

∎

###  7.3 Results concerning approximation

######  Lemma 7.10.

Let $B_{w}(z)=\sup_{x\in\mathbb{R}^{D},u\in[0,1]}w(x)/w(x-uz)$ and
$M_{w}=\sup_{x\in\mathbb{R}^{D}}\lVert\nabla\log w(x)\rVert_{2}.$ Let $Z$ be a
random variable with $\mathbb{E}_{Z}\bigl{[}\lVert
Z\rVert_{2}B_{w}(Z)\bigr{]}<\infty.$ With fixed $\rho\in(0,1],$ define for
$g_{R,\delta}^{w}\coloneqq g_{R,\delta}/w,$ the convolution

$g_{\rho}^{w}(x)=\mathbb{E}_{Z}\left[\frac{g_{R,\delta}(x-\rho Z)}{w(x-\rho
Z)}\right].$

We have

$\lVert
g_{R,\delta}^{w}-g_{\rho}^{w}\rVert_{2}\leq\frac{\rho}{w(x)}\cdot\tilde{u}_{P,\delta,D,w}^{(1)}\\{1+(R+\delta)^{q-1}\\}$

with a constant

$\tilde{u}_{P,\delta,D,w}^{(1)}=\left[\sqrt{D}\zeta_{1}M_{w}\mathbb{E}\Bigl{[}\left\|Z\right\|_{2}B_{w}(\rho
Z)\Bigr{]}+\left\\{\zeta_{2}+C_{\delta}\zeta_{1}\right\\}\right],$

where $C_{\delta}$ is a constant bounding $\lVert\nabla
1_{R,\delta}(x)\rVert_{2}$ satisfying $C_{\delta}=8e^{-\delta}$ for
$\delta>1/2.$

###### Proof.

By the definition of $g_{\rho},$ we have

$g_{\rho}^{w}(x)-g_{R,\delta}^{w}(x)=\mathbb{E}_{Z}\left[g_{R,\delta}(x-\rho
Z)\left\\{\frac{1}{w(x-\rho
Z)}-\frac{1}{w(x)}\right\\}+\frac{g_{R,\delta}(x-\rho
Z)-g_{R,\delta}(x)}{w(x)}\right].$

To bound each quantity inside the expectation, we derive their norm estimates.
For $g_{R,\delta},$ we have

$\displaystyle\begin{aligned}
M_{0}(g_{R,\delta})&\coloneqq\sup_{x\in\mathbb{R}^{D}}\lVert
g_{R,\delta}(x)\rVert_{\mathrm{op}}\\\ &=\max_{\lVert x\rVert_{2}\leq
R+\delta}\lVert
g(x)\rVert_{2}=\sqrt{D}\zeta_{1}\\{1+(R+\delta)^{q-1}\\}\end{aligned}$ (13)

and

$\displaystyle\begin{aligned}
\tilde{\pi}(g_{R,\delta})_{1,0}&\coloneqq\sup_{x^{\prime}\in\mathbb{R}^{D}}\lVert\nabla
g_{R,\delta}(x^{\prime})\rVert_{\mathrm{op}}\\\
&\leq\sup_{x^{\prime}\in\mathbb{R}^{D}}1_{R,\delta}(x)\left\|\nabla
g(x)\right\|_{\mathrm{op}}+\sup_{x^{\prime}\in\mathbb{R}^{D}}\lVert\nabla
1_{R,\delta}(x)\rVert_{2}\left\|g(x)\right\|_{\mathrm{2}}\\\
&\leq\left(\zeta_{2}+C_{\delta}\zeta_{1}\right)\\{1+(R+\delta)^{q-1}\\},\end{aligned}$
(14)

where $C_{\delta}$is a universal constant depending on $\delta.$ Further, by
the fundamental theorem of calculus,

$\displaystyle\lVert g_{K,\delta}(x-\rho Z)-g_{K,\delta}(x)\rVert_{2}$
$\displaystyle\leq\rho\left\|\int_{0}^{1}\nabla g_{R,\delta}(x-t\rho
Z)Z_{2}\differential t\right\|_{2}$
$\displaystyle\leq\rho\int_{0}^{1}\lVert\nabla g_{R,\delta}(x-t\rho
Z)\rVert_{\mathrm{op}}\lVert Z\rVert_{2}\differential t_{2}$
$\displaystyle\leq\rho\lVert Z\rVert_{2}\tilde{\pi}(g_{R,\delta})_{1,0}.$

We also have

$\displaystyle\left|\frac{1}{w(x-\rho Z)}-\frac{1}{w(x)}\right|$
$\displaystyle=\rho\int_{0}^{1}\left|\left\langle\frac{\nabla
w}{w^{2}}(x-t\rho Z),Z\right\rangle\right|\differential t$
$\displaystyle\leq\rho\left\|Z\right\|_{2}\frac{1}{w(x)}\int_{0}^{1}\frac{w(x)}{w(x-t\rho
Z)}\left\|\frac{\nabla w}{w}(x-t\rho Z)\right\|_{2}\differential t$ (15)
$\displaystyle\leq\frac{\rho M_{w}\left\|Z\right\|_{2}B_{w}(\rho Z)}{w(x)}.$

Combining these evaluations yields

$\displaystyle\lVert g_{\rho}^{w}(x)-g_{R,\delta}^{w}(x)\rVert_{2}$
$\displaystyle\leq\mathbb{E}_{Z}\left[\lVert g_{R,\delta}(x-\rho
Z)\rVert_{2}\left|\frac{1}{w(x-\rho Z)}-\frac{1}{w(x)}\right|\right]$
$\displaystyle\hphantom{\leq}\
+\mathbb{E}_{Z}\left[\left\|\frac{g_{R,\delta}(x-\rho
Z)-g_{R,\delta}(x)}{w(x)}\right\|_{2}\right]$
$\displaystyle\leq\frac{\rho}{w(x)}\left[M_{w}\mathbb{E}\Bigl{[}\left\|Z\right\|_{2}B_{w}(\rho
Z)\Bigr{]}M_{0}(g_{R,\delta})+\tilde{\pi}(g_{R,\delta})_{1,0}\right]$
$\displaystyle=\left[\sqrt{D}\zeta_{1}M_{w}\mathbb{E}\bigl{[}\left\|Z\right\|_{2}B_{w}(\rho
Z)\bigr{]}+\left\\{\zeta_{2}+C_{\delta}\zeta_{1}\right\\}\right]\cdot\frac{\rho\\{1+(R+\delta)^{q-1}\\}}{w(x)}$

∎

######  Lemma 7.11.

Define symbols as in Lemma 7.10. For each fixed $\rho\in(0,1],$ we have

$\lVert\nabla g_{\rho}^{w}(x)-\nabla
g_{R,\delta}^{w}(x)\rVert_{\mathrm{op}}\leq\frac{\rho}{w(x)}\tilde{u}_{P,\delta,D,w}^{(2)}(x)\cdot\\{1+(R+\delta)^{q-1}\\},$

where

$\displaystyle\tilde{u}_{P,\delta,D,w}^{(2)}$
$\displaystyle=\left\\{(1+M_{w})\left(\zeta_{3}+2C_{\delta}\zeta_{2}+C_{R,\delta}\zeta_{1}\right)\mathbb{E}_{Z}\bigl{[}\lVert
Z\rVert_{2}\Bigr{]}\right.$
$\displaystyle\left.\hphantom{=}\quad+M_{w}\left(1+2M_{w}\right)\left(\left(\zeta_{2}+C_{\delta}\zeta_{1}\right)\right)\mathbb{E}_{Z}\Bigl{[}\left\|Z\right\|_{2}B_{w}(Z)\Bigr{]}\right\\},$

where $C_{\delta}$ and $C_{R,\delta}$ are respective uniform bounds on
$\lVert\nabla 1_{R,\delta}(x)\rVert_{2}$ and
$\lVert\nabla^{2}1_{R,\delta}(x)\rVert_{\mathrm{\mathrm{op}}},$ satisfying
$C_{\delta}=8e^{-\delta}$ and

$C_{R,\delta}=\frac{8}{R}e^{1/\delta-2}+\left(\frac{96\sqrt{3}}{(\sqrt{3}-1)^{4}}e^{-\frac{2\sqrt{3}}{\sqrt{3}-1}}+32e^{-4}(e^{1/\delta}+4)\right)e^{1/\delta}.$

for $\delta>1/2.$

###### Proof.

Before the proof, we introduce a notation. We denote the $l$-mode (vector)
product of a tensor $T\in\mathbb{R}^{D_{1}\times\cdots\times D_{L}}$ with a
vector $v\in\mathbb{R}^{D_{l}}$ by $T\bar{\times}_{l}v.$ The resulting tensor
is of order $L-1;$ its size is $(D_{1},\dots,D_{l-1},D_{l+1},\dots,D_{L});$ it
is expressed element-wise as

$(T\bar{\times}_{l}v)_{i_{1}\cdots i_{l-1}i_{l+1}\cdots
i_{L}}=\sum_{i_{l}=1}^{D_{l}}T_{i_{1}\cdots i_{l}\cdots L}v_{i_{l}}.$

First, note that

$\displaystyle\begin{aligned} &\lVert\nabla g_{\rho}^{w}(x)-\nabla
g_{R,\delta}^{w}(x)\rVert_{\mathrm{op}}=\left\|\mathbb{E}_{Z}\Bigl{[}\nabla
g_{R,\delta}^{w}(x-\rho Z)-\nabla
g_{R,\delta}^{w}(x)\Bigr{]}\right\|_{\mathrm{op}}\\\
&\leq\underbrace{\left\|\mathbb{E}_{Z}\left[\frac{\nabla g_{R,\delta}(x-\rho
Z)}{w(x-\rho Z)}-\frac{\nabla
g_{R,\delta}(x)}{w(x)}\right]\right\|_{\mathrm{op}}}_{\mathrm{(a)}}\\\
&\hphantom{\leq\quad}+\underbrace{\left\|\mathbb{E}_{Z}\left[\frac{\nabla\log
w(t-\rho Z)}{w(x-\rho Z)}\otimes\nabla g_{R,\delta}(x-\rho Z)-\frac{\nabla\log
w(x)}{w(x)}\otimes\nabla
g_{R,\delta}(x)\right]\right\|_{\mathrm{op}}}_{\mathrm{(b)}},\end{aligned}$
(16)

In the first line, we have exchanged the gradient and the expectation
operation. We evaluate each term below.

The term (a) is evaluated as

$\displaystyle\left\|\mathbb{E}_{Z}\left[\frac{\nabla g_{R,\delta}(x-\rho
Z)}{w(x-\rho Z)}-\frac{\nabla
g_{R,\delta}(x)}{w(x)}\right]\right\|_{\mathrm{op}}$
$\displaystyle\leq\underbrace{\left\|\mathbb{E}_{Z}\left[\nabla
g_{R,\delta}(x-\rho Z)\left(\frac{1}{w(x-\rho
Z)}-\frac{1}{w(x)}\right)\right]\right\|_{\mathrm{op}}}_{(\mathrm{i})}$
$\displaystyle\hphantom{\leq}\quad+\underbrace{\frac{1}{w(x)}\left\|\mathbb{E}_{Z}\left[\nabla
g_{R,\delta}(x-\rho Z)-\nabla
g_{R,\delta}(x)\right]\right\|_{\mathrm{op}}}_{\mathrm{(ii)}},$ (17)

The term (i) is bounded as

$\displaystyle\mathrm{(i)}$
$\displaystyle\leq\mathbb{E}_{Z}\left[\left|\frac{1}{w(x-\rho
Z)}-\frac{1}{w(x)}\right|\lVert\nabla g_{R,\delta}(x-\rho
Z)\rVert_{\mathrm{op}}\right]$
$\displaystyle\leq\frac{\rho}{w(x)}M_{w}\tilde{\pi}(g_{R,\delta})_{1,0}\mathbb{E}_{Z}\left[\left\|Z\right\|_{2}B_{w}(\rho
Z)\right].$

The term (ii) is evaluated as follows. By the fundamental theorem of calculus,

$\nabla g_{R,\delta}(x-\rho Z)-\nabla
g_{R,\delta}(x)=-\rho\int_{0}^{1}\nabla^{2}g_{R,\delta}(x-t\rho
Z)\bar{\times}_{1}Z\differential t.$

Note that the operator norm of $\nabla^{2}g_{R,\delta}$ is bounded by

$\displaystyle\begin{aligned}
&\tilde{\pi}(g_{R,\delta})_{2,0}\coloneqq\sup_{x\in\mathbb{R}^{D}}\lVert\nabla^{2}g_{R,\delta}(x)\rVert_{\mathrm{op}}\\\
&\leq\sup_{x\in\mathbb{R}^{D}}\left(1_{R,\delta}(x)\lVert\nabla^{2}g(x)\rVert_{\mathrm{op}}+2\lVert\nabla
1_{R,\delta}(x)\rVert_{2}\lVert
g_{R,\delta}(x)\rVert_{2}+\lVert\nabla^{2}1_{R,\delta}(x)\rVert_{2}\lVert
g_{R,\delta}(x)\rVert_{2}\right)\\\
&\leq\sup_{x\in\mathbb{R}^{D}}\left(1_{R,\delta}(x)\zeta_{3}+2\lVert\nabla
1_{R,\delta}(x)\rVert_{2}\zeta_{2}+\lVert\nabla^{2}1_{R,\delta}(x)\rVert_{2}\zeta_{1}\right)(1+\lVert
x\rVert_{2}^{q-1})\\\
&\leq\left(\zeta_{3}+2C_{\delta}\zeta_{2}+C_{R,\delta}\zeta_{1}\right)\\{1+(R+\delta)^{q-1}\\}.\end{aligned}$
(18)

Thus, the operator norm in the term (ii) is bounded as

$\displaystyle\left\|\mathbb{E}_{Z}\bigl{[}\nabla g_{R,\delta}(x-\rho
Z)-\nabla g_{R,\delta}(x)\bigr{]}\right\|_{\mathrm{op}}$
$\displaystyle\leq\mathbb{E}_{Z}\bigl{[}\lVert\nabla g_{R,\delta}(x-\rho
Z)-\nabla g_{R,\delta}(x)\rVert_{\mathrm{op}}\bigr{]}$
$\displaystyle=\rho\mathbb{E}_{Z}\left[\lVert Z\rVert_{2}\sup_{\lVert
u^{(3)}\rVert_{2}=1}\left\|\left\\{\int_{0}^{1}\nabla^{2}g_{R,\delta}(x-t\rho
Z)\bar{\times}_{1}\frac{Z}{\lVert Z\rVert_{2}}\differential
t\right\\}\bar{\times}_{3}u^{(3)}\right\|_{2}\right]$
$\displaystyle\leq\rho\mathbb{E}_{Z}\left[\lVert Z\rVert_{2}\sup_{\lVert
u^{(l)}\rVert_{2}=1,l\in\\{1,2,3\\}}\left|\left\\{\int_{0}^{1}\nabla^{2}g_{R,\delta}(x-t\rho
Z)\bar{\times}_{1}u^{(1)}\differential
t\right\\}\bar{\times}_{3}u^{(3)}\bar{\times}_{2}u^{(2)}\right|\right]$
$\displaystyle\leq\rho\mathbb{E}_{Z}\left[\lVert
Z\rVert_{2}\int_{0}^{1}\sup_{\lVert
u^{(l)}\rVert=1}\lvert\langle\nabla^{2}g_{R,\delta}(x-t\rho Z),u^{(1)}\otimes
u^{(2)}\otimes u^{(3)}\rangle\rvert\differential t\right]$
$\displaystyle\leq\rho\mathbb{E}_{Z}\left[\lVert
Z\rVert_{2}\int_{0}^{1}\lVert\nabla^{2}g_{R,\delta}(x-t\rho
Z)\rVert_{\mathrm{op}}\differential t\right]$
$\displaystyle\leq\rho\tilde{\pi}(g_{R,\delta})_{2,0}\mathbb{E}_{Z}\lVert
Z\rVert_{2}.$

Thus, the term (ii) is bounded by

$\frac{\text{$\rho$}}{w(x)}\tilde{\pi}(g_{K,\delta})_{2,0}\mathbb{E}_{Z}\lVert
Z\rVert_{2}.$

Similarly, we can evaluate the term (b) in (16)

$\displaystyle\mathrm{(b)}$ $\displaystyle=\frac{\left\|\mathbb{E}_{Z}[\nabla
w(t-\rho Z)\otimes\nabla g_{R,\delta}(x-\rho Z)-\nabla w(x)\otimes\nabla
g_{R,\delta}(x)]\right\|_{\mathrm{op}}}{w(x)}$
$\displaystyle\leq\frac{1}{w(x)}\left\|\mathbb{E}_{Z}\left[\frac{\nabla\log
w(t-\rho Z)}{w(x-\rho Z)}\otimes\bigl{(}\nabla g_{R,\delta}(x-\rho Z)-\nabla
g_{R,\delta}(x)\bigr{)}\right]\right\|_{\mathrm{op}}$
$\displaystyle\hphantom{\leq}\quad+\frac{1}{w(x)}\left\|\mathbb{E}_{Z}\left[\left(\frac{\nabla\log
w(t-\rho Z)}{w(x-\rho Z)}-\frac{\nabla\log w(x)}{w(x)}\right)\otimes\nabla
g_{R,\delta}(x)\right]\right\|_{\mathrm{op}}$
$\displaystyle\leq\frac{1}{w(x)}\mathbb{E}_{Z}\left\|\frac{\nabla\log w(t-\rho
Z)}{w(x-\rho Z)}\right\|_{2}\lVert\nabla g_{R,\delta}(x-\rho Z)-\nabla
g_{R,\delta}(x)\rVert_{\mathrm{op}}$
$\displaystyle\hphantom{\leq}\quad+\frac{1}{w(x)}\lVert\nabla
g_{R,\delta}(x)\rVert_{2}\mathbb{E}_{Z}\left\|\frac{\nabla\log w(t-\rho
Z)}{w(x-\rho Z)}-\frac{\nabla\log w(x)}{w(x)}\right\|_{2}$
$\displaystyle\leq\frac{M_{w}}{w(x)}\mathbb{E}_{Z}\lVert\nabla
g_{R,\delta}(x-\rho Z)-\nabla g_{R,\delta}(x)\rVert_{\mathrm{op}}$
$\displaystyle\hphantom{\leq}\quad+\frac{2\rho
M_{w}^{2}}{w(x)^{2}}\tilde{\pi}(g_{R,\delta})_{1,0}\mathbb{E}_{Z}\Bigl{[}\left\|Z\right\|_{2}B_{w}(\rho
Z)\Bigr{]}$ $\displaystyle\leq\frac{\rho
M_{w}}{w(x)}\left(\mathbb{E}_{Z}\lVert
Z\rVert_{2}\tilde{\pi}(g_{R,\delta})_{2,0}+\frac{2M_{w}}{w(x)}\tilde{\pi}(g_{w,\delta})_{1,0}\mathbb{E}_{Z}\Bigl{[}\left\|Z\right\|_{2}B_{w}(\rho
Z)\Bigr{]}\right).$

With $B(\rho Z)\leq B(Z)$ in mind, combining the results, we obtain

$\lVert\nabla g_{\rho}^{w}(x)-\nabla
g_{R,\delta}^{w}(x)\rVert_{\mathrm{op}}\leq\frac{\rho}{w(x)}\tilde{u}_{P,\delta,D,w}^{(2)}(x)\\{1+(R+\delta)^{q-1}\\},$

where

$\displaystyle\tilde{u}_{P,\delta,D,w}^{(2)}$
$\displaystyle=(1+M_{w})\mathbb{E}_{Z}\lVert
Z\rVert_{2}\tilde{\pi}(g_{R,\delta})_{2,0}$
$\displaystyle\hphantom{=\quad}+M_{w}\left(1+2M_{w}\right)\mathbb{E}_{Z}\Bigl{[}\left\|Z\right\|_{2}B_{w}(Z)\Bigr{]}\tilde{\pi}(g_{R,\delta})_{1,0}$
$\displaystyle=\left\\{(1+M_{w})\left(\zeta_{3}+2C_{\delta}\zeta_{2}+C_{R,\delta}\zeta_{1}\right)\mathbb{E}_{Z}\bigl{[}\lVert
Z\rVert_{2}\Bigr{]}\right.$
$\displaystyle\left.\hphantom{=}\quad+M_{w}\left(1+2M_{w}\right)\left(\left(\zeta_{2}+C_{\delta}\zeta_{1}\right)\right)\mathbb{E}_{Z}\Bigl{[}\left\|Z\right\|_{2}B_{w}(Z)\Bigr{]}\right\\}.$

∎

###  7.4 Results for DKSD

####  7.4.1 DKSD and uniform integrability

See 3.6

###### Proof.

Let $g\in{\cal G}_{k\mathrm{Id}}$ be a function with the stated properties.
Let $f(x)=\lVert x\rVert_{2}^{q}(x)1\\{\lVert x\rVert_{2}>r\\}.$ We consider
the integral

$\int_{\\{\lVert x\rVert_{2}>r\\}}\lVert x\rVert_{2}^{q}\differential
Q(x)=\int f(x)\differential Q(x)=\int_{0}^{\infty}Q(\\{f(x)>t\\})\differential
t.$

By dividing the range of the integral, we obtain

$\displaystyle\int_{0}^{\infty}Q(\\{f(x)>t\\})\differential t$
$\displaystyle=r^{q}Q(\\{\lVert
x\rVert_{2}>r\\})+\int_{r^{q}}^{\infty}Q(\\{f(x)>t\\})\differential t$
$\displaystyle=r^{q}Q(\\{\lVert
x\rVert_{2}>r\\})+\int_{r}^{\infty}Q\bigl{\\{}\lVert
x\rVert_{2}>t^{1/q}\bigr{\\}}\differential t,$

where we regard the second term as zero when $q=0.$

We evaluate the tail probabilities in terms of the Stein discrepancy.
Following the proof of Gorham and Mackey [2017, Lemma 17], we define
$\gamma(r)=\inf\\{{\cal T}_{P}g(x)-\nu:\lVert x\rVert_{2}\geq r\\}.$ By
assumption, there exists $r_{\eta}>0$ such that ${\cal{\cal
T}}_{P}g\geq\eta\lVert x\rVert_{2}^{q+\theta}$ for $\lVert
x\rVert_{2}>r_{\eta}.$ Define $\text{$r_{\gamma}$}\coloneqq r_{\eta}\lor
2(\lvert\nu\rvert/\eta)^{1/(q+\theta)}.$ It is straightforward to check that
for $r\geq r_{\gamma},$ we have $\gamma(r)\geq\eta r^{q+\theta}/2.$ By
Markov’s inequality,

$\displaystyle Q(\\{\lVert x\rVert_{2}$
$\displaystyle>r\\})\leq\frac{\mathbb{E}_{X\sim Q}\gamma(\lVert
X\rVert_{2})}{\gamma(r)}\leq\frac{\mathbb{E}_{X\sim Q}[{\cal
T}_{P}g(X)-\nu]}{\gamma(r)}\leq\frac{{\cal S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\gamma(r)}.$

These observations yield the following estimate of the above integral:

$\displaystyle\int_{\\{\lVert x\rVert_{2}>r\\}}\lVert
x\rVert_{2}^{q}\differential Q(x)$ $\displaystyle=r^{q}Q(\\{\lVert
x\rVert_{2}>r\\})+1_{\\{q>0\\}}\int_{r}^{\infty}Q(\\{\lVert
x\rVert_{2}>t^{1/q}\\})\differential t$ $\displaystyle\leq r^{q}\frac{{\cal
S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\gamma\bigl{(}r\bigr{)}}+1_{\\{q>0\\}}\int_{r}^{\infty}\frac{{\cal
S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\gamma\bigl{(}t\bigr{)}}\differential t$
$\displaystyle\leq 2\frac{{\cal S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\eta
r^{\theta}}+21_{\\{q>0\\}}\int_{r}^{\infty}\frac{{\cal S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\eta t^{1+\theta/q}}\differential t$
$\displaystyle\leq 2\frac{{\cal S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\eta}\left(\frac{1}{r^{\theta}}+\frac{q}{\theta}\frac{1}{r^{\theta/q}}1_{\\{q>0\\}}\right)$
$\displaystyle\leq 2\left(1+\frac{q}{\theta}\right)\frac{{\cal S}(Q,{\cal
T}_{P},{\cal G}_{k\mathrm{Id}})-\nu}{\eta}\frac{1}{r^{\theta\land\theta/q}}$

where we assume $r\geq r_{\gamma}\lor 1.$ Therefore, for $\epsilon>0,$ by
taking sufficiently large $r_{\epsilon}\geq 1$ such that

$2\left(1+\frac{q}{\theta}\right)\frac{{\cal S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\eta}\frac{1}{r_{\varepsilon}^{\theta\land\theta/q}}\leq\varepsilon\
\text{and}\ r_{\varepsilon}\geq r_{\gamma},$

we have

$\int_{\lVert x\rVert_{2}>r_{\epsilon}}\lVert x\rVert_{2}^{q}\differential
Q\leq{\cal\varepsilon}.$

Therefore, the order-$q$ integrability rate $R_{q}(Q,\varepsilon)$ satisfies

$R_{q}(Q,\varepsilon)\leq\left\\{2\left(1+\frac{q}{\theta}\right)\left(\frac{{\cal
S}(Q,{\cal T}_{P},{\cal
G}_{k\mathrm{Id}})-\nu}{\eta\varepsilon}\right)\right\\}^{\frac{1}{\theta}\lor\frac{q}{\theta}}\vee
r_{\gamma}.$

For sufficiently small $\varepsilon,$ the Stein discrepancy term dominates
$r_{\gamma}.$ Thus, the claim has been proved. ∎

####  7.4.2 The DKSD with the tilted linear kernel detects non-uniform
integrability

See 3.7

###### Proof.

We prove that the function $g(x)=-w(x)x$ satisfies the properties in the
statement. Note that the kernel $k$ is the linear kernel tilted by
$(v^{2}+\lVert x\rVert_{2}^{2})^{q_{w}-u}.$The function $g$ then belongs to
the RKHS ${\cal G}_{k\mathrm{Id}},$ since each component is the product of two
functions from the RKHSs of the respective kernels. It is straightforward to
check $\lVert g\rVert_{{\cal G}_{k\mathrm{Id}}}=\sqrt{D}.$ Applying the
diffusion Stein operator yields

$\displaystyle{\cal T}_{P}g(x)$ $\displaystyle=w(x)\left(-2\langle
b(x),x\rangle-\left\langle
m(x),\mathrm{Id}\right\rangle-\frac{2(q_{w}-u)}{(v^{2}+\lVert
x\rVert_{2}^{2})}\left\langle m(x),x\otimes x\right\rangle\right)$
$\displaystyle=w(x)\left(-{\cal A}_{P}\lVert
x\rVert_{2}^{2}-\frac{2(q_{w}-u)\lVert x\rVert_{2}^{2}}{v^{2}+\lVert
x\rVert_{2}^{2}}\frac{\left\langle\sigma(x)\sigma(x)^{\top},x\otimes
x\right\rangle}{\lVert x\rVert_{2}^{2}}\right).$

We first address the case $q_{w}-u\leq 0.$ In this case, we have

${\cal T}_{P}g(x)\geq w(x)(\alpha\lVert x\rVert_{2}^{2}-\beta),$

where the inequality follows from Condition 2.3 and the nonnegative second
term inside the parentheses above. From this estimate, the following relation
holds for $\lVert x\rVert_{2}>R=\sqrt{\beta/\alpha+1},$

${\cal T}_{P}g(x)\geq\eta\lVert x\rVert^{2(q_{w}-u+1)},$

where
$\eta=\bigl{(}1+v^{2}/R^{2}\bigr{)}^{q_{w}-u}\alpha\\{1-\beta/(\alpha+\beta)\\}>0.$
As ${\cal T}_{p}g(x)$ is continuous, it has the minimum in the centered closed
ball of radius $R.$ Thus,

$\displaystyle{\cal T}_{P}g(x)$ $\displaystyle\geq\nu\coloneqq
0\lor\min_{0\leq\lVert x\rVert_{2}\leq R}{\cal T}_{P}g(x)$
$\displaystyle=-\beta w(0)$

We next show the case $q_{w}-u>0.$ Using Condition 2.3 and the growth
condition (Condition 2.2), we obtain

${\cal T}_{P}g(x)\geq w(x)\left(\alpha\lVert
x\rVert_{2}^{2}-\beta-\frac{\lambda_{a}(q_{w}-u)}{2}\frac{\lVert
x\rVert_{2}^{2}}{(v^{2}+\lVert x\rVert_{2}^{2})}\bigl{(}1+\lVert
x\rVert_{2}^{q_{a}+1}\bigr{)}\right)$

This estimate provides us the lower bound

${\cal T}_{P}g(x)\geq\eta\lVert x\rVert_{2}^{2(q_{w}-u+1)}$

for $\lVert x\rVert_{2}>R_{1}=R_{0}+1,$with
$\eta=\bigl{(}1+v^{2}/R^{2}\bigr{)}^{q_{w}-u}f(R_{1})$ where

$f(r)=\left\\{\alpha-\frac{1}{r^{2}}\left(\beta+\frac{\lambda_{a}(q_{w}-u)}{2}\frac{r^{2}}{v^{2}+r^{2}}\bigl{(}1+r^{q_{a}+1}\bigr{)}\right)\right\\},$

and $R_{0}$ is chosen such that $f(R_{0})=0.$ The existence of such $R_{0}$ is
guaranteed if $f$ is increasing and achieves a positive value; the case
$q_{a}=0$ automatically satisfies this requirement, whereas the case $q_{a}=1$
further requires

$\alpha>\frac{\lambda_{a}(q_{w}-u)}{2}.$

To show a uniform lower bound, note that with $R_{1}$ above, ${\cal
T}_{P}g(x)\geq 0$ for $\lVert x\rVert_{2}>R_{1},$ and

${\cal
T}_{P}g(x)\geq-w(R_{1})\left\\{\beta+\frac{\lambda_{a}(q_{w}-u)}{2}\frac{R_{1}^{2}}{v^{2}+R_{1}^{2}}\bigl{(}1+R_{1}^{q_{a}+1}\bigr{)}\right\\}$

for $\lVert x\rVert_{2}\leq R_{1}.$ ∎

####  7.4.3 The KSD with the tilted IMQ kernel detects non-uniform
integrability

######  Lemma 7.12.

Suppose the diffusion targeting $P$ satisfies the dissipativity condition
(Condition 2.3) with $\alpha,\beta>0$ and the coefficient condition (Condition
2.2) with $\lambda_{a}>0$ and $q_{a}\in\\{0,1\\}.$ Let $w(x)=(v^{2}+\lVert
x\rVert_{2}^{2})^{q_{w}-u}$ with $q_{w}\geq 0,\ u\geq 0,\ \text{and}\ v>0.$
Assume $(q_{w}-u)<2\alpha/\lambda_{a}$ if $q_{a}=1.$ Let

$k(x,x^{\prime})=w(x)w(y)(v_{0}^{2}+\lVert x-x^{\prime}\rVert^{2})^{-t}$

for $t\in(0,1).$ Then, there exists a function $g\in{\cal G}_{k\mathrm{Id}}$
such that with any fixed $s\in(0,(t+1)/2),$

${\cal T}_{P}g(x)\geq\nu\ \text{\text{for any}}\ x\in\mathbb{R}^{D}\
\text{and}\ \liminf_{\lVert x\rVert\to\infty}\lVert
x\rVert_{2}^{-2(q_{w}-u+s)}{\cal T}_{P}g(x)\geq\eta$

for some $\nu\in\mathbb{R}$ and $\eta>0.$

###### Proof.

From the proof of Lemma 16 of Gorham and Mackey [2017], for any fixed
$2s\in(0,t+1)$ and $w>v_{0}/2,$ we have that the function

$g(x)=-2\alpha\frac{x}{(w^{2}+\lVert x\rVert_{2}^{2})^{1-s}}$

is an element of ${\cal G}_{k\mathrm{Id}}$ with the RKHS norm ${\cal
D}(w,v_{0},s,t)^{1/2}<\infty$ [see Lemma 16 of Gorham and Mackey, 2017, for
the norm estimate] The rest of the proof proceeds as in Lemma 3.7. ∎

###  7.5 Polynomial functions are pseudo-Lipschitz functions

We show that the class ${\cal F}_{q}$ suffices for characterizing convergence
in moments.

######  Lemma 7.13.

Let $q\geq 1$ be an integer. The $q$-th power $\left\|x\right\|_{2}^{q}$ of
the Euclidean norm is a pseudo-Lipschitz function of order $q-1.$ Its pseudo-
Lipschitz constant is bounded by $1\lor q/2.$

###### Proof.

The case $q=1$ follows from the triangle inequality. For $q\geq 2,$ the claim
follows by observing

$\displaystyle\left|\lVert x\rVert_{2}^{q}-\lVert y\rVert_{2}^{q}\right|$
$\displaystyle\leq q\int_{0}^{1}\left|\lVert
tx+(1-t)y\rVert_{2}^{q-1}\left\langle
tx+(1-t)y,x-y\right\rangle\right|\differential t$ $\displaystyle\leq q\lVert
x-y\rVert_{2}\int_{0}^{1}\lVert tx+(1-t)y\rVert_{2}^{q-1}\differential t$
$\displaystyle\leq q\lVert x-y\rVert_{2}\int_{0}^{1}t\lVert
x\rVert_{2}^{q-1}+(1-t)\lVert y\rVert_{2}^{q-1}\differential t$
$\displaystyle=\frac{q}{2}(\lVert x\rVert_{2}^{q-1}+\lVert
y\rVert_{2}^{q-1})\lVert x-y\rVert_{2}$ $\displaystyle\leq\frac{q}{2}(1+\lVert
x\rVert_{2}^{q-1}+\lVert y\rVert_{2}^{q-1})\lVert x-y\rVert_{2},$

where we have applied Jensen’s inequality to derive the third line. ∎

######  Lemma 7.14.

Let $q\geq 1$ be an integer. Let
$\bm{q}=(q_{1},\dots,q_{D})\in\\{0,\dots,q\\}^{D}$ be a multi-index such that
$\sum_{d=1}^{D}q_{d}=q\geq 1.$ Then,
$x^{\bm{q}}\coloneqq\prod_{d=1}^{D}x_{d}^{q_{d}}$ is pseudo-Lipschitz of order
$q-1.$ Its pseudo-Lipschitz constant
$\tilde{\mu}_{\mathrm{pLip}}(x^{\bm{q}})_{\mathrm{1},q-1}$ is bounded by
$1\lor(2(D-1)+1)\cdot q/2,$ and its degree $q-1$ polynomial derivative
coefficient $\tilde{\pi}(x^{\bm{q}})_{q-1,i}$ is bounded by
$\max_{d=1,\dots,D}q_{d}!\binom{i+D-1}{D-1}.$

###### Proof.

We first prove the following relationship:

$\lvert x^{\bm{q}}-y^{\bm{q}}\rvert\leq C_{D}\frac{q}{2}(\lVert
x\rVert^{q-1}+\lVert y\rVert^{q-1})\lVert x-y\rVert_{2},$

where $C_{D}=2(D-1)+1.$ From the proof of Lemma 7.13, for $D=1,$ we have

$\lvert x^{q}-y^{q}\rvert\leq\frac{q}{2}(\lvert x\rvert^{q-1}+\lvert
y\rvert^{q-1})\lvert x-y\rvert.$

For $D>1,$ suppose that the relation is true for $D-1.$ Take a multi-index
$\bm{q}$ of size $q.$ For $q=1,$ the claim is true with Lipschitz constant
$1.$ Without loss of generality, we may assume $\lVert x\rVert_{2}\geq\lVert
y\rVert_{2}.$ Then, for $q>1,$

$\displaystyle\lvert x^{\bm{q}}-y^{\bm{q}}\rvert$
$\displaystyle=\left|\prod_{d=1}^{D-1}x_{d}^{q_{d}}\cdot
x_{D}^{q_{D}}-\prod_{d=1}^{D-1}x_{d}^{q_{d}}\cdot
y_{D}^{q_{D}}+\prod_{d=1}^{D-1}x_{d}^{q_{d}}\cdot
y_{D}^{q_{D}}-\prod_{d=1}^{D-1}y_{d}^{q_{d}}\cdot y_{D}^{q_{D}}\right|$
$\displaystyle\leq\left|\prod_{d=1}^{D-1}x_{d}^{q_{d}}\right|\cdot\left|x_{D}^{q_{D}}-y_{D}^{q_{D}}\right|+\lvert
y_{D}^{q_{D}}\rvert\cdot\left|\prod_{d=1}^{D-1}x_{d}^{q_{d}}-\prod_{d=1}^{D-1}y_{d}^{q_{d}}\right|$
$\displaystyle\leq\lVert
x\rVert^{\sum_{d=1}^{D-1}q_{d}}\cdot\frac{q_{D}}{2}(\lvert
x_{D}\rvert^{q_{D}-1}+\lvert y_{D}\rvert^{q_{D}-1})\lvert x_{D}-y_{D}\rvert$
$\displaystyle\hphantom{\leq}+\lvert
y_{D}\rvert\cdot\frac{\sum_{d=1}^{D-1}q_{d}}{2}(\lVert
x\rVert_{2}^{\sum_{d=1}^{D-1}q_{d}-1}+\lVert
y\rVert_{2}^{\sum_{d=1}^{D-1}q_{d}-1})\lVert(x_{1},\dots,x_{D-1})-(y_{1},\dots,y_{D-1})\rVert_{2}$
$\displaystyle\leq\lVert x-y\rVert_{2}\left\\{\frac{q_{D}}{2}\lVert
x\rVert_{2}^{\sum_{d=1}^{D-1}q_{d}}\cdot(\lVert x\rVert_{2}^{q_{D}-1}+\lVert
y\rVert_{2}^{q_{D}-1})\right.$ $\displaystyle\hphantom{=\lVert
x-y\rVert_{2}}\quad\left.+\lVert
y\rVert_{2}^{q_{D}}C_{D-1}\frac{\sum_{d=1}^{D-1}q_{d}}{2}(\lVert
x\rVert_{2}^{\sum_{d=1}^{D-1}q_{d}-1}+\lVert
y\rVert_{2}^{\sum_{d=1}^{D-1}q_{d}-1})\right\\}$ $\displaystyle\leq\lVert
x-y\rVert_{2}\left\\{\frac{q_{D}}{2}2\lVert
x\rVert_{2}^{q-1}+C_{D-1}\frac{\sum_{d=1}^{D-1}q_{d}}{2}(\lVert
x\rVert_{2}^{q-1}+\lVert y\rVert_{2}^{q-1})\right\\}$
$\displaystyle\leq\frac{q}{2}\lVert x-y\rVert_{2}\\{(C_{D-1}+2)\lVert
x\rVert_{2}^{q-1}+C_{D-1}\lVert y\rVert_{2}^{q-1}\\}$
$\displaystyle\leq\frac{q}{2}(C_{D-1}+2)\lVert x-y\rVert_{2}(\lVert
x\rVert_{2}^{q-1}+\lVert y\rVert_{2}^{q-1}).$

Solving $C_{D}=C_{D-1}+2$ yields $C_{D}=2(D-1)+1.$ Therefore,

$\lvert x^{\bm{q}}-y^{\bm{q}}\rvert\leq\frac{q}{2}(2(D-1)+1)\cdot(1+\lVert
x\rVert_{2}^{q-1}+\lVert y\rVert_{2}^{q-1})\lVert x-y\rVert_{2}.$

Next we check the degree $q$ polynomial coefficient of the $i$-th derivatives.
We assume $q\geq i$ below, as the derivatives are zero otherwise. Note that we
have

$\displaystyle(\nabla^{i}x^{\bm{n}})_{l_{1},\dots,l_{i}}$
$\displaystyle=\prod_{d=1}^{D}\frac{n_{d}!}{(n_{d}-m_{d})!}\cdot
x_{d}^{q_{d}-m_{d}}\cdot 1_{\\{q_{d}\geq m_{d}\\}},$

where $m_{d}\coloneqq\\#\\{l_{d}:l_{d}=d\\},$ and

$\displaystyle\lVert\nabla^{i}x^{\bm{q}}\rVert_{\mathrm{op}}$
$\displaystyle=\sup_{\lVert u^{(d)}\rVert_{2}=1}\left|\sum_{\sum
m_{d}=i}\prod_{d=1}^{D}\left(\frac{q_{d}!}{(q_{d}-m_{d})!}\cdot
x_{d}^{q_{d}-m_{d}}1_{\\{q_{d}\geq m_{d}\\}}\right)u_{l_{d}}^{(d)}\right|$
$\displaystyle\leq\max_{d}q_{d}!\sup_{\lVert u^{(d)}\rVert_{2}=1}\sum_{\sum
m_{d}=i}\prod_{d=1}^{D}\lvert\lVert
x\rVert_{2}^{q_{d}-m_{d}}u_{i_{d}}^{(d)}\rvert$
$\displaystyle\leq\max_{d}q_{d}!\sup_{\lVert u^{(d)}\rVert_{2}=1}\sum_{\sum
m_{d}=i}\prod_{d=1}^{D}\lVert x\rVert_{2}^{q_{d}-m_{d}}\lVert
u^{(d)}\rVert_{2}$ $\displaystyle\leq\max_{d}q_{d}!\sum_{\sum m_{d}=i}\lVert
x\rVert_{2}^{\sum_{d}q_{d}-m_{d}}$
$\displaystyle\leq\max_{d}q_{d}!\binom{i+D-1}{D-1}\lVert x\rVert_{2}^{q-i}.$

Therefore,

$\displaystyle\tilde{\pi}(x^{\bm{q}})_{q-1,i=}\sup_{x\in\mathbb{R}^{D}}\frac{\lVert\nabla^{i}x^{\bm{q}}\rVert_{\mathrm{op}}}{1+\lVert
x\rVert_{2}^{q-1}}$
$\displaystyle\leq\max_{d}q_{d}!\binom{i+D-1}{D-1}\sup_{x\in\mathbb{R}^{D}}\frac{\left(\lVert
x\rVert_{2}^{q-i}\right)}{1+\lVert x\rVert_{2}^{q-1}}.$

Consider the function $f(r)=r^{m}/(1+r^{m+i-1})$ on $[0,\infty)$ with
$m>0,i\geq 1$. If $i=1,$ the function is monotonically increasing and its
supremum is $\lim_{r\to\infty}f(r)=1.$ If $i>1,$ the function is nonnegative,
and by taking the derivative, it can be shown that the function takes its
maximum at $r^{*}=\\{m/(i-1)\\}^{m/(m+i-1)}$ with its value

$f(r^{*})=\frac{(\frac{m}{i-1})^{\frac{m}{m+i-1}}}{1+\frac{m}{i-1}}\leq\frac{\frac{m}{i-1}}{1+\frac{m}{i-1}}<1.$

Thus, we have

$\tilde{\pi}(x^{\bm{q}})_{i,q}\leq\max_{d=1,\dots,D}q_{d}!\binom{i+D-1}{D-1}.$

∎

The above result indicates that if we divide a given monomial
$x^{\bm{q}}\coloneqq\prod_{d=1}^{D}x_{d}^{q_{d}}$ by the maximum of
$1\lor(2(D-1)+1)\cdot q/2$ and $\max_{d=1,\dots,D}q_{d}!\binom{3+D-1}{D-1},$
we have $x^{\bm{q}}\in{\cal F}_{q},$ where ${\cal F}_{q}$ is the psuedo-
Lipschitz class used in (10).


# Learning in High Dimension Always Amounts to Extrapolation

Randall Balestriero1 1Facebook AI Research, 2NYU
<EMAIL_ADDRESS>Jérôme Pesenti1 1Facebook AI Research, 2NYU
<EMAIL_ADDRESS>Yann LeCun1,2 1Facebook AI Research, 2NYU
<EMAIL_ADDRESS>
###### Abstract

The notion of interpolation and extrapolation is fundamental in various fields
from deep learning to function approximation. Interpolation occurs for a
sample $\boldsymbol{x}$ whenever this sample falls inside or on the boundary
of the given dataset’s convex hull. Extrapolation occurs when $\boldsymbol{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 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.

######  Definition 1.

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 $0$
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 $0$ 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 $0$ 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.

######  Theorem 1 (Bárány and Füredi, (1988)).

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

$\lim_{d\rightarrow\infty}p(\underbrace{\boldsymbol{x}\in\text{Hull}(\boldsymbol{X})}_{\text{interpolation}})=\begin{cases}1\iff
N>d^{-1}2^{d/2}\\\ 0\iff N<d^{-1}2^{d/2}\\\ \end{cases}$

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

###  2.1 The Role of the Intrinsic, Ambient and Convex Hull Dimensions

$d^{*}=d$

$\log(N)$

$p(\boldsymbol{x}\in\text{Hull}(\boldsymbol{X}))$

$d^{*}=1$, nonlinear

$\log(N)$

$d^{*}=4$, linear

$\log(N)$

Figure 1: Depiction of the evolution of the probability that a new sample is
in interpolation regime (y-axis,
$p(\boldsymbol{x}\in\text{Hull}(\boldsymbol{X}))$) given increasing dataset
size (x-axis, $N$) seen in logarithmic scale, and for various ambient space
dimensions ($d$) based on Monte-Carlo estimates on $500,000$ trials. On the
left, the data is sampled from a Gaussian density
$\boldsymbol{x}_{i}\sim\mathcal{N}(0,I_{d})$ while in the middle, the data is
sampled from a nonlinear continuous manifold with intrinsic dimension of $1$
(see Fig. 2 for details on the manifold data) and on the right, the data is
sampled from a Gaussian density that lives in an affine subspace of constant
dimension $4$ (while the ambient dimension increases). It is clear from those
figures that in order to maintain a constant probability to be in
interpolation regime, the training set size has to increase exponentially with
$d^{*}$ regardless of the underlying intrinsic manifold dimension where
$d^{*}$ is the dimension of the lowest dimensional affine subspace including
the entire data manifold i.e. the convex hull dimension.

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.

$N$

dimension index $z$

Figure 2: Depiction of the manifold data samples used for the middle plot of
Figure. 1 with ${\rm dim}=5$ on the left and ${\rm dim}=3$ on the right. In
all cases, the intrinsic dimension of this dataset is $1$, the latent
coordinate ($z$) that governs the data ($\boldsymbol{x}(z)$) is depicted on
the top row while the manifold samples in the ambient space are depicted in
the bottom row. This manifold is continuous, nonlinear and piecewise smooth,
and corresponds to walking around the simplex.

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

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

Proportion of test set in interpolation regime

considered number of dimensions $(d)$

Figure 3: Depiction of the proportion of the test set that is in interpolation
of the training set for MNIST (top), CIFAR (middle) and Imagenet (bottom) as a
function of the number of selected dimensions. We propose two settings (blue)
selecting increasingly large central patches (some cases consist of irregular
patches for intermediate dimension values) and (red) smoothing-subsampling the
original images (some cases consist of irregular images for intermediate
dimension values). Note that the blue line is always decreasing with $d$, and
that $d=147$ (right of the x-axis) represents 19% of MNIST total number of
dimensions, 5% for CIFAR and less than 1% for Imagenet. As can be seen
throughout those settings the proportion of the test set that is in
interpolation regime decreases exponentially fast with respect to the number
of dimensions ultimately becoming negligible well prior reaching the full data
dimensionality. The different slopes of those curves can be explained by the
smallest dimensional affine space containing each type of data of (see Tab.
1).

MNIST CIFAR10 IMAGENET

considered number of sub-image dimensions (d)

considered number of principal components

Figure 4: Depiction of levels ($90\%$ to $99\%$ from light to dark) of
explained variance from a Principal Component Analysis model for varying sub-
images dimensions ($1$ to $147$) x-axis based on the number of considered
components (y-axis). The sub-images of dimension $d$ are obtained either by
selecting the central spatial dimensions (blue, top-row) or by smoothing and
subsampling (red, bottom-row) as per Fig. 3. From this, it is clear that for
each sub-image dimension ($d$), the smallest dimensional affine subspace
containing the data reduces when going from MNIST to CIFAR10 to IMAGENET
leading to the different slopes observed in Fig. 3 (recall Fig. 1).

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.

Table 1: Proportion (in $\%$) of the test set that falls into the interpolation regime for various datasets (rows) and embeddings (columns) with varying (randomly selected) dimensions ($10$, $20$ and $30$), in all cases the embeddings are of dimension $512$. “random projection” represents a linear mapping with random Gaussian weights, the remaining six columns represent the use of the Resnet18 architecture’s latent space with either untrained weights (usual initialization) or Imagenet-pretrained weights. We shall note that such results are not surprising based on the probabilities computed in Fig. 1 for synthetic data, since the embedded samples behave more closely to gaussian samples than in the original pixel-space. | random projection | random Resnet18 | pretrained Resnet18
---|---|---|---
# selected dimensions | 10 | 20 | 30 | 10 | 20 | 30 | 10 | 20 | 30
MNIST $d$:764/train:50K/test:10K | 83$\pm$1 | 12$\pm$2 | 0$\pm$0 | 94$\pm$3 | 21$\pm$10 | 0$\pm$0 | 95$\pm$2 | 52$\pm$17 | 14$\pm$12
CIFAR $d$:3072/train:50K/test:10K | 89$\pm$1 | 41$\pm$0 | 15$\pm$0 | 88$\pm$4 | 23$\pm$8 | 0$\pm$0 | 92$\pm$2 | 21$\pm$8 | 0$\pm$0
Imagenet $d$:150528/train:1M/test:100K | 81$\pm$4 | 48$\pm$1 | 22$\pm$1 | 91$\pm$1 | 30$\pm$1 | 3$\pm$0 | 90$\pm$2 | 26$\pm$3 | 1$\pm$0

Figure 5: Depiction of various nonlinear dimensionality reduction techniques
applied onto a synthetic dataset containing all the hypercube vertices for an
hypercube of dimension $8$ (left) and $10$ (right). Coloring goes from blue
for the vertex at position $(1,\dots,1)$ to green for the vertex at position
$(-1,\dots,-1)$ in a linear manner. This data is chosen since each
point/vertex is in extrapolation regime from all the other points/vertices.
However, existing techniques for dimensionality reduction primarily focus on
preserving local geometric information. As a result, regardless of the
employed dimensionality reduction algorithm, the interpolation/extrapolation
information is lost as can be seen in all the proposed subplots. This can lead
to hazardous assumptions and conclusions.

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

######  Definition 2 (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.

######  Theorem 2 (Valtr, (1995, 1996)).

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

$\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$ to be an hypersphere, as given in Thm. 1 and in the following result.

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

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.

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

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

$\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

$\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 $\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.

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

## References

  * Adlam and Pennington, (2020) Adlam, B. and Pennington, J. (2020).  The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization.  In International Conference on Machine Learning, pages 74–84. PMLR.
  * Balasubramanian et al., (2002) Balasubramanian, M., Schwartz, E. L., Tenenbaum, J. B., de Silva, V., and Langford, J. C. (2002).  The isomap algorithm and topological stability.  Science, 295(5552):7–7.
  * Bárány and Füredi, (1988) Bárány, I. and Füredi, Z. (1988).  On the shape of the convex hull of random points.  Probability theory and related fields, 77(2):231–240.
  * Belkin et al., (2018) Belkin, M., Ma, S., and Mandal, S. (2018).  To understand deep learning we need to understand kernel learning.  In International Conference on Machine Learning, pages 541–549. PMLR.
  * Belkin and Niyogi, (2003) Belkin, M. and Niyogi, P. (2003).  Laplacian eigenmaps for dimensionality reduction and data representation.  Neural computation, 15(6):1373–1396.
  * Bennett, (1965) Bennett, R. S. (1965).  Representation and analysis of signals part xxi. the intrinsic dimensionality of signal collections.  Technical report, Johns Hopkins University.
  * Bietti and Mairal, (2019) Bietti, A. and Mairal, J. (2019).  On the inductive bias of neural tangent kernels.  arXiv preprint arXiv:1905.12173.
  * Bishop, (2006) Bishop, C. M. (2006).  Pattern recognition.  Machine learning, 128(9).
  * Buchta, (1986) Buchta, C. (1986).  On a conjecture of re miles about the convex hull of random points.  Monatshefte für Mathematik, 102(2):91–102.
  * Chatterji et al., (2021) Chatterji, N. S., Long, P. M., and Bartlett, P. L. (2021).  When does gradient descent with logistic loss find interpolating two-layer networks?  Journal of Machine Learning Research, 22(159):1–48.
  * Dasgupta and Gupta, (2003) Dasgupta, S. and Gupta, A. (2003).  An elementary proof of a theorem of johnson and lindenstrauss.  Random Structures & Algorithms, 22(1):60–65.
  * DeVore, (1998) DeVore, R. A. (1998).  Nonlinear approximation.  Acta numerica, 7:51–150.
  * Donoho and Grimes, (2003) Donoho, D. L. and Grimes, C. (2003).  Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data.  Proceedings of the National Academy of Sciences, 100(10):5591–5596.
  * Johnson and Lindenstrauss, (1984) Johnson, W. B. and Lindenstrauss, J. (1984).  Extensions of lipschitz mappings into a hilbert space 26.  Contemporary mathematics, 26.
  * Kabluchko and Zaporozhets, (2020) Kabluchko, Z. and Zaporozhets, D. (2020).  Absorption probabilities for gaussian polytopes and regular spherical simplices.  Advances in Applied Probability, 52(2):588–616.
  * Kolmogoroff, (1941) Kolmogoroff, A. (1941).  Interpolation und extrapolation von stationaren zufalligen folgen.  Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 5(1):3–14.
  * Kruskal, (1964) Kruskal, J. B. (1964).  Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis.  Psychometrika, 29(1):1–27.
  * Majumdar et al., (2010) Majumdar, S. N., Comtet, A., and Randon-Furling, J. (2010).  Random convex hulls and extreme value statistics.  Journal of Statistical Physics, 138(6):955–1009.
  * Roweis and Saul, (2000) Roweis, S. T. and Saul, L. K. (2000).  Nonlinear dimensionality reduction by locally linear embedding.  science, 290(5500):2323–2326.
  * Spielman and Teng, (2004) Spielman, D. A. and Teng, S.-H. (2004).  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  Journal of the ACM (JACM), 51(3):385–463.
  * Valtr, (1995) Valtr, P. (1995).  Probability thatn random points are in convex position.  Discrete & Computational Geometry, 13(3-4):637–643.
  * Valtr, (1996) Valtr, P. (1996).  The probability that n random points in a triangle are in convex position.  Combinatorica, 16(4):567–573.
  * Van der Maaten and Hinton, (2008) Van der Maaten, L. and Hinton, G. (2008).  Visualizing data using t-sne.  Journal of machine learning research, 9(11).
  * Wiener, (1949) Wiener, N. (1949).  Extrapolation, interpolation, and smoothing of stationary time series, with engineering applications.
  * Zhang and Wang, (2007) Zhang, Z. and Wang, J. (2007).  Mlle: Modified locally linear embedding using multiple weights.  In Advances in neural information processing systems, pages 1593–1600. Citeseer.
  * Zhang and Zha, (2004) Zhang, Z. and Zha, H. (2004).  Principal manifolds and nonlinear dimensionality reduction via tangent space alignment.  SIAM journal on scientific computing, 26(1):313–338.