$\phi(\tilde{\mathcal{X}}_{n})$ is a compact subset of
$({\mathbb{R}}^{n_{\epsilon}},\ell_{2})$. By the Heine-Borel theorem (Munkres,
2000, Theorem 27.3), there exists an $r>0$ such that
$\phi(\tilde{\mathcal{X}}_{n})\subseteq\overline{\operatorname{Ball}_{{\mathbb{R}}^{n_{\epsilon}},\ell_{2}}(0,r)}$;
where,
$\overline{\operatorname{Ball}_{{\mathbb{R}}^{n_{\epsilon}},\ell_{2}}(0,r)}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{u\in{\mathbb{R}}^{n_{\epsilon}}:\,\|x\|_{\ell_{2}}\leq r\\}$.
Since
$\phi(\tilde{\mathcal{X}}_{n})\subseteq\overline{\operatorname{Ball}_{({\mathbb{R}}^{n_{\epsilon}},\ell_{2})}(0,r)}$
then (Kloeckner, 2010, Proposition 7.4) applies. More specifically, as
formulated in (Bertrand and Kloeckner, 2012, Example 5.5)) there exists some
$b\in{\mathbb{R}}^{n_{\epsilon}}$ (which can be computed explicitly using
Algorithm 1) such that the map

$\iota:(\overline{\operatorname{Ball}_{({\mathbb{R}}^{n_{\epsilon}},\ell_{2})}(0,r)},\ell_{2})\ni
x\mapsto\frac{1}{n_{\epsilon}}\sum_{k=1}^{n_{\epsilon}}\,\delta_{\sqrt{n_{\epsilon}}(x+b)_{k}}\in(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2}),$

is an isometry. Since the composition of isometries is itself an isometry
then, the map $\varphi\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\iota\circ\phi:(\tilde{\mathcal{X}}_{n},d_{n})\hookrightarrow(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2})$
is an isometry and is of the required form. Lastly, since $\iota\circ\phi$ is
has range in the set of “degenerate Gaussian mixtures”
$\mathcal{Z}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{{\mathbb{P}}\in\mathcal{GM}_{2}({\mathbb{R}}):\,\exists
N\in{\mathbb{N}}_{+}\,\exists
w\in\Delta_{N}\,\exists\mu_{1},\dots,\mu_{N}\in{\mathbb{R}}\,s.t.\,{\mathbb{P}}=\sum_{n=1}^{N}\,w_{n}\delta_{\mu_{n}}\\}$
then, we obtain the conclusion by applying the comparison result in (Delon and
Desolneux, 2020, Proposition 6) which states that the “identity map” on
$(\mathcal{W}_{2}({\mathbb{R}}),\mathcal{W}_{2})\ni{\mathbb{P}}\mapsto{\mathbb{P}}\in(\mathcal{GM}_{2}({\mathbb{R}}),\mathcal{MW}_{2})$
is an isometry between on the collection of finitely supported probability
measures (i.e. “degenerate Gaussian mixtures”). Applying Lemma 17 to the map
$\phi\circ[x\mapsto(d(x,\tilde{x})_{\tilde{x}\in\mathcal{X}_{n}})]$ yields the
desired tranformer $T$ satisfying

$sd_{n}(x,\tilde{x})\leq\mathcal{MW}_{2}(T(x),T(\tilde{x}))\leq
s(2+\epsilon)^{2}d_{n}(x,\tilde{x}),$

for all $x,\tilde{x}\in\tilde{\mathcal{X}}_{n}$.

Comment: From here, it now only remains to estimate the probability that a
uniformly and independently chosen pair of random points in $\mathcal{X}_{n}$
lie in $\tilde{\mathcal{X}}_{n}$.

Step 3 - Estimating Probability of Independently and Uniformly Sampling two
Points in the Dvoretzky-type Subspace
Let ${\mathbb{P}}$ be the uniform probability distribution on
$\mathcal{X}_{n}$ and let $X,\tilde{X}\sim{\mathbb{P}}$ be independent
$\mathcal{X}_{n}$-valued random elements. By independence and the fact that
$X$ and $\tilde{X}$ have the same law we can compute the following

${\mathbb{P}}\left(X\in\tilde{\mathcal{X}}_{n}\mbox{ and
}\tilde{X}\in\tilde{\mathcal{X}}_{n}\right)={\mathbb{P}}\left(X\in\tilde{\mathcal{X}}_{n}\right){\mathbb{P}}\left(\tilde{X}\in\tilde{\mathcal{X}}_{n}\right)={\mathbb{P}}\left(X\in\tilde{\mathcal{X}}_{n}\right)^{2}.$
(39)

Together, the lower-bound in (34), the definition of ${\mathbb{P}}$, and (39)
imply that

