# Central limit theorem for the Sliced 1-Wasserstein distance and the max-
Sliced 1-Wasserstein distance ∗

Xianliang Xu and Zhongyi Huang† Department of Mathematics, Tsinghua
University, Beijing 100084, China<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The Wasserstein distance has been an attractive tool in many fields. But due
to its high computational complexity and the phenomenon of the curse of
dimensionality in empirical estimation, various extensions of the Wasserstein
distance have been proposed to overcome the shortcomings such as the Sliced
Wasserstein distance. It enjoys a low computational cost and dimension-free
sample complexity, but there are few distributional limit results of it. In
this paper, we focus on Sliced 1-Wasserstein distance and its variant max-
Sliced 1-Wasserstein distance. We utilize the central limit theorem in Banach
space to derive the limit distribution for the Sliced 1-Wasserstein distance.
Through viewing the empirical max-Sliced 1-Wasserstein distance as a supremum
of an empirical process indexed by some function class, we prove that the
function class is $P$-Donsker under mild moment assumption. Moreover, for
computing Sliced $p$-Wasserstein distance based on Monte Carlo method, we
explore that how many random projections that can make sure the error small in
high probability. We also provide upper bound of the expected max-Sliced
1-Wasserstein between the true and the empirical probability measures under
different conditions and the concentration inequalities for max-Sliced
1-Wasserstein distance are also presented. As applications of the theory, we
utilize them for two-sample testing problems.

† Corresponding author.

∗ This work was partially supported by the NSFC Projects No. 12025104,
11871298, 81930119.

##  1\. Introduction

In many fields, it is fundamental to choose a proper distance to measure the
discrepancy between two probability measures. Comparing to Kullback-
Leibler(KL) divergence, $\chi^{2}$ statistic, the Wasserstein distance enjoys
better geometric properties by considering the underlying geometry of the
space. It has been employed successfully in statistics[1, 2, 3, 4], machine
learning[5, 6, 7, 8], computer graphics[9, 10]. However, there are also many
shortcomings that limit its practical applications. In the aspect of
computation, the computational cost is of order $\mathcal{O}(n^{3}\log n)$ for
discrete probability measure supported in points of size $n$. It becomes an
obstacle of applying the Wasserstein distance in many machine learning tasks.
Moreover, when true distributions are estimated from samples, the Wasserstein
distance suffers from the curse of dimensionality which means that the
convergence rate decays rapidly with dimension. Motivated by the fact that the
Wasserstein distance has a closed form in one dimension, the Sliced
Wasserstein distance has been proposed as an alternative to the original
Wasserstein distance via averaging the Wasserstein distance between the random
one-dimensional projections which follow the uniform distribution on the
sphere[11, 12]. And its variant max-Sliced Wasserstein distance which is the
maximum of the Wasserstein distance between the one-dimensional projections
has also gained much attention.

Recently, the Sliced Wasserstein distance and the max-Sliced Wasserstein
distance have been successfully applied in many tasks [13, 14, 15, 16, 17].
Their sample complexity doesn’t depend on the dimensionality[18] and they have
some similar properties as the Wasserstein distance. Several recent studies
have explored the limit distribution for the Wasserstein distance, but there
are few results for the Sliced Wasserstein distance and max-Sliced Wasserstein
distance. In this study, we derive distribution limits for them.

###  1.1. Contributions

Our contributions can be summarized as follows:

  * •

We derive the central limit theorem result for the Sliced 1-Wasserstein
distance based on the theory of probability in Banach space and the results of
convergence rate in empirical estimation. We also explore the number of random
projections that makes sure that Monte Carlo method has a small error in high
probability in computing Sliced $p$-Wasserstein distance.

  * •

We prove that the max-Sliced 1-Wasserstein distance between the true and the
empirical distributions is a supremum of an empirical process indexed by some
function class, which is $P$-Donsker when the ($4+\delta$)-th $(\delta>0)$
moment of the true distribution is finite. And the limit distribution of max-
Sliced 1-Wasserstein distance follows from the continuous mapping theorem.

  * •

We provide upper bound of expected max-Sliced 1-Wasserstein in empirical
estimation and verify that it doesn’t depend on the dimensionality. And the
concentration inequalities of max-Sliced 1-Wasserstein distance are also
presented.

  * •

We apply the Sliced 1-Wasserstein distance and the max-Sliced 1-Wasserstein in
the problem of two-sample testing.

###  1.2. Related works

In one dimension, [19] derived the limit distribution of the empirical
Wasserstein distance based on the central limit theorem in Banach space, more
specifically in $L^{1}(\mathbb{R})$. [20] explored the necessary and
sufficient conditions for $Lip_{1}(\mathbb{R})$ to be $P$-Donsker, thus the
limit distribution of empirical 1-Wasserstein distance follows from
Kantorovich-Rubinstein(KR) duality and continuous mapping theorem. [21]
provided asymptotic distribution for a weighted version of empirical
2-Wasserstein distance. [22] and [23] also consider the case in one dimension
under the $i.i.d.$ condition or non-$i.i.d.$ condition.

In general dimensions, combining Efron-Stein variance inequality and the
stability results of optimal transportation potentials, [24] showed that
$\sqrt{n}(W_{2}^{2}(P_{n},Q)-\mathbb{E}W_{2}^{2}(P_{n},Q))$ converges to a
zero-mean Gaussian distribution under that $P\neq Q$ and other moment
assumptions. And [25] sharpened their results in one dimension. Inspired by
[24], [26] obtained a central limit theorem of the form
$\sqrt{n}(W_{2}^{2}(P,Q_{n})-W_{2}^{2}(P,Q))\xrightarrow{d}N(0,\sigma^{2})$
under some regularity assumptions. When $P$ and $Q$ are supported in finite
points, [27] applied directional Hadamard differentiability theory to obtain
limit distribution by dealing the Wasserstein distance between $P$ and $Q$ as
a functional in finite dimensional space. And for $P$ and $Q$ supported in a
countable set, [28] derived limit distribution for empirical Wasserstein
distance based on the sensitivity of optimal values of infinite dimensional
mathematics programs and a delta method.

For extensions of original Wasserstein distance like Smooth Wasserstein
distance [29] and entropic regularization of OT(EOT) [30], a central limit
theorem for EOT was provided in [31] for probability measures with finite
support based on same technique in [27] (see also [32, 33]). By bounding the
entropy of the function class of Gaussian-smoothed Lipschitz functions and
Theorem 1.1 in [34], [35] showed that the function class is $P$-Donsker under
some conditions. [36] explored the limit distribution of projection-based
Wasserstein distance based on the same argument of [27] for distributions with
finite support. And [37] derived limit law of Sliced $p$-Wasserstein distance
under that $P\neq Q$ for all $p>1$ by Hadamard differentiability theory, but
it requires some regularity assumptions such as the absolutely continuity of
all one-dimension projections. The most similar to our work is the concurrent
work [37]. For Sliced 1-Wasserstein distance, we obtain the necessary and
sufficient conditions under which the central limit theorem holds and they
present only the sufficient condition. And by the method in [23] for
1-Wasserstein distance in one dimension, we derive the limit distribution for
Sliced 1-Wasserstein distance under weaker conditions than [37]. For max-
Sliced 1-Wasserstein distance, our construction of the bracketing cover of the
function class is different from their, our method is based on the bracketing
number of 1-Lipschitz continuous functions vanishing at zero and their method
is based on the covering number. The differences will be discussed in details
in the paper.

###  1.3. Notations

$\|\cdot\|$ denotes the Euclidean norm. The class of Borel probability measure
on $\mathbb{R}^{d}$ is denoted by $\mathcal{P}(\mathbb{R}^{d})$ and the set of
probability measure with finite moment of order $p$ is denoted by
$\mathcal{P}_{p}(\mathbb{R}^{d})$. Given a map
$T:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and a probability of
$\mathcal{P}(\mathbb{R}^{d})$, we write $T_{\\#}P$ for the pushforward of $P$
under $T$, which means that for any Borel set $A\subset\mathbb{R}^{d}$ we have
$T_{\\#}P(A)=P(T^{-1}(A))$. For $A\in\mathbb{R}^{m\times n}$, define real-
valued function $A^{*}:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ with
$A^{*}(x)=A^{T}x$ for all $x\in\mathbb{R}^{m}$. Given
$\mu\in\mathcal{P}(\mathbb{R}^{d})$, define
$M_{p}(\mu):=(\int_{\mathbb{R}^{d}}\|x\|^{p}d\mu(x))^{\frac{1}{p}}$. We write
$m$ for the Lebesgue measure in $\mathbb{R}$.

For non-empty set $\mathcal{T}$, let $l^{\infty}(\mathcal{T})$ denote the set
of all bounded function $f:\mathcal{T}\rightarrow\mathbb{R}$ with respect to
the uniform norm $\|f\|_{\mathcal{T}}:=\sup_{t\in\mathcal{T}}|f(t)|$. For the
class of Lipschitz continuous real-valued function on $\mathbb{R}^{d}$ with
Lipschitz constant at most 1, we denote it by $Lip_{1}(\mathbb{R}^{d})$. And
write $Lip_{1,0}(\mathbb{R}^{d})$ for the functions that belong to
$Lip_{1}(\mathbb{R}^{d})$ and vanish at zero. We write
$\mathcal{N}(\epsilon,\mathcal{F},d)$ for the $\epsilon$-number of function
class $\mathcal{F}$ w.r.t the metric $d$ and $\mathcal{N}_{[\
]}(\epsilon,\mathcal{F},d)$ for the $\epsilon$-bracket number of
$\mathcal{F}$. For brevity, we write $SW_{p}$, $MSW_{p}$ for the Sliced
$p$-Wasserstein distance and max-Sliced $p$-Wasserstein distance respectively.

##  2\. Background

###  2.1. The Wasserstein Distance

The Wasserstein distance is related to the theory of optimal transport. Given
two probability $P,Q\in\mathcal{P}(\mathbb{R}^{d})$, the $p$-Wasserstein
distance between them is defined as :

$W_{p}(P,Q)=\left(\inf_{\pi\in\prod(P,Q)}\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}\|x-y\|^{p}d\pi(x,y)\right)^{\frac{1}{p}},$

where $\prod(P,Q)$ is the set of so-called transport plans whose marginals
coincide with $P$ and $Q$ respectively. When $d=1$, the Wasserstein distance
has a closed form, that is

$W_{p}(P,Q)=\left(\int_{0}^{1}|F^{-1}(x)-G^{-1}(x)|^{p}dx\right)^{\frac{1}{p}},$

where $F$ and $G$ denote the cumulative distribution functions(CDF) of $P$ and
$Q$ respectively and their pseudo-inverses are denoted by $F^{-1}$ and
$G^{-1}$. Particularly, for $p=1$ and $d=1$, $W_{1}$ has the form as

$W_{1}(P,Q)=\int_{-\infty}^{+\infty}|F(x)-G(x)|dx,$

which can be regarded as the $L^{1}$ distance between the CDF of $P$ and $Q$.
Besides, when $p=1$, KR duality shows that $W_{1}$ can be also represented as

$W_{1}(P,Q)=\sup_{f\in Lip_{1}(\mathbb{R}^{d})}\int_{\mathbb{R}^{d}}fd(P-Q).$

It’s obvious that $Lip_{1}(\mathbb{R}^{d})$ can be replaced by
$Lip_{1,0}(\mathbb{R}^{d})$, since $P$ and $Q$ have the same total mass.
Moreover, empirical $W_{1}$ can be seen as a supremum of an empirical process
indexed by $Lip_{1,0}(\mathbb{R}^{d})$. In one dimension, [20] presented the
necessary and sufficient conditions for $Lip_{1,0}(\mathbb{R})$ to be
$P$-Donsker.

###  2.2. Sliced 1-Wasserstein Distance and max-Sliced 1-Wasserstein Distance

Trough slicing method, the Sliced $p$-Wasserstein distance is defined as

$SW_{p}(P,Q)=\left(\int_{S^{d-1}}W_{p}^{p}(\theta_{\\#}^{*}P,\theta_{\\#}^{*}Q)d\sigma(\theta)\right)^{\frac{1}{p}}.$

where $\sigma$ is the uniform distribution on $S^{d-1}$.

And the max-Sliced $p$-Wasserstein distance is defined as

$MSW_{p}(P,Q)=\max_{\theta\in
S^{d-1}}W_{p}(\theta_{\\#}^{*}P,\theta_{\\#}^{*}Q).$

$SW_{p}$ has some similar properties as the Wasserstein distance and is
equivalent to the Wasserstein distance when distributions are with compact
support [11].

##  3\. Central Limit Theorem for the Sliced 1-Wasserstein Distance

In this section, we explore the limit distribution of Sliced 1-Wasserstein
distance between the empirical and the true probability measure. We derive
similar results as Theorem 2.1 in [19] which provided central limit theorem
for the Wasserstein distance in one dimension. Based on the central limit
theorem in Banach space, more specifically in
$L^{1}(S^{d-1}\times\mathbb{R},\sigma\times m)$, for brevity, we denote it by
$L^{1}(S^{d-1}\times\mathbb{R})$. Notice that for
$P,Q\in\mathcal{P}(\mathbb{R})$, $W_{1}(P,Q)$ is the $L^{1}$ distance between
the CDF of $P$ and $Q$, thus for $\mu\in\mathcal{P}(\mathbb{R}^{d})$,
$SW_{1}(\mu_{n},\mu)$ has the form as follows.

$SW_{1}(\mu_{n},\mu)=\int_{S^{d-1}}\int_{-\infty}^{+\infty}|F_{n}(\theta,t)-F(\theta,t)|dtd\sigma(\theta),$

where $F_{n}(\theta,t)=\frac{1}{n}\sum\limits_{i=1}^{n}I_{\theta^{T}X_{i}\leq
t}$, $F(\theta,t)=P(\theta^{T}X\leq t)$ and $X,X_{1},\cdots,X_{n}$ are
$i.i.d.$ random variables with values in $\mathbb{R}^{d}$ and common
distribution $\mu$. In this Section, we define

$\mathcal{P}_{2,1}(\mathbb{R}^{d})=\\{\mu\in\mathcal{P}(\mathbb{R}^{d}):\
\int_{0}^{\infty}\sqrt{\mu(\|x\|>t)}dt<\infty\\}.$

######  Theorem 1.

Let $X,X_{i}$, $i\in\mathbb{N}$ be i.i.d. random variables with values in
$\mathbb{R}^{d}$ and $X\sim\mu$. Let

$Y(\theta,t):=P(\theta^{T}X>t)-I_{\theta^{T}X>t}.$

And $Y_{i}$’s definition is the same as $Y$, just replace the $X$ by $X_{i}$,
then

(1) The processes
$\sum\limits_{i=1}^{n}Y_{i}/\sqrt{n}=\sqrt{n}(F_{n}(\theta,t)-F(\theta,t))$
converge to $B_{\mu}$ in law in $L^{1}(S^{d-1}\times\mathbb{R})$ if and only
if $\Lambda_{2,1}(X)<\infty$, where $B_{\mu}(\theta,t)$ is a centered Gaussian
process with covariance function
$\mathbb{E}[B_{\mu}(\theta_{1},x_{1})B_{\mu}(\theta_{2},x_{2})]=Cov(Y(\theta_{1},x_{1}),Y(\theta_{2},x_{2}))$
and $\Lambda_{2,1}(X):=\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt.$

(2) The sequence

$\|\sum\limits_{i=1}^{n}\frac{Y_{i}}{\sqrt{n}}\|_{L^{1}(S^{d-1}\times\mathbb{R})}=\sqrt{n}\int_{S^{d-1}}\int_{-\infty}^{+\infty}|F_{n}(\theta,t)-F(\theta,t)|dtd\sigma(\theta),n\in\mathbb{N},$

is stochastically bounded if and only if $\Lambda_{2,1}(X)<\infty$.

By noticing the similarity between $W_{1}$ in one dimension and the $SW_{1}$,
the method in [23] can be applied to $SW_{1}$ naturally and leads to a weaker
condition than Theorem 3 in [37].

######  Proposition 1.

(1) For $\mu\in\mathcal{P}_{2,1}(\mathbb{R}^{d})$ and
$\nu\in\mathcal{P}(\mathbb{R}^{d})$, let $F(\theta,t)=P(\theta^{T}X\leq
t),G(\theta,t)=P(\theta^{T}Y\leq t)$ for $X\sim\mu,Y\sim\nu$, then

$\sqrt{n}H_{n}\xrightarrow{d}\int_{F>G}G_{\mu}dtd\sigma(\theta)-\int_{F<G}G_{\mu}dtd\sigma(\theta)+\int_{F=G}|G_{\mu}|dtd\sigma(\theta),$

where $G_{\mu}$ is a centered Gaussian process with covariance function

$cov(G_{\mu}(\theta_{1},x_{1}),G_{\mu}(\theta_{2},x_{2}))=\mu(\theta_{1}^{T}x\leq
x_{1},\theta_{2}^{T}x\leq x_{2})-\mu(\theta_{1}^{T}x\leq
x_{1})\mu(\theta_{2}^{T}x\leq x_{2}).$

and
$H_{n}=\sqrt{n}\int_{S^{d-1}}\int_{-\infty}^{\infty}(|F_{n}(\theta,t)-G(\theta,t)|-|F(\theta,t)-G(\theta,t)|)ddtd\sigma(\theta)$.
If in addition $\nu\in\mathcal{P}_{1}(\mathbb{R}^{d})$, then
$H_{n}=SW_{1}(\mu_{n},\nu)-SW_{1}(\mu,\nu)$.

(2) Let $(X_{i},Y_{i})_{1\leq i\leq n}$ be a sequence of $i.i.d.$ random
variables with values in $\mathbb{R}^{d}\times\mathbb{R}^{d}$ and assume that
$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{var(I_{\\{\theta^{T}X_{1}\leq
t\\}}-I_{\\{\theta^{T}Y_{1}\leq t\\}})}dtd\sigma(\theta)<\infty$. Then for
probability measures $\mu_{n}=\sum\limits_{i=1}^{n}\delta_{X_{i}}/n$ and
$\nu_{n}=\sum\limits_{i=1}^{n}\delta_{Y_{i}}/n$, we have

$\sqrt{n}(SW_{1}(\mu_{n},\nu_{n})-SW_{1}(\mu,\nu))\xrightarrow{d}\int_{F>G}G^{{}^{\prime}}dtd\sigma(\theta)-\int_{F<G}G^{{}^{\prime}}dtd\sigma(\theta)+\int_{F=G}|G^{{}^{\prime}}|dtd\sigma(\theta),$

where $G^{{}^{\prime}}$ is a centered Gaussian process with covariance
function

$cov(G^{{}^{\prime}}(\theta_{1},x_{1}),G^{{}^{\prime}}(\theta_{2},x_{2}))=cov(I_{\theta_{1}^{T}X_{1}\leq
x_{1}}-I_{\theta_{1}^{T}Y_{1}\leq x_{1}},I_{\theta_{2}^{T}X_{1}\leq
x_{2}}-I_{\theta_{2}^{T}Y_{1}\leq x_{2}}).$

######  Remark 1.

[37] has proved that the processes converge weakly in
$L^{1}(S^{d-1}\times\mathbb{R})$ when
$\mu\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})$ for any $\epsilon>0$, but
from Theorem 1, we can see that it is stronger than our condition since
$\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})\subset\mathcal{P}_{2,1}(\mathbb{R}^{d})$
holds for any $\epsilon>0$. Besides, they doesn’t show the relation between
the stochastical boundness of the sequence in Theorem 1(2) and the condition
under which the central limit theorem holds. Comparing to [37], Theorem 3(i)
in [37] requires that $\mu\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})$ and
$\nu\in\mathcal{P}_{1}(\mathbb{R}^{d})$, but the Proposition 1(1) just need
that $\mu\in\mathcal{P}_{2,1}(\mathbb{R}^{d})$ and
$\nu\in\mathcal{P}(\mathbb{R}^{d})$. Theorem 3(ii) in [37] is for the
condition that $X_{i}$ is independent of $Y_{i}$ and requires that
$\mu,\nu\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})$ for
$X_{1}\sim\mu,Y_{1}\sim\nu$. Note that the fact that
$\mu,\nu\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})$ implies that
$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{var(I_{\\{\theta^{T}X_{1}\leq
t\\}}-I_{\\{\theta^{T}Y_{1}\leq t\\}})}dtd\sigma(\theta)<\infty$. Note also
that if $X_{i}$ is independent of $Y_{i}$,
$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{var(I_{\\{\theta^{T}X_{1}\leq
t\\}}-I_{\\{\theta^{T}Y_{1}\leq t\\}})}dtd\sigma(\theta)<\infty$ is indeed
equivalent to $\Lambda(X_{1})<\infty$ and $\Lambda(Y_{1})<\infty$.