$\displaystyle{\mathbb{P}}\left(X\in\tilde{\mathcal{X}}_{n}\mbox{ and
}\tilde{X}\in\tilde{\mathcal{X}}_{n}\right)$
$\displaystyle={\mathbb{P}}\left(X\in\tilde{\mathcal{X}}_{n}\right)^{2}$ (40)
$\displaystyle=\left(\frac{\\#\tilde{\mathcal{X}}_{n}}{\\#\mathcal{X}_{n}}\right)^{2}$
$\displaystyle\geq\left(\frac{n^{\theta_{\epsilon}}}{n}\right)^{2}$
$\displaystyle\geq\left(\frac{n^{1-(2e/2+\epsilon)}}{n}\right)^{2}$
$\displaystyle=n^{-4e/(2+\epsilon)}.$

Moreover, by (Naor and Tao, 2012, Theorem 1.2) the precise value of
$\theta_{\epsilon}$ is given by the unique solution $\theta\in(0,1)$ to
$\frac{2}{2+\epsilon}=(1-\theta)\theta^{\theta/(1-\theta)}$; nb,
$\theta_{\epsilon}\in[1-2e/(2+\epsilon),1).$ Labeling
$D\stackrel{{\scriptstyle\mbox{\tiny def.}}}{{=}}2+\epsilon$,
$\theta_{D}\stackrel{{\scriptstyle\mbox{\tiny def.}}}{{=}}\theta_{\epsilon}$,
observing that $T$ is defined on all of $\mathcal{X}$, and noting that by
construction $d_{T}=k$ yields the theorem’s statement and concludes our proof.

Step 4 - Inverting the relation between $D$ and $\theta_{D}$:
Fix $\delta\in(0,1)$ such that $n^{-2+2\theta_{D}}=\delta$. Solving for
$\theta_{D}$ yields

$\theta_{D}=1+\log_{n}(\sqrt{\delta}).$ (41)

Since $\theta_{D}$ must belong to $(0,1)$ then (41) only gives a valid
$\theta_{D}$ if $\delta\in\big{(}1/e^{2},1\big{)}$; thus, we now impose that
constraint. Since $\theta_{D}$ solves
$\frac{2}{D}=(1-\theta)\,\theta^{\theta/(1-\theta)}$ where
$\theta\in[1-\frac{2e}{D},1)$ then (41) implies that

$D=-2\frac{\big{(}1+\log_{n}(\sqrt{\delta})\big{)}^{\frac{1+\log_{n}(\sqrt{\delta})}{\log_{n}(\sqrt{\delta})}}}{\log_{n}(\sqrt{\delta})}.$
(42)

In order for $D$ in (42) to be a valid distortion (compatible with our
argument) we need that $D>2$. Therefore, we require that $\delta>\delta_{n}$;
where $\tilde{\delta}_{n}\in[\frac{1}{e^{2}},1)$ is the unique solution to

$\log_{n}(\sqrt{\delta})=\big{(}1+\log_{n}(\sqrt{\delta})\big{)}^{\frac{1+\log_{n}(\sqrt{\delta})}{\log_{n}(\sqrt{\delta})}}.$

Set $\delta_{n}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\max\\{\frac{1}{e^{2}},\tilde{\delta}_{n}\\}$. Restricting
$\delta\in(\delta_{n},1)$ yields a $\delta$ for which $\theta_{D}$ and $D$
both satisfy the required assumptions of our argument. This complete the
proof.

###  B.2 Proof of Distortionless Multivariate Embeddings

Proof [Proof of Theorem 7] Fix a positive integer $n$ and let
$\mathcal{X}_{n}$ be a $n$-point subset of a metric space $(\mathcal{X},d)$
which we view as an $n$-point metric space $(\mathcal{X}_{n},d)$. Let
$\iota:(\mathcal{X}_{n},d)\rightarrow(\mathbb{R}^{n},\|\cdot\|_{\infty})$ be
the Fréchet embedding defined by $\iota(x)\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}(d(x,x_{i}))_{i=1}^{n}$ and denote
$\tilde{\mathcal{X}}_{n}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\iota(\mathcal{X}_{n})$. Clearly, $(\mathcal{X}_{n},d)$ and
$(\tilde{\mathcal{X}}_{n},\|\cdot\|_{\infty})$ are isometric with isometry
given by $\iota$. It is therefore sufficient to bi-Hölder embed
$({\mathcal{X}}_{n},\|\cdot\|_{\infty})$ into
$(\mathcal{P}_{2}(\mathbb{R}^{3}),\mathcal{W}_{2})$; we do this now. In the
proof of (Andoni et al., 2018, Theorem 1) from (Andoni et al., 2018, Equation
(12) to Equation(22)), the authors define a map
$\tilde{\phi}:\tilde{\mathcal{X}}_{n}\rightarrow(\mathcal{P}_{2}(\mathbb{R}^{3}),\mathcal{W}_{2})$
with the property that: there is some positive integer $N$ such that for every
$x\in\tilde{\mathcal{X}}_{n}$

$\tilde{\phi}(x)=\frac{1}{N}\,\sum_{n=1}^{N}\,\delta_{u_{n}(x)}$ (43)

for some set of points
$\\{u_{n}(x):\,n=1,\dots,N,\,x\in\tilde{\mathcal{X}}_{n}\\}$ in
$\mathbb{R}^{3}$. Moreover, a careful reading of the construction show that
the positive integer $N$ is such bounded above by151515As a brief reference,
we note that, in the notation of Andoni et al. (2018), $N\leq\\#\mathcal{C}$,
$\mathcal{C}\subseteq\cup_{i,j=1,\dots,n;\,i<j}\,\mathcal{B}_{i,j}$ and
$\\#\mathcal{B}_{i,j}=5K+2$; for some hyperparameter $K\in\mathbb{N}_{+}$
independent of the construction thus far.

$N\leq n(n-1)/2\,(5K+2)$ (44)

for some hyperparameter $K\in\mathbb{N}_{+}$ to be decided upon shortly. The
quantitative version of the result in question, namely (Andoni et al., 2018,
Lemma 15), shows that for every distortion $D>1$, taking
$\frac{5n^{4}}{2(D-1)}\,\operatorname{aspect}(\tilde{\mathcal{X}}_{n},d)^{2}\leq
K$ implies that: there is some scale $s>0$ such that for every
$x,\tilde{x}\in\tilde{\mathcal{X}}_{n}$ it holds that

$s\,\|x-\tilde{x}\|_{\infty}^{1/2}\leq\mathcal{W}_{2}\big{(}\tilde{\phi}(x),\tilde{\phi}(\tilde{x})\big{)}\leq
D\,s\,\|x-\tilde{x}\|_{\infty}^{1/2}.$ (45)

Since $\iota$ is an isometry and every pointmass on $\mathbb{R}^{3}$ is a
Gaussian measure with mean at that point and zero variance then the map
$\phi\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\tilde{\phi}\circ\iota^{-1}$ sends $(\mathcal{X}_{n},d)$ to
$(\mathcal{GM}_{2}(\mathbb{R}^{3}),\mathcal{MW}_{2})$ and it has
representation

$\phi(x)=\sum_{n=1}^{N}\,\frac{1}{N}\,N_{3}(u_{n}(x),\bm{0}),$

where $\bm{0}$ is the $3\times 3$-dimensional zero matrix. Moreover, since
$\iota$ is an isometry and by (Delon and Desolneux, 2020, Proposition 6) the
inclusion of the set of finitely supported probability measures in
$(\mathcal{P}_{2}(\mathbb{R}^{3}),\mathcal{W}_{2})$ into
$(\mathcal{GM}_{2}(\mathbb{R}^{3}),\mathcal{MW}_{2})$ is an isometry then (45)
implies that: there is a scale $s>0$ such that for every
$x,\tilde{x}\in\mathcal{X}_{n}$ it holds that

$s\,d(x,\tilde{x})^{1/2}\leq\mathcal{MW}_{2}\big{(}\phi(x),\phi(\tilde{x})\big{)}\leq
D\,s\,d(x,\tilde{x})^{1/2}.$ (46)

That is, $\phi$ is a $\frac{1}{2}$-bi-Hölder embedding of
$(\mathcal{X}_{n},d)$ into
$(\mathcal{GM}_{2}(\mathbb{R}^{3}),\mathcal{MW}_{2})$. Applying the Key Lemma,
Lemma 17, and to the map $\phi$ yields the conclusion; upon noting that the
probabilistic transformer $T$ is defined on all of $\mathcal{X}$.

###  B.3 Proof of Embedding Lemmata

Proof [Proof of Lemma 18] Since $(\mathcal{X},d)$ is a doubling metric space
then, by (Naor and Neiman, 2012, Theorem 1.2) there exist constant $c,C>0$
such that for any $0<\epsilon<\frac{1}{2}$ there exists an injective function
$\phi:(\mathcal{X},d)\hookrightarrow({\mathbb{R}}^{D},\ell_{2})$ satisfying

$d_{\mathcal{X}}^{1-\epsilon}(x,\tilde{x})\leq\|\phi(x)-\phi(\tilde{x})\|_{\ell_{2}}\leq\left\lceil\frac{C\log(C_{d})^{2}}{(1-(1-\epsilon))^{2}}\right\rceil
d_{\mathcal{X}}^{1-\epsilon}(x,\tilde{x});$ (47)

where $D\leq c\log(C_{d})$. Since $\mathcal{X}_{n}\subseteq\mathcal{X}$ is
finite, then $\mathcal{X}_{n}$ is compact. By (47), $\phi$ is
$(\frac{1}{2},1)\ni(1-\epsilon)$-Hölder continuous and therefore, by (Munkres,
2000, Theorem 26.5) $\phi(\mathcal{X}_{n})$ must be a compact subset of
$({\mathbb{R}}^{D},\ell_{2})$. As before, by appealing to the Heine-Borel
theorem ((Munkres, 2000, Theorem 27.3)) we conclude that there must exist some
$r>0$ such that
$\phi(\mathcal{X}_{n})\subseteq\overline{\operatorname{Ball}_{{\mathbb{R}}^{D},\ell_{2}}(0,r)}$;
where
$\overline{\operatorname{Ball}_{{\mathbb{R}}^{D},\ell_{2}}(0,r)}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{u\in{\mathbb{R}}^{D}:\,\|x\|_{\ell_{2}}\leq r\\}$. Thus,
(Kloeckner, 2010, Proposition 7.4) implies that there exists some
$b\in{\mathbb{R}}^{D}$ (which can be constructed using Algorithm 1) such that
the map

$\iota:(\overline{\operatorname{Ball}_{({\mathbb{R}}^{D},\ell_{2})}(0,r)},\ell_{2})\ni
x\mapsto\frac{1}{D}\sum_{k=1}^{D}\,\delta_{\sqrt{D}(x+b)_{k}}\in(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2}),$

is an isometry. As in the proof of Lemma 24, since $\iota\circ\phi$ is has
range in the set of “degenerate Gaussian mixtures”; i.e. belonging to
$\mathcal{Z}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{{\mathbb{P}}\in\mathcal{GM}_{2}({\mathbb{R}}^{d}):\,\exists
N\in{\mathbb{N}}_{+}\,\exists
w\in\Delta_{N}\,\exists\mu_{1},\dots,\mu_{N}\in{\mathbb{R}}^{d}\,s.t.\,{\mathbb{P}}=\sum_{n=1}^{N}\,w_{n}\delta_{\mu_{n}}\\}$
then, we obtain the conclusion by applying the comparison result in (Delon and
Desolneux, 2020, Proposition 6) which states that the identity map on
$(\mathcal{GM}_{2}({\mathbb{R}}^{d}),\mathcal{W}_{2})\ni{\mathbb{P}}\mapsto{\mathbb{P}}\in(\mathcal{GM}_{2}({\mathbb{R}}^{d}),\mathcal{MW}_{2})$
is an isometry between on the collection of degenerate mixtures of in
$\mathcal{Z}$. Setting $\phi\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\iota\circ\phi$ and $\alpha\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}1-\epsilon$ concludes the proof.

###  B.4 Proof of Main Results

The proof of Theorem 4 relies on the following lemma relating the rate at
which the volume of a ball doubles as a function of its radius to
$\mathcal{X}_{n}$’s metric capacity. To formulate the required lemma, we must
first revisit the notion of a doubling measure (Heinonen, 2001, Page 3 and
Chapter 13).

Let us begin by recalling that, given any $x\in\mathcal{X}_{n}$ and any $r>0$,
the metric ball about $x$ of radius $r$ is defined by
$B(x,r)\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{u\in\mathcal{X}_{n}:\,d_{\mathcal{X}}(u,z)<r\\}$. Briefly, we
say that a (finite Borel) measure $\mu$ on $(\mathcal{X}_{n},d_{n})$ is a
doubling measure with doubling constant $c_{\mu}$ if for every
$x\in\mathcal{X}_{n}$ and every $r>0$ it holds that

$\mu(B(x,2r))\leq c_{\mu}\mu(B(x,r)).$ (48)

In Vol’berg and Konyagin (1987) it was shown that the existence of a doubling
measure is equivalent to $d_{n}$ being doubling as a metric space; this means
that there is a (metric) doubling constant $c_{d_{n}}>0$ such that: for each
$r>0$ every metric ball in $\mathcal{X}_{n}$ of radius $2r$ can be covered by
at most $c_{d_{n}}$ metric balls of radius $r$. In (Bruè et al., 2021,
Proposition 1.7), it is shown that the existence of a bound on
$\mathrm{cap}(\mathcal{X}_{n})$ is equivalent to the existence and a bound for
$c_{d_{n}}$. Thus, a bound on the constant of a doubling measure $c_{\mu}$
should, in principle, imply a bound on the $\mathrm{cap}(\mathcal{X}_{n})$.
The next explicitly spells out the relationship between these “metric
quantities”.

######  Lemma 21 (Bounds of Metric Capacity via (Metric and Measure) Doubling
Constants)

Let $\mu$ be a doubling measure on $(\mathcal{X}_{n},d_{n})$ with doubling
constant $c_{\mu}$, as in (48). Then, the metric capacity of
$(\mathcal{X}_{n},d_{n})$ is bounded above by

$\log(c_{d_{n}})\leq\log(\mathrm{cap}(\mathcal{X}_{n}))\leq 12\log(c_{\mu}).$

Proof [Proof of Lemma 21] Suppose that $N$ is a positive integer for which
there does not exist points $x_{1},\dots,x_{N}\in B(x,r)$ satisfying

$\operatorname{Ball}_{g}(x,r)\subseteq\bigcup_{i=1}^{N}\operatorname{Ball}_{g}(x_{i},r/2),$

then, $N$ is an upper-bound for $c_{d_{n}}$. Moreover, there must exist $N$
points $x_{1},\dots,x_{n}$ in $B(x,r)$ for which

$0<\min_{i,j=1,\dots,N;\,i\neq
j}\,\min_{u\in\mathcal{X}_{n},\,d_{n}(u,x_{i})\leq
2^{-2}r}\min_{\tilde{u}\in\mathcal{X}_{n},\,d_{n}(\tilde{u},x_{j})\leq
2^{-2}r}\,d_{n}(u,\tilde{u}).$

Pick
$N^{\star}\in\underset{i=1,\dots,N}{\operatorname{argmin}}\,\mu(B(x_{i},r))$.
Thus, we have that

$\displaystyle\mu(B(x_{N^{\star}},4r))$
$\displaystyle\geq\sum_{i=1}^{N}\,\mu(B(x_{i},2^{-2}r))$ $\displaystyle\geq
n\min_{i=1,\dots,N}\,\mu(B(x_{i},r))$
$\displaystyle=n\mu(B(x_{N^{\star}},r)).$

Therefore, $c_{d}\leq c_{\mu}^{4}$. Now, by (Bruè et al., 2021, Proposition
1.7 (i)), we have that

$\mathrm{cap}(\mathcal{X}_{n})\leq C_{d}^{3}.$ (49)

Combining the estimate (49) with the estimate $c_{d}\leq c_{\mu}^{4}$ yields
the desired upper-bound on $\mathrm{cap}(\mathcal{X}_{n})$. The lower-bound on
$\mathrm{cap}(\mathcal{X}_{n})$ is given in (Bruè et al., 2021, Proposition
1.7 (i)).

Proof [Proof of Theorem 4] Fix an $n\geq 2$-point metric subspace
$(\mathcal{X}_{n},d_{n})$ of $(\mathcal{X},d_{\mathcal{X}})$. Restricting to
$(\mathcal{X}_{n},d_{n})$, the result for $\mathcal{X}=\mathcal{X}_{n}$
follows from Lemma 17 applied to Lemma 18 and then using Lemma 21 to upper-
bound $\log_{2}(c_{d_{n}})$ by
$12\log_{2}(\mathrm{cap}(\mathcal{X}_{n},d_{n}))$. The general statement,
follows by simply noting that $T$ constructed this way is defined on all of
$\mathcal{X}$.

###### Remark 22

The proof of Theorem 4 implies that the result holds with
$\mathrm{cap}(\mathcal{X}_{n},d_{n})$ replaced by $\mathcal{X}_{n}$’s doubling
constant. Nevertheless, one can still derive the result with $C_{d}^{3}$ in
place of $\mathrm{cap}(\mathcal{X}_{n})$ as a consequence of the present
formulation of Theorem 4 and of (Bruè et al., 2021, Proposition 1.7 (ii)).
Thus, we only make the remark to state that the result can be sharpened if one
prefers to consider doubling constants rather than metric capacity.

###  B.5 Proofs of Secondary Results

####  B.5.1 Proofs of Deterministic Embeddings

Let us consider the case where $(\mathcal{X}_{n},d_{n})$ is a tree.

######  Lemma 23 (Bi-Lipschitz Embedding of (Finite) Combinatorial Trees into
$(\mathcal{MG}_{2}({\mathbb{R}}),\mathcal{MW}_{2})$)

Let $G=(V,E)$ be an $n$-vertex tree and let $(V,d_{G})$ be its associated
metric space (as in Example 2.1). There is an absolute constant $C>0$ such
that, for every $M\in{\mathbb{N}}_{+}$ there exists a map of the form

$\varphi(x)\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\frac{1}{M}\sum_{k=1}^{M}N_{d}(\phi(x)_{k},0),$

such that the following holds: for every $x,\tilde{x}\in\mathcal{X}_{n}$ we
have that

$d_{G}(x,\tilde{x})\leq\mathcal{W}_{2}(\varphi(x),\varphi(\tilde{x}))\leq\mathcal{MW}_{2}(\varphi(x),\varphi(\tilde{x}))\leq
Cn^{1/(d-1)}d_{G}(x,\tilde{x}),$

where $\phi:V\rightarrow{\mathbb{R}}^{M}$ and $C>0$ is an absolute constant
independent of $n$, $d$, and of $(\mathcal{X}_{n},d_{n})$.

Proof [Proof of Lemma 23] Fix $\epsilon>0$. Since $d_{n}$ is a tree metric on
$\mathcal{X}_{n}$ then (Gupta, 2000, Theorem 1) implies there is an absolute
constant $C>0$ (independent of $n$ and of $(\mathcal{X}_{n},d_{n})$) and bi-
Lipschitz embedding $\phi:V\rightarrow{\mathbb{R}}^{d}$ satisfying: for every
$x,\tilde{x}\in V$

$d_{n}(x,\tilde{x})\leq\|\phi(x)-\phi(\tilde{x})\|\leq
Cn^{1/(d-1)}d_{n}(x,\tilde{x}).$ (50)

Since $\mathcal{X}_{n}$ is finite, then $(\mathcal{X}_{n},d_{n})$ is compact.
Since $\phi$ is a bi-Lipschitz map then, it is continuous and therefore by
(Munkres, 2000, Theorem 26.5), $\phi(\mathcal{X}_{n})$ is a compact subset of
$({\mathbb{R}}^{5},\ell_{2})$. By the Heine-Borel theorem ((Munkres, 2000,
Theorem 27.3)), there exists an $r>0$ such that
$\phi(\mathcal{X}_{n})\subseteq\overline{\operatorname{Ball}_{{\mathbb{R}}^{5},\ell_{2}}(0,r)}$;
where
$\overline{\operatorname{Ball}_{{\mathbb{R}}^{5},\ell_{2}}(0,r)}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{u\in{\mathbb{R}}^{5}:\,\|x\|_{\ell_{2}}\leq r\\}$. Since
$\phi(\mathcal{X}_{n})\subseteq\overline{\operatorname{Ball}_{({\mathbb{R}}^{5},\ell_{2})}(0,r)}$
then (Kloeckner, 2010, Proposition 7.4) applies. More specifically, the proof
of (Kloeckner, 2010, Proposition 7.4) (see the comment in (Bertrand and
Kloeckner, 2012, Example 5.5)) guarantee that there exists some
$b\in{\mathbb{R}}^{d}$ (which can be constructed using Algorithm 1 in Section
C) such that the map

$\iota:(\overline{\operatorname{Ball}_{({\mathbb{R}}^{5},\ell_{2})}(0,r)},\ell_{2})\ni
x\mapsto\frac{1}{d}\sum_{k=1}^{d}\,\delta_{\sqrt{d}(x+b)_{k}}\in(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2}),$

is an isometry. Since the composition of isometries is itself an isometry,
then the map $\varphi\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\iota\circ\phi:(\mathcal{X}_{n},d_{n})\hookrightarrow(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2})$
is an isometry and is of the required form. Lastly, since $\iota\circ\phi$ is
has range in the set of “degenerate Gaussian mixtures”
$\mathcal{Z}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{{\mathbb{P}}\in\mathcal{GM}_{2}({\mathbb{R}}^{d}):\,\exists
N\in{\mathbb{N}}_{+}\,\exists
w\in\Delta_{N}\,\exists\mu_{1},\dots,\mu_{N}\in{\mathbb{R}}^{d}\,s.t.\,{\mathbb{P}}=\sum_{n=1}^{N}\,w_{n}\delta_{\mu_{n}}\\}$
then, we obtain the conclusion by applying the comparison result in (Delon and
Desolneux, 2020, Proposition 6) which states that the “identity map” on
$(\mathcal{W}_{2}({\mathbb{R}}),\mathcal{W}_{2})\ni{\mathbb{P}}\mapsto{\mathbb{P}}\in(\mathcal{GM}_{2}({\mathbb{R}}),\mathcal{MW}_{2})$
is an isometry on the collection of finitely supported probability measures
(i.e. “degenerate Gaussian mixtures”).

Proof [Proof of Proposition 11] Since $(\mathcal{X}_{n},d_{n})$ is a
combinatorial (metric) graph then
$\operatorname{aspect}(\mathcal{X}_{n},d_{n})\leq\operatorname{diam}(\mathcal{X}_{n},d_{n})$.
The result now follows directly from Lemma 17 applied to Lemma 23.
Our next case concerns the structure of a low-distortion embedding of a graph
whose points are drawn from a Riemannian manifold. In this case, we see that
the number of pointmasses required scales quadratically in the dimension of
the latent Riemannian manifold.