There are various results of convergence in expectation of Wasserstein
distance in empirical estimation[38, 39, 40, 41]. Inspired by the results in
one dimension[42], we have the results for $SW_{1}$ as follows.

######  Proposition 2.

For any $\mu\in\mathcal{P}_{1}(\mathbb{R}^{d})$, we have
$\mathbb{E}[SW_{1}(\mu_{n},\mu)]\to 0,\ as\ n\to\infty.$

And for the convergence rate, we have

######  Corollary 1.

Given $\mu\in\mathcal{P}_{1}(\mathbb{R}^{d})$, then
$\mathbb{E}[SW_{1}(\mu_{n},\mu)]=\mathcal{O}(\frac{1}{\sqrt{n}})$ if and only
if $\Lambda_{2,1}(X)<\infty$ for $X\sim\mu$.

######  Remark 2.

By Theorem 1 and Corollary 2, we obtain the equivalence among the central
limit theorem for $SW_{1}$, stochastical boundness of the sequence in Theorem
1(2) and $\Lambda_{2,1}(X)<\infty$ for $X\sim\mu$. Moreover,
$\frac{1}{\sqrt{n}}$ is the best rate for $\mathbb{E}[SW_{1}(\mu_{n},\mu)]$
under that $\mu$ is not degenerate.

######  Proposition 3.

For $\mu\in\mathcal{P}_{1}(\mathbb{R}^{d})$ that is not degenerate, we have

$\mathbb{E}[SW_{1}(\mu_{n},\mu)]\geq
c\frac{\mathbb{E}\|X-\mathbb{E}X\|}{\sqrt{n}},$

where $X\sim\mu$ and $c$ is an absolute positive constant.

##  4\. The aspect of computing $SW_{p}$

Despite that $SW_{p}$ has a low computational cost, it needs many random
projections in high dimension to make the approximation error small when using
Monte Carlo method. Inspired by the fact that one-dimensional projections of a
high-dimensional random vector are approximately Gaussian under mild
assumptions, [43] developed a simple deterministic approximation for $SW_{2}$
without requiring random projections. But their method can’t obtain an
approximation with arbitrarily small error and just works for $SW_{2}$. By
noticing the phenomenon of concentration of measure, we can give the number of
random projections that can make error small in high probability when
computing $SW_{p}$ based on Monte Carlo approximation.

######  Proposition 4.

For fixed $\epsilon$ and $\delta$, when the number of random projections $n$
satisfies that $n\geq\frac{2L^{2}}{(d-1)\epsilon^{2}}\log\frac{2}{\delta}$, we
have

$P\left(|SW_{p}^{p}(\mu,\nu)-{SW}_{p,n}^{p}(\mu,\nu)|\geq\epsilon\right)\leq\delta,$