######  Lemma 24 (Bi-Lipschitz Embeddings of Riemannian Datasets - For Compact
Manifolds)

Let $n,d\in{\mathbb{N}}_{+}$. Let $(M,g)$ be a $d$-dimensional Riemannian
manifold with geodesic distance $d_{g}$ and let $K\subseteq M$ be compact.
There exists a constant $C_{K}$ (depending only on $K$) such that for any
$\mathcal{X}_{n}\subseteq M$ if $d_{n}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}d_{g}|_{\mathcal{X}_{n}}$, then exists a map
$\varphi:(\mathcal{X}_{n},d_{n})\rightarrow(\mathcal{GM}_{2}({\mathbb{R}}),\mathcal{MW}_{2})$
of the form

$\varphi(x)=\frac{1}{2d}\sum_{k=1}^{2d}\,N_{1}(\phi(x)_{k},0);$

satisfying: for every $x,\tilde{x}\in\mathcal{X}$ the following holds

$d_{\mathcal{X}}(x,\tilde{x})\leq\mathcal{W}_{2}(\varphi(x),\varphi(\tilde{x}))\leq\mathcal{MW}_{2}(\varphi(x),\varphi(\tilde{x}))\leq
C\,C_{K}d_{\mathcal{X}}(x,\tilde{x});$

where $\phi:(\mathcal{X}_{n},d_{n})\rightarrow({\mathbb{R}}^{2d},\ell_{2})$ is
a class-$C^{1}$-(Riemannian) isometric embedding.

Proof [Proof of Lemma 24] Since $(M,g)$ is a Riemannian manifold then, (Nash,
1954, Theorem 2) implies that there exists a class-$C^{1}$ (Riemannian
isometric embedding)
$\phi:(M,d_{g})\hookrightarrow({\mathbb{R}}^{2d},\ell_{2})$. Since $\phi$ is a
class $C^{1}$ Riemannian isometric embedding, it is a diffeomorphism onto its
image and therefore, $\phi$ has a class $C^{1}$ inverse on $\phi(M)$ which we
denote by $\phi^{-1}$. Since $K$ is compact then and $\phi$ is continuous then
$\phi(K)$ is compact and therefore the following is finite

$C_{K}\stackrel{{\scriptstyle\mbox{\tiny def.}}}{{=}}\max\\{\max_{x\in
K}\,\|\nabla\phi(x)\|,\max_{x\in\phi(K)}\,\|\nabla\phi^{-1}(x)\|\\}.$

Therefore, by the Rademacher-Stepanov Theorem (Federer, 1978, Theorem 3.1.6)
we have that: for every $x,\tilde{x}\in K$

$d_{g}(x,\tilde{x})\leq\|\phi(x)-\phi(\tilde{x})\|\leq
C_{K}d_{g}(x,\tilde{x}).$ (51)

Since $\phi$ is class-$C^{1}$, it is continuous and since $\mathcal{X}_{n}$ is
a compact subset of $M$ (since it is finite) then by (Munkres, 2000, Theorem
26.5) $\phi(\mathcal{X}_{n})$ is a non-empty compact subset of
$({\mathbb{R}}^{2d},\ell_{2})$. By the Heine-Borel Theorem (Munkres, 2000,
Theorem 27.3), there exists some $r>0$ such that
$\phi(\mathcal{X}_{n})\subseteq\overline{\operatorname{Ball}_{({\mathbb{R}}^{2d},\ell_{2})}(0,r)}$
where
$\overline{\operatorname{Ball}_{({\mathbb{R}}^{2d},\ell_{2})}(0,r)}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{z\in{\mathbb{R}}^{2d}:\,\|z\|_{\ell_{2}}\leq r\\}.$

Since
$\phi(\mathcal{X}_{n})\subseteq\overline{\operatorname{Ball}_{({\mathbb{R}}^{2d},\ell_{2})}(0,r)}$
then (Kloeckner, 2010, Proposition 7.4) applies. More specifically, the proof
of (Kloeckner, 2010, Proposition 7.4) (see the comment in (Bertrand and
Kloeckner, 2012, Example 5.5)) guarantee that there exists some
$b\in{\mathbb{R}}^{2d}$ (that can be built explicitly via Algorithm 1 in
Section C) such that the map

$\iota:(\overline{\operatorname{Ball}_{({\mathbb{R}}^{2d},\ell_{2})}(0,r)},\ell_{2})\ni
x\mapsto\frac{1}{2d}\sum_{k=1}^{2d}\,\delta_{\sqrt{2d}(x+b)_{k}}\in(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2}),$

is an isometry. Combining the two maps, we find that the composite map

$\varphi:(\mathcal{X}_{n},d_{g})\ni
x\mapsto\frac{1}{2d}\sum_{k=1}^{2d}\,\delta_{\sqrt{2d}(\phi(x)+b)_{k}}\in(\mathcal{P}_{2}(\mathbb{R}),\mathcal{W}_{2}),$

is an isometry. As in the proof of Lemma 23, since $\iota\circ\phi$ is has
range in the set of “degenerate Gaussian mixtures”
$\mathcal{Z}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{{\mathbb{P}}\in\mathcal{GM}_{2}({\mathbb{R}}^{d}):\,\exists
N\in{\mathbb{N}}_{+}\,\exists
w\in\Delta_{N}\,\exists\mu_{1},\dots,\mu_{N}\in{\mathbb{R}}^{d}\,s.t.\,{\mathbb{P}}=\sum_{n=1}^{N}\,w_{n}\delta_{\mu_{n}}\\}$
then, we obtain the conclusion by applying the comparison result in (Delon and
Desolneux, 2020, Proposition 6) which states that the “identity map” on
$(\mathcal{W}_{2}({\mathbb{R}}),\mathcal{W}_{2})\ni{\mathbb{P}}\mapsto{\mathbb{P}}\in(\mathcal{GM}_{2}({\mathbb{R}}),\mathcal{MW}_{2})$
is an isometry between on the collection of finitely supported probability
measures in $\mathcal{Z}$. Relabeling $\phi$ as $\phi(\cdot)+b$ yields the
conclusion.

Proof [Proof of Proposition 8] The result is directly follows from Lemma 17
applied to the map $\varphi$ of Lemma 24 and relabeling $C\,C_{K}$ as $C_{K}$.

####  B.5.2 Proof of Corollaries to Main Results

Proof [Proof of Corollary 12] We only upper-bound
$\mathrm{cap}(\mathcal{X}_{n})$ in order to apply Theorem 4. By Lemma 21
$\log(\mathrm{cap}(\mathcal{X}_{n},d_{n}))\leq 12\log(c_{\mu})$ for any
doubling measure $\mu$ on $(\mathcal{X}_{n},d_{n})$. Since
$(\mathcal{X}_{n},d_{n})$ is the metric space associated to a (finite)
combinatorial graph in which every two vertices are connected by at most $2$
edges then, (Durand-Cartagena et al., 2021, Theorem 5, Proposition 18, and
Proposition 19) we know that $c_{\mu}=1+\rho(A_{V})$. Note also that
$\operatorname{aspect}(\mathcal{X}_{n},d_{n})=\operatorname{diam}(\mathcal{X}_{n},d_{n})$
since the shortest distance between any two points in a combinatorial (metric)
graph is $1$. Thus, $\log(\mathrm{cap}(\mathcal{X}_{n},d_{n}))\leq
12\log(1+\rho(A_{V}))$ and the result now follows from Theorem 4.

Proof [Proof of Corollary 9] As argued in (Baudoin and Garofalo, 2011, pages
1121-1122), the complete $d$-dimensional Riemannian manifold $(M,g)$ satisfies
the curvature-dimension inequality of (2) for some $r\in{\mathbb{R}}$ if and
only if $(M,g)$’s Ricci curvature tensor ((Jost, 2017, Definition 4.3.3)) is
uniformly lower-bounded by $r$. As demonstrated in (Baudoin and Garofalo,
2011, Equation (1.1)) the lower Ricci-cuvature bound on $(M,g)$ together with
the Bishop-Gromov Volume Comparison Theorem (e.g. see (Chavel, 1993, Theorem
3.10)) implies that $c_{d_{n}}\leq d$. Therefore, (Bruè et al., 2021,
Proposition 1.7 (ii)) implies that
$\log(\mathrm{cap}(\mathcal{X}_{n},d_{n}))\leq 3\log(c_{d_{n}})$. The result
therefore follows from Theorem 4.

####  B.5.3 Proof of Impossibility Results

Proof [Proof of Proposition 13]
Step 1 - A lower Bound when Embedding into Spaces of Markov type $p\geq 2$
On (Naor et al., 2006, page 173) the authors discuss that the proof of a
result in Linial et al. (2002) implies the following for any metric space
$\mathcal{R}$ of Markov type $2$ (see (Naor et al., 2006, Definition 1.1)). If
$\Gamma_{g,\delta}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}(X_{g,\delta},d_{g,\delta})$ is a graph (equipped with the usual
graph geodesic distance) in which the shortest loop has length at least $g>0$
(called $\Gamma_{g,\delta}$’s girth) and its average degree is $\delta>2$
then, any bi-Lipschitz embedding
$f:\Gamma_{g,\delta}\rightarrow(\mathcal{R},d_{\mathcal{R}})$ (here $s=1$) has
distortion $\operatorname{Dist}(f)$ at-least

$\operatorname{Dist}(f)\geq\frac{\delta-2}{2\,M_{p}(\mathcal{R})}g^{(p-1)/p},$
(52)

where $p$ is the Markov-type of $(\mathcal{R},d_{\mathcal{R}})$ as defined by
in (Ball, 1992, Definition 1.1) and $M_{p}(\mathcal{R})>0$ is a constant
depending only on $\mathcal{R}$’s geometry.

Step 2 - Markov Type of $(M,g)$
Let $(\mathcal{R},d_{\mathcal{R}})\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}(M,d_{g})$ where $(M,g)$ is a complete Riemannian manifold with
sectional curvature pinched between $[-C,-c]$ for some $0<c\leq C<\infty$.
Therefore, (Naor et al., 2006, Corollary 6.5) applies implying that
$(M,d_{g})$ has Markov type $p=2$.

Step 3 - Realizing the Diverging Lower-Bound via Sextet Graphs
The main result of Weiss (1984) shows that, for every prime integer $n>2$
satisfying $n\bmod 16\in\\{\pm 3,\pm 5,\pm 7\\}$, the sextet graph with $n$
vertices is a cubic graph (i.e. each vertex has exactly $3$ edges connected to
it and therefore $\delta=3>2$) and its girth $g$ is at-least
$\frac{4}{3}\log_{2}(n)-2$. Therefore, setting $\Gamma_{g,\delta}$ to be the
sextet graph with $n$-vertices we deduce from (52) and step 2 that any bi-
Lipschitz embedding $f:\Gamma_{g,\delta}\rightarrow\mathcal{R}$ satisfies

$\operatorname{Dist}(f)\geq\frac{1}{2\,M_{p}(\mathcal{R})}\sqrt{\frac{4}{3}\log_{2}(n)-2}.$

Setting $c_{\mathcal{R}}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\frac{1}{2\,M_{p}(\mathcal{R})}$ yields the conclusion.

Proof [Proof of Proposition 15] We argue by contradiction. Assume that
$\mathcal{R}$ is a Riemannian manifold which is bi-Lipschitz embedded in the
Hilbert space $\ell^{2}$ with distortion $D_{1}$; denote this bi-Lipschitz
embedding by $\psi:(\mathcal{R},g)\hookrightarrow(\mathbb{R}^{2d},\ell_{2})$
and with the property that: for every $n\in{\mathbb{N}}_{+}$ there is no
$n$-point metric space $(\mathcal{X}_{n},d_{n})$ which can be bi-Lipschitz
embedded in $(\mathcal{R},d_{g})$ with distortion
$D_{2}\left(\frac{\log(n)}{\log(\log(n))}\right)$ (here $D_{2}$ is a constant
depending only on $\mathcal{R}$).

Therefore, for every $n$-point metric space $(\mathcal{X}_{n},d_{n})$ there
exists a bi-Lipschitz embedding
$\phi:(\mathcal{X}_{n},d_{n})\hookrightarrow(\mathcal{R},d_{g})$ whose
distortion $D$ is less than $D_{2}\frac{\log(n)}{\log(\log(n))}$. Thus
$\psi\circ\phi:\mathcal{X}_{n}\rightarrow\ell^{2},$ is a bi-Lipschitz
embedding with at-least distortion $D_{1}D_{2}$. Thus, for $n$ large enough
there is an $n$-point metric space which bi-Lipschitz embeds into
$(\ell^{2},\ell_{2})$ with distortion less than
$\mathcal{O}\left(\frac{\log(n)}{\log(\log(n))}\right)$. This is a
contradiction of a main result of Bourgain (1985). Whence, $(\mathcal{R},g)$
does not exist.

##  Appendix C Algorithmic Construction of the “Bias Term” in our Embeddings’
Proofs

This short appendix contains an explicit algorithmic construction of the shift
(or “bias term”), denoted by $b$, used when embedding a bounded Euclidean ball
into the Wasserstein space. The term $b\in{\mathbb{R}}^{d}$ maps the Euclidean
ball into the space $\mathbb{R}_{<}^{d}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{x\in{\mathbb{R}}^{d}:\,x_{1}<\dots<x_{d}\\}$ used in (Bertrand
and Kloeckner, 2012, Example 5.5) and initially proposed in (Kloeckner, 2010,
Proposition 7.4) .

Algorithm 1 Initialize Bias

Set of $n$-vectors $\mathbb{X}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}\\{x^{(1)},\dots,x^{(n)}\\}$ in ${\mathbb{R}}^{K}$,

$b_{0}\stackrel{{\scriptstyle\mbox{\tiny def.}}}{{=}}0$ $\triangleright$
Initialize first shift

for $n=1,\dots,N$ do $\tilde{x}^{n}_{1}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}x_{1}^{(n)}+b_{1}$ $\triangleright$ Dummy vectors

end for

for $k=1,\dots,K$ do $\triangleright$ Iteratively build bias components

$b_{k}\stackrel{{\scriptstyle\mbox{\tiny def.}}}{{=}}\max_{n\leq
N}\,\operatorname{ReLU}(x_{k-1}^{(n)}-x_{k-1}^{(n)})$

for $n\leq N$ do $\tilde{x}^{n}_{k}\stackrel{{\scriptstyle\mbox{\tiny
def.}}}{{=}}x_{k}^{(n)}+b_{k}$ $\triangleright$ Dummy vectors

end for

end for

return $b\stackrel{{\scriptstyle\mbox{\tiny def.}}}{{=}}(b_{1},\dots,b_{K})$
$\triangleright$ Return Bias)