where
${SW}_{p,n}^{p}(\mu,\nu)=\frac{1}{n}\sum\limits_{i=1}^{n}W_{p}^{p}({\theta_{i}}_{\\#}^{*}\mu,{\theta_{i}}_{\\#}^{*}\nu)$,
$\\{\theta_{i}\\}_{i=1}^{n}$ i.i.d. from $\sigma$ and
$L=pW_{p}^{p-1}(\mu,\nu)(M_{p}(\mu)+M_{p}(\nu))$.

Notice that $|x-y|^{p}\leq|x^{p}-y^{p}|$ holds for any positive number $x,y$
and $p\geq 1$. Then by Proposition 2, we obtain the result for $SW_{p}$.

######  Corollary 2.

For fixed $\epsilon$ and $\delta$, when the number of random projections $n$
satisfies that $n\geq\frac{2L^{2}}{(d-1)\epsilon^{2p}}\log\frac{2}{\delta}$,
we have

$P\left(|SW_{p}(\mu,\nu)-{SW}_{p,n}(\mu,\nu)|\geq\epsilon\right)\leq\delta,$

where ${SW}_{p,n}(\mu,\nu)=\left({SW}_{p,n}^{p}(\mu,\nu)\right)^{1/p}$.

From the lower bound of $n$ in Corollary 3, we can see that for $p\neq 1$,
there should be a proper prior estimation of $W_{p}(\mu,\nu)$ first in
practice. Thus there is an obstacle between theory and application. But for
$p=1$, there is no such problem and $n$ may be independent of $d$ under some
condition.

######  Corollary 3.

For
$n\geq\frac{4(\Delta_{\mu}+\Delta_{\nu})^{2}}{\epsilon^{2}}\log\frac{2}{\delta}$,
we have

$P\left(|SW_{1}(\mu,\nu)-{SW}_{1,n}(\mu,\nu)|\geq\epsilon\right)\leq\delta,$

where $\Delta_{\mu}=\max_{i}M_{2}((\pi_{i})_{\\#}\mu)$ and
$\Delta_{\nu}=\max_{i}M_{2}((\pi_{i})_{\\#}\nu)$.

Thus if there is a dimension independent upper bound for
$\max_{i}M_{2}((\pi_{i})_{\\#}\mu)$ and $\max_{i}M_{2}((\pi_{i})_{\\#}\nu)$,
then $n$ is independent of $d$. For example, let $(X_{i})_{i\in\mathbb{N}}$ be
a stationary sequence of one-dimensional random variables, i.e. $X_{i}$ and
$X_{j}$ have the same distribution for any $i,j\in\mathbb{N}$ and
$(Y_{i})_{i\in\mathbb{N}}$ be another stationary sequence. Denote by $\mu_{d}$
and $\nu_{d}$ the distribution of $(X_{1},\cdots,X_{d})$ and
$(Y_{1},\cdots,Y_{d})$ respectively. Then by Corollary 3, $n$ is independent
of $d$.

For $p\neq 1$, the problem can be handled by replace $SW_{p}$ with a variant
of it, which is defined as

$\widehat{SW_{p}}(\mu,\nu)=\int_{S^{d-1}}W_{p}({\theta}_{\\#}^{*}\mu,{\theta}_{\\#}^{*}\mu)d\sigma(\theta).$

It’s easy to check that $\widehat{SW_{p}}$ is indeed a distance. Then, based
on the same technique, we have:

######  Corollary 4.

For fixed $\epsilon$ and $\delta$, when
$n\geq\frac{2\tilde{L}^{2}}{(d-1)\epsilon^{2}}\log\frac{2}{\delta}$, we have

$P(|\widehat{SW}_{p}(\mu,\nu)-\widehat{SW}_{p,n}(\mu,\nu)|\geq\epsilon)\leq\delta,$

where
$\widehat{SW}_{p,n}(\mu,\nu)=\frac{1}{n}\sum\limits_{i=1}^{n}W_{p}({\theta_{i}}_{\\#}^{*}\mu,{\theta_{i}}_{\\#}^{*}\nu)$,
$\\{\theta_{i}\\}_{i=1}^{n}$ i.i.d. from $\sigma$ and
$\tilde{L}=M_{p}(\mu)+M_{p}(\nu)$.

######  Remark 3.

With no priori information about $\mu$ and $\nu$, it may be reasonable to
choose random projections uniformly distributed on the unit sphere. There are
also variant potential distribution for random projections deserved to be
explored. For example, [43] replaced the uniform distribution by a zero-mean
Gaussian distribution with covariance matrix $(1/d)I_{d}$ and showed that
there are equivalent up to a constant that only depends the dimension $d$ and
the order $p$. Here, we present the result.

$\widetilde{SW}_{p}^{p}(\mu,\nu):=\int_{R^{d}}W_{p}^{p}({\theta}_{\\#}^{*}\mu,{\theta}_{\\#}^{*}\nu)d\gamma_{d}(\theta)=(2/d)^{1/2}\\{\Gamma(d/2+p/2)/\Gamma(d/2)\\}^{1/p}SW_{p}^{p}(\mu,\nu),$

where $p\in[1,+\infty)$, $\Gamma$ is the Gamma function and $\gamma_{d}$ is
the zero-mean Gaussian distribution with covariance matrix $(1/d)I_{d}$. In
particular, when $p=2$, $\widetilde{SW}_{2}^{2}(\mu,\nu)=SW_{2}^{2}(\mu,\nu)$.
Let $c_{p,d}$ denote the constant
$(2/d)^{1/2}\\{\Gamma(d/2+p/2)/\Gamma(d/2)\\}^{1/p}$, i.e.
$\widetilde{SW}_{p}^{p}(\mu,\nu)=c_{p,d}SW_{p}^{p}(\mu,\nu)$.

Under the observation that the Lipschitz function of Gaussian variables is
sub-Gaussian (see Theorem 2.26 in [44]), we can obtain similar results for
$\widetilde{SW}_{p}$.

######  Corollary 5.

For fixed $\epsilon$ and $\delta$, when
$n\geq\frac{2L^{2}}{d^{p}\epsilon^{2}}\log{\frac{2}{\delta}}$, we have

$P(|\widetilde{SW}_{p}^{p}(\mu,\nu)-\frac{1}{d^{p/2}}\overline{SW}_{p,n}^{n}|\geq\epsilon)\leq\delta,$

where
$\overline{SW}_{p,n}^{p}(\mu,\nu)=\frac{1}{n}\sum\limits_{i=1}^{n}W_{p}({\theta_{i}}_{\\#}^{*}\mu,{\theta_{i}}_{\\#}^{*}\nu)$,
$\\{\theta_{i}\\}_{i=1}^{n}$ i.i.d. from the zero-mean Gaussian distribution
with covariance matrix $I_{d}$ and $L$ is the same as in Proposition 2.

Through the equivalence between $\widetilde{SW}_{p}^{p}$ and ${SW}_{p}^{p}$,
we can estimate ${SW}_{p}^{p}$ from the estimation of
$\widetilde{SW}_{p}^{p}$.

######  Corollary 6.

For fixed $\epsilon$ and $\delta$, when
$n\geq\frac{2L^{2}}{d^{p}c_{p,d}^{2}\epsilon^{2}}\log{\frac{2}{\delta}}$, we
have

$P(|{SW}_{p}^{p}(\mu,\nu)-\frac{1}{d^{p/2}c_{p,d}}\overline{SW}_{p,n}^{n}|\geq\epsilon)\leq\delta.$

##  5\. Central Limit Theorem for Max-Sliced 1-Wasserstein Distance

###  5.1. Limit Distribution for $MSW_{1}$

In this section, we characterize the limit distribution of
$\sqrt{n}MSW_{1}(P_{n},P)$ via the theory of empirical process. First, we show
that $MSW_{1}(P_{n},P)$ can be translated to the supremum of an empirical
process through KR duality.

######  Lemma 1.

Given $P\in\mathcal{P}(\mathbb{R}^{d})$, we have
$MSW_{1}(P_{n},P)=\sup\limits_{f\in\mathcal{F}}(P_{n}-P)f$, where

$\mathcal{F}:=\\{f:\mathbb{R}^{d}\to\mathbb{R}\ |\ f(x)=g(\theta^{T}x),g\in
Lip_{1,0}(\mathbb{R}),\theta\in S^{d-1}\\}.$

By bounding the bracketing entropy integral of $\mathcal{F}$ with respect to
$P$ which is defined as

$J_{[\
]}(\delta,\mathcal{F},L_{2}(P))=\int_{0}^{\delta}\sqrt{\log\mathcal{N}_{[\
]}(\epsilon,\mathcal{F},L_{2}(P))}d\epsilon,$

we have result as follows.

######  Theorem 2.

When the ($4+\delta$)-th ($\delta>0$) moment of $P$ is finite, $\mathcal{F}$
is $P$-Donsker. Then from continuous mapping theorem, we have

$\sqrt{n}MSW_{1}(P_{n},P)\xrightarrow{d}\|G_{P}\|_{\mathcal{F}},$

where $G_{P}$ is a tight version of a zero-mean Gaussian process on
$\mathcal{F}$ with covariance function $Cov(G_{P}f,G_{P}g)=P(fg)-(Pf)(Pg)$.

The technique in the proof of Theorem 2 can also be applied to other integral
probability metrics (IPM) defined as

$\gamma_{\mathcal{F}}(P,Q):=\sup_{f\in\mathcal{F}}|\int fdP-\int fdQ|,$

and the max-Sliced version of the IPM is defined as

$\max-\gamma_{\mathcal{F}}(P,Q):=\max_{\theta\in
S^{d-1}}\sup_{f\in\mathcal{F}}|\int fd{\theta}_{\\#}^{*}P-\int
fd{\theta}_{\\#}^{*}Q|.$

Similar to Lemma 1, we have

$\max-\gamma_{\mathcal{F}}(P,Q)=\sup_{f\in\widehat{\mathcal{F}}}|\int fdP-\int
fdQ|,$

where $\widehat{\mathcal{F}}:=\\{f:\mathbb{R}^{d}\to\mathbb{R}\ |\
f(x)=g(\theta^{T}x),g\in\mathcal{F},\theta\in S^{d-1}\\}$.

For function class satisfied the following assumptions :

######  Assumption 1.

$\mathcal{F}\subset Lip_{L}(\mathbb{R})$, for some positive constant $L$.

######  Assumption 2.

For any positive constant $M\in\mathbb{R}$, the bracketing entropy of
$\mathcal{F}|_{[0,M]}$ satisfies that $\log\mathcal{N}_{[\
]}(\epsilon,\mathcal{F}|_{[0,M]},\|\cdot\|_{\infty})=O(\frac{M^{\alpha}}{{\epsilon}^{\beta}})$
for some constants $\alpha>0$ and $0<\beta<2$, where
$\mathcal{F}|_{[0,M]}:=\\{f|_{[0,M]}\ |\ f\in\mathcal{F}\\}$.

Then we have the following result for IPMs.

######  Corollary 7.

If the $(2+\frac{2\alpha}{2-\beta})$-th moment of $P$ is finite,
$\widehat{\mathcal{F}}$ is $P$-Donsker and the continuous mapping theorem
implies

$\sqrt{n}\max-\gamma_{\mathcal{F}}(P_{n},P)\xrightarrow{d}\|G_{P}\|_{\widehat{\mathcal{F}}},$

where $G_{P}$ is a tight version of a zero-mean Gaussian process on
$\widehat{\mathcal{F}}$ with covariance function
$Cov(G_{P}f,G_{P}g)=P(fg)-(Pf)(Pg)$.

##  6\. Statistical analysis for $MSW_{1}$

###  6.1. Upper bound in empirical estimation

It’s obvious that $SW_{1}$ enjoys dimension-free sample complexity, i.e. the
convergence rate under empirical estimation is independent of dimensionality.
But it’s not clear for $MSW_{1}$. [45] has showed the upper bound when the
probability measure satisfies the transportation cost inequality. Also [46]
has explored the convergence rate for projection based Wasserstein distance
under strong assumptions like satisfying the Bernstein tail condition or
projection Poincare inequality and the results in [46] imply that $MSW_{1}$
also has sample complexity independent of dimensionality. In the next, we use
chaining method to obtain the convergence rate of $MSW_{1}$ under different
conditions. For $\alpha>0$, let
$\|\xi\|_{\psi_{\alpha}}:=\inf\\{C>0:\mathbb{E}[e^{\|\xi\|/C}]\leq 2\\}$ be
the Orlicz $\psi_{\alpha}$-(quasi)norm for real-valued random variable $\xi$.

######  Theorem 3.

Suppose that one of the conditions holds: (1)
$\mu\in\mathcal{P}_{p}(\mathbb{R}^{d})$ for $1<p<2$; (2)
$\mu\in\mathcal{P}_{p}(\mathbb{R}^{d})$ for $2\leq p\leq 4$; (3)
$\mu\in\mathcal{P}_{p}(\mathbb{R}^{d})$ for $p>4$, then

$\mathbb{E}[MSW_{1}(\mu_{n},\mu)]=\left\\{\begin{aligned}
&\mathcal{O}(n^{-\frac{p-1}{2p}}),&under\ (1),\\\
&\mathcal{O}(n^{-\frac{p-1}{2p-1}}),&under\ (2),\\\
&\mathcal{O}(n^{-\frac{1}{2}}),&under\ (3).\\\ \end{aligned}\right.$

######  Remark 4.

Note that in [45] the convergence rate is $\mathcal{O}(\sqrt{\frac{\log
n}{n}})$ under the condition that $\mu$ satisfies the $T_{1}(\sigma^{2})$
inequality which is equivalent to that $\|\|X\|\|_{\psi_{2}}<\infty$. In
condition (3), our condition is weaker and upper bound is tigher. Notice that
under the condition (3), we can conclude from Proposition 3 that the upper
bound is also sharp.

###  6.2. Concentration Inequalities

In this section, we consider the concentration inequalities for $MSW_{1}$ and
$SW_{1}$ under different conditions which is similar with Proposition 1 in
[35]. Trough treating $MSW_{1}$ between the empirical probability and the true
probability as the supremum of an empirical process, the results follow
directly from [47].

######  Proposition 5.

Let $X\sim P$ with $supp(P)=\mathcal{X}$ and suppose one of the following
conditions holds :(i) $\mathcal{X}$ is compact; (ii)
$\|\|X\|\|_{\psi_{\alpha}}<\infty$, for some $\alpha\in(0,1]$. Then for all
$\eta\in(0,1)$, there exists constant $C:=C_{\eta}$ such that for all $t>0$:

$P(MSW_{1}(\mu_{n},\mu)\geq(1+\eta)\mathbb{E}[MSW_{1}(\mu_{n},\mu)+t)])\leq\exp(-\frac{nt^{2}}{2(1+\delta)\mathbb{E}\|x\|^{2}})+\alpha(n,t),$

and

$P(MSW_{1}(\mu_{n},\mu)\leq(1-\eta)\mathbb{E}[MSW_{1}(\mu_{n},\mu)-t)])\leq\exp(-\frac{nt^{2}}{2(1+\delta)\mathbb{E}\|x\|^{2}})+\alpha(n,t),$

where

$\alpha(n,t)=\left\\{\begin{aligned}
&\exp\left(-\frac{nt}{Cdiam(\mathcal{X})}\right),&under\ (i).\\\
&3\exp\left(-\left(\frac{nt}{C\|\|X\|+\mathbb{E}\|X\|\|_{\psi_{\alpha}}}\right)^{\alpha}\right),&under\
(ii).\end{aligned}\right.$

If $\mu$ is induced by a $\sigma^{2}$-Subgaussian random vector $X$ with value
in $\mathbb{R}^{d}$, i.e. for all $\alpha\in\mathbb{R}^{d}$,

$\mathbb{E}[\exp(\alpha^{T}(X-\mathbb{E}X))]\leq\exp(\|\alpha\|^{2}\sigma^{2}/2)$

then we have

$P(|MSW_{1}(\mu_{n},\mu)-\mathbb{E}MSW_{1}(\mu_{n},\mu)|\geq t)\leq
2e^{-\frac{nt^{2}}{32d\sigma^{2}}},$

and

$P(|SW_{1}(\mu_{n},\mu)-\mathbb{E}SW_{1}(\mu_{n},\mu)|\geq t)\leq
2e^{-\frac{nt^{2}}{4\sigma^{2}}}.$

###  6.3. Two-Sample Settings

Let $X_{1},\cdots,X_{m}$ and $Y_{1},\cdots,Y_{n}$ be independent random
samples from distributions $P$ and $Q$ respectively. It’s fundamental in
statistics to test the null hypothesis $H_{0}:P=Q$ versus the alternative
$H_{1}:P\neq Q$. By considering $MSW_{1}$, we define the statistic

$W_{m,n}:=\sqrt{\frac{mn}{N}}MSW_{1}(P_{m},Q_{n})=\sqrt{\frac{mn}{N}}\|P_{m}-Q_{n}\|_{\mathcal{F}},$

where $\mathcal{F}$ is the function class in Lemma 1 and $N=m+n$. Following by
chapter 3.7 in [48], let
$(Z_{N1},\cdots,Z_{NN})=(X_{1},\cdots,X_{m},Y_{1},\cdots,Y_{n})$ and
$\lambda=m/N$, consider the pooled empirical measure

$H_{N}=\frac{1}{N}\sum\limits_{i=1}^{N}\delta_{Z_{Ni}}=\lambda_{N}P_{m}+(1-\lambda_{N})Q_{n}.$

Let $Z_{1},\cdots,Z_{N}$ be a bootstrap sample from $H_{N}$ and define

$P_{m}^{B}:=\frac{1}{m}\sum\limits_{i=1}^{m}\delta_{Z_{i}},\
Q_{n}^{B}:=\frac{1}{n}\sum\limits_{i=m+1}^{N}\delta_{Z_{i}}.$

Let $W_{m,n}^{B}=\sqrt{\frac{mn}{N}}MSW_{1}(P_{m}^{B},Q_{n}^{B})$, we have the
following corollary.

######  Corollary 8.

Let $P,Q\in\mathcal{P}(\mathbb{R}^{d})$. Assume that the $(4+\delta)$-th
moment of $P$ and $Q$ are finite. Then with the same notation as above, we
have

(i) If $P=Q$, then $W_{m,m}\xrightarrow{d}G_{P}$, and
$W_{m,n}\xrightarrow{P}\infty$, otherwise.

(ii) $W_{m,n}^{B}\xrightarrow{d}G_{H}$ given almost every sequence
$X_{1},\cdots,X_{m},Y_{1},\cdots,Y_{n}$ where $G_{H}$ is a tight Brownian
bridge process corresponding the measure $H=\lambda P+(1-\lambda)Q$.

For $P\neq Q$, we consider the following statistic.

$\overline{W}_{m,n}:=\sqrt{\frac{mn}{m+n}}\left(MSW_{1}(P_{m},Q_{n})-MSW_{1}(P,Q)\right).$

Following from a direct application of Theorem 6.1 in [49], we derive limit
distribution for $\overline{W}_{m,n}$ which is similar to Corollary 4 in [35].

######  Corollary 9.

Under the assumptions of Corollary 10, let

$d(f,g):=\sqrt{\mathbb{E}_{P}(f-g)^{2}}+\sqrt{\mathbb{E}_{Q}(f-g)^{2}},f,g\in\mathcal{F}.$

Then $(\mathcal{F},d)$ is a totally bounded pseudometric space. Moreover, we
have

$\overline{W_{m,n}}\to\sup_{\overline{M}^{+}(D,d)}G,$

where $G:=\sqrt{1-\lambda}G_{P}-\sqrt{\lambda}G_{Q}$,

$\widetilde{M}^{+}(D,d):=\\{f\in(\overline{\mathcal{F}},d):\mathbb{E}_{P}(f)-\mathbb{E}_{Q}(f)=MSW_{1}(P,Q)\\},$

and $\overline{\mathcal{F}}$ is the completion of $\mathcal{F}$ with respect
to $d$.

##  7\. Application

###  7.1. Two-Sample Testing

The Problem of two-sample testing is a fundamental topic in statistics.
Specifically, for $\mu,\nu\in\mathcal{P}(\mathbb{R}^{d})$, let
$X_{1},\cdots,X_{m}\sim\mu$ and $Y_{1},\cdots,Y_{n}\sim\nu$ be independent
samples from $\mu$ and $\nu$ respectively. Based on these samples, we wish to
know whether $\mu=\nu$, that is, decide whether to accept the null hypothesis
$H_{0}\ :\ \mu=\nu$ or alternative hypothesis $H_{1}\ :\ \mu\neq\nu$. In this
section, we consider the non-parametric two-sample testing and utilize
$SW_{1}$ and $MSW_{1}$ to construct test statistic.

First, we state the definition of asymptotically level. For a sequence of two-
sample tests $T_{m,n}$ defined as

$T_{m,n}(X_{1},\cdots,X_{m},Y_{1},\cdots,Y_{n})=\left\\{\begin{aligned}
H_{1}&,&if\ D_{m,n}>c_{m,n},\\\ H_{0}&,&otherwise,\end{aligned}\right.$

where $D_{m,n}$ is a sequence of statistics based on samples
$(X_{1},\cdots,X_{m},Y_{1},\cdots,Y_{n})$. We say $T_{m,n}$ is asymptotically
level $\alpha\in[0,1]$ if
$\lim\sup_{m,n\to\infty}P(T_{m,n}>c_{m,n})\leq\alpha$ under $H_{0}$ and
$T_{m,n}$ is consistent at asymptotic level $\alpha$ if it is asymptotic level
$\alpha$ and $\lim\inf_{n\to\infty}P(T_{m,n}>c_{m,n})=1$ under $H_{1}$.

######  Proposition 6.

Under the setting of Section 6.3, consider the problem of testing $H_{0}\ :\
\mu=\nu$ versus $H_{1}\ :\ \mu\neq\nu$. Let

$D_{m,n}=\left\\{\begin{aligned}
&\overline{W}_{m,n}=\sqrt{\frac{mn}{N}}\|P_{m}-Q_{n}\|_{L^{1}(S^{d-1}\times\mathbb{R})},&(1),\\\
&W_{m,n}=\sqrt{\frac{mn}{N}}\|P_{m}-Q_{n}\|_{\mathcal{F}},&(2),\end{aligned}\right.$

and $T_{m,n}$ is defined as above, where under (1) $c_{m,n}$ is the
$\alpha$-quantile of
$\overline{W}_{m,n}^{B}:=\sqrt{\frac{mn}{N}}\|P_{m}^{B}-Q_{n}^{B}\|_{L^{1}(S^{d-1}\times\mathbb{R})}$
and under (2) $c_{m,n}$ is the $\alpha$-quantile of $W_{m,n}^{B}$. Then, this
test is consistent at asymptotic level $\alpha$ if under (1)
$\Lambda_{2,1}(X)<\infty$ and $\Lambda_{2,1}(Y)<\infty$ for $X\sim\mu$ and
$Y\sim\nu$; under (2) the $(4+\delta)$-th ($\delta>0$) moment of $\mu$ and
$\nu$ are finite.

##  8\. Concluding Remarks

In this work, we characterize the limit distribution of empirical $SW_{1}$ and
$MSW_{1}$. Furthermore, for the computation of $SW_{p}$ based on Monte Carlo
method, we show the number of random projections that can make sure the error
small in high probability and propose a variant of $SW_{p}$ which can be
estimated easily. Also the results of convergence for $SW_{1}$ are presented.
For $MSW_{1}$, we present concentration inequalities results and upper bound
in expectation in empirical estimation.

In the future, we want to explore the central limit theorem for $SW_{p}$. For
$SW_{p}$ and $MSW_{p}$, other possible direction include applications in
statistics and developing efficient algorithms, which is a core problem in
practice.

##  9\. Appendix

###  9.1. Proof of Theorem 1(i)

###### Proof.

Notice that $Y(\theta,t)\in L^{1}(S^{d-1}\times\mathbb{R})$ a.e. as long as
$\mathbb{E}\|X\|<\infty$, since

$\displaystyle\|Y\|_{L^{1}}$
$\displaystyle=\int_{S^{d-1}}\int_{-\infty}^{+\infty}|P(\theta^{T}X>t)-I_{\theta^{T}X>t}|dtd\sigma(\theta)$
$\displaystyle=\int_{S^{d-1}}\int_{-\infty}^{\theta^{T}X}P(\theta^{T}X\leq
t)dtd\sigma(\theta)+\int_{S^{d-1}}\int_{\theta^{T}X}^{+\infty}P(\theta^{T}X>t)dtd\sigma(\theta)$
$\displaystyle\leq\int_{S^{d-1}}\int_{-\infty}^{|\theta^{T}X|}P(\theta^{T}X\leq
t)dtd\sigma(\theta)+\int_{S^{d-1}}\int_{-|\theta^{T}X|}^{+\infty}P(\theta^{T}X>t)dtd\sigma(\theta)$
$\displaystyle\leq\int_{S^{d-1}}\int_{-\infty}^{-|\theta^{T}X|}P(\theta^{T}X\leq
t)dtd\sigma(\theta)+\int_{S^{d-1}}\int_{|\theta^{T}X|}^{+\infty}P(\theta^{T}X>t)dtd\sigma(\theta)+4|\theta^{T}X|$
$\displaystyle=\int_{S^{d-1}}\int_{|\theta^{T}X|}^{+\infty}P(\theta^{T}X\leq-t)+P(\theta^{T}X>t)dtd\sigma(\theta)+4\|X\|$
$\displaystyle\leq\int_{S^{d-1}}\int_{0}^{+\infty}P(|\theta^{T}X|\geq
t)dtd\sigma(\theta)+4\|X\|$ $\displaystyle\leq\mathbb{E}\|X\|+4\|X\|.$

Thus following from the central limit theorem in Banach space (Theorem 10.10
in [50], see also Theorem 3 in [51] which is more specific), we have that
$\sum\limits_{i=1}^{n}Y_{i}/\sqrt{n}$ converges weakly in
$L^{1}(S^{d-1}\times\mathbb{R})$ if and only if
$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\left(\mathbb{E}[|Y(\theta,t)|^{2}]\right)^{1/2}dtd\sigma(\theta)<\infty$
and $P(\|Y\|_{L^{1}}>t)=o(t^{-2})$.

Notice that $\|Y\|_{L^{1}}\leq\mathbb{E}\|X\|+4\|X\|$, so if
$\mathbb{E}\|X\|^{2}<\infty$ , then from Markov inequality,
$P(\|Y\|_{L^{1}}>t)=o(t^{-2})$ holds.

Since
$\mathbb{E}[|Y(\theta,s)|^{2}]=P(\theta^{T}X>t)(1-P(\theta^{T}X>t))=F(\theta,t)(1-F(\theta,t))$,
we have

$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\left(\mathbb{E}[|Y(\theta,t)|^{2}]\right)^{1/2}dtd\sigma(\theta)<\infty\Leftrightarrow\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dtd\sigma(\theta)<\infty.$

We divide the proof into three steps .

Step 1: In the following, we prove that

$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dtd\sigma(\theta)<\infty\Leftrightarrow\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dtd\sigma(\theta)<\infty.$

We first prove ” $\Leftarrow$ ”:

$\displaystyle\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dt$
$\displaystyle=\int_{-\infty}^{+\infty}\sqrt{P(\theta^{T}X\leq
t)P(\theta^{T}X>t)}dt$
$\displaystyle=\int_{0}^{+\infty}\sqrt{P(\theta^{T}X\leq
t)P(\theta^{T}X>t)}+\sqrt{P(\theta^{T}X\leq-t)P(\theta^{T}X>-t)}dt$
$\displaystyle\leq\int_{0}^{+\infty}\sqrt{P(\theta^{T}X>t)}+\sqrt{P(\theta^{T}X\leq-t)}dt$
$\displaystyle\leq\int_{0}^{+\infty}\sqrt{2}\sqrt{P(\theta^{T}X\geq
t)+P(\theta^{T}X\leq-t)}dt$
$\displaystyle=\int_{0}^{+\infty}\sqrt{2}\sqrt{P(|\theta^{T}X|\geq t)}dt$
$\displaystyle=\int_{-1}^{+\infty}\sqrt{2}\sqrt{P(|\theta^{T}X|\geq t+1)}dt$
$\displaystyle\leq\int_{-1}^{+\infty}\sqrt{2}\sqrt{P(|\theta^{T}X|>t)}dt$
$\displaystyle=\sqrt{2}+\int_{0}^{+\infty}\sqrt{2}\sqrt{P(|\theta^{T}X|>t)}dt,$

where the second inequality follows from
$\sqrt{a}+\sqrt{b}\leq\sqrt{2}\sqrt{a+b}$ for $a\geq 0,b\geq 0$. Thus

$\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dtd\sigma(\theta)<\infty\Rightarrow\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dtd\sigma(\theta)<\infty.$

Next, we prove ”$\Rightarrow$”:

As
$P(|\theta^{T}X|>t)\leq\frac{\mathbb{E}|\theta^{T}X|}{t}\leq\frac{\mathbb{E}\|X\|}{t}$,
we have that for any $\epsilon>0$, there exists a constant $t_{0}>0$ such that
for any $\theta$ and $t\geq t_{0}$, $P(|\theta^{T}X|>t)\leq\epsilon$ holds. It
leads to

$\displaystyle\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dt$
$\displaystyle=\int_{0}^{+\infty}\sqrt{P(\theta^{T}X\leq
t)P(\theta^{T}X>t)}+\sqrt{P(\theta^{T}X\leq-t)P(\theta^{T}X>-t)}dt$
$\displaystyle\geq\int_{t_{0}}^{+\infty}(\sqrt{P(\theta^{T}X\leq
t)P(\theta^{T}X>t)}dt+\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X\leq-t)P(\theta^{T}X>-t)})dt.$

For the first integral, we have

$\displaystyle\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X\leq
t)P(\theta^{T}X>t)}dt$
$\displaystyle=\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X>t)(1-P(\theta^{T}X>t))}dt$
$\displaystyle\geq\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X>t)}dt.$

The inequality follows from that when $t\geq t_{0}$, $P(\theta^{T}X>t)\leq
P(|\theta^{T}X|>t)\leq\epsilon$.

Similarly, we have

$\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X\leq-t)P(\theta^{T}X>-t)}dt\geq\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X\leq-t)}dt.$

Thus

$\displaystyle\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X\leq
t)P(\theta^{T}X>t)}+\sqrt{P(\theta^{T}X\leq-t)P(\theta^{T}X>-t)}dt$
$\displaystyle\geq\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X>t)}+\sqrt{P(\theta^{T}X\leq-t)}dt$
$\displaystyle\geq\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X>t)+P(\theta^{T}X\leq-t)}dt$
$\displaystyle\geq\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(\theta^{T}X>t)+P(\theta^{T}X<-t)}dt$
$\displaystyle=\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dt.$

The second inequality is from $\sqrt{a}+\sqrt{b}\geq\sqrt{a+b}$.
From above, we have

$\displaystyle\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dt$
$\displaystyle\geq\sqrt{1-\epsilon}\int_{t_{0}}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dt$
$\displaystyle\geq\sqrt{1-\epsilon}\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dt-
t_{0}\sqrt{1-\epsilon}.$

Now, we can assert that

$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dtd\sigma(\theta)<\infty\Rightarrow\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dtd\sigma(\theta)<\infty.$

Step 2: In this step, we are going to prove that

$\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dtd\sigma(\theta)<\infty\Leftrightarrow\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt<+\infty.$

”$\Leftarrow$”: It follows directly from $|\theta^{T}X|\leq\|X\|$.

”$\Rightarrow$”:

From
$\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dtd\sigma(\theta)<\infty$,
we have

$\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dt<\infty,\ for\ a.e.\ \theta\in
S^{d-1}.$

Notice that by the compactness of $S^{d-1}$, we can pick a finite set
$\\{\theta_{1},\cdots,\theta_{n}\\}\subset S^{d-1}$ such that
$\int_{0}^{+\infty}\sqrt{P(|{\theta}_{i}^{T}X|>t)}dt<\infty\ (1\leq i\leq n)$
and for all $x\in\mathbb{R}^{d}$, the following inequality holds

$\frac{\|x\|}{2}\leq\max_{1\leq i\leq
n}|\theta_{i}^{T}x|\leq\sum\limits_{i=1}^{n}|\theta_{i}^{T}x|.$

Thus, we have

$\displaystyle\sqrt{P(\|X\|>t)}$
$\displaystyle\leq\sqrt{P(\sum\limits_{i=1}^{n}|\theta_{i}^{T}X|>\frac{t}{2})}$
$\displaystyle\leq\sqrt{\sum\limits_{i=1}^{n}P(|\theta_{i}^{T}X|>\frac{t}{2n})}$
$\displaystyle\leq\sum\limits_{i=1}^{n}\sqrt{P(|\theta_{i}^{T}X|>\frac{t}{2n})}.$

It leads to

$\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt\leq\sum\limits_{i=1}^{n}\int_{0}^{+\infty}\sqrt{P(|\theta_{i}^{T}X|>\frac{t}{2n})}dt<\infty.$

It follows from step 1 and step 2 that

$\int_{S^{d-1}}\int_{-\infty}^{+\infty}\left(E[|Y(\theta,t)|^{2}]\right)^{1/2}dtd\sigma(\theta)<\infty\Leftrightarrow\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt<+\infty.$

Therefore, we only need to prove that

$\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt<+\infty\Rightarrow
P(\|Y\|_{L^{1}}>t)=o(t^{-2}).$

Notice that $\|Y\|_{L^{1}}\leq\mathbb{E}\|X\|+4\|X\|$, it’s sufficient to
prove

$\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt<+\infty\Rightarrow\mathbb{E}\|X\|^{2}<\infty,$

which is obvious. Thus we complete the proof. ∎

###  9.2. Proof of Theorem 1(ii)

###### Proof.

The proof is just a minor modification of the proof of Theorem 2.1(b) in [19].
Let $Z(\theta,t)=I_{\theta^{T}X>t}$, then
$Y(\theta,t)=Z(\theta,t)-\mathbb{E}Z(\theta,t)$.

For necessity, from the proof of Theorem 2.1(b) in [19] (i.e. combining with
Hoffmann-Jørgensen’s inequality and Montgomery-Smith’s inequality, the
stochastical boundness implies the boundness of the first moment), we have

$\sup_{n}\mathbb{E}\left\|\frac{\sum_{i=1}^{n}(Z_{i}-\mathbb{E}Z_{i})}{\sqrt{n}}\right\|_{L^{1}}<\infty,$

and for a binomial $(n,p)$ random variable $\xi$ such that $4c_{1}/n\leq p\leq
1/2$, we have

$\frac{np}{2}\leq\mathbb{E}(\xi-\mathbb{E}\xi)^{2}\leq
c_{1}[1+(c_{2}^{-1}\mathbb{E}|\xi-\mathbb{E}\xi|)^{2}]\leq\frac{np}{4}+\frac{c_{1}}{c_{2}^{2}}(\mathbb{E}|\xi-\mathbb{E}\xi|)^{2}.$

In other words, there exist positive finite constants $C_{1}$ and $C_{2}$ such
that

$\displaystyle L(\xi)=Bin(n,p)\ with\ \frac{C_{1}}{n}\leq p\leq\frac{1}{2}\
implies\ E|\xi-E\xi|\geq C_{2}\sqrt{np}.$ (1)

For real-valued random variables $\hat{X},\hat{X_{1}},\cdots,\hat{X_{n}}$,

when $t<0$, observe that $I_{\hat{X}^{+}>t}-P(\hat{X}^{+}>t)=0$, so we have
$|\sum_{i=1}^{n}I_{\hat{X}_{i}>t}-P(\hat{X}_{i}>t)|\geq
0=|\sum_{i=1}^{n}I_{\hat{X_{i}}^{+}>t}-P(\hat{X_{i}}^{+}>t)|$;

when $t\geq 0$, we have $I_{\hat{X}>t}=I_{\hat{X}^{+}>t},\
P(\hat{X}>t)=P(\hat{X}^{+}>t)$, which implies
$|\sum_{i=1}^{n}I_{\hat{X_{i}}>t}-P(\hat{X_{i}}>t)|=|\sum_{i=1}^{n}I_{\hat{X_{i}}^{+}>t}-P(\hat{X_{i}}^{+}>t)|$.

Combining above, we have
$|\sum_{i=1}^{n}I_{\hat{X}_{i}>t}-P(\hat{X}_{i}>t)|\geq|\sum_{i=1}^{n}I_{\hat{X}_{i}^{+}>t}-P(\hat{X}_{i}^{+}>t)|$
holds for any $t\in\mathbb{R}$.

Let $Z^{+}(\theta,t)=I_{(\theta^{T}X)^{+}>t}$. From above, we have
$|\sum_{i=1}^{n}(Z_{i}^{+}-\mathbb{E}Z_{i}^{+})|\leq|\sum_{i=1}^{n}(Z_{i}-\mathbb{E}Z_{i})|$,
which implies that
$\|\sum_{i=1}^{n}\frac{Z_{i}^{+}-\mathbb{E}Z_{i}^{+}}{\sqrt{n}}\|_{L^{1}}$ is
also stochastically bounded. Thus (1) yields

$\sqrt{P((\theta^{T}X)^{+}>t)}\leq\frac{1}{C_{2}}\mathbb{E}\left|\frac{\sum_{i=1}^{n}I_{(\theta^{T}X_{i})^{+}>t}-P((\theta^{T}X_{i})^{+}>t)}{\sqrt{n}}\right|,$

for $med((\theta^{T}X)^{+})<t<Q_{\theta}(1-\frac{C_{1}}{n})$, where
$Q_{\theta}(t)=\inf\\{x:P((\theta^{T}X)^{+}\leq x)\geq t\\}$. After
integrating both sides, we have

$\displaystyle\int_{S^{d-1}}\int_{med((\theta^{T}X)^{+})}^{Q_{\theta}(1-\frac{C_{1}}{n})}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)$
$\displaystyle\leq\frac{1}{C_{2}}\int_{S^{d-1}}\int_{med((\theta^{T}X)^{+})}^{Q_{\theta}(1-\frac{C_{1}}{n})}\mathbb{E}\left|\frac{\sum_{i=1}^{n}I_{(\theta^{T}X_{i})^{+}>t}-P((\theta^{T}X_{i})^{+}>t)}{\sqrt{n}}\right|dtd\sigma(\theta)$
$\displaystyle\leq\frac{1}{C_{2}}\int_{S^{d-1}}\int_{0}^{+\infty}\mathbb{E}\left|\frac{\sum_{i=1}^{n}I_{(\theta^{T}X_{i})^{+}>t}-P((\theta^{T}X_{i})^{+}>t)}{\sqrt{n}}\right|dtd\sigma(\theta)$
$\displaystyle=\frac{1}{C_{2}}E\left\|\frac{\sum_{i=1}^{n}(Z_{i}^{+}-\mathbb{E}Z_{i}^{+})}{\sqrt{n}}\right\|_{L^{1}}.$