## References

  * Acciaio et al. (2020) B. Acciaio, J. Backhoff-Veraguas, and A. Zalashko.  Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimization.  _Stochastic Process. Appl._ , 130(5):2918–2953, 2020.  URL https://doi.org/10.1016/j.spa.2019.08.009.
  * Acciaio et al. (2022) Beatrice Acciaio, Anastasis Kratsios, and Gudmund Pammer.  Metric hypertransformers are universal adapted maps.  _ArXiV_ , 2022.
  * Agarwal and Niyogi (2009) Shivani Agarwal and Partha Niyogi.  Generalization bounds for ranking algorithms via algorithmic stability.  _J. Mach. Learn. Res._ , 10:441–474, 2009.  ISSN 1532-4435.
  * Amari (2016) Shun-ichi Amari.  Information geometry and its applications.  194:xiii+374, 2016.
  * Andoni et al. (2018) Alexandr Andoni, Assaf Naor, and Ofer Neiman.  Snowflake universality of Wasserstein spaces.  _Ann. Sci. Éc. Norm. Supér. (4)_ , 51(3):657–700, 2018.
  * Assouad (1979) Patrice Assouad.  Étude d’une dimension métrique liée à la possibilité de plongements dans ${\bf R}^{n}$.  _C. R. Acad. Sci. Paris Sér. A-B_ , 288(15):A731–A734, 1979.
  * Backhoff et al. (2022) Julio Backhoff, Daniel Bartl, Mathias Beiglböck, and Johannes Wiesel.  Estimating processes in adapted Wasserstein distance.  _Ann. Appl. Probab._ , 32(1):529–550, 2022.
  * Backhoff-Veraguas and Pammer (2022a) J. Backhoff-Veraguas and G. Pammer.  Stability of martingale optimal transport and weak optimal transport.  _Ann. Appl. Probab._ , 32(1):721–752, 2022a.  URL https://doi.org/10.1214/21-aap1694.
  * Backhoff-Veraguas and Pammer (2022b) J. Backhoff-Veraguas and G. Pammer.  Stability of martingale optimal transport and weak optimal transport.  _Ann. Appl. Probab._ , 32(1):721–752, 2022b.
  * Backhoff-Veraguas et al. (2020a) Julio Backhoff-Veraguas, Daniel Bartl, Mathias Beiglböck, and Manu Eder.  All adapted topologies are equal.  _Probab. Theory Related Fields_ , 178(3-4):1125–1172, 2020a.  ISSN 0178-8051.  URL https://doi.org/10.1007/s00440-020-00993-8.
  * Backhoff-Veraguas et al. (2020b) Julio Backhoff-Veraguas, Daniel Bartl, Mathias Beiglböck, and Manu Eder.  All adapted topologies are equal.  _Probab. Theory Related Fields_ , 178(3-4):1125–1172, 2020b.
  * Ball (1992) Keith Ball.  Markov chains, riesz transforms and lipschitz maps.  _Geometric & Functional Analysis GAFA_, 2(2):137–172, 1992.
  * Bartal et al. (2005) Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor.  On metric Ramsey-type phenomena.  _Ann. of Math. (2)_ , 162(2):643–709, 2005.  URL https://doi.org/10.4007/annals.2005.162.643.
  * Bartlett and Long (2021) Peter L. Bartlett and Philip M. Long.  Failures of model-dependent generalization bounds for least-norm interpolation.  _J. Mach. Learn. Res._ , 22:Paper No. 204, 15, 2021.  ISSN 1532-4435.
  * Bartlett et al. (2017) Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  _Advances in neural information processing systems_ , 30, 2017.
  * Bartlett et al. (2019) Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian.  Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks.  _Journal of Machine Learning Research_ , 20(63):1–17, 2019.  URL http://jmlr.org/papers/v20/17-612.html.
  * Baudoin and Garofalo (2011) Fabrice Baudoin and Nicola Garofalo.  Perelman’s entropy and doubling property on Riemannian manifolds.  _J. Geom. Anal._ , 21(4):1119–1131, 2011.  URL https://doi.org/10.1007/s12220-010-9180-x.
  * Baudoin et al. (2014) Fabrice Baudoin, Michel Bonnefont, and Nicola Garofalo.  A sub-Riemannian curvature-dimension inequality, volume doubling property and the Poincaré inequality.  _Math. Ann._ , 358(3-4):833–860, 2014.  URL https://doi.org/10.1007/s00208-013-0961-y.
  * Beiglböck et al. (2017a) Mathias Beiglböck, Pierre Henry-Labordère, and Nizar Touzi.  Monotone martingale transport plans and Skorokhod embedding.  _Stochastic Process. Appl._ , 127(9):3005–3013, 2017a.  URL https://doi.org/10.1016/j.spa.2017.01.004.
  * Beiglböck et al. (2017b) Mathias Beiglböck, Marcel Nutz, and Nizar Touzi.  Complete duality for martingale optimal transport on the line.  _Ann. Probab._ , 45(5):3038–3074, 2017b.
  * Belkin and Niyogi (2003) Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural computation_ , 15(6):1373–1396, 2003\.
  * Belkin and Niyogi (2006) Mikhail Belkin and Partha Niyogi.  Convergence of laplacian eigenmaps.  _Advances in neural information processing systems_ , 19, 2006.
  * Bertrand and Kloeckner (2012) Jérôme Bertrand and Benoît Kloeckner.  A geometric study of Wasserstein spaces: Hadamard spaces.  _J. Topol. Anal._ , 4(4):515–542, 2012.  URL https://doi.org/10.1142/S1793525312500227.
  * Biggs and Hoare (1983) Norman L Biggs and MJ Hoare.  The sextet construction for cubic graphs.  _Combinatorica_ , 3(2):153–165, 1983.
  * Bigot et al. (2017) Jérémie Bigot, Raúl Gouet, Thierry Klein, and Alfredo López.  Geodesic PCA in the Wasserstein space by convex PCA.  _Ann. Inst. Henri Poincaré Probab. Stat._ , 53(1):1–26, 2017.  URL https://doi.org/10.1214/15-AIHP706.
  * Bilokopytov and Kratsios (2020) Eugene Bilokopytov and Anastasis Kratsios.  Non-Euclidean Universal Approximation.  _NeurIPS_ , 33, 2020.
  * Bion-Nadal and Talay (2019) Jocelyne Bion-Nadal and Denis Talay.  On a Wasserstein-type distance between solutions to stochastic differential equations.  _Ann. Appl. Probab._ , 29(3):1609–1639, 2019\.  URL https://doi.org/10.1214/18-AAP1423.
  * Bishop (1994) Christopher M Bishop.  Mixture density networks.  _Unpublished_ , 1994.
  * Bourgain (1985) J. Bourgain.  On Lipschitz embedding of finite metric spaces in Hilbert space.  _Israel J. Math._ , 52(1-2):46–52, 1985.
  * Bruè et al. (2021) Elia Bruè, Simone Di Marino, and Federico Stra.  Linear Lipschitz and $C^{1}$ extension operators through random projection.  _J. Funct. Anal._ , 280(4):Paper No. 108868, 21, 2021.  URL https://doi.org/10.1016/j.jfa.2020.108868.
  * Bubeck et al. (2020) Sebastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer.  Network size and size of the weights in memorization with two-layers neural networks.  33:4977–4986, 2020.
  * Buckley and Harary (1988) Fred Buckley and Frank Harary.  On the Euclidean dimension of a wheel.  _Graphs Combin._ , 4(1):23–30, 1988.  URL https://doi.org/10.1007/BF01864150.
  * Burger and Neubauer (2001) Martin Burger and Andreas Neubauer.  Error bounds for approximation with neural networks.  _J. Approx. Theory_ , 112(2):235–250, 2001.
  * Chami et al. (2020) Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré.  From trees to continuous embeddings and back: Hyperbolic hierarchical clustering.  _Advances in Neural Information Processing Systems_ , 33:15065–15076, 2020.  URL https://dl.acm.org/doi/abs/10.5555/3495724.3496987.
  * Chami et al. (2021) Ines Chami, Albert Gu, Dat P Nguyen, and Christopher Ré.  Horopca: Hyperbolic dimensionality reduction via horospherical projections.  In _International Conference on Machine Learning_ , pages 1419–1429. PMLR, 2021.
  * Chavel (1993) Isaac Chavel.  Riemannian geometry-a modern introduction.  108:xii+386, 1993.
  * Chen et al. (2021) Yaqing Chen, Zhenhua Lin, and Hans-Georg Müller.  Wasserstein regression.  _Journal of the American Statistical Association_ , pages 1–14, 2021\.
  * Cheridito et al. (2021) Patrick Cheridito, Arnulf Jentzen, and Florian Rossmannek.  Efficient approximation of high-dimensional functions with neural networks.  _IEEE Transactions on Neural Networks and Learning Systems_ , pages 1–15, 2021.
  * Chevallier (2018) Julien Chevallier.  Uniform decomposition of probability measures: quantization, clustering and rate of convergence.  _Journal of Applied Probability_ , 55(4):1037–1045, 2018.
  * Costa et al. (2015) Sueli I.R. Costa, Sandra A. Santos, and João E. Strapasson.  Fisher information distance: A geometrical reading.  _Discrete Applied Mathematics_ , 197:59–69, 2015.  Distance Geometry and Applications.
  * Cruceru et al. (2020) Calin Cruceru, Gary Becigneul, and Octavian-Eugen Ganea.  Computationally tractable riemannian manifolds for graph embeddings.  _arXiv preprint arXiv:2002.08665_ , 2020.
  * Cruceru et al. (2021) Calin Cruceru, Gary Becigneul, and Octavian-Eugen Ganea.  Computationally tractable riemannian manifolds for graph embeddings.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(8):7133–7141, May 2021.  URL https://ojs.aaai.org/index.php/AAAI/article/view/16877.
  * Cuesta and Matran (1989) Juan Antonio Cuesta and Carlos Matran.  Notes on the wasserstein metric in hilbert spaces.  _The Annals of Probability_ , 17(3):1264–1276, 1989.  ISSN 00911798.  URL http://www.jstor.org/stable/2244406.
  * Dai and Müller (2018) Xiongtao Dai and Hans-Georg Müller.  Principal component analysis for functional data on Riemannian manifolds and spheres.  _Ann. Statist._ , 46(6B):3334–3361, 2018.
  * Daniely (2020) Amit Daniely.  Neural networks learning and memorization with (almost) no over-parameterization.  33:9007–9016, 2020.
  * Das and Kumar (2004) Kinkar Ch. Das and Pawan Kumar.  Some new bounds on the spectral radius of graphs.  _Discrete Math._ , 281(1-3):149–161, 2004.  ISSN 0012-365X.
  * Debarnot and Weiss (2022) Valentin Debarnot and Pierre Weiss.  Deep-blur : Blind identification and deblurring with convolutional neural networks.  June 2022.
  * Delon and Desolneux (2020) Julie Delon and Agnès Desolneux.  A Wasserstein-type distance in the space of Gaussian mixture models.  _SIAM Journal on Imaging Sciences_ , 13(2):936–970, 2020.
  * Delon and Desolneux (2021) Julie Delon and Agnès Desolneux.  Optimal transport between gaussian mixture models.  https://github.com/judelo/gmmot, 2021.
  * Dhingra et al. (2018) Bhuwan Dhingra, Christopher J. Shallue, Mohammad Norouzi, Andrew M. Dai, and George E. Dahl.  Embedding text in hyperbolic spaces.  _TextGraphs@NAACL-HLT_ , pages 59–69, 2018.
  * Dolinsky and Soner (2014) Yan Dolinsky and H. Mete Soner.  Martingale optimal transport and robust hedging in continuous time.  _Probab. Theory Related Fields_ , 160(1-2):391–427, 2014.  ISSN 0178-8051.
  * Dowty (2018) James G. Dowty.  Chentsov’s theorem for exponential families.  _Inf. Geom._ , 1(1):117–135, 2018.
  * Durand-Cartagena et al. (2021) Estibalitz Durand-Cartagena, Javier Soria, and Pedro Tradacete.  Doubling constants and spectral theory on graphs.  _arXiv preprint arXiv:2111.09199_ , 2021.
  * Dvoretzky (1961) Aryeh Dvoretzky.  Some results on convex bodies and Banach spaces.  pages 123–160, 1961.
  * E. and Wojtowytsch (2022) Weinan E. and Stephan Wojtowytsch.  Representation formulas and pointwise properties for Barron functions.  _Calc. Var. Partial Differential Equations_ , 61(2):Paper No. 46, 37, 2022.
  * Eidi and Jost (2020) Marzieh Eidi and Jürgen Jost.  Ollivier Ricci curvature of directed hypergraphs.  _Scientific Reports_ , 10(1):12466, 2020.
  * Erdős (1964/65) P. Erdős.  On an extremal problem in graph theory.  _Colloq. Math._ , 13:251–254, 1964/65.  ISSN 0010-1354.
  * Erdős et al. (1966) P. Erdős, A. Rényi, and V. T. Sós.  On a problem of graph theory.  _Studia Sci. Math. Hungar._ , 1:215–235, 1966.  ISSN 0081-6906.
  * Erdös and Sachs (1963) Paul Erdös and Horst Sachs.  Regukre graphen gegebener taillenweite mit minimaler knotenzahl.  _Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle_ , pages 251–258, 1963.
  * Eriksson-Bique (2018) Sylvester Eriksson-Bique.  Quantitative bi-Lipschitz embeddings of bounded-curvature manifolds and orbifolds.  _Geometry & Topology_, 22(4):1961–2026, 2018\.
  * Falconer (1986) K. J. Falconer.  The geometry of fractal sets, 1986.
  * Federer (1978) Herbert Federer.  Colloquium lectures on geometric measure theory.  _Bull. Amer. Math. Soc._ , 84(3):291–338, 1978\.
  * Feldman and Zhang (2020) Vitaly Feldman and Chiyuan Zhang.  What neural networks memorize and why: Discovering the long tail via influence estimation.  33:2881–2891, 2020.
  * Flamary et al. (2021) Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer.  POT: Python optimal transport.  _Journal of Machine Learning Research_ , 22(78):1–8, 2021.  URL http://jmlr.org/papers/v22/20-451.html.
  * Fletcher et al. (2009) P. Thomas Fletcher, Suresh Venkatasubramanian, and Sarang Joshi.  The geometric median on riemannian manifolds with application to robust atlas estimation.  _NeuroImage_ , 45(1):S143 – S152, 2009.  Mathematics in Brain Imaging.
  * Fréchet (1906) M Maurice Fréchet.  Sur quelques points du calcul fonctionnel.  _Rendiconti del Circolo Matematico di Palermo (1884-1940)_ , 22(1):1–72, 1906.
  * Ganea et al. (2018) Octavian Ganea, Gary Becigneul, and Thomas Hofmann.  Hyperbolic neural networks.  _Advances in Neural Information Processing Systems_ , 31:5345–5355, 2018.  URL https://proceedings.neurips.cc/paper/2018/file/dbab2adc8f9d078009ee3fa810bea142-Paper.pdf.
  * Giovanni et al. (2022) Francesco Di Giovanni, Giulia Luise, and Michael Bronstein.  Heterogeneous manifolds for curvature-aware graph embedding.  _ArXiV_ , 2022.
  * Graf and Luschgy (2000) Siegfried Graf and Harald Luschgy.  Foundations of quantization for probability distributions.  1730:x+230, 2000.
  * Guo and Obł ój (2019) Gaoyue Guo and Jan Obł ój.  Computational methods for martingale optimal transport problems.  _Ann. Appl. Probab._ , 29(6):3311–3347, 2019\.
  * Gupta (2000) A. Gupta.  Embedding tree metrics into low-dimensional Euclidean spaces.  _Discrete Comput. Geom._ , 24(1):105–116, 2000\.
  * Heinonen (2001) Juha Heinonen.  Lectures on analysis on metric spaces, 2001.
  * Heinonen (2003) Juha Heinonen.  Geometric embeddings of metric spaces, 2003.
  * Hopf and Rinow (1931) H. Hopf and W. Rinow.  Ueber den Begriff der vollständigen differentialgeometrischen Fläche.  _Comment. Math. Helv._ , 3(1):209–225, 1931.
  * Jost (2017) Jürgen Jost.  Riemannian geometry and geometric analysis, 2017.
  * Jung (1901) Heinrich Jung.  Ueber die kleinste kugel, die eine räumliche figur einschliesst.  _Journal für die reine und angewandte Mathematik_ , 123:241–257, 1901.  URL http://eudml.org/doc/149122.
  * Jungerman and Ringel (1978) Mark Jungerman and Gerhard Ringel.  The genus of the $n$-octahedron: regular cases.  _J. Graph Theory_ , 2(1):69–75, 1978.  ISSN 0364-9024.
  * Katz and Katz (2011) Karin Usadi Katz and Mikhail G. Katz.  Bi-Lipschitz approximation by finite-dimensional imbeddings.  _Geom. Dedicata_ , 150:131–136, 2011.
  * Kidger and Lyons (2020) Patrick Kidger and Terry Lyons.  Universal approximation with deep narrow networks.  125:2306–2327, 09–12 Jul 2020.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.
  * Kloeckner (2010) Benoît Kloeckner.  A geometric study of Wasserstein spaces: Euclidean spaces.  _Ann. Sc. Norm. Super. Pisa Cl. Sci. (5)_ , 9(2):297–323, 2010.  URL https://doi.org/10.2422/2036-2145.2010.2.03.
  * Kloeckner (2012) Benoît Kloeckner.  Approximation by finitely supported measures.  _ESAIM Control Optim. Calc. Var._ , 18(2):343–359, 2012.
  * Kloeckner and Bertrand (2016) Benoît R Kloeckner and Jérome Bertrand.  A geometric study of wasserstein spaces: isometric rigidity in negative curvature.  _International Mathematics Research Notices_ , 2016(5):1368–1386, 2016.
  * Kochurov et al. (2020) Max Kochurov, Rasul Karimov, and Serge Kozlukov.  Geoopt: Riemannian optimization in pytorch.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , Virtual, 13–18 Jul 2020. PMLR.
  * Kolyvakis et al. (2020) Prodromos Kolyvakis, Alexandros Kalousis, and Dimitris Kiritsis.  Hyperbolic knowledge graph embeddings for knowledge base completion.  In _European Semantic Web Conference_ , pages 199–214. Springer, 2020\.
  * Kratsios (2022) Anastasis Kratsios.  Universal regular conditional distributions.  _Constructive Approximation (minor revisions)_ , 2022.
  * Kratsios and Papon (2022) Anastasis Kratsios and Léonie Papon.  Universal approximation theorems for differentiable geometric deep learning.  _Journal of Machine Learning Research_ , 23:1–73, 2022\.
  * Kratsios et al. (2022) Anastasis Kratsios, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić.  Universal approximation under constraints is possible with transformers.  In _International Conference on Learning Representations_ , 2022.
  * Krauthgamer et al. (2005) R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor.  Measured descent: a new embedding method for finite metrics.  _Geom. Funct. Anal._ , 15(4):839–858, 2005.
  * Krioukov et al. (2010) Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná.  Hyperbolic geometry of complex networks.  _Physical Review E_ , 82(3):036106, 2010.
  * Le et al. (2019) Matt Le, Stephen Roller, Laetitia Papaxanthos, Douwe Kiela, and Maximilian Nickel.  Inferring concept hierarchies from text corpora via hyperbolic embeddings.  _ArXiV_ , 2019.
  * Le Donne and Rajala (2015) Enrico Le Donne and Tapio Rajala.  Assouad dimension, nagata dimension, and uniformly close metric tangents.  _Indiana University Mathematics Journal_ , pages 21–54, 2015.
  * Linial et al. (2002) N. Linial, A. Magen, and A. Naor.  Girth and Euclidean distortion.  _Geom. Funct. Anal._ , 12(2):380–394, 2002.
  * Liu and Neufeld (2019) Chong Liu and Ariel Neufeld.  Compactness criterion for semimartingale laws and semimartingale optimal transport.  _Trans. Amer. Math. Soc._ , 372(1):187–231, 2019\.
  * Liu and Pagès (2020) Yating Liu and Gilles Pagès.  Convergence rate of optimal quantization and application to the clustering performance of the empirical measure.  _Journal of Machine Learning Research_ , 21(86):1–36, 2020.  URL http://jmlr.org/papers/v21/18-804.html.
  * López and Strube (2020) Federico López and Michael Strube.  A fully hyperbolic neural model for hierarchical multi-class classification.  _ArXiV_ , 2020.
  * Lopez et al. (2021) Federico Lopez, Beatrice Pozzetti, Steve Trettel, Michael Strube, and Anna Wienhard.  Symmetric spaces for graph embeddings: A finsler-riemannian approach.  139:7090–7101, 18–24 Jul 2021.
  * Margulis (1982) Grigorii A Margulis.  Explicit constructions of graphs without short cycles and low density codes.  _Combinatorica_ , 2(1):71–78, 1982.
  * Margulis (1988) Grigorii Aleksandrovich Margulis.  Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators.  _Problemy peredachi informatsii_ , 24(1):51–60, 1988.
  * Matoušek (2013) Jirı Matoušek.  Lecture notes on metric embeddings.  Technical report, Technical report, ETH Zürich, 2013.
  * Matoušek (1996) Jiří Matoušek.  On the distortion required for embedding finite metric spaces into normed spaces.  _Israel J. Math._ , 93:333–344, 1996.  ISSN 0021-2172.
  * Matoušek (2002) Jiří Matoušek.  Lectures on discrete geometry.  212:xvi+481, 2002.
  * Mei and Montanari (2022) Song Mei and Andrea Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  _Comm. Pure Appl. Math._ , 75(4):667–766, 2022\.
  * Mei et al. (2022) Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration.  _Appl. Comput. Harmon. Anal._ , 59:3–84, 2022.
  * Mi et al. (2018) Liang Mi, Wen Zhang, Xianfeng Gu, and Yalin Wang.  Variational wasserstein clustering.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 322–337, 2018.
  * Miolane et al. (2020) Nina Miolane, Nicolas Guigui, Alice Le Brigant, Johan Mathe, Benjamin Hou, Yann Thanwerdas, Stefan Heyder, Olivier Peltre, Niklas Koep, Hadi Zaatiti, Hatem Hajri, Yann Cabanes, Thomas Gerald, Paul Chauchat, Christian Shewmake, Daniel Brooks, Bernhard Kainz, Claire Donnat, Susan Holmes, and Xavier Pennec.  Geomstats: A python package for Riemannian geometry in machine learning.  _Journal of Machine Learning Research_ , 21(223):1–9, 2020.  URL http://jmlr.org/papers/v21/19-027.html.
  * Munkres (2000) James R. Munkres.  Topology, 2000.  Second edition.
  * Munzner (1997) Tamara Munzner.  H3: Laying out large directed graphs in 3d hyperbolic space.  In _Proceedings of VIZ’97: Visualization Conference, Information Visualization Symposium and Parallel Rendering Symposium_ , pages 2–10. IEEE, 1997\.
  * Muscoloni et al. (2017) Alessandro Muscoloni, Josephine Maria Thomas, Sara Ciucci, Ginestra Bianconi, and Carlo Vittorio Cannistraci.  Machine learning meets complex networks via coalescent embedding in the hyperbolic space.  _Nature communications_ , 8(1):1–19, 2017.
  * Naor (2015) Assaf Naor.  Metric embeddings and lipschitz extensions.  _Princeton University, Department of Mathematics_ , 2015.
  * Naor (2018) Assaf Naor.  Metric dimension reduction: a snapshot of the Ribe program.  pages 759–837, 2018.
  * Naor and Neiman (2012) Assaf Naor and Ofer Neiman.  Assouad’s theorem with dimension independent of the snowflaking.  _Revista Matematica Iberoamericana_ , 28(4):1123–1142, 2012.
  * Naor and Tao (2012) Assaf Naor and Terence Tao.  Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem.  _Israel J. Math._ , 192(1):489–504, 2012.  ISSN 0021-2172.
  * Naor et al. (2006) Assaf Naor, Yuval Peres, Oded Schramm, and Scott Sheffield.  Markov chains in smooth banach spaces and gromov-hyperbolic metric spaces.  _Duke Mathematical Journal_ , 134(1):165–197, 2006.
  * Nash (1954) John Nash.  $C^{1}$ isometric imbeddings.  _Ann. of Math. (2)_ , 60:383–396, 1954.
  * Neyshabur et al. (2015) Behnam Neyshabur, Russ R Salakhutdinov, and Nati Srebro.  Path-sgd: Path-normalized optimization in deep neural networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Nickel and Kiela (2017) Maximillian Nickel and Douwe Kiela.  Poincaré embeddings for learning hierarchical representations.  _Advances in neural information processing systems_ , 30, 2017.
  * Orlin (1988) James Orlin.  A faster strongly polynomial minimum cost flow algorithm.  In _Proceedings of the Twentieth annual ACM symposium on Theory of Computing_ , pages 377–387, 1988.
  * Ostrovskii (2013) Mikhail I. Ostrovskii.  Metric embeddings.  49:xii+372, 2013.  Bilipschitz and coarse embeddings into Banach spaces.
  * Pansu (1989) Pierre Pansu.  Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un.  _Ann. of Math. (2)_ , 129(1):1–60, 1989.  ISSN 0003-486X.
  * Park et al. (2020) S. Park, C. Yun, J. Lee, and J. Shin.  Minimum width for universal approximation, 2020.
  * Park et al. (2021) Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin.  Provable memorization via deep neural networks using sub-linear parameters.  134:3627–3661, 15–19 Aug 2021.
  * Pflug and Pichler (2015) Georg Ch. Pflug and Alois Pichler.  Dynamic generation of scenario trees.  _Comput. Optim. Appl._ , 62(3):641–668, 2015\.
  * Puthawala et al. (2022) Michael Puthawala, Konik Kothari, Matti Lassas, Ivan Dokmanić, and Maarten de Hoop.  Globally injective ReLU networks.  _Journal of Machine Learning Research_ , 23:1–55, 2022\.
  * Ravasz and Barabási (2003) Erzsébet Ravasz and Albert-László Barabási.  Hierarchical organization in complex networks.  _Physical review E_ , 67(2):026112, 2003.
  * Robinson (2006a) P. L. Robinson.  The sphere is not flat.  _The American Mathematical Monthly_ , 113(2):171–173, 2006a.  URL http://www.jstor.org/stable/27641870.
  * Robinson (2006b) PL Robinson.  The sphere is not flat.  _The American Mathematical Monthly_ , 113(2):171–173, 2006b.
  * Samal et al. (2018) Areejit Samal, R. P. Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost.  Comparative analysis of two discretizations of Ricci curvature for complex networks.  _Scientific Reports_ , 8(1):8650, 2018.
  * Sarkar (2011) Rik Sarkar.  Low distortion delaunay embedding of trees in hyperbolic plane.  In _International Symposium on Graph Drawing_ , pages 355–366. Springer, 2011.
  * Shen et al. (2021) Zuowei Shen, Haizhao Yang, and Shijun Zhang.  Deep network with approximation error being reciprocal of width to power of square root of depth.  _Neural Comput._ , 33(4):1005–1036, 2021.  ISSN 0899-7667.
  * Shimizu et al. (2021) Ryohei Shimizu, YUSUKE Mukuta, and Tatsuya Harada.  Hyperbolic neural networks++.  In _International Conference on Learning Representations_ , 2021.
  * Shkarin (2004) SA Shkarin.  Isometric embedding of finite ultrametric spaces in banach spaces.  _Topology and its Applications_ , 142(1-3):13–17, 2004.
  * Sontag (1997a) Eduardo D. Sontag.  Shattering all sets of ‘$k$’ points in “general position” requires $(k—1)/2$ parameters.  _Neural Computation_ , 9(2):337–348, 1997a.
  * Sontag (1997b) Eduardo D Sontag.  Shattering all sets of ‘k’points in “general position” requires (k—1)/2 parameters.  _Neural Computation_ , 9(2):337–348, 1997b.
  * Suzuki (2019) Taiji Suzuki.  Adaptivity of deep ReLU network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality.  _International Conference on Learning Representations_ , 2019.
  * Tabaghi and Dokmanić (2020) Puoya Tabaghi and Ivan Dokmanić.  Hyperbolic distance matrices.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1728–1738, 2020.
  * Tabaghi and Dokmanić (2021) Puoya Tabaghi and Ivan Dokmanić.  On procrustes analysis in hyperbolic space.  _IEEE Signal Processing Letters_ , 28:1120–1124, 2021.
  * Tabaghi et al. (2021) Puoya Tabaghi, Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenković.  Linear classifiers in product space forms.  _arXiv preprint arXiv:2102.10204_ , 2021.
  * Vardi et al. (2022) Gal Vardi, Gilad Yehudai, and Ohad Shamir.  On the optimal memorization power of ReLU neural networks.  _International Conference on Learning Representations_ , 2022.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  _International Conference on Learning Representations_ , 2018.
  * Vershynin (2020) Roman Vershynin.  Memory capacity of neural networks with threshold and rectified linear unit activations.  _SIAM Journal on Mathematics of Data Science_ , 2(4):1004–1033, 2020.
  * Vestfrid and Timan (1979) I. A. Vestfrid and A. F. Timan.  A universality property of Hilbert spaces.  _Dokl. Akad. Nauk SSSR_ , 246(3):528–530, 1979\.  ISSN 0002-3264.
  * Vol’berg and Konyagin (1987) A. L. Vol’berg and S. V. Konyagin.  On measures with the doubling condition.  _Izv. Akad. Nauk SSSR Ser. Mat._ , 51(3):666–675, 1987.
  * Waserstein (1969) Leonid Nisonovich Waserstein.  Markov processes over denumerable products of spaces, describing large systems of automata.  _Problemy Peredachi Informatsii_ , 5(3):64–72, 1969.
  * Weiss (1984) Alfred Weiss.  Girths of bipartite sextet graphs.  _Combinatorica_ , 4(2):241–245, 1984.
  * Yarotsky (2017) Dmitry Yarotsky.  Error bounds for approximations with deep ReLU networks.  _Neural Networks_ , 94:103 – 114, 2017.  ISSN 0893-6080.
  * Zheng et al. (2019) Shuxin Zheng, Qi Meng, Huishuai Zhang, Wei Chen, Nenghai Yu, and Tie-Yan Liu.  Capacity control of ReLU neural networks by basis-path norm.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):5925–5932, Jul. 2019.
  * Zhou (2020) Ding-Xuan Zhou.  Universality of deep convolutional neural networks.  _Applied and computational harmonic analysis_ , 48(2):787–794, 2020.
  * Zipf (1949) George Kingsley Zipf.  Human behavior and the principle of least effort.  pages 1–334, 1949.