It implies that

$\sup_{n}\int_{S^{d-1}}\int_{med((\theta^{T}X)^{+})}^{Q_{\theta}(1-\frac{C_{1}}{n})}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)\leq\sup_{n}\frac{1}{C_{2}}\mathbb{E}\left\|\frac{\sum_{i=1}^{n}(Z_{i}^{+}-\mathbb{E}Z_{i}^{+})}{\sqrt{n}}\right\|_{L^{1}}<\infty.$

Since $Q_{\theta}(1-\frac{C_{2}}{n})\rightarrow ess\sup(\theta^{T}X)^{+}$ as
$n\to\infty$. We have

$\displaystyle\int_{S^{d-1}}\int_{med((\theta^{T}X)^{+})}^{+\infty}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)$
$\displaystyle=\int_{S^{d-1}}\liminf_{n\to\infty}\int_{med((\theta^{T}X)^{+})}^{Q_{\theta}(1-\frac{C_{1}}{n})}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)$
$\displaystyle\leq\liminf_{n\to\infty}\int_{S^{d-1}}\int_{med((\theta^{T}X)^{+})}^{Q_{\theta}(1-\frac{C_{1}}{n})}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)$
$\displaystyle\leq\sup_{n}\int_{S^{d-1}}\int_{med((\theta^{T}X)^{+})}^{Q_{\theta}(1-\frac{C_{1}}{n})}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)$
$\displaystyle<\infty,$

where the first inequality follows from the Fatou lemma. In the other hand,
from the definition of the median, we have $P((\theta^{T}X)^{+}\geq
med((\theta^{T}X)^{+})\geq\frac{1}{2}$ and then

$P(\|X\|\geq med((\theta^{T}X)^{+})\geq P(|\theta^{T}X|\geq
med((\theta^{T}X)^{+})\geq P((\theta^{T}X)^{+}\geq
med((\theta^{T}X)^{+})\geq\frac{1}{2}.$

Combining with $\mathbb{E}\|X\|<\infty$ and $P(\|X\|\geq
t)\leq\frac{\mathbb{E}\|X\|}{t}$. Let $t=med((\theta^{T}X)^{+})$, we have
$med((\theta^{T}X)^{+}\leq 2\mathbb{E}\|X\|$.

Thus
$\int_{S^{d-1}}\int_{2\mathbb{E}\|X\|}^{+\infty}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)<\infty$
and it implies that

$\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P((\theta^{T}X)^{+}>t)}dtd\sigma(\theta)<\infty.$

For $\hat{X},\hat{X_{1}},\cdots,\hat{X_{n}}$ defined as above.

When $t\leq 0$, we have $I_{\hat{X}^{-}\geq t}-P(\hat{X}^{-}\geq t)=0$, thus
$|\sum_{i=1}^{n}I_{\hat{X_{i}}\leq-t}-P(\hat{X_{i}}\leq-t)|\geq
0=|\sum_{i=1}^{n}I_{\hat{X_{i}}^{-}\geq t}-P(\hat{X_{i}}^{-}\geq t)|$.

When $t>0$, we have $\hat{X}\leq-t\Leftrightarrow\hat{X}^{-}\geq t$, so
$I_{\hat{X}\leq-t}-P(\hat{X}\leq-t)=I_{\hat{X}^{-}\geq t}-P(\hat{X}^{-}\geq
t)$.

From above, for any $t\in\mathbb{R}$,
$|\sum_{i=1}^{n}I_{\hat{X}_{i}\leq-t}-P(\hat{X}_{i}\leq-t)|\geq|\sum_{i=1}^{n}I_{\hat{X}_{i}^{-}\geq
t}-P(\hat{X}_{i}^{-}\geq t)|$ holds.

Let $Z^{-}=I_{(\theta^{T}X)^{-}\geq t}$, for the sequence
$\sum_{i=1}^{n}Y_{i}$, we have

$\displaystyle\int_{-\infty}^{+\infty}|\sum_{i=1}^{n}Y_{i}|dt$
$\displaystyle=\int_{-\infty}^{+\infty}|\sum_{i=1}^{n}(I_{\theta^{T}X>t}-P(\theta^{T}X>t))|dt$
$\displaystyle=\int_{-\infty}^{+\infty}|\sum_{i=1}^{n}(I_{\theta^{T}X\leq
t}-P(\theta^{T}X\leq t))|dt$
$\displaystyle=\int_{-\infty}^{+\infty}|\sum_{i=1}^{n}(I_{\theta^{T}X\leq-t}-P(\theta^{T}X\leq-t))|dt$
$\displaystyle\geq\int_{-\infty}^{+\infty}|\sum_{i=1}^{n}(I_{(\theta^{T}X)^{-}\geq
t}-P((\theta^{T}X)^{-}\geq t))|dt,$

which implies that the sequence
$\|\sum_{i=1}^{n}\frac{Z_{i}^{-}-\mathbb{E}Z_{i}^{-}}{\sqrt{n}}\|_{L^{1}}$ is
also stochastically bounded. Thus similarly, we can obtain that

$\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P((\theta^{T}X)^{-}>t)}dtd\sigma(\theta)<\infty.$

Since

$\displaystyle\sqrt{P(|\theta^{T}X|>t)}$
$\displaystyle=\sqrt{P((\theta^{T}X)^{+}+(\theta^{T}X)^{-}>t)}$
$\displaystyle\leq\sqrt{P((\theta^{T}X)^{+}>\frac{t}{2})+P((\theta^{T}X)^{-}>\frac{t}{2})}$
$\displaystyle\leq\sqrt{P((\theta^{T}X)^{+}>\frac{t}{2})}+\sqrt{P((\theta^{T}X)^{-}>\frac{t}{2})}.$

Now we can conclude that
$\int_{S^{d-1}}\int_{0}^{+\infty}\sqrt{P(|\theta^{T}X|>t)}dtd\sigma(\theta)<\infty$.
And it leads to that $\int_{0}^{+\infty}\sqrt{P(\|X\|>t)}dt<\infty$.

Sufficiency: If $\Lambda_{2,1}(X)<\infty$, Corollary 1 implies that there
exists a constant $M>0$ such that
$\sup_{n}\mathbb{E}[\sqrt{n}SW_{1}(\mu_{n},\mu)]\leq M$. Therefore, the
conclusion follows from Markov inequality.
∎

###  9.3. Proof of Proposition 1

###### Proof.

(1): The proof is based on the method in Proposition 2.1 in [23] with just a
little change. [37] explored the central limit theorem for $W_{1}$ in one
dimension under $i.i.d.$ and non-$i.i.d.$ conditions. Due to the similarity
between $W_{1}$ in one dimension and $SW_{1}$, the method also works for
$SW_{1}$.

Following from the same decomposition:

$|x+h|-|x|=hI_{x+h\geq 0,x>0}-hI_{x+h<0,x<0}+|h|I_{x=0}+(|x+h|-|x|)(I_{x+h\geq
0,x<0}+I_{x+h<0,x>0}),$

which yields that

$\displaystyle|x+h|-|x|=$ $\displaystyle
hI_{x>0}-hI_{x<0}+|h|I_{x=0}-hI_{x+h<0,x>0}+hI_{x+h\geq 0,x<0}$
$\displaystyle(|x+h|-|x|)(I_{x+h\geq 0,x<0}+I_{x+h<0,x>0}).$

Then we have

$|x+h|-|x|=hI_{x>0}-hI_{x<0}+|h|I_{x=0}+2R(h,x),$ (2)

where $R(h,x)\leq|h|(I_{x+h\geq 0,x<0}+I_{x+h<0,x>0})$.

Let $x=F(\theta,t)-G(\theta,t)$, $h=F_{n}(\theta,t)-F(\theta,t)$ in (2), we
can deduce that

$\sqrt{n}(|F_{n}-G|-|F-G|)=sign\\{F-G\\}\sqrt{n}(F_{n}-F)I_{F\neq
G}+\sqrt{n}|F_{n}-F|I_{F=G}+2R_{n},$

where

$|R_{n}|\leq\sqrt{n}|F_{n}-F|(I_{F_{n}\geq G,F<G}+I_{F_{n}<G,F>G}),$ (3)

and

$sign(x)=\left\\{\ \begin{aligned} 1&,&x>0,\\\ 0&,&x=0,\\\
-1&,&x<0.\end{aligned}\right.$

Recall that

$\sqrt{n}(SW_{1}(\mu_{n},\nu)-SW_{1}(\mu,\nu))=\sqrt{n}\int_{S^{d-1}}\int_{-\infty}^{\infty}(|F_{n}(\theta,t)-G(\theta,t)|-|F(\theta,t)-G(\theta,t)|)ddtd\sigma(\theta).$

By central limit theorem in $L^{1}(S^{d-1}\times\mathbb{R})$ and continuous
mapping theorem (notice that $sign\\{F-G\\},I_{F\neq G},I_{F=G}\in
L^{\infty}(S^{d-1}\times\mathbb{R})$), it’s sufficient to prove that
$\|R_{n}\|_{L^{1}}$ converges to 0 in probability as $n\to\infty$.

On the other hand, provided $\mu\in\mathcal{P}_{2,1}(\mathbb{R}^{d})$, by
Fubini theorem and Cauchy inequality, we have

$\displaystyle\mathbb{E}[\|R_{n}\|_{L^{1}}]$
$\displaystyle=\int_{S^{d-1}}\int_{-\infty}^{\infty}\mathbb{E}|R_{n}(\theta,t)|dtd\sigma(\theta)$
$\displaystyle\leq\int_{S^{d-1}}\int_{-\infty}^{\infty}(\mathbb{E}|R_{n}(\theta,t)|^{2})^{1/2}dtd\sigma(\theta)$
$\displaystyle\leq\int_{S^{d-1}}\int_{-\infty}^{\infty}\sqrt{P(|\theta^{T}X_{1}|>t)}dtd\sigma(\theta)<\infty.$

With dominated convergence theorem, it’s sufficient to prove that
$\mathbb{E}|R_{n}(\theta,t)|$ converges to 0 as $n\to\infty$ for any
$(\theta,t)\in S^{d-1}\times\mathbb{R}$.

Let $T_{n}(\theta,t)=\sqrt{n}|F_{n}-F|(I_{F_{n}\geq G,F<G}+I_{F_{n}<G,F>G})$.
By (3) and Markov inequality, we have

$\displaystyle\mathbb{E}|R_{n}(\theta,t)|\leq\mathbb{E}T_{n}(\theta,t)I_{T_{n}(\theta,t)>M}$
$\displaystyle+MP(F_{n}(\theta,t)\geq G(\theta,t),F(\theta,t)<G(\theta,t))$
$\displaystyle+MP(F_{n}(\theta,t)<G(\theta,t),F(\theta,t)>G(\theta,t)).$

Since $F_{n}(\theta,t)$ converges almost surely to $F(\theta,t)$, we can
assert that

$\lim\limits_{n\to\infty}P(F_{n}(\theta,t)\geq
G(\theta,t),F(\theta,t)<G(\theta,t))+P(F_{n}(\theta,t)<G(\theta,t),F(\theta,t)>G(\theta,t))=0.$

Moreover, by Markov inequality, we have

$\mathbb{E}T_{n}(\theta,t)I_{T_{n}(\theta,t)>M}\leq\frac{\mathbb{E}T_{n}(\theta,t)^{2}}{M}\leq\frac{1}{M}.$

Combining above, we have

$\lim\limits_{n\to\infty}\lim\sup_{n\to\infty}\mathbb{E}T_{n}(\theta,t)I_{T_{n}(\theta,t)>M}=0.$

Therefore, $\mathbb{E}|R_{n}(\theta,t)|$ converges to 0 as $n\to\infty$ for
any $(\theta,t)\in S^{d-1}\times\mathbb{R}$, which yields the conclusion.

(2) Let
$x=F(\theta,t)-G(\theta,t),h=(F_{n}(\theta,t)-G_{n}(\theta,t))-(F(\theta,t)-G(\theta,t))$,
by the same proof in (1), we have the conclusion. ∎

###  9.4. Proof of Proposition 2

###### Proof.

First, Fubini theorem implies

$\displaystyle\mathbb{E}[SW_{1}(\mu_{n},\mu)]$
$\displaystyle=\int_{S^{d-1}}\mathbb{E}[W_{1}(\theta_{\\#}^{*}\mu_{n},\theta_{\\#}^{*}\mu)]d\sigma(\theta)$
$\displaystyle=\int_{S^{d-1}}\mathbb{E}[\int_{-\infty}^{+\infty}|F_{n}(\theta,t)-F(\theta,t)|dt]d\sigma(\theta).$

To invoke dominated convergence theorem, we need to estimate the part inside
the integral.

$\displaystyle\mathbb{E}\left[\int_{-\infty}^{+\infty}|F_{n}(\theta,t)-F(\theta,t)|dt\right]$
$\displaystyle=\int_{-\infty}^{+\infty}\mathbb{E}[|F_{n}(\theta,t)-F(\theta,t)|]dt$
$\displaystyle=\int_{-\infty}^{0}\mathbb{E}[|F_{n}(\theta,t)-F(\theta,t)|]dt+\int_{0}^{+\infty}\mathbb{E}[|F_{n}(\theta,t)-F(\theta,t)|]dt.$

For $t\in(-\infty,0]$, we have

$\displaystyle\mathbb{E}[|F_{n}(\theta,t)-F(\theta,t)|]$
$\displaystyle\leq\mathbb{E}[F_{n}(\theta,t)+F(\theta,t)]$
$\displaystyle=2F(\theta,t)$ $\displaystyle=2P(\theta^{T}X\leq t)\leq
2P(\|X\|\geq|t|).$

For $t\in(0,+\infty)$, we have

$\displaystyle\mathbb{E}[|F_{n}(\theta,t)-F(\theta,t)|]$
$\displaystyle\leq\mathbb{E}[1-F_{n}(\theta,t)+1-F(\theta,t)]$
$\displaystyle=2(1-F(\theta,t))$ $\displaystyle=2P(\theta^{T}X>t)\leq
2P(\|X\|>t).$

Combining above, we obtain that

$\mathbb{E}\left[\int_{-\infty}^{+\infty}|F_{n}(\theta,t)-F(\theta,t)|dt\right]\leq
4\int_{0}^{+\infty}P(\|X\|\geq t)dt=4\mathbb{E}[\|X\|].$

Theorem 2.14 in [42] gives the same result for the Wasserstein distance in one
dimension, which implies that
$\mathbb{E}[W_{1}(\theta_{\\#}^{*}\mu_{n},\theta_{\\#}^{*}\mu)]\to 0,as\
n\to\infty$ for any $\theta\in S^{d-1}$. Thus the conclusion follows from the
dominated convergence theorem. ∎

###  9.5. Proof of Corollary 1

###### Proof.

Sufficiency:

$\displaystyle\mathbb{E}[SW_{1}(\mu_{n},\mu)]$
$\displaystyle=\int_{S^{d-1}}\int_{-\infty}^{+\infty}\mathbb{E}|F_{n}(\theta,t)-F(\theta,t)|dtd\sigma(\theta)$
$\displaystyle\leq\int_{S^{d-1}}\int_{-\infty}^{+\infty}\left(\mathbb{E}|F_{n}(\theta,t)-F(\theta,t)|^{2}\right)^{1/2}dtd\sigma(\theta)$
$\displaystyle=\frac{1}{\sqrt{n}}\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dtd\sigma(\theta).$

Thus $\mathbb{E}[SW_{1}(\mu_{n},\mu)]=\mathcal{O}(\frac{1}{\sqrt{n}})$, Since

$\Lambda_{2,1}(X)<\infty\Leftrightarrow\int_{S^{d-1}}\int_{-\infty}^{+\infty}\sqrt{F(\theta,t)(1-F(\theta,t))}dtd\sigma(\theta)<\infty.$

Necessity: $\mathbb{E}[SW_{1}(\mu_{n}),\mu]=\mathcal{O}(\frac{1}{\sqrt{n}})$
implies that the sequence in Theorem 1(ii) is stochastically bounded, so
$\Lambda_{2,1}(X)<\infty$. ∎

###  9.6. Proof of Proposition 3

By Lemma 3.4 in [42], that is for any independent mean zero random variables
$\xi_{1},\cdots,\xi_{n}$, the following inequality holds.

$\mathbb{E}|\sum\limits_{k=1}^{n}\xi_{k}|\geq
c\mathbb{E}\left(\sum\limits_{k=1}^{n}\xi_{k}^{2}\right)^{1/2},$

where $c$ is an absolute constant.

Note that

$\mathbb{E}[SW_{1}(\mu_{n},\mu)]=\int_{S^{d-1}}\int_{-\infty}^{+\infty}\mathbb{E}|F_{n}(\theta,t)-F(\theta,t)|dtd\sigma(\theta).$

And let $\xi_{k}=I_{\theta^{T}X_{i}\leq t}-F(\theta,t)$, we have

$\displaystyle\mathbb{E}|F_{n}(\theta,t)-F(\theta,t)|$
$\displaystyle\geq\frac{c}{n}\mathbb{E}\left(\sum\limits_{k=1}^{n}\xi_{k}^{2}\right)^{1/2}$
$\displaystyle\geq\frac{c}{n}\left(\sum\limits_{k=1}^{n}(\mathbb{E}|\xi_{k}|)^{2}\right)^{1/2}$
$\displaystyle=\frac{2c}{\sqrt{n}}F(\theta,t)(1-F(\theta,t)),$

where the second inequality follows from the Minkowski inequality.

Then

$\mathbb{E}[SW_{1}(\mu_{n},\mu)]\geq\frac{2c}{\sqrt{n}}\int_{S^{d-1}}\left[\int_{-\infty}^{+\infty}F(\theta,t)(1-F(\theta,t))dt\right]d\sigma(\theta).$

Note that for a real-valued random variable $Y$ with CDF $G(y)$ and let
$Y^{{}^{\prime}}$ be an independent copy of $Y$, the equality
$\int_{-\infty}^{\infty}G(y)(1-G(y))dy=\frac{1}{2}\mathbb{E}|Y-Y^{{}^{\prime}}|$
holds. Let $X\sim\mu$ and $X^{{}^{\prime}}$ be an independent copy of $X$,
then we have

$\displaystyle\mathbb{E}[SW_{1}(\mu_{n},\mu)]$
$\displaystyle\geq\frac{c}{\sqrt{n}}\int_{S^{d-1}}\mathbb{E}|\theta^{T}X-\theta^{T}X^{{}^{\prime}}|d\sigma(\theta)$
$\displaystyle=\frac{c}{\sqrt{n}}\mathbb{E}\left[\int_{S^{d-1}}|\theta^{T}X-\theta^{T}X^{{}^{\prime}}|d\sigma(\theta)\right]$
$\displaystyle=\frac{c\gamma_{d}}{\sqrt{n}}\mathbb{E}\|X-X^{{}^{\prime}}\|,$

where $\gamma_{d}$ is a constant depending only on $d$.

In the next, we write $\mathbb{E}_{X}$ for taking expectation for $X$, then we
have

$\displaystyle\mathbb{E}\|X-\mathbb{E}X\|$
$\displaystyle=\mathbb{E}_{X}\|X-\mathbb{E}_{X}X-\mathbb{E}_{X^{{}^{\prime}}}(X^{{}^{\prime}}-\mathbb{E}_{X^{{}^{\prime}}}X^{{}^{\prime}})\|$
$\displaystyle=\mathbb{E}_{X}\|\mathbb{E}_{X^{{}^{\prime}}}(X-\mathbb{E}_{X}X)-(X^{{}^{\prime}}-\mathbb{E}_{X^{{}^{\prime}}}X^{{}^{\prime}})\|$
$\displaystyle\leq\mathbb{E}_{X,X^{{}^{\prime}}}\|(X-\mathbb{E}_{X}X)-(X^{{}^{\prime}}-\mathbb{E}_{X^{{}^{\prime}}}X^{{}^{\prime}})\|$
$\displaystyle=\mathbb{E}\|X-X^{{}^{\prime}}\|.$

Combining above, we conclude.

###  9.7. Proof of Proposition 4

###### Proof.

Let $F(\theta):=W_{p}^{p}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\nu)$, then
$SW_{p}^{p}(\mu,\nu)=\mathbb{E}_{\sigma}F(\theta)$. We firstly prove that
$F(\theta)$ is a Lipschitz continuous function with Lipschitz constant at most
$pW_{p}^{p-1}(\mu,\nu)(M_{p}(\mu)+M_{p}(\nu))$.

$\displaystyle|F(\theta_{1})-F(\theta_{2})|$
$\displaystyle=|W_{p}^{p}({\theta_{1}^{*}}_{\\#}\mu,{\theta_{1}^{*}}_{\\#}\nu)-W_{p}^{p}({\theta_{2}^{*}}_{\\#}\mu,{\theta_{2}^{*}}_{\\#}\nu)|$
$\displaystyle=p\xi^{p-1}|W_{p}({\theta_{1}^{*}}_{\\#}\mu,{\theta_{1}^{*}}_{\\#}\nu)-W_{p}({\theta_{2}^{*}}_{\\#}\mu,{\theta_{2}^{*}}_{\\#}\nu)|$
$\displaystyle\leq
p\xi^{p-1}[W_{p}({\theta_{1}^{*}}_{\\#}\mu,{\theta_{2}^{*}}_{\\#}\mu)+W_{p}({\theta_{1}^{*}}_{\\#}\nu,{\theta_{2}^{*}}_{\\#}\nu)]$
$\displaystyle\leq
pW_{p}^{p-1}(\mu,\nu)[W_{p}({\theta_{1}^{*}}_{\\#}\mu,{\theta_{2}^{*}}_{\\#}\mu)+W_{p}({\theta_{1}^{*}}_{\\#}\nu,{\theta_{2}^{*}}_{\\#}\nu)]$

where the second equality follows from the Lagrange Mean value Theorem and the
last inequality follows by that for
$W_{p}({\theta^{*}}_{\\#}\mu,{\theta^{*}}_{\\#}\nu)\leq W_{p}(\mu,\nu)$ for
any $\theta\in S^{d-1}$.

Notice that
$({\theta_{1}^{*}},{\theta_{2}^{*}})_{\\#}\mu\in\prod({\theta_{1}^{*}}_{\\#}\mu,{\theta_{2}^{*}}_{\\#}\mu)$
where
$({\theta_{1}^{*}},{\theta_{2}^{*}})(x)=({\theta_{1}^{*}}(x),{\theta_{2}^{*}}(x))$.
Thus we have

$\displaystyle W_{p}({\theta_{1}^{*}}_{\\#}\mu,{\theta_{2}^{*}}_{\\#}\mu)$
$\displaystyle\leq\left(\int_{\mathbb{R}\times\mathbb{R}}|x-y|^{p}d({\theta_{1}^{*}},{\theta_{2}^{*}})_{\\#}\mu(x,y)\right)^{\frac{1}{p}}$
$\displaystyle=\left(\int_{\mathbb{R}^{d}}|\theta_{1}^{*}(z)-\theta_{2}^{*}(z)|^{p}d\mu(z)\right)^{\frac{1}{p}}$
$\displaystyle=\left(\int_{\mathbb{R}^{d}}|\langle\theta_{1}-\theta_{2},z\rangle|^{p}d\mu(z)\right)^{\frac{1}{p}}$
$\displaystyle\leq\|\theta_{1}-\theta_{2}\|\left(\int_{\mathbb{R}^{d}}\|z\|^{p}d\mu(z)\right)^{\frac{1}{p}}$
$\displaystyle=\|\theta_{1}-\theta_{2}\|M_{p}(\mu).$

Similarly, we have
$W_{p}({\theta_{1}^{*}}_{\\#}\nu,{\theta_{2}^{*}}_{\\#}\nu)\leq|\theta_{1}-\theta_{2}|M_{p}(\nu)$.
Thus, we obtain

$\displaystyle|F(\theta_{1})-F(\theta_{2})|$ $\displaystyle\leq
pW_{p}^{p-1}(\mu,\nu)(M_{p}(\mu)+M_{p}(\nu))\|\theta_{1}-\theta_{2}\|$
$\displaystyle\leq
pW_{p}^{p-1}(\mu,\nu)(M_{p}(\mu)+M_{p}(\nu))\rho(\theta_{1},\theta_{2})$

where $\rho(x,y):=\arccos\langle x,y\rangle$ is the geodesic distance in
$S^{d-1}$.

In the following, we need the concentration inequality of uniform distribution
over the $d$-dimensional unit sphere. By seeing $S^{d-1}$ as a compact
connected smooth Riemannian manifold, then Proposition 2.17 in [52] tells us
that for any 1-Lipschitz continuous function $f$ on $S^{d-1}$ and
$X\sim\sigma$, $f(X)$ is sub-Gaussian with parameter
${\widetilde{\sigma}}^{2}=\frac{1}{c(S^{d-1})}=\frac{1}{d-1}$, where
$c(S^{d-1})$ is infimum of Ricci curvature tensor over all tangent vectors.
Then from Hoeffding’s inequality (Proposition 2.5 in [44]), we have

$P\left(|\frac{F(\theta_{1})+\cdots+F(\theta_{n})}{n}-\mathbb{E}_{\sigma}[F(\theta)]|\geq\epsilon\right)\leq
2e^{-\frac{(d-1)n\epsilon^{2}}{2L^{2}}}.$

Therefore if requiring
$P\left(|\frac{F(\theta_{1})+\cdots+F(\theta_{n})}{n}-\mathbb{E}_{\sigma}[F(\theta)]|\geq\epsilon\right)\leq\delta$,
we can let $2e^{-\frac{(d-1)n\epsilon^{2}}{2L^{2}}}\leq\delta$, i.e.
$n\geq\frac{2L^{2}}{(d-1)\epsilon^{2}}\log\frac{2}{\delta}$. ∎

###  9.8. Proof of Corollary 3

###### Proof.

$\displaystyle M_{2}^{2}(\mu)$
$\displaystyle=\int_{\mathbb{R}^{d}}x_{1}^{2}+\cdots+x_{d}^{2}d\mu(x)$
$\displaystyle=\int_{\mathbb{R}^{d}}f\circ\pi_{1}(x)+\cdots+f\circ\pi_{d}(x)\mu(x)$
$\displaystyle=\int_{\mathbb{R}}f(y)d(\pi_{i})_{\\#}\mu(y)+\cdots+f(y)d(\pi_{d})_{\\#}\mu(y)$
$\displaystyle=\sum\limits_{i=1}^{d}M_{2}^{2}((\pi_{i})_{\\#}\mu)\leq
d\max_{i}M_{2}^{2}((\pi_{i})_{\\#}\mu).$

Combining with Corollary 3 and $\frac{d}{d-1}\leq 2$ for $d\geq 2$, we have
the conclusion. ∎

###  9.9. Proof of Corollary 5

###### Proof.

Let

$\overline{SW}_{p}^{p}(\mu,\nu):=\int_{\mathbb{R}^{d}}W_{p}^{p}({\theta}_{\\#}^{*}\mu,{\theta}_{\\#}^{*}\nu)d\beta_{d}(\theta).$

where $\beta_{d}$ is the zero-mean Gaussian distribution with covariance
matrix $I_{d}$.

Then by calculation similar to Proposition 1 in [43], we have
$\overline{SW}_{p}^{p}(\mu,\nu)=d^{p/2}\widetilde{SW}_{p}^{p}(\mu,\nu)$. Thus
the conclusion follows by the concentration properties of Lipschitz functions
of Gaussian variables (Theorem 2.26 in [44]). ∎

###  9.10. Proof of Lemma 1

###### Proof.

$\displaystyle MSW_{1}(P_{n},P)$ $\displaystyle=\max_{\theta\in
S^{d-1}}W_{1}({\theta}_{\\#}^{*}P_{n},{\theta}_{\\#}^{*}P)$
$\displaystyle=\max_{\theta\in S^{d-1}}\sup_{g\in Lip_{1,0}(\mathbb{R})}\int
gd{\theta}_{\\#}^{*}P_{n}-\int gd{\theta}_{\\#}^{*}P$
$\displaystyle=\max_{\theta\in S^{d-1}}\sup_{g\in Lip_{1,0}(\mathbb{R})}\int
g(\theta^{T}x)dP_{n}(x)-\int g(\theta^{T}x)dP(x)$
$\displaystyle=\sup_{f\in\mathcal{F}}\int fdP_{n}-\int fdP$
$\displaystyle=\sup_{f\in\mathcal{F}}(P_{n}-P)f,$

where

$\mathcal{F}:=\\{f:\mathbb{R}^{d}\to\mathbb{R}|\ f(x)=g(\theta^{T}x),g\in
Lip_{1,0}(\mathbb{R}),\theta\in S^{d-1}\\}.$

∎

Before bounding the bracket number of $\mathcal{F}$, we need the following
lemmas:

######  Lemma 2.

For any positive constant $M$, we have

$\mathcal{N}_{[\ ]}(\epsilon,Lip_{1,0}([-M,M]),\|\cdot\|_{\infty})\leq
e^{\frac{4M}{\epsilon}\log 2}.$

######  Lemma 3.

$\mathcal{N}(\epsilon,S^{d-1},\|\cdot\|)\leq(1+\frac{4}{\epsilon})^{d}$.

###### Proof of Lemma 2:.

First, we divide $[0,M]\times[-M,M]$ into a grid of squares with side length
$\frac{\epsilon}{2}$. In $[0,\frac{\epsilon}{2}]$, let $g(x)=-x,f(x)=x$, then
for any $h\in Lip_{1,0}([0,M])$ and $x\in[0,\frac{\epsilon}{2}]$, $g(x)\leq
h(x)\leq f(x)$ holds, which means in $\in[0,\frac{\epsilon}{2}]$, $h\in[g,f]$.

In $[\frac{\epsilon}{2},2\frac{\epsilon}{2}]$, let $f_{1}(x)=\epsilon-x$ and
$g_{1}(x)=-\epsilon+x$. For any $h\in Lip_{1,0}([0,M])$, we are going to prove
that in $[\frac{\epsilon}{2},2\frac{\epsilon}{2}]$ there don’t exist two
points in $h$’s graph such that one is above strictly $f_{1}$’s graph and the
other is below strictly $g_{1}$’s graph. If not, there exist $x_{0}$ and
$x_{1}$ such that $h(x_{0})>f_{1}(x_{0})$ and $h(x_{1})<g_{1}(x_{1})$. Without
loss of generality, we can assume that $x_{0}<x_{1}$. The Lipschitz continuity
of $h$ implies that $h(x_{1})-h(x_{0})\geq x_{0}-x_{1}$, thus we have

$h(x_{1})\geq h(x_{0})+x_{0}-x_{1}>f_{1}(x_{0})+x_{0}-x_{1}=\epsilon-
x_{1}=f_{1}(x_{1})\geq g_{1}(x_{1}),$

which contradicts the assumption $h(x_{1})<g_{1}(x_{1})$.

So there are only three cases:

  * •

There exist points in $h$’s graph that are above strictly $f_{1}$’s graph.

By the consideration above, we can assert that $h(x)\geq g_{1}(x)$ for all
$x\in[\frac{\epsilon}{2},2\frac{\epsilon}{2}]$. It implies that in
$[\frac{\epsilon}{2},2\frac{\epsilon}{2}]$, $h\in[g_{1},f_{2}]$, where
$f_{2}(x):=x$.

  * •

There exist points in $h$’s graph that are below strictly $g_{1}$’s graph.

Thus $h(x)\leq f_{1}(x)$. As a consequence, $h\in[g_{2},f_{1}]$, where
$g_{2}(x):=-x$.

  * •

There exist points in $h$’s graph that are below $f_{1}$’s graph and above
$g_{1}$’s graph.

Then $h$ satisfies that $h\in[g_{1},f_{1}]$.

From the construction above, we can assert that if in
$[0,\frac{\epsilon}{2}]$, $h\in[g,f]$, then in
$[\frac{\epsilon}{2},2\frac{\epsilon}{2}]$,
$h\in[-\frac{\epsilon}{2}+g(\frac{\epsilon}{2})+x,\
-\frac{\epsilon}{2}+f(\frac{\epsilon}{2})+x]$ or
$h\in[\frac{\epsilon}{2}+g(\frac{\epsilon}{2})-x,\
\frac{\epsilon}{2}+f(\frac{\epsilon}{2})-x]$. Similarly, we can conclude that
if in $[0,k\frac{\epsilon}{2}]$, $h\in[g,f]$, then in
$[k\frac{\epsilon}{2},(k+1)\frac{\epsilon}{2}]$,
$h\in[-k\frac{\epsilon}{2}+g(k\frac{\epsilon}{2})+x,\
-k\frac{\epsilon}{2}+f(k\frac{\epsilon}{2})+x]$ or
$h\in[k\frac{\epsilon}{2}+g(k\frac{\epsilon}{2})-x,\
k\frac{\epsilon}{2}+f(k\frac{\epsilon}{2})-x]$. The conclusion implies that if
we have constructed the brackets in $[0,k\frac{\epsilon}{2}]$, then we can
construct the brackets in $[0,(k+1)\frac{\epsilon}{2}]$ which are only
doubled.

Thus by above, we have

$\mathcal{N}_{[\ ]}(\epsilon,Lip_{1,0}([0,M]),\|\cdot\|_{\infty})\leq
2^{\lceil\frac{M}{\frac{\epsilon}{2}}\rceil-1}\leq
2^{\frac{2M}{\epsilon}}=e^{\frac{2M}{\epsilon}\log 2}.$

It’s easy to see that

$\mathcal{N}_{[\
]}(\epsilon,Lip_{1,0}([-M,M]),\|\cdot\|_{\infty})\leq{\mathcal{N}_{[\
]}(\epsilon,Lip_{1,0}([0,M]),\|\cdot\|_{\infty})}^{2}\leq
e^{\frac{4M}{\epsilon}\log 2}.$

∎

Lemma 2 implies that $\log\mathcal{N}_{[\
]}(\epsilon,Lip_{1,0}([0,M]),\|\cdot\|_{\infty})=MO(\frac{1}{\epsilon})$. On
the other hand, we can obtain a lower bound for the bracketing entropy from
the construction above.

######  Corollary 10.

$\log\mathcal{N}_{[\
]}(\epsilon,Lip_{1,0}([-M,M]),\|\cdot\|_{\infty})=M\Theta(\frac{1}{\epsilon})$.

###### Proof.

It’s sufficient to prove the lower bound. In the construction above, we denote
the larger function in the $i$-th bracket by $f_{i}$. Thus we have that
$\|f_{i}-f_{j}\|_{\infty}=\epsilon,(i\neq j)$ if
$M=k\frac{\epsilon}{2},k\in\mathbb{N}$, which implies

$\displaystyle\log\mathcal{N}_{[\ ]}(\frac{\epsilon}{2},Lip_{1,0}([0,M])$
$\displaystyle\geq\log\mathcal{N}_{[\
]}(\frac{\epsilon}{2},Lip_{1,0}([0,\lfloor\frac{2M}{\epsilon}\rfloor\frac{\epsilon}{2}])$
$\displaystyle\geq\log 2^{\lfloor\frac{2M}{\epsilon}\rfloor-1}$
$\displaystyle=(\lfloor\frac{2M}{\epsilon}\rfloor-1)\log 2$
$\displaystyle=M\Omega(\frac{1}{\epsilon}).$

So we have $\log\mathcal{N}_{[\
]}(\epsilon,Lip_{1,0}([0,M]),\|\cdot\|_{\infty})=M\Theta(\frac{1}{\epsilon})$
and obviously

$\log\mathcal{N}_{[\
]}(\epsilon,Lip_{1,0}([-M,M]),\|\cdot\|_{\infty})=M\Theta(\frac{1}{\epsilon}).$

∎

###### Proof of Lemma 3:.

Notice that for a metric space $(\mathcal{X},d)$, if $A\subset
B\subset\mathcal{X}$, then
$\mathcal{N}(\epsilon,A,d)\leq\mathcal{N}(\frac{\epsilon}{2},B,d)$. Since for
the unit sphere $B_{2}(1)$ in $d$-dimensional Euclidean space, we have
$\mathcal{N}(\epsilon,B_{2}(1),\|\cdot\|)\leq(1+\frac{2}{\epsilon})^{d}$, thus

$\mathcal{N}(\epsilon,S^{d-1},\|\cdot\|)\leq\mathcal{N}(\frac{\epsilon}{2},B_{2}(1),\|\cdot\|)\leq(1+\frac{4}{\epsilon})^{d}.$

∎

###  9.11. Proof of Theorem 2

###### Proof.

We write $\mathcal{F}_{1}$ for the set consisting of the $\epsilon$-brackets
of $Lip_{1,0}([-M,M])$ constructed in the proof of Lemma 3, where $M$ is a
positive constant to be determined. Before constructing brackets for
$\mathcal{F}$, we need to extend the functions in brackets of
$\mathcal{F}_{1}$ first. For bracket $[g,f]\in\mathcal{F}_{1}$, when $x>M$,
let $f(x)=-M+f(M)+x,g(x)=M+g(M)-x$ and when $x<-M$, let
$f(x)=-M+f(-M)-x,g(x)=M+g(-M)+x$. Next, we construct the brackets of
$\mathcal{F}$. Recall that

$\mathcal{F}=\\{f:\mathbb{R}^{d}\to\mathbb{R}\ |\ f(x)=g(\theta^{T}x),g\in
Lip_{1,0}(\mathbb{R}),\theta\in S^{d-1}\\}.$

Let $\mathcal{G}$ be a minimal $\epsilon$-cover of $S^{d-1}$ in the sense of
Euclidean norm, that is
$|\mathcal{G}|=\mathcal{N}(\epsilon,S^{d-1},\|\cdot\|)$. Let
$\mathcal{H}=\\{[g(\theta^{T}x)-\epsilon\|x\|,f(\theta^{T}x)+\epsilon\|x\|]:[g,f]\in\mathcal{F}_{1},\
\theta\in\mathcal{G}\\}$. In the next, we are going to prove that
$\mathcal{H}$ is a $C\epsilon$-bracket cover of $\mathcal{F}$, where $C$ is a
constant depending only on the moment of $P$.

Given any $\hat{h}\in\mathcal{F}$, assume that
$\hat{h}(\cdot)=h(\theta^{T}\cdot)$, where $h\in Lip_{1,0}(\mathbb{R}),\
\theta\in S^{d-1}$. Thus by construction of $\mathcal{F}_{1}$, there exist
$[g,f]\in\mathcal{F}_{1}$ and $\theta_{1}\in\mathcal{G}$ such that $g(y)\leq
h(y)\leq f(y),\ \forall y\in\mathbb{R}$ and
$\|\theta-\theta_{1}\|_{2}\leq\epsilon$. We just need to restrict $h$ to
$[-M,M]$ and the existence of the bracket follows from the construction and
the extension. Then we have

$\displaystyle\hat{h}(x)$ $\displaystyle=h(\theta^{T}x)$
$\displaystyle=h(\theta^{T}x)-h(\theta_{1}^{T}x)+h(\theta_{1}^{T}x)$
$\displaystyle\leq|\theta^{T}x-\theta_{1}^{T}x|+h(\theta_{1}^{T}x)$
$\displaystyle\leq\|\theta-\theta_{1}\|\|x\|+h(\theta_{1}^{T}x)$
$\displaystyle\leq\epsilon\|x\|+f(\theta_{1}^{T}x).$

Similarly, $\hat{h}(x)\geq-\epsilon\|x\|+g(\theta_{1}^{T}x)$.

Next, we start to bound the $L_{2}(P)$-size of the brackets in $\mathcal{H}$.
Define

$c:=\|(f(\theta^{T}x)+\epsilon\|x\|)-(g(\theta^{T}x)-\epsilon\|x\|)\|_{L^{2}(P)}.$

Then

$\displaystyle c^{2}$
$\displaystyle=\int\left(f(\theta^{T}x)-g(\theta^{T}x)+2\epsilon\|x\|\right)^{2}dP(x)$
$\displaystyle\leq
2\int\left(f(\theta^{T}x)-g(\theta^{T}x)\right)^{2}dP(x)+8\epsilon^{2}\int\|x\|^{2}dP(x).$

The inequality follows by $(a+b)^{2}\leq 2(a^{2}+b^{2})$.

Denote the first term by
$I:=\int\left(f(\theta^{T}x)-g(\theta^{T}x)\right)^{2}dP(x)$.

For estimating $I$, we divide $I$ into two terms.

$\displaystyle
I=\int_{\\{|\theta^{T}x|>M\\}}\left(f(\theta^{T}x)-g(\theta^{T}x)\right)^{2}dP(x)+\int_{\\{|\theta^{T}x|\leq
M\\}}\left(f(\theta^{T}x)-g(\theta^{T}x)\right)^{2}dP(x).$

We write $I_{1}$ for the first term and $I_{2}$ for the last term.

From the construction of $f$ and $g$, we have

$I_{2}\leq P(|\theta^{T}x|\leq
M)\|f-g\|_{\infty}^{2}|_{[-M,M]}\leq\epsilon^{2}.$

For $I_{1}$, we have

$\displaystyle I_{1}$
$\displaystyle=\int_{\\{|\theta^{T}x|>M\\}}\left(f(\theta^{T}x)-g(\theta^{T}x)\right)^{2}dP(x)$
$\displaystyle\leq\int_{\\{|\theta^{T}x|>M\\}}4\|x\|^{2}dP(x)$
$\displaystyle\leq\int_{\\{\|x\|>M\\}}4\|x\|^{2}dP(x).$

Since when $y>M$, $-y\leq g(y)\leq f(y)\leq y$ , when $y<-M$, $y\leq g(y)\leq
f(y)\leq-y$, then when $|y|>M$, $|f(y)-g(y)|\leq 2|y|$. Thus when
$|\theta^{T}x|>M$, we have $|f(\theta^{T}x)-g(\theta^{T}x)|\leq
2|\theta^{T}x|\leq 2\|x\|$, the first inequality holds. The second inequality
follows by $\\{x:|\theta^{T}x|>M\\}\subset\\{x:\|x\|>M\\}$.

If the ($2+\delta$)-th moment of $P$ is finite, we have

$\displaystyle I_{1}$ $\displaystyle\leq 4\int_{\\{\|x\|>M\\}}\|x\|^{2}dP(x)$
$\displaystyle\leq
4\int_{\\{\|x\|>M\\}}\|x\|^{2+\delta}\frac{1}{M^{\delta}}dP(x)$
$\displaystyle\leq 4\frac{1}{M^{\delta}}\int\|x\|^{2+\delta}dP(x).$

Let $m_{p}=\int\|x\|^{p}dP(x)$, then

$I=I_{1}+I_{2}\leq 4\frac{1}{M^{\delta}}m_{2+\delta}+\epsilon^{2}.$

Then for $c$, we have

$c^{2}\leq 2I+8\epsilon^{2}m_{2}\leq
2\epsilon^{2}+8\frac{1}{M^{\delta}}m_{2+\delta}+8\epsilon^{2}m_{2}.$

Let $M=(\frac{1}{\epsilon})^{\frac{2}{\delta}}$, i.e.
$M^{\delta}=\frac{1}{\epsilon^{2}}$. Now, we have

$c^{2}\leq
2\epsilon^{2}+8\epsilon^{2}m_{2}+8\epsilon^{2}m_{2+\delta}=C^{2}\epsilon^{2},$

where $C:=\sqrt{2+8m_{2}+8m_{2+\delta}}$.

With these preparations above, we can estimate $\mathcal{N}_{[\
]}(C\epsilon,\mathcal{F},L_{2}(P))$.

$\displaystyle\mathcal{N}_{[\ ]}(C\epsilon,\mathcal{F},L_{2}(P))$
$\displaystyle\leq e^{4\frac{M}{\epsilon}\log 2}(1+\frac{4}{\epsilon})^{d}$
$\displaystyle=e^{4\log
2({\frac{1}{\epsilon}})^{1+\frac{2}{\delta}}}(1+\frac{4}{\epsilon})^{d}.$

Therefore

$\mathcal{N}_{[\ ]}(\epsilon,\mathcal{F},L_{2}(P))\leq e^{4\log
2({\frac{C}{\epsilon}})^{1+\frac{2}{\delta}}}(1+\frac{4C}{\epsilon})^{d}.$

Then for the bracketing entropy integral of $\mathcal{F}$, we have

$\displaystyle J_{[\ ]}(1,\mathcal{F},L_{2}(P))$
$\displaystyle=\int_{0}^{1}\sqrt{\log\mathcal{N}_{[\
]}(\epsilon,\mathcal{F},L_{2}(P))}d\epsilon$
$\displaystyle\leq\int_{0}^{1}\sqrt{4\log
2({\frac{C}{\epsilon}})^{1+\frac{2}{\delta}}+d\log(1+\frac{4C}{\epsilon})}d\epsilon$
$\displaystyle\leq\int_{0}^{1}\left(2\sqrt{\log
2}({\frac{C}{\epsilon}})^{\frac{1}{2}+\frac{1}{\delta}}+\sqrt{d\log(1+\frac{4C}{\epsilon})}\right)d\epsilon.$

The second inequality follows from $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ ($a,b\geq
0$). Observe that when $\frac{1}{2}+\frac{1}{\delta}<1$, i.e. $\delta>2$,
$J_{[\ ]}(1,\mathcal{F},L_{2}(P))<\infty$. Thus when the $(4+\delta)$-th
($\delta>0$) moment of $P$ is finite, $\mathcal{F}$ is $P$-Donsker. ∎

######  Remark 5.

Note that for $I_{1}$, we have a tighter estimation.

$\displaystyle I_{1}$
$\displaystyle=\int_{\\{|\theta^{T}x|>M\\}}\left(f(\theta^{T}x)-g(\theta^{T}x)\right)^{2}dP(x)$
$\displaystyle=\int_{\\{|y|>M\\}}(f(y)-g(y))^{2}d{\theta^{*}_{\\#}}P(y)$
$\displaystyle\leq\int_{\\{|y|>M\\}}4|y|^{2}d{\theta^{*}_{\\#}}P(y).$

Then the condition becomes $\sup\limits_{\theta\in
S^{d-1}}\mathbb{E}|\theta^{T}X|^{4+\delta}<\infty$, but it’s equivalent to
$\mathbb{E}\|X\|^{4+\delta}<\infty$.

###  9.12. Proof of Corollary 7

###### Proof.

Let $\mathcal{F}_{1}$ be a $\epsilon$-bracket cover of $\mathcal{F}|_{[0,M]}$
(in the sense of $\|\cdot\|_{\infty}$) with
$\log|\mathcal{F}_{1}|=c\frac{M^{\alpha}}{\epsilon^{\beta}}$. Then for any
$\epsilon$-bracket $[g,f]\in\mathcal{F}_{1}$, let $f(x)=-LM+f(M)+Lx,\
g(x)=LM+g(M)-Lx$ when $x>M$ and $f(x)=-LM+f(-M)-Lx,\ g(x)=LM+g(-M)+Lx$ when
$x<-M$.

Similarly let $\mathcal{G}$ be a minimal $\epsilon$-cover of $S^{d-1}$ in the
sense of Euclidean norm that is
$|\mathcal{G}|=\mathcal{N}(\epsilon,S^{d-1},\|\cdot\|)$. Then
$\mathcal{H}:=\\{[g(\theta^{T}x)-L\epsilon\|x||,f(\theta^{T}x)+L\epsilon\|x\|]:[g,f]\in\mathcal{F}_{1},\
\theta\in\mathcal{G}\\}$ is a $C\epsilon$-bracket cover of
$\widehat{\mathcal{F}}$ where $C$ depends only on the moment of $P$ and $L$.

From the same estimation as Theorem 2, let $M^{\delta}=\frac{1}{\epsilon^{2}}$
(provided the ($2+\delta$)-th moment of $P$ is finite), we have

$\displaystyle\|(f(\theta^{T}x)+L\epsilon\|x\|_{2})-(g(\theta^{T}x)-L\epsilon\|x||_{2})\|_{L^{2}(P)}$
$\displaystyle\leq
2\epsilon^{2}+8L^{2}m_{2}\epsilon^{2}+8L^{2}m_{2+\delta}\epsilon^{2}:=C^{2}\epsilon^{2}.$

Thus we have

$\log\mathcal{N}_{[\ ]}(\epsilon,\widehat{F},L_{2}(P))\leq
c(\frac{C}{\epsilon})^{\frac{2\alpha}{\delta}+\beta}+d\log(1+\frac{4C}{\epsilon}).$

Then the bracketing entropy integral of $\widehat{\mathcal{F}}$ is finite if
$\frac{\alpha}{\delta}+\frac{\beta}{2}<1$ i.e.
$\delta>\frac{2\alpha}{2-\beta}$. In this condition, $\widehat{\mathcal{F}}$
is $P$-Donsker. ∎

###  9.13. Proof of Theorem 3

###### Proof.

Note that

$\displaystyle\mathbb{E}[MSW_{1}(\mu_{n},\mu)]$
$\displaystyle=\mathbb{E}[\sup_{f\in\mathcal{F}}\int f(x)d\mu_{n}(x)-\int
f(x)d\mu(x)]$ $\displaystyle=\mathbb{E}[\sup_{f\in\mathcal{F}}\int
f(x)I_{\|x\|\leq M}d\mu_{n}(x)-\int f(x)I_{\|x\|\leq M}d\mu(x)+\int
f(x)I_{\|x\|>M}d\mu_{n}(x)-\int f(x)I_{\|x\|>M}d\mu(x)]$
$\displaystyle\leq\mathbb{E}[\sup_{f\in\mathcal{F}}\int f(x)I_{\|x\|\leq
M}d\mu_{n}(x)-\int f(x)I_{\|x\|\leq M}d\mu(x)+\sup_{f\in\mathcal{F}}\int
f(x)I_{\|x\|>M}d\mu_{n}(x)-\int f(x)I_{\|x\|>M}d\mu(x)]$
$\displaystyle=\mathbb{E}[\sup_{f\in\mathcal{F}_{M}}\int f(x)d\mu_{n}(x)-\int
f(x)d\mu(x)]+\mathbb{E}[\sup_{f\in\mathcal{F}_{M^{c}}}\int
f(x)d\mu_{n}(x)-\int f(x)d\mu(x)],$

where $M$ is constant to be determined and
$\mathcal{F}_{M}:=\\{f(x)I_{\|x\|\leq M}:\ f\in\mathcal{F}\\}$,
$\mathcal{F}_{M^{c}}:=\\{f(x)I_{\|x\|>M}:\ f\in\mathcal{F}\\}$. And let
$I_{1}$ be the first term above and $I_{2}$ be the last term.

By the standard symmetrization and Theorem 16 in [53], we have

$I_{1}\lesssim\mathbb{E}\left[\inf_{\delta>0}\left\\{\delta+\frac{1}{\sqrt{n}}\int_{\delta}^{\sigma_{n}}\sqrt{\log\mathcal{N}(\mathcal{F}_{M},\|\cdot\|_{L^{2}(\mu_{n})},\epsilon)}d\epsilon\right\\}\right],$
(4)

where $\sigma_{n}=\sup_{f\in\mathcal{F}_{M}}\|f\|_{L^{2}(\mu_{n})}$.

Recall that

$\mathcal{F}:=\\{f:\mathbb{R}^{d}\to\mathbb{R}\ |\ f(x)=g(\theta^{T}x),g\in
Lip_{1,0}(\mathbb{R}),\theta\in S^{d-1}\\}.$

Notice that for any $g_{1},g_{2}\in Lip_{1,0}([-M,M]),\theta_{1},\theta_{2}\in
S^{d-1}$ and $\|x\|\leq M$, we have

$\displaystyle|g_{1}(\theta_{1}^{T}x)-g_{2}(\theta_{2}^{T}x)|$
$\displaystyle\leq|g_{1}(\theta_{1}^{T}x)-g_{2}(\theta_{1}^{T}x)|+|g_{2}(\theta_{1}^{T}x)-g_{2}(\theta_{2}^{T}x)|$
$\displaystyle\leq\|g_{1}-g_{2}\|_{\infty}+\|\theta_{1}-\theta_{2}\|M.$

Therefore

$\displaystyle\mathcal{N}(\mathcal{F}_{M},\|\cdot\|_{\infty},\epsilon)$
$\displaystyle\leq\mathcal{N}(Lip_{1,0}([-M,M]),\|\cdot\|_{\infty},\frac{\epsilon}{2})\cdot\mathcal{N}(S^{d-1},\|\cdot\|_{2},\frac{\epsilon}{2M})$
$\displaystyle\leq e^{c\frac{M}{\epsilon}}(1+c\frac{M}{\epsilon})^{d},$

where $c$ is a universal constant.

Then by (4) and the fact that $\|f\|_{L^{2}(\mu_{n})}\leq\|f\|_{\infty}$, we
obtain that

$\displaystyle I_{1}$
$\displaystyle\lesssim\mathbb{E}\left[\inf_{\delta>0}\left\\{\delta+\frac{1}{\sqrt{n}}\int_{\delta}^{\sigma_{n}}\sqrt{\log\mathcal{N}(\mathcal{F}_{M},\|\cdot\|_{\infty},\epsilon)}d\epsilon\right\\}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\inf_{\delta>0}\left\\{\delta+\frac{1}{\sqrt{n}}\int_{\delta}^{\sigma_{n}}\sqrt{\frac{M}{\epsilon}}d\epsilon\right\\}\right]$
$\displaystyle=\mathbb{E}\left[\inf_{\delta>0}\left\\{\delta+\frac{1}{\sqrt{n}}2\sqrt{M}(\sqrt{\sigma_{n}}-\sqrt{\delta})\right\\}\right].$

By choosing $\delta=\frac{\sigma_{n}}{\sqrt{n}}$, we have

$\displaystyle I_{1}$
$\displaystyle\lesssim\frac{1}{\sqrt{n}}\mathbb{E}[\sigma_{n}]+\frac{1}{\sqrt{n}}\sqrt{M}\mathbb{E}[\sqrt{\sigma_{n}}].$

For $\sigma_{n}$, we have

$\displaystyle\mathbb{E}[\sigma_{n}]$
$\displaystyle=\mathbb{E}\left[\sup_{f\in\mathcal{F}_{M}}\sqrt{\frac{1}{n}\sum\limits_{i=1}^{n}f(X_{i})^{2}}\right]$
$\displaystyle\leq\mathbb{E}\left[\sqrt{\frac{1}{n}\sum\limits_{i=1}^{n}\|X_{i}\|^{2}I_{\|X_{i}\|\leq
M}}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}[\frac{1}{n}\sum\limits_{i=1}^{n}\|X_{i}\|^{2}I_{\|X_{i}\|\leq
M}]}$ $\displaystyle\leq\sqrt{\mathbb{E}[\|X\|^{2}]},$

where the second inequality follows by the fact that $t(x)=x^{\frac{1}{2}}$ is
concave and Jensen inequality. Similarly,
$\mathbb{E}[\sqrt{\sigma_{n}}]\leq\sqrt[4]{\mathbb{E}\|X\|^{2}}$.

Therefore under conditions (2), we have $I_{1}\lesssim\sqrt{\frac{M}{n}}$ and

$I_{2}\leq 2\mathbb{E}[\|X\|I_{\|X\|>M}]\leq
2\frac{\mathbb{E}\|X\|^{1+\delta}}{M^{\delta}}.$

Then

$\displaystyle\mathbb{E}[MSW_{1}(\mu_{n},\mu)]$ $\displaystyle\leq
I_{1}+I_{2}$
$\displaystyle\lesssim\sqrt{\frac{M}{n}}+\frac{\mathbb{E}\|X\|^{1+\delta}}{M^{\delta}}$
$\displaystyle\lesssim n^{-\frac{\delta}{1+2\delta}}=n^{-\frac{p-1}{2p-1}},$

where the last inequality follows by choosing $M=n^{\frac{1}{1+2\delta}}$.

Under condition (3), the result can be derived straightly from Theorem 3.5.13
in [54] and applying Markov inequality for the second term in the right of
(3.203).

Under condition (1), $\mathbb{E}[\|X\|^{2}]<\infty$ may not hold, so the
method above doesn’t work. But we can utilize Dudley’s integral inequality
directly (Corollary 5.25 in [55]).

By the standard symmetrization argument, we have

$I_{1}\leq
2\mathbb{E}_{X}\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}_{M}}\frac{1}{n}\sum\limits_{i=1}^{n}\epsilon_{i}f(X_{i}).$

With $X_{1},\cdots,X_{n}$ fixed, we define stochastic process indexed by
$\mathcal{F}_{M}$ as

$X_{f}=\frac{1}{n}\sum\limits_{i=1}^{n}\epsilon_{i}f(X_{i}).$

To invoke Dudley’s integral inequality, we need to verify that the random
process $(X_{f})_{f\in\mathcal{F}_{M}}$ is sub-Gaussian. By Hoeffding’s
inequality, we have

$\displaystyle\mathbb{E}_{\epsilon}[e^{\lambda(X_{f}-X_{g})}]$
$\displaystyle=\prod_{i=1}^{n}\mathbb{E}_{\epsilon}[e^{\frac{\lambda\epsilon_{i}(f(X_{i})-g(X_{i}))}{n}}]$
$\displaystyle\leq\prod_{i=1}^{n}e^{\frac{\lambda^{2}(f(X_{i})-g(X_{i}))^{2}}{2n^{2}}}$
$\displaystyle\leq e^{\frac{\lambda^{2}\|f-g\|_{\infty}^{2}}{2n}}.$

Therefore, Dudley’s integral inequality yields that

$\displaystyle I_{1}$
$\displaystyle\lesssim\mathbb{E}_{X}\mathbb{E}_{\epsilon}\sup_{f\in\mathcal{F}_{M}}\frac{1}{n}\sum\limits_{i=1}^{n}\epsilon_{i}f(X_{i})$
$\displaystyle\lesssim\frac{1}{\sqrt{n}}\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\mathcal{F}_{M},\|\cdot\|_{\infty},\epsilon)d\epsilon}$
$\displaystyle\lesssim\frac{1}{\sqrt{n}}\int_{0}^{M}\sqrt{\frac{M}{\epsilon}}d\epsilon$
$\displaystyle\lesssim\frac{M}{\sqrt{n}}.$

Therefore

$\displaystyle\mathbb{E}[MSW_{1}(\mu_{n},\mu)]$ $\displaystyle\leq
I_{1}+I_{2}$
$\displaystyle\lesssim\frac{M}{\sqrt{n}}+\frac{1}{M^{\delta}}\mathbb{E}[\|X\|^{1+\delta}]$
$\displaystyle\lesssim n^{-\frac{\delta}{2(1+\delta)}}=n^{-\frac{p-1}{2p}},$

where the last inequality follows by choosing $M=n^{-\frac{1}{2(2+\delta)}}$.
∎

###  9.14. Proof of Proposition 5

###### Proof.

By taking $MSW_{1}(\mu_{n},\mu)$ as a supremum of an empirical process, the
concentration inequalities follows from a direct application of Lemma 1 and
Theorem 4 in [47]. For brevity, We omit the details.

Assume that $\mu$ is induced by a $\sigma^{2}$-Subgaussian random vector $X$
with value in $\mathbb{R}^{d}$. Let
$g(x_{1},\cdots,x_{n})=\sup_{f\in\mathcal{F}}|\sum\limits_{i=1}^{n}\frac{f(x_{i})-\mathbb{E}f(X)}{n}|$.
It’s easy to verify that $g$ is $1/n$-Lipschitz continuous with respect to the
distance
$d((x_{1},\cdots,x_{n}),(x_{1}^{{}^{\prime}},\cdots,x_{n}^{{}^{\prime}})):=\sum\limits_{i=1}^{n}\|x_{i}-x_{i}^{{}^{\prime}}\|$.
Then

$MSW_{1}(\mu_{n},\mu)=\sup_{f\in\mathcal{F}}|\sum\limits_{i=1}^{n}\frac{f(X_{i})-\mathbb{E}f(X)}{n}|=g(X_{1},\cdots,X_{n}).$

To invoke transpotation cost inequality, we need to verify that $\mu$
satisfies the transpotation cost inequality. For $X\sim\mu$, let $Y$ be an
independent copy of $X$, for any $f\in Lip_{1}(\mathbb{R}^{d})$, we have

$\displaystyle\mathbb{E}e^{\lambda(f(X)-\mathbb{E}f(X))}$
$\displaystyle=\mathbb{E}_{X}e^{\lambda(f(X)-\mathbb{E}_{X}f(X))}$
$\displaystyle=\mathbb{E}_{X}e^{\lambda(\mathbb{E}_{Y}f(X)-\mathbb{E}_{Y}f(Y))}$
$\displaystyle=\mathbb{E}_{X}e^{\lambda\mathbb{E}_{Y}(f(X)-f(Y))}$
$\displaystyle\leq\mathbb{E}_{X,Y}e^{\lambda(f(X)-f(Y))}$
$\displaystyle=\frac{1}{2}\mathbb{E}_{X,Y}e^{\lambda(f(X)-f(Y))}+\frac{1}{2}\mathbb{E}_{X,Y}e^{-\lambda(f(X)-f(Y))}$
$\displaystyle\leq\frac{1}{2}\mathbb{E}_{X,Y}e^{\lambda\|X-Y\|}+\frac{1}{2}\mathbb{E}_{X,Y}e^{-\lambda\|X-Y\|}$
$\displaystyle=\mathbb{E}_{X,Y,\epsilon}e^{\lambda\epsilon\|X-Y\|}.$

By the fact that $X-Y$ is $2\sigma^{2}$-Subgaussian and Proposition 10 in
[45], we can infer that $\epsilon\|X-Y\|$ is $16d\sigma^{2}$-Subgaussian,
which implys that for any $f\in Lip_{1}(\mathbb{R}^{d})$, $f(X)$ is
$16d\sigma^{2}$-Sungaussian. Then from Bobkov Theorem (Theorem 4.8 in [55]),
the following inequality holds.

$W_{1}(\mu,\nu)\leq\sqrt{2(16d\sigma^{2})D(\nu\|\mu)},\ for\ \forall\
\nu\in\mathcal{P}(\mathbb{R}^{d}).$

By tensorization, we have

$W_{1}(\mu^{\otimes n},\nu)\leq\sqrt{2(16nd\sigma^{2})D(\nu\|\mu)},\ for\
\forall\ \nu\in\mathcal{P}(\mathbb{R}^{nd}).$

Since $g$ is $1/n$-Lipschitz continuous with respect to $d$, by Bobkov Theorem
we have

$P(|MSW_{1}(\mu_{n},\mu)-\mathbb{E}MSW_{1}(\mu_{n},\mu)|\geq t)\leq
2e^{-\frac{nt^{2}}{32d\sigma^{2}}}.$

And for $SW_{1}$, we have

$\displaystyle\mathbb{E}e^{\lambda(SW_{1}(\mu,\mu_{n})-\mathbb{E}SW_{1}(\mu,\mu_{n}))}$
$\displaystyle=\mathbb{E}e^{\lambda\int_{S^{d-1}}(W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n})-\mathbb{E}W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n}))d\sigma(\theta)}$
$\displaystyle\leq\mathbb{E}[\int_{S^{d-1}}e^{\lambda(W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n})-\mathbb{E}W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n})}d\sigma(\theta)]$
$\displaystyle=\int_{S^{d-1}}\mathbb{E}[e^{\lambda(W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n})-\mathbb{E}W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n}))}]d\sigma(\theta)$

Similarily, let $h(y_{1},\cdots,y_{n})=\sup\limits_{f\in
Lip_{1}(\mathbb{R})}\sum\limits_{i=1}^{n}|\frac{f(y_{i})-\mathbb{E}f(\theta^{T}X_{i})}{n}|$,
then $h$ is $1/n$-Lipschitz continuous with respect to the distance
$d((y_{1},\cdots,y_{n}),(y_{1}^{{}^{\prime}},\cdots,y_{n}^{{}^{\prime}})):=\sum\limits_{i=1}^{n}|y_{i}-y_{i}^{{}^{\prime}}|$.
Then we have
$W_{1}(\theta_{\\#}^{*}\mu,\theta_{\\#}^{*}\mu_{n})=h(\theta^{T}X_{1},\cdots,\theta^{T}X_{n}).$

By the fact that univariate random variable $\theta^{T}(X-Y)$ is symmetric, we
can infer that $\epsilon|\theta^{T}(X-Y)|$ has the common distribution with
$\epsilon(\theta^{T}(X-Y))$, which implys that $\epsilon|\theta^{T}(X-Y)|$ is
$2\sigma^{2}$-Subgaussian. By tensorization, we have

$W_{1}(({\theta_{\\#}^{*}\mu})^{\otimes
n},v)\leq\sqrt{2(2n\sigma^{2})D(\nu\|({\theta_{\\#}^{*}\mu})^{\otimes n})},\
for\ \forall\nu\in\mathcal{P}(\mathbb{R}^{n}).$

Then

$\mathbb{E}e^{\lambda(SW_{1}(\mu,\mu_{n})-\mathbb{E}SW_{1}(\mu,\mu_{n}))}\leq\int_{S^{d-1}}e^{-\frac{\lambda^{2}}{2}\frac{2\sigma^{2}}{n}}d\sigma(\theta)=e^{-\frac{\lambda^{2}}{2}\frac{2\sigma^{2}}{n}}.$

Thus,

$P(|SW_{1}(\mu_{n},\mu)-\mathbb{E}SW_{1}(\mu_{n},\mu)|\geq t)\leq
2e^{-\frac{nt^{2}}{4\sigma^{2}}}.$

∎

###  9.15. Proof of Corollary 10

###### Proof.

(i) Theorem 2 implies that $\mathcal{F}$ is a Donsker class under both $P$ and
$Q$, then the conclusion follows directly from Chapter 3.7 of [48].

(ii) It follows by Theorem 3.7.7 in [48]. ∎

###  9.16. Proof of Proposition 6

###### Proof.

Under (1), the proof is almost same as Theorem 2.3 in [56]. The only thing we
need to prove is that for each $\epsilon>0$ and each $\delta>0$ we can choose
some $r\in\mathbb{N}$ such that

$\mathbb{E}\int_{S^{d-1}\times[-r,r]^{c}}|P_{m}^{B}-Q_{n}^{B}|dtd\sigma(\theta)<\epsilon\delta.$

It’s easy to obtain a similar form as equation (8) in [56].

$\displaystyle\ \
\mathbb{E}\int_{S^{d-1}\times[-r,r]^{c}}|P_{m}^{B}-Q_{n}^{B}|dtd\sigma(\theta)$
$\displaystyle\leq\left(\mathbb{E}\int_{S^{d-1}\times[-r,r]^{c}}|P_{m}^{B}-Q_{n}^{B}|^{2}dtd\sigma(\theta)\right)^{1/2}$
$\displaystyle=\left(\int_{S^{d-1}\times[-r,r]^{c}}\mathbb{E}|P_{m}^{B}-Q_{n}^{B}|^{2}dtd\sigma(\theta)\right)^{1/2}$
$\displaystyle\leq\sqrt{\frac{m}{N}\frac{1}{m}\sum\limits_{i=1}^{m}\|X_{i}\|I_{\\{\|X_{i}\|>r\\}}+\frac{n}{N}\frac{1}{n}\sum\limits_{k=1}^{n}\|Y_{k}\|I_{\\{\|Y_{k}\|>r\\}}},$

where the first inequality follows from Cauchy inequality and the second
inequality follows from (8) in [56]. Given almost every
$X_{1},\cdots,X_{m},Y_{1},\cdots,Y_{n}$, the result follows from the law of
large numbers. Then by the same argument as Theorem 2.3 in [56], we conclude.

Under (ii), it follows immediately from Corollary 8. ∎

## References

  * [1] J. Weed and Q. Berthet, “Estimation of smooth densities in wasserstein distance,” in _Conference on Learning Theory_. PMLR, 2019, pp. 3118–3119.
  * [2] Y. Zemel and V. M. Panaretos, “Fréchet means and procrustes analysis in wasserstein space,” _Bernoulli_ , vol. 25, no. 2, pp. 932–976, 2019.
  * [3] E. Del Barrio, P. Gordaliza, H. Lescornel, and J.-M. Loubes, “Central limit theorem and bootstrap procedure for wasserstein’s variations with an application to structural relationships between distributions,” _Journal of Multivariate Analysis_ , vol. 169, pp. 341–362, 2019.
  * [4] P. Rigollet and J. Weed, “Entropic optimal transport is maximum-likelihood deconvolution,” _Comptes Rendus Mathematique_ , vol. 356, no. 11-12, pp. 1228–1235, 2018.
  * [5] R. Flamary, M. Cuturi, N. Courty, and A. Rakotomamonjy, “Wasserstein discriminant analysis,” _Machine Learning_ , vol. 107, no. 12, pp. 1923–1945, 2018.
  * [6] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville, “Improved training of wasserstein gans,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [7] M. Arjovsky, S. Chintala, and L. Bottou, “Wasserstein generative adversarial networks,” in _International conference on machine learning_. PMLR, 2017, pp. 214–223.
  * [8] P. Gordaliza, E. Del Barrio, G. Fabrice, and J.-M. Loubes, “Obtaining fairness using optimal transport theory,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 2357–2365.
  * [9] H. Lavenant, S. Claici, E. Chien, and J. Solomon, “Dynamical optimal transport on discrete surfaces,” _ACM Transactions on Graphics (TOG)_ , vol. 37, no. 6, pp. 1–16, 2018.
  * [10] J. Solomon, F. De Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas, “Convolutional wasserstein distances: Efficient optimal transportation on geometric domains,” _ACM Transactions on Graphics (ToG)_ , vol. 34, no. 4, pp. 1–11, 2015.
  * [11] N. Bonnotte, “Unidimensional and evolution methods for optimal transportation,” Ph.D. dissertation, Paris 11, 2013.
  * [12] J. Rabin, G. Peyré, J. Delon, and M. Bernot, “Wasserstein barycenter and its application to texture mixing,” in _International Conference on Scale Space and Variational Methods in Computer Vision_. Springer, 2011, pp. 435–446.
  * [13] I. Deshpande, Z. Zhang, and A. G. Schwing, “Generative modeling using the sliced wasserstein distance,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 3483–3491.
  * [14] S. Kolouri, P. E. Pope, C. E. Martin, and G. K. Rohde, “Sliced wasserstein auto-encoders,” in _International Conference on Learning Representations_ , 2018.
  * [15] M. Carriere, M. Cuturi, and S. Oudot, “Sliced wasserstein kernel for persistence diagrams,” in _International conference on machine learning_. PMLR, 2017, pp. 664–673.
  * [16] C.-Y. Lee, T. Batra, M. H. Baig, and D. Ulbricht, “Sliced wasserstein discrepancy for unsupervised domain adaptation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 10 285–10 295.
  * [17] I. Deshpande, Y.-T. Hu, R. Sun, A. Pyrros, N. Siddiqui, S. Koyejo, Z. Zhao, D. Forsyth, and A. G. Schwing, “Max-sliced wasserstein distance and its use for gans,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 10 648–10 656.
  * [18] K. Nadjahi, A. Durmus, L. Chizat, S. Kolouri, S. Shahrampour, and U. Simsekli, “Statistical and topological properties of sliced probability divergences,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 20 802–20 812, 2020.
  * [19] E. del Barrio, E. Giné, and C. Matrán, “Central limit theorems for the wasserstein distance between the empirical and the true distributions,” _Annals of Probability_ , pp. 1009–1071, 1999.
  * [20] E. Giné and J. Zinn, “Empirical processes indexed by lipschitz functions,” _The Annals of Probability_ , pp. 1329–1338, 1986.
  * [21] E. Del Barrio, E. Giné, and F. Utzet, “Asymptotics for l2 functionals of the empirical quantile process, with applications to tests of fit based on weighted wasserstein distances,” _Bernoulli_ , vol. 11, no. 1, pp. 131–189, 2005.
  * [22] P. Berthet and J.-C. Fort, “Weak convergence of empirical wasserstein type distances,” _arXiv preprint arXiv:1911.02389_ , 2019.
  * [23] P. Berthet, J. Dedecker, and F. Merlevède, “Central limit theorem and almost sure results for bivariate empirical w 1 distances,” 2020.
  * [24] E. Del Barrio and J.-M. Loubes, “Central limit theorems for empirical transportation cost in general dimension,” _The Annals of Probability_ , vol. 47, no. 2, pp. 926–951, 2019.
  * [25] E. Del Barrio, P. Gordaliza, and J.-M. Loubes, “A central limit theorem for lp transportation cost on the real line with application to fairness assessment in machine learning,” _Information and Inference: A Journal of the IMA_ , vol. 8, no. 4, pp. 817–849, 2019.
  * [26] T. Manole, S. Balakrishnan, J. Niles-Weed, and L. Wasserman, “Plugin estimation of smooth optimal transport maps,” _arXiv preprint arXiv:2107.12364_ , 2021.
  * [27] M. Sommerfeld and A. Munk, “Inference for empirical wasserstein distances on finite spaces,” _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , vol. 80, no. 1, pp. 219–238, 2018.
  * [28] C. Tameling, M. Sommerfeld, and A. Munk, “Empirical optimal transport on countable metric spaces: Distributional limits and statistical applications,” _The Annals of Applied Probability_ , vol. 29, no. 5, pp. 2744–2781, 2019.
  * [29] S. Nietert, Z. Goldfeld, and K. Kato, “Smooth $p$-wasserstein distance: Structure, empirical approximation, and statistical applications,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 8172–8183.
  * [30] M. Cuturi, “Sinkhorn distances: Lightspeed computation of optimal transport,” _Advances in neural information processing systems_ , vol. 26, 2013.
  * [31] J. Bigot, E. Cazelles, and N. Papadakis, “Central limit theorems for entropy-regularized optimal transport on finite spaces and statistical applications,” _Electronic Journal of Statistics_ , vol. 13, no. 2, pp. 5120–5150, 2019.
  * [32] M. Klatt, C. Tameling, and A. Munk, “Empirical regularized optimal transport: Statistical theory and applications,” _SIAM Journal on Mathematics of Data Science_ , vol. 2, no. 2, pp. 419–443, 2020.
  * [33] G. Mena and J. Niles-Weed, “Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [34] A. Van Der Vaart, “New donsker classes,” _The Annals of Probability_ , vol. 24, no. 4, pp. 2128–2140, 1996.
  * [35] R. Sadhu, Z. Goldfeld, and K. Kato, “Limit distribution theory for the smooth 1-wasserstein distance with applications,” _arXiv preprint arXiv:2107.13494_ , 2021.
  * [36] R. Okano and M. Imaizumi, “Inference for projection-based wasserstein distances on finite spaces,” _arXiv preprint arXiv:2202.05495_ , 2022.
  * [37] Z. Goldfeld, K. Kato, G. Rioux, and R. Sadhu, “Statistical inference with regularized optimal transport,” _arXiv preprint arXiv:2205.04283_ , 2022\.
  * [38] S. Dereich, M. Scheutzow, and R. Schottstedt, “Constructive quantization: Approximation by empirical measures,” in _Annales de l’IHP Probabilités et statistiques_ , vol. 49, no. 4, 2013, pp. 1183–1203.
  * [39] N. Fournier and A. Guillin, “On the rate of convergence in wasserstein distance of the empirical measure,” _Probability Theory and Related Fields_ , vol. 162, no. 3, pp. 707–738, 2015.
  * [40] J. Lei, “Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces,” _Bernoulli_ , vol. 26, no. 1, pp. 767–798, 2020.
  * [41] J. Weed and F. Bach, “Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance,” _Bernoulli_ , vol. 25, no. 4A, pp. 2620–2648, 2019.
  * [42] S. Bobkov and M. Ledoux, “One-dimensional empirical measures, order statistics and kantorovich transport distances,” _preprint_ , vol. 7127347, 2014.
  * [43] K. Nadjahi, A. Durmus, P. E. Jacob, R. Badeau, and U. Simsekli, “Fast approximation of the sliced-wasserstein distance using concentration of random projections,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [44] M. J. Wainwright, _High-dimensional statistics: A non-asymptotic viewpoint_. Cambridge University Press, 2019, vol. 48.
  * [45] J. Niles-Weed and P. Rigollet, “Estimation of wasserstein distances in the spiked transport model,” _arXiv preprint arXiv:1909.07513_ , 2019.
  * [46] T. Lin, Z. Zheng, E. Chen, M. Cuturi, and M. I. Jordan, “On projection robust optimal transport: Sample complexity and model misspecification,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2021, pp. 262–270.
  * [47] R. Adamczak, “A tail inequality for suprema of unbounded empirical processes with applications to markov chains,” _Electronic Journal of Probability_ , vol. 13, pp. 1000–1034, 2008.
  * [48] A. W. Van Der Vaart, A. W. van der Vaart, A. van der Vaart, and J. Wellner, _Weak convergence and empirical processes: with applications to statistics_. Springer Science & Business Media, 1996.
  * [49] J. Cárcamo, A. Cuevas, and L.-A. Rodríguez, “Directional differentiability for supremum-type functionals: statistical applications,” _Bernoulli_ , vol. 26, no. 3, pp. 2143–2175, 2020.
  * [50] M. Ledoux and M. Talagrand, _Probability in Banach Spaces: isoperimetry and processes_. Springer Science & Business Media, 1991, vol. 23.
  * [51] Z. Goldfeld and K. Kato, “Limit distributions for smooth total variation and $\chi$ 2-divergence in high dimensions,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 2640–2645.
  * [52] M. Ledoux, _The concentration of measure phenomenon_. American Mathematical Soc., 2001, no. 89.
  * [53] U. von Luxburg and O. Bousquet, “Distance-based classification with lipschitz functions.” _J. Mach. Learn. Res._ , vol. 5, no. Jun, pp. 669–695, 2004\.
  * [54] E. Giné and R. Nickl, _Mathematical foundations of infinite-dimensional statistical models_. Cambridge university press, 2021.
  * [55] R. Van Handel, “Probability in high dimension,” PRINCETON UNIV NJ, Tech. Rep., 2014.
  * [56] L. Baringhaus and C. Franz, “On a new multivariate two-sample test,” _Journal of multivariate analysis_ , vol. 88, no. 1, pp. 190–206, 2004.