# Sample Complexity Bounds for Estimating Probability Divergences under
Invariances

Behrooz Tahmasebi
MIT CSAIL
<EMAIL_ADDRESS>Stefanie Jegelka
TU Munich and MIT CSAIL
<EMAIL_ADDRESS>
###### Abstract

Group-invariant probability distributions appear in many data-generative
models in machine learning, such as graphs, point clouds, and images. In
practice, one often needs to estimate divergences between such distributions.
In this work, we study how the inherent invariances, with respect to any
smooth action of a Lie group on a manifold, improve sample complexity when
estimating the Wasserstein distance, the Sobolev Integral Probability Metrics
(Sobolev IPMs), the Maximum Mean Discrepancy (MMD), and also the complexity of
the density estimation problem (in the $L^{2}$ and $L^{\infty}$ distance). Our
results indicate a two-fold gain: (1) reducing the sample complexity by a
multiplicative factor corresponding to the group size (for finite groups) or
the normalized volume of the quotient space (for groups of positive
dimension); (2) improving the exponent in the convergence rate (for groups of
positive dimension). These results are completely new for groups of positive
dimension and extend recent bounds for finite group actions.

##  1 Introduction

Estimating the optimal transportation distance [50, 51, 40] between
probability measures is a fundamental problem in statistics, with many
applications in machine learning, from Generative Adversarial Networks (GANs)
[22, 2, 39, 31] to domain adaptation and generalization [18, 14, 13],
geometric data processing (e.g., Wasserstein barycenters [15] and intrinsic
dimension estimation [7]), biomedical research [53], and control and dynamical
systems [9].

Estimating the Wasserstein distance is known to be a difficult task in
general, and it suffers from the curse of dimensionality [49]. The slow
convergence rate is generally unimprovable, as there exist probability
measures that are difficult to estimate. However, those hard instances barely
appear in practice when we study more structured probability measures. Indeed,
in many applications (e.g., graphs, point clouds, molecules, spectral data),
the underlying probability measures are invariant with respect to a group
action on the input space. As observed in recent works [6, 12], considering
the group invariances in the mathematical model can help improve the
convergence rate of the Wasserstein distance and the Sobolev Integral
Probability Metrics (Sobolev IPMs), with applications, e.g., to generative
models for invariant data.

Table 1: Summary of the Main Results

Divergence Measure | $\delta_{G}$ | $\kappa_{G}$
---|---|---
Wasserstein Distance (Theorem 1) | $\operatorname*{vol}(\mathcal{M}/G)$ | $1/d$
Wasserstein Distance ($s$-smooth, Theorem 2) | $\operatorname*{vol}(\mathcal{M}/G)$ | $(s+1)/(2s+d)$
Sobolev IPMs ($\alpha<d/2$, Theorem 3) | $\operatorname*{vol}(\mathcal{M}/G)$ | $(s+\alpha)/(2s+d)$
Sobolev IPMs ($\alpha>d/2$, MMD regime, Theorem 4) | $\mathcal{Z}(\alpha;G)$ | 1/2
Density Estimation in $L^{2}$ Distance (Theorem 5) | $\operatorname*{vol}(\mathcal{M}/G)$ | $s/(2s+d)$
Density Estimation in $L^{\infty}$ Distance ($s>d/2$, Theorem 6) | $(\operatorname*{vol}(\mathcal{M}/G))^{\frac{2s}{s-d/2}}$ | $(s-d/2)/(2s+d)$

  * •

*For any divergence measure $D$ in the table, we prove that there exists an estimator $\tilde{\mu}$, as a function of $n$ i.i.d. samples from $\mu$, such that $\mathbb{E}[D(\mu,\tilde{\mu})]\lesssim\Big{(}\frac{\delta_{G}}{n}\Big{)}^{\kappa_{G}}$. Sobolev IPMs use the Sobolev space $\mathcal{H}^{\alpha}(\mathcal{M})$ as test functions, for some $\alpha\geq 0$. Moreover, $d\mu/dx\in\mathcal{H}^{s}(\mathcal{M})$ for some $s\geq 0$. Also, $d$ denotes the dimension of the quotient space $\mathcal{M}/G$, and $\mathcal{Z}(\alpha;G)$ is the zeta function of the manifold when it is restricted to the invariant eigenfunction of the Laplace-Beltrami operator with respect to the group $G$.

In this paper, we study the sample complexity gain of invariances for
estimating probability measures in the Wasserstein distance, the Sobolev IPMs,
the Maximum Mean Discrepancy (MMD), and also for the density estimation
problem (in $L^{2}$ and $L^{\infty}$ distance). We consider probability
measures supported on a connected compact smooth manifold $\mathcal{M}$ that
are invariant with respect to a smooth action of a Lie group $G$ on
$\mathcal{M}$. In this general setting, given a (Borel) probability measure
$\mu$, supported on the manifold $\mathcal{M}$, we prove that there exists an
estimator $\tilde{\mu}$ (as a function of $n$ i.i.d. samples from $\mu$), such
that

$\displaystyle\mathbb{E}[D(\mu,\tilde{\mu})]\lesssim\Big{(}\frac{\delta_{G}}{n}\Big{)}^{\kappa_{G}},$
(1)

where $D$ can be replaced by the Wasserstein distance, the Sobolev IPMs, the
MMD, and also the $L^{2}(\mathcal{M})$ and $L^{\infty}(\mathcal{M})$ distance
between distributions (the density estimation problem in $L^{2}(\mathcal{M})$
and $L^{\infty}(\mathcal{M})$). The exponent $\kappa_{G}$ and the factor
$\delta_{G}$ depend on the distribution’s smoothness properties and the
quotient space’s dimension and volume.

The new sample complexity bound shows two different aspects of gain of
invariances. First, the quantity $\kappa_{G}$ is observed to be a non-
increasing function of the quotient space’s dimension $d$, so compared to the
general case (i.e., without invariances, $G=\\{\text{id}_{G}\\}$), the
exponent is improved, as $d$ can be potentially as small as
$\dim(\mathcal{M})-\dim(G)$.

Second, the factor $\delta_{G}$ is a non-decreasing function of the quotient
space’s volume $\operatorname*{vol}(\mathcal{M}/G)$, which can be potentially
much smaller than $\operatorname*{vol}(\mathcal{M})$. For instance, it can be
$\operatorname*{vol}(\mathcal{M})/|G|$ for finite groups. In particular, we
have $\delta_{G}=\operatorname*{vol}(\mathcal{M}/G)$ for estimating the
Wasserstein distance. Therefore, for finite groups (i.e., $\dim(G)=0$), we may
view the gain of invariances for sample complexity (compared to the general
case) as replacing the number of samples $n$ by $n\times|G|$ in the classical
convergence rate of the Wasserstein distance estimation (without invariances).
This is intuitively reasonable: the gain of invariances for finite groups is
that each sample effectively conveys the information of $|G|$ samples when
comparing the invariant case to the general case. Our result proves this
intuition formally.

The upper bound proved in this paper is completely new for groups of positive
dimension. For finite groups, it extends a recent result for submanifolds (of
full dimension) of $\mathbb{R}^{d}$ under $1$-Lipschitz group actions [12] to
arbitrary manifolds and arbitrary Lie groups.

We further study the convergence rate of estimating probability divergences
for smooth distributions. Indeed, for probability measures having a density
with respect to the uniform distribution on the manifold, with $s$ times
square-integrable derivatives (known as being in the Sobolev space
$\mathcal{H}^{s}(\mathcal{M})$), we prove upper bounds on the convergence rate
that exhibit the same two-fold gain for the sample complexity as discussed
above, namely a factor in the “effective” number of samples, and an
improvement in the exponent. Note that all the proven upper bounds in the
paper reduce to the known tight bounds on estimating without invariances if we
set $G=\\{\text{id}_{G}\\}$ (i.e., the trivial group).

Our findings cannot be derived immediately from known results on estimating
the Wasserstein distance or Sobolev IPMs. Instead of the idea of using
covering numbers, which are used in a recent work [12], we use a Fourier
approach to bounding the error. Specifically, we use the theory of the
Laplace-Beltrami operator on manifolds, and via a new version of Weyl’s law,
which captures the sparsity of the Fourier series on manifolds, as well as
ideas from differential geometry and Fourier analysis, we prove the main
result.

In short, in this paper, we make the following contributions:

  * •

We prove convergence rates for estimating the Wasserstein distance for any
invariant probability measure to a smooth Lie group action on a connected
compact manifold (Theorem 1). Moreover, we extend this result to smooth
distributions under invariances (Theorem 2).

  * •

We prove convergence rates for estimating the Sobolev IPMs (Theorem 3) and
Maximum Mean Discrepancy (MMD, Theorem 4) under group invariances.

  * •

We prove convergence rates for the density estimation problem in
$L^{2}(\mathcal{M})$ and $L^{\infty}(\mathcal{M})$ distance under invariances
(Theorem 5 and Theorem 6).

##  2 Related Work

Optimal transportation has been an extensive area of research for the last few
decades [50, 51]. The Kantorovich duality [27] allows the dual formulation of
the optimal transportation problem used in this paper. The study of the
convergence rate of the Wasserstein distance is a classical problem [49, 19,
52, 8, 29, 10, 36, 2, 33, 32, 38, 21]. Canas and Rosasco [11] use the
Wasserstein distance for learning probability measures on manifolds. The
computational aspects of optimal transport in machine learning are also
addressed in [37].

Group-invariant probability measures have many applications in machine
learning; for example, in addition to what was presented in the previous
section, in group equivariant GANs [16, 6], normalizing flow [5] and
equivariant flows [28].

In a recent paper, Chen et al. [12] studied the gain of invariances for
estimating the Wasserstein distance, and they proved upper bounds on the
convergence rate for finite groups with $1$-Lipschitz actions of submanifolds
(of full dimension) of $\mathbb{R}^{d}$, while our rates hold for any group
(including groups of positive dimension), and any manifold, thus extending the
previous results. In another closely related work, the gain of group
invariances is investigated for the kernel ridge regression problem on
manifolds [46]. While we study completely different divergence estimation
problems here, we follow the approach proposed in [46] to use the Laplace-
Beltrami operator (i.e., Fourier basis) to study the benefits of invariances.
For more on the benefits of invariances, see [4].

It is known that the convergence rate of estimating the Wasserstein distance
can be improved if the densities are smooth [41, 19, 30, 35]. The study of
convergence rates of the Sobolev IPMs for smooth distributions has
applications, e.g., in Sobolev GANs [33]. See [20, 23, 24, 42, 25, 1, 47, 48,
44, 43] for the study of achievable convergence rates and other properties of
MMDs and [26] for the density estimation problem (without invariances).

##  3 Preliminaries

Let $\mathcal{M}$ denote an arbitrary compact, connected, and smooth manifold
without boundary111The results can also be generalized to manifolds with
boundaries. But we consider boundaryless manifolds here for simplicity.. Let
$\mathcal{P}(\mathcal{M})$ denote the set of Borel probability measures on
$\mathcal{M}$, and also let $\operatorname*{Lip}(\mathcal{M})$ denote the set
of all measurable functions $f:\mathcal{M}\to\mathbb{R}$ such that
$|f(x)-f(y)|\leq\operatorname*{dist}(x,y)$, for all $x,y\in\mathcal{M}$, where
$\operatorname*{dist}(.,.)$ denotes the geodesic distance between points on
$\mathcal{M}$.

######  Definition 1.

The Wasserstein distance between any two $\mu,\nu\in\mathcal{P}(\mathcal{M})$
is defined as follows:

$\displaystyle
W_{1}(\mu,\nu):=\sup_{f\in\operatorname*{Lip}(\mathcal{M})}\Big{\\{}\int_{\mathcal{M}}fd\mu-\int_{\mathcal{M}}fd\nu\Big{\\}}.$
(2)

For any (unknown) probability measures $\mu,\nu\in\mathcal{P}(\mathcal{M})$,
assume that we are given independent samples
$X_{1},X_{2},\ldots,X_{n}\overset{\text{i.i.d.}}{\sim}\mu$ and
$Y_{1},Y_{2},\ldots,Y_{n}\overset{\text{i.i.d.}}{\sim}\nu$. The goal is to
estimate $D(\mu,\nu)$, where $D$ denotes a metric distance between
distributions (such as the Wasserstein distance or a Sobolev Integral
Probability Metric), using the $2n$ independent samples. Note that given
estimations of the (unknown) probability measures $\mu,\nu$ as a function of
their i.i.d. samples, such as $\tilde{\mu},\tilde{\nu}$, one can estimate
$D(\mu,\nu)$ by the triangle inequality:

$\displaystyle|D(\tilde{\mu},\tilde{\nu})-D(\mu,\nu)|\leq
D(\mu,\tilde{\mu})+D(\nu,\tilde{\nu}).$ (3)

Thus, $D(\tilde{\mu},\tilde{\nu})$ gives an estimation of the true distance
$D(\mu,\nu)$. This means that to study the convergence of the probability
divergences $D(\mu,\nu)$, one just needs to prove an upper bound on
$D(\mu,\tilde{\mu})$ for any probability measure
$\mu\in\mathcal{P}(\mathcal{M})$. In particular, we can focus on the problem
of estimating probability measures from samples in the $D(.,.)$ distance, and
study the effects of group invariances on its sample complexity.

Let $G$ be an arbitrary Lie group acting smoothly on $\mathcal{M}$. Without
loss of generality, we assume that $\mathcal{M}$ is equipped with a Riemannian
metric $g$ such that the action of $G$ is isometric on $\mathcal{M}$ with
respect to $g$. A probability measure $\mu\in\mathcal{P}(\mathcal{M})$ is
called $G$-invariant if for any Borel set $A\subseteq\mathcal{M}$ and all
$\tau\in G$, one has $\mu(A)=\mu(\tau A)$. For example, the uniform
distribution on $(\mathcal{M},g)$ is invariant with respect to any isometric
group action. Without loss of generality and just for simplicity, in this
paper, we assume that $\operatorname*{vol}(\mathcal{M})=1$, and we denote the
volume element on the manifold by $dx:=d\operatorname*{vol}_{g}(x)$.

##  4 Main Results

This section presents our main results on bounding $D(\mu,\tilde{\mu})$ under
invariances. We start with the Wasserstein distance for arbitrary probability
measures (Theorem 1) and then state the results for smooth distributions
(Theorem 2). Then, we study the sample complexity of Sobolev IPMs (Theorem 3)
and MMD (Theorem 4). Finally, we state our results for the density estimation
problem in $L^{2}(\mathcal{M})$ distance (Theorem 5) and in
$L^{\infty}(\mathcal{M})$ distance (Theorem 6).

###  4.1 Wasserstein Distance

For any probability measure $\mu\in\mathcal{P}(\mathcal{M})$, assume that we
are given samples $X_{1},X_{2},\ldots,X_{n}\overset{\text{i.i.d.}}{\sim}\mu$.
Let $\hat{\mu}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}$ denote the empirical
measure given $X_{1},X_{2},\ldots,X_{n}$, where $\delta_{x}$ denotes the Dirac
measure supported on $x\in\mathcal{M}$. The empirical measure $\hat{\mu}$ is
probably the most straightforward way to generate an estimator of $\mu$ from
samples. However, for $G$-invariant $\mu$, the empirical measure $\hat{\mu}$
is not necessarily $G$-invariant. To address this issue, we introduce and use
a modified empirical measure, where the estimation is restricted to only the
non-trivial parts of the Fourier transform of the measure (see the proof of
Theorem 1), as for measures that exhibit invariance, parts of the spectrum
that correspond to non-invariant functions are zero. Thus, the modified
empirical measure is always $G$-invariant. The first result of this paper is
the following theorem on the convergence of the Wasserstein distance for
arbitrary (Borel) probability measures using the modified empirical measure.

######  Theorem 1 (Convergence rate of the Wasserstein distance under
invariances).

For any $G$-invariant probability measure $\mu\in\mathcal{P}(\mathcal{M})$,
there exists an estimator $\tilde{\mu}\in\mathcal{P}(\mathcal{M})$, as a
function of $n$ i.i.d. samples $X_{1},X_{2}\ldots,X_{n}\sim\mu$, such that

$\displaystyle\mathbb{E}[W_{1}(\mu,\tilde{\mu})]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{1}{d}},$
(4)

where $\operatorname*{vol}(\mathcal{M}/G)$ is the volume of the quotient space
$\mathcal{M}/G$, and $d:=\dim(\mathcal{M}/G)\geq 3$. Also, the constant can
only depend on the manifold $\mathcal{M}$. Consequently, one has

$\displaystyle\mathbb{E}[|W_{1}(\tilde{\mu},\tilde{\nu})-W_{1}(\mu,\nu)|]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{1}{d}},$
(5)

for any $\mu,\nu\in\mathcal{P}(\mathcal{M})$.

In proving this theorem, there are some complications to overcome. For
instance, even though we used the notation $\dim(\mathcal{M}/G)$ and
$\operatorname*{vol}(\mathcal{M}/G)$, we notice that the quotient space
$\mathcal{M}/G$ is not necessarily a manifold. Also, it may exhibit boundary,
even though $\mathcal{M}$ is assumed to be boundaryless; this can make the
Fourier approach inapplicable to this problem [46]. To address this issue, we
define $\dim(\mathcal{M}/G)$ (or $\operatorname*{vol}(\mathcal{M}/G)$) as the
dimension (or the volume) of the principal part of the quotient space. The
principal part, denoted as $\mathcal{M}_{0}/G$, is a connected dense subset of
$\mathcal{M}/G$, such that it has a manifold structure inherited from
$\mathcal{M}$. Since it is a manifold, one can define its dimension/volume in
a natural way. It is guaranteed that the principal part exists, and is unique,
under the assumptions of this paper. Besides the principal part,
$\mathcal{M}/G$ is only a disjoint union of finitely many other manifolds, all
of lower dimension than the principal part. Note that
$\operatorname*{vol}(\mathcal{M}/G)$ is defined with respect to the dimension
of the quotient space $\dim(\mathcal{M}/G)$, so it is nonzero even if
$\dim(\mathcal{M}/G)<\dim(\mathcal{M})$.

To compare the convergence rate with the general case (i.e., not necessarily
$G$-invariant probability measures), note that if $G=\\{\text{id}_{G}\\}$,
then the convergence rate is
$\mathbb{E}[W_{1}(\mu,\hat{\mu})]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M})}{n}\Big{)}^{\frac{1}{\dim(\mathcal{M})}},$
as expected from the standard results for arbitrary probability measures [19].
This shows that the sample complexity of estimating the Wasserstein distance
is improved under invariances; (1) the new exponent is $\frac{1}{d}$ with
$d=\dim(\mathcal{M}/G)$, which can be potentially much greater than
$\frac{1}{\dim(\mathcal{M})}$, (2) the number of samples $n$ is multiplied by
$\operatorname*{vol}(\mathcal{M})/\operatorname*{vol}(\mathcal{M}/G)$. For
finite groups, if the action on $\mathcal{M}$ is effective222The action of a
group $G$ on a manifold $\mathcal{M}$ is called effective if any
$\text{id}_{G}\neq\tau\in G$ corresponds to a non-trivial bijection on
$\mathcal{M}$., then Theorem 1 shows that

$\displaystyle\mathbb{E}[W_{1}(\mu,\hat{\mu})]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M})}{n|G|}\Big{)}^{\frac{1}{\dim(\mathcal{M})}}.$
(6)

This could be interpreted as each sample being worth the same as $|G|$ samples
under invariances compared to the general (non-invariant) case. This improves
a recent result on the convergence of the Wasserstein metric under invariances
[12]. Chen et al. [12] prove that this rate is achievable for finite group
actions on a compact submanifold (of full dimension) of the Euclidean space
$\mathbb{R}^{d}$. However, our result is more general, holding for arbitrary
smooth compact manifolds, including spheres, tori, and hyperbolic spaces, and
also for arbitrary groups, not necessarily finite groups. Indeed, to the best
of our knowledge, the improvement in the exponent is new for the convergence
of the Wasserstein distance under invariances.

Let us observe the result of Theorem 1 in the following example.

######  Example 1.

Consider a point cloud as a set
$\\{p_{1},p_{2},\ldots,p_{m}\\}\subseteq(\mathbb{R}/\mathbb{Z})^{3}$ of $m$
points. For fixed $m$, we can think of each point cloud as a point on the
manifold $(\mathbb{R}/\mathbb{Z})^{3m}$. Point clouds are assumed to be
unchanged under a change of coordinates for all the points:

$\displaystyle\\{p_{1},p_{2},\ldots,p_{m}\\}\cong\\{Ap_{1},Ap_{2},\ldots,Ap_{m}\\},$
(7)

for any orthogonal matrix $A$. Also, permuting the points will not change the
point clouds. Let $G$ denote the group of invariances for point clouds defined
on $(\mathbb{R}/\mathbb{Z})^{3m}$ as above. Then, by Theorem 1, the gain of
invariances (i.e., estimating the Wasserstein distance on point clouds by
considering the invariances of the problem) is (1) improving the exponent from
$3m$ to $3m-6$, and (2) multiplying the number of samples $n$ by $m!$.

Proof sketch for Theorem 1. In this part, we give a quick proof sketch for
Theorem 1. The complete proof is available in the appendix.

To prove the theorem, we focus on an approach for upper bounding the
Wasserstein distance using the orthonormal basis $\phi_{\ell}\in
L^{2}(\mathcal{M})$, $\ell=0,1,\ldots$, of eigenfunctions of the Laplace-
Beltrami operator on $\mathcal{M}$ in $L^{2}(\mathcal{M})$ (see the appendix
for more details). This allows us to conclude that

$\displaystyle W_{1}^{2}(\mu,\nu)\leq$
$\displaystyle\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-\nu_{\ell})^{2}}{\lambda_{\ell}},$
(8)

where $\mu_{\ell}=\int_{\mathcal{M}}\phi_{\ell}d\mu$ for each $\ell$ (defined
similarly for $\nu$), and $\lambda_{\ell}$, $\ell=0,1,\ldots$, are the
eigenvalues of the Laplace-Beltrami operator on $\mathcal{M}$. This approach
shows that to upper bound the Wasserstein distance, all we need is to know how
sparse the sequence $\mu_{\ell}$, $\ell=0,1,\ldots$, is for a $G$-invariant
probability measure $\mu$. To this end, we use recent results on quantifying
the sparsity of the series for $G$-invariant functions defined on a connected
compact smooth manifold $(\mathcal{M},g)$ [46].

However, it turns out that using this method cannot guarantee a finite
convergence rate since high-frequency components in the sum accumulate a lot
of noise for empirical measures. To solve this issue, we use a mollifier
function with exponential tail decay (in the Laplace-Beltrami basis) and use
the theory of heat kernels on manifolds to achieve the final result. Further
detailed explanations are provided in the appendix, where the complete proof
is presented.

###  4.2 Wasserstein Distance for Smooth Densities

Assume that $\mu\in\mathcal{P}(\mathcal{M})$ is absolutely continuous with
respect to the uniform probability measure
$dx=\frac{1}{\operatorname*{vol}(\mathcal{M})}d\operatorname*{vol}_{g}(x)$ on
$(\mathcal{M},g)$. Assume that
$\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$, for some $s\geq 0$, where
$\mathcal{H}^{s}(\mathcal{M})$ denotes the Sobolev space of real-valued
measurable functions on $(\mathcal{M},g)$ having $s$ times square-integrable
derivatives. In this special case, the probability measure is smoother as $s$
grows.

It turns out that in this special case, the convergence rate of estimating the
Wasserstein distance as a function of the number of samples can be improved
using a new estimator $\tilde{\mu}$ (which is different from the modified
empirical estimator $\hat{\mu}$). The following theorem states the main result
for smooth distributions.

######  Theorem 2 (Convergence rate of the Wasserstein distance for smooth
distributions under invariances).

For any $G$-invariant probability measure $\mu\in\mathcal{P}(\mathcal{M})$
with $\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$ for some $s\geq 0$,
there exists an estimator $\tilde{\mu}\in\mathcal{P}(\mathcal{M})$, as a
function of $n$ i.i.d. samples $X_{1},X_{2}\ldots,X_{n}\sim\mu$, such that

$\displaystyle\mathbb{E}[W_{1}(\mu,$
$\displaystyle\tilde{\mu})]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{s+1}{2s+d}}\leavevmode\nobreak\
\Big{\|}\frac{d\mu}{dx}\Big{\|}_{\mathcal{H}^{s}(\mathcal{M})}^{\frac{d-2}{2s+d}},$

where $\operatorname*{vol}(\mathcal{M}/G)$ is the volume of the quotient space
$\mathcal{M}/G$ and $d:=\dim(\mathcal{M}/G)\geq 3$.

Theorem 2 shows that the gain of invariances for estimating the Wasserstein
distance for smooth distributions under invariances follows the same behavior
as before, for any $s\geq 0$. The two-fold gain is observed in the exponent
and the multiplicative factor. The new upper bound’s exponent interpolates
between the worst-case exponent $1/\dim(\mathcal{M})$ and $1/2$. As $s$ grows,
the exponent converges to $1/2$, as expected. Moreover, if
$G=\\{\text{id}_{G}\\}$, the bound reduces to the known convergence rate of
Wasserstein distance estimation under smoothness (without invariances) [30,
35].

Proof sketch for Theorem 2. To define the estimator $\tilde{\mu}$, we need to
review some facts about manifolds. The set of square-integrable $G$-invariant
functions on a connected, compact, smooth manifold $\mathcal{M}$ has an
orthonormal basis $\phi_{\ell}^{\text{inv}}\in L^{2}(\mathcal{M})$,
$\ell=0,1,\ldots$ that consists of the eigenfunctions of the Laplace-Beltrami
operator on $\mathcal{M}$ (see the appendix for more details). For example,
for the circle $\mathcal{M}=\mathbb{S}^{1}$, these functions correspond to the
sinusoidal waves that are invariant under the group action. Given $n$ samples
$X_{1},X_{2},\ldots,X_{n}$, the Borel measure $\tilde{\mu}$ is defined using
its Radon–Nikodym derivative with respect to the uniform probability measure
on $(\mathcal{M},g)$ as follows:

$\displaystyle\frac{d\tilde{\mu}}{dx}:=\frac{1}{n}\sum_{\ell=0}^{T-1}\sum_{i=1}^{n}\phi_{\ell}^{\text{inv}}(X_{i})\phi_{\ell}^{\text{inv}},$
(9)

where $T$ is a fixed positive integer (to be set). For any $T$, $\tilde{\mu}$
is a Borel measure, but generally, it can be a signed measure. We can then
take the closest probability measure to $\tilde{\mu}$ in the Wasserstein
distance as the final estimation for $\mu$. With a slight abuse of notation,
we denote the final output of the algorithm by $\tilde{\mu}$ again.

The parameter $T$ indicates when the sum is terminated. Note that estimating
the higher-order coefficients in the Fourier basis requires many samples, and
so if the Fourier coefficients decay quickly, one can neglect them and
truncate the sum at a finite $T$ with a small error. Indeed, choosing a higher
number $T$ of eigenfunctions reduces the bias of the estimator, but it also
increases the variance due to the randomness of sampling and the difficulty of
estimating the higher-order terms. Therefore, optimizing $T$ to balance the
bias and variance terms, according to the problem’s parameters, allows us to
achieve the best algorithm of this type (in terms of the convergence rate).
Note that the decay of the Fourier coefficients is provided using the Sobolev
space assumption (see the appendix for more details). We follow this approach
to prove Theorem 2.

###  4.3 Sobolev Integral Probability Metrics (Sobolev IPMs)

Sobolev Integral Probability Metrics (IPMs) are a family of integral
probability metrics [34, 45] that use the Sobolev space
$\mathcal{H}^{\alpha}(\mathcal{M})$ as the set of test functions to define a
divergence between probability measures.

######  Definition 2 (Sobolev IPMs).

For any $\alpha\geq 0$, the Sobolev IPM with parameter $\alpha$ is defined as

$\displaystyle D_{\alpha}(\mu,\nu)$
$\displaystyle:=\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})}\leq
1\end{subarray}}\Big{\\{}\mathbb{E}_{x\sim\mu}[f(x)]-\mathbb{E}_{x\sim\nu}[f(x)]\Big{\\}},$

for any (Borel) probability measures $\mu,\nu\in\mathcal{P}(\mathcal{M})$.

Here, we study the sample complexity of estimating Sobolev IPMs under
invariances, where we assume that we have samples from a smooth probability
measure $\mu$; more precisely,
$\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$ for some $s\geq 0$. Note that
for $\alpha>d/2$, the Sobolev IPMs are special cases of the Maximum Mean
Discrepancies (MMDs) with the Reproducing Kernel Hilbert Space (RKHS)
$\mathcal{H}^{\alpha}(\mathcal{M})$. Since we cover the convergence rates of
MMDs in the next section, we focus on the non-MMD regime where $\alpha\leq
d/2$.

######  Theorem 3 (Convergence rate of Sobolev IPMs under invariances).

Consider a $G$-invariant probability measure $\mu\in\mathcal{P}(\mathcal{M})$
with $\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$ for some $s\geq 0$.

  * •

If $\alpha<d/2$, then there exists an estimator
$\tilde{\mu}\in\mathcal{P}(\mathcal{M})$, as a function of $n$ i.i.d. samples
$X_{1},X_{2}\ldots,X_{n}\sim\mu$, such that

$\displaystyle\mathbb{E}[D_{\alpha}(\mu,\tilde{\mu})]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{s+\alpha}{2s+d}}\leavevmode\nobreak\
\Big{\|}\frac{d\mu}{dx}\Big{\|}_{\mathcal{H}^{s}(\mathcal{M})}^{\frac{d-2\alpha}{2s+d}},$

where the constant only depends on the manifold,
$\operatorname*{vol}(\mathcal{M}/G)$ is the volume of the quotient space
$\mathcal{M}/G$, and $d:=\dim(\mathcal{M}/G)$.

  * •

If $\alpha=d/2$, then there exists an estimator
$\tilde{\mu}\in\mathcal{P}(\mathcal{M})$ such that

$\displaystyle\mathbb{E}[D_{\alpha}(\mu,$
$\displaystyle\tilde{\mu})]\lesssim\sqrt{\frac{\operatorname*{vol}(\mathcal{M}/G)\log(n)}{n}}.$

We note that the same two-fold gain is observed in the convergence of the
Sobolev IPMs when $\alpha\leq d/2$.

The convergence results behave differently in the three regimes. First, if
$\alpha<d/2$, it extends the Wasserstein distance convergence rate for smooth
distributions to the Sobolev IPMs. Second, if $\alpha>d/2$, as we will see in
the next section, the rate saturates at $O(n^{-1/2})$. Finally, in the third
convergence regime where $\alpha=d/2$, we get a convergence rate of the order
$O(\sqrt{\log(n)/n})$.

######  Remark 1.

While Theorem 3 holds when (at least) $\frac{d\mu}{dx}\in L^{2}(\mathcal{M})$,
we can extend it to all (Borel) probability measures (for which the rate
corresponds to $s=0$), by the same approach as the proof of Theorem 1.

Proof sketch for Theorem 3. We follow the same approach as Theorem 2. Here,
the coefficients of the test functions $f\in\mathcal{H}^{\alpha}(\mathcal{M})$
in the Laplace-Beltrami basis can be upper bounded using the parameter
$\alpha$ (by the definition of Sobolev spaces). Then, we use an appropriate
cut-off frequency $T$, as a function of $\alpha$, to simultaneously minimize
the bias and variance terms.

###  4.4 Maximum Mean Discrepancy (MMD)

The Maximum Mean Discrepancy (MMD) is an integral probability metric
associated with a Positive Definite Symmetric (PDS) kernel, where the set of
test functions is a Reproducing Kernel Hilbert Space (RKHS) [3].

######  Definition 3.

For any PDS kernel $K:\mathcal{M}\times\mathcal{M}\to\mathbb{R}$ with the RKHS
denoted by $\mathcal{H}$, define

$\displaystyle D_{\mathcal{H}}(\mu,\nu)$
$\displaystyle:=\sup_{\begin{subarray}{c}f\in\mathcal{H}\\\
\|f\|_{\mathcal{H}}\leq
1\end{subarray}}\Big{\\{}\mathbb{E}_{x\sim\mu}[f(x)]-\mathbb{E}_{x\sim\nu}[f(x)]\Big{\\}},$

for any (Borel) probability measures $\mu,\nu\in\mathcal{P}(\mathcal{M})$.

Note that when $\alpha>d/2$, the Sobolev IPMs are MMDs, since in that case,
$\mathcal{H}^{\alpha}(\mathcal{M})$ is an RKHS (Sobolev Inequality). For
simplicity, we assume that the PDS kernel $K$ is diagonalizable in the
Laplace-Beltrami basis:

$\displaystyle
K(x,y)=\sum_{\ell=0}^{\infty}\xi_{\ell}\phi_{\ell}(x)\phi_{\ell}(y),$ (10)

for some $\xi_{\ell}\in\mathbb{R}$. This holds, for example, for the dot-
product kernels on the sphere $\mathbb{S}^{d-1}.$

To study the gain of invariances for estimating MMDs we need to define a
quantity that measures how many eigenfunctions can take non-zero coefficients
when restricted to the $G$-invariant functions. This weighted quantity must
also depend on the kernel decomposition in the Laplace-Beltrami operator. To
this end, define

$\displaystyle\operatorname*{Tr}(K;G):=\sum_{\lambda\neq
0}^{\infty}m(\lambda;G)|\xi_{\ell}(\lambda)|,$ (11)

where the sum is over all the eigenvalues of the Laplace-Beltrami operator on
the manifold $(\mathcal{M},g)$, and $m(\lambda;G)$ denotes the multiplicity of
the eigenvalue $\lambda$ when restricted to invariant eigenfunctions (see the
appendix for more details).

The following theorem related the quantity $\operatorname*{Tr}(K;G)$ to the
sample complexity gain of invariances for the MMD estimation.

######  Theorem 4.

Consider a $G$-invariant probability measure $\mu\in\mathcal{P}(\mathcal{M})$
with $\frac{d\mu}{dx}\in\mathcal{H}$. Then, there exists an estimator
$\tilde{\mu}\in\mathcal{P}(\mathcal{M})$ such that

$\displaystyle\mathbb{E}[D_{\mathcal{H}}(\mu,\hat{\mu})]\leq\sqrt{\frac{\operatorname*{Tr}(K;G)}{n}}.$
(12)

This allows us to immediately conclude the following result for the Sobolev
IPMs with $\alpha>d/2$ (i.e., the MMD regime).

######  Corollary 1.

(Gain of invariances for the Sobolev IPMs in the MMD regime). For any
$\alpha>d/2$, there exists an estimator
$\tilde{\mu}\in\mathcal{P}(\mathcal{M})$ such that

$\displaystyle\mathbb{E}[D_{\alpha}(\mu,$
$\displaystyle\tilde{\mu})]\leq\sqrt{\frac{\mathcal{Z}(\alpha;G)}{n}},$

where $\mathcal{Z}(\alpha;G)$ is the zeta function associated with the Lie
group action $G$ on the manifold $\mathcal{M}$:

$\displaystyle\mathcal{Z}(\alpha;G):=\sum_{\lambda\neq
0}m(\lambda;G)\lambda^{-\alpha}.$ (13)

Note that if $\alpha>d/2$ (i.e., the MMD regime), the exponent is always
$\frac{1}{2}$ and it does not depend on the group of invariances. Moreover,
the gain of invariances in this case can intuitively be understood as having
effectively

$\displaystyle n\times\frac{\mathcal{Z}(\alpha)}{\mathcal{Z}(\alpha;G)}$ (14)

samples instead of $n$ samples, where $\mathcal{Z}(\alpha)$ is the original
zeta function of the manifold (achieved via the trivial group
$G=\\{\text{id}_{G}\\}$). Therefore, the quantity
$\mathcal{Z}(\alpha)/\mathcal{Z}(\alpha;G)$ represents the sample complexity
gain of invariances in the kernel regime.

We provide an example to see how the behavior of the quantity
$\mathcal{Z}(\alpha)/\mathcal{Z}(\alpha;G)$ can depend on more delicate
information about the group action (i.e., more than the dimension of the group
and the volume of the quotient space).

######  Example 2.

Consider the unit circle $\mathbb{S}^{1}$ with the round metric. Note that if
we parameterize functions defined on $\mathbb{S}^{1}$ as functions of the
angle $\theta\in[0,2\pi)$, then the eigenfunctions of the Laplace-Beltrami
operator on $\mathbb{S}^{1}$ are the sinusoidal functions:

$\displaystyle\phi_{k}(\theta)=\exp(ik\theta)\quad\text{with}\quad\lambda=k^{2};\quad
k\in\mathbb{Z}.$ (15)

This allows us to compute the zeta function of the unit circle as

$\displaystyle\mathcal{Z}(\alpha)$ $\displaystyle=\sum_{\lambda\neq
0}^{\infty}m(\lambda)\lambda^{-\alpha}=2\sum_{k=1}^{\infty}k^{-2\alpha}=2\zeta(2\alpha),$
(16)

where $\zeta$ denotes the Riemann zeta function.

Now consider the finite group of rotations around the center:
$G:=\Big{\\{}\frac{2\pi j}{|G|}:j\in\mathbb{Z}\Big{\\}}.$ An eigenfunction
$\phi_{k}$ is invariant with respect to the action of $G$ if and only if we
have

$\displaystyle\phi_{k}(\theta)=\phi_{k}\Big{(}\theta+\frac{2\pi
j}{|G|}\Big{)},$ (17)

for any $\theta\in[0,2\pi)$ and $j\in\mathbb{Z}$. This is equivalent to having
$k$ divide $|G|$. Thus, we get

$\displaystyle\mathcal{Z}(\alpha;G)$ $\displaystyle=\sum_{\lambda\neq
0}^{\infty}m(\lambda;G)\lambda^{-\alpha}=2|G|^{-2\alpha}\sum_{k=1}^{\infty}k^{-2\alpha}=2|G|^{-2\alpha}\zeta(2\alpha).$
(18)

This shows that the gain of invariances in sample complexity, in this case, is
to have effectively

$\displaystyle n\times|G|^{2\alpha}$ (19)

many samples instead of $n$ samples. Note that $\alpha>d/2$ in the MMD regime.
Therefore, this example shows how the multiplicative gain can be improved from
$|G|$ to $|G|^{\alpha}$ in the MMD regime, which is in contrast to the problem
of estimating Sobolev IPMs in the non-MMD regime (Theorem 3).

######  Example 3.

Let $\mathbb{T}^{d}=[0,1]^{d}$ denote the $d$-dimensional flat torus, and
consider the isometric action of the group $G=\mathbb{T}^{\dim(G)}$ with the
circular shift on the first $\dim(G)$ coordinates of $\mathbb{T}^{d}$; for any
$\tau\in G$ and $x\in\mathbb{T}^{d}$:

$\displaystyle\tau x:=$
$\displaystyle(\tau_{1}+x_{1},\tau_{2}+x_{2},\ldots,\tau_{\dim(G)}+x_{\dim(G)},x_{\dim(G)+1},\ldots,x_{d}),$
(20)

where the coordinates are summed modulo one. Consider the heat kernel on
$\mathbb{T}^{d}$, defined as:

$\displaystyle K_{\beta}(x,y)=\sum_{0\neq
v\in\mathbb{Z}^{d}}\exp(-\beta\|v\|^{2}_{2}+2\pi i\langle
v,x+y\rangle_{L^{2}(\mathcal{M})}).$

Note that

$\displaystyle\operatorname*{Tr}(K_{\beta};G)$ $\displaystyle=\sum_{0\neq
v\in\mathbb{Z}^{d-\dim(G)}}\exp(-\beta\|v\|^{2}_{2})=\Theta_{\beta}^{(d-\dim(G))}-1,$
(21)

where

$\displaystyle\Theta_{\beta}:=\sum_{v\in\mathbb{Z}}\exp(-\beta v^{2})>1.$ (22)

This shows that the gain of having invariances with respect to the group $G$
for estimating the MMD with the heat kernel is to have effectively

$\displaystyle
n\times\frac{\operatorname*{Tr}(K;\\{\operatorname*{id}_{G}\\})}{\operatorname*{Tr}(K;G)}$
$\displaystyle=n\times\frac{\Theta_{\beta}^{d}-1}{\Theta_{\beta}^{d-\dim(G)}-1}\approx
n\times\Theta_{\beta}^{\dim(G)},$

many samples, instead of $n$. This shows that the gain of invariances can
exponentially depend on the Lie group dimension $\dim(G)$ while estimating
MMDs.

Proof sketch for Theorem 4. The spectrum of the test functions
$f\in\mathcal{H}$, in the Laplace-Beltrami basis, decays quickly in the MMD
case, and it can be shown that we can take $T\to\infty$, and use a similar
approach to Theorem 3 to prove the convergence result.

###  4.5 Density Estimation in $L^{2}(\mathcal{M})$

In this section, we present convergence results for estimating probability
density functions $\frac{d\mu}{dx}$ in $L^{2}(\mathcal{M})$ distance while
having $n$ i.i.d. samples from $\mu\in\mathcal{P}(\mathcal{M})$.

######  Theorem 5 (Convergence rate for density estimation in
$L^{2}(\mathcal{M})$ distance under invariances).

Consider a $G$-invariant probability measure $\mu\in\mathcal{P}(\mathcal{M})$
with $\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$. Then, there exists an
estimator $\tilde{\mu}\in\mathcal{P}(\mathcal{M})$ such that

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-$
$\displaystyle\frac{d\mu}{dx}\Big{\|}_{L^{2}(\mathcal{M})}\Big{]}\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{s}{2s+d}}\leavevmode\nobreak\
\Big{\|}\frac{d\mu}{dx}\Big{\|}_{L^{2}(\mathcal{M})}^{\frac{d}{2s+d}},$

where the constant only depends on the manifold,
$\operatorname*{vol}(\mathcal{M}/G)$ denotes the volume of the quotient space
$\mathcal{M}/G$, and $d:=\dim(\mathcal{M}/G)\geq 3$.

We observe that the density estimation problem in the $L^{2}(\mathcal{M})$
distance exploits the same two-fold gain as previous cases.

###  4.6 Density Estimation in $L^{\infty}(\mathcal{M})$

In this part, we study the gain of group invariances for the density
estimation problem in the $L^{\infty}(\mathcal{M})$ distance.

######  Theorem 6 (Convergence rate for density estimation in
$L^{\infty}(\mathcal{M})$ under invariances).

Consider a $G$-invariant probability measure $\mu\in\mathcal{P}(\mathcal{M})$
with $\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$ for some $s>d/2$. Then,
there exists an estimator $\tilde{\mu}\in\mathcal{P}(\mathcal{M})$, such that

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-$
$\displaystyle\frac{d\mu}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}\Big{]}\lesssim\Big{(}\frac{(\operatorname*{vol}(\mathcal{M}/G))^{\frac{2s}{s-d/2}}}{n}\Big{)}^{\frac{s-d/2}{2s+d}}\leavevmode\nobreak\
\Big{\|}\frac{d\mu}{dx}\Big{\|}_{\mathcal{H}^{s}(\mathcal{M})}^{\frac{d}{s+d/2}},$

where the constant only depends on the manifold.

Note that here we only get a convergence result if $s>d/2$; otherwise, the
density $\frac{d\mu}{dx}$ is not necessarily bounded, since
$\mathcal{H}^{s}(\mathcal{M})$ contains unbounded functions in that case
(Sobolev inequality).

######  Remark 2.

Note that in the density estimation in $L^{2}(\mathcal{M})$ distance, for
finite groups, the effective number of samples is $n\times|G|$, as intuitively
expected (for all $s,d$). However, for the $L^{\infty}(\mathcal{M})$ distance,
better rates are achievable according to Theorem 6. For instance, let us take
$d=4$ and $s=6$; then, for finite groups, the convergence rate becomes

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-$
$\displaystyle\frac{d\mu}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}\Big{]}\lesssim\Big{(}\frac{1}{n|G|^{3}}\Big{)}^{1/4}.$
(23)

This shows that the effective number of samples can potentially be more than
the linear gain, i.e., in this example, we have an effective number of samples
$n\times|G|^{3}$.

##  5 Conclusion

In this paper, we studied the sample complexity gain of group invariances for
estimating various divergence measures on manifolds, given a number of i.i.d.
samples. We extended the recent theoretical results for finite group actions
on submanifolds (of full dimension) of $\mathbb{R}^{d}$ to arbitrary manifolds
(including spheres, tori, hyperbolic spaces, etc.), and to arbitrary groups
(including groups of positive dimension). The gain of invariances in sample
complexity is two-fold: improving the exponent and multiplying the number of
samples by a factor depending on the group of invariances. We also studied
faster convergence rates for smooth distributions and showed a similar gain in
this case.

## Acknowledgments

The authors extend their appreciation to Philippe Rigollet for his valuable
inspiration. This work was supported by the NSF TRIPODS program (award
DMS-2022448), the Office of Naval Research award N00014-20-1-2023 (MURI ML-
SCOPE), the NSF award CCF-2112665 (TILOS AI Institute), and the NSF award
2134108.

## References

  * Anderson et al. [2019] Brandon Anderson, Truong-Son Hy, and Risi Kondor.  Cormorant: Covariant molecular neural networks.  _Advances in Neural Information Processing Systems_ , 2019.
  * Arjovsky et al. [2017] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In _International conference on machine learning_ , pages 214–223. PMLR, 2017.
  * Berlinet and Thomas-Agnan [2011] Alain Berlinet and Christine Thomas-Agnan.  _Reproducing kernel Hilbert spaces in probability and statistics_.  Springer Science & Business Media, 2011.
  * Bietti et al. [2021] Alberto Bietti, Luca Venturi, and Joan Bruna.  On the sample complexity of learning under geometric stability.  _Advances in Neural Information Processing Systems_ , 34:18673–18684, 2021.
  * Biloš and Günnemann [2021] Marin Biloš and Stephan Günnemann.  Scalable normalizing flows for permutation invariant densities.  In _International Conference on Machine Learning_ , pages 957–967. PMLR, 2021.
  * Birrell et al. [2022] Jeremiah Birrell, Markos A Katsoulakis, Luc Rey-Bellet, and Wei Zhu.  Structure-preserving gans.  _arXiv preprint arXiv:2202.01129_ , 2022.
  * Block et al. [2022] Adam Block, Zeyu Jia, Yury Polyanskiy, and Alexander Rakhlin.  Intrinsic dimension estimation using wasserstein distance.  _The Journal of Machine Learning Research_ , 23(1):14124–14160, 2022.
  * Boissard and Le Gouic [2014] Emmanuel Boissard and Thibaut Le Gouic.  On the mean speed of convergence of empirical and occupation measures in wasserstein distance.  In _Annales de l’IHP Probabilités et statistiques_ , volume 50, pages 539–563, 2014.
  * Bunne [2023] Charlotte Bunne.  Optimal transport in learning, control, and dynamical systems.  _ICML Tutorial_ , 2023.
  * Butkovsky [2014] Oleg Butkovsky.  Subgeometric rates of convergence of markov processes in the wasserstein metric.  _Annals of Applied Probability_ , 2014.
  * Canas and Rosasco [2012] Guillermo Canas and Lorenzo Rosasco.  Learning probability measures with respect to optimal transport metrics.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Chen et al. [2023] Ziyu Chen, Markos A Katsoulakis, Luc Rey-Bellet, and Wei Zhu.  Sample complexity of probability divergences under group symmetry.  _arXiv preprint arXiv:2302.01915_ , 2023.
  * Chuang et al. [2021] Ching-Yao Chuang, Youssef Mroueh, Kristjan Greenewald, Antonio Torralba, and Stefanie Jegelka.  Measuring generalization with optimal transport.  _Advances in Neural Information Processing Systems_ , 34:8294–8306, 2021.
  * Courty et al. [2014] Nicolas Courty, Rémi Flamary, and Devis Tuia.  Domain adaptation with regularized optimal transport.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part I 14_ , pages 274–289. Springer, 2014.
  * Cuturi and Doucet [2014] Marco Cuturi and Arnaud Doucet.  Fast computation of wasserstein barycenters.  In _International conference on machine learning_ , pages 685–693. PMLR, 2014.
  * Dey et al. [2020] Neel Dey, Antong Chen, and Soheil Ghafurian.  Group equivariant generative adversarial networks.  _arXiv preprint arXiv:2005.01683_ , 2020.
  * Evans and Gariepy [2015] Lawrence Craig Evans and Ronald F Gariepy.  _Measure theory and fine properties of functions_.  CRC press, 2015.
  * Flamary et al. [2016] R Flamary, N Courty, D Tuia, and A Rakotomamonjy.  Optimal transport for domain adaptation.  _IEEE Trans. Pattern Anal. Mach. Intell_ , 1, 2016.
  * Fournier and Guillin [2015] Nicolas Fournier and Arnaud Guillin.  On the rate of convergence in wasserstein distance of the empirical measure.  _Probability theory and related fields_ , 162(3-4):707–738, 2015.
  * Fukumizu et al. [2007] Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf.  Kernel measures of conditional dependence.  _Advances in neural information processing systems_ , 20, 2007.
  * Genevay et al. [2019] Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré.  Sample complexity of sinkhorn divergences.  In _The 22nd international conference on artificial intelligence and statistics_ , pages 1574–1583. PMLR, 2019.
  * Goodfellow et al. [2020] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  _Communications of the ACM_ , 63(11):139–144, 2020.
  * Gretton et al. [2006] Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola.  A kernel method for the two-sample-problem.  _Advances in neural information processing systems_ , 19, 2006.
  * Gretton et al. [2007] Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola.  A kernel statistical test of independence.  _Advances in neural information processing systems_ , 20, 2007.
  * Gretton et al. [2012] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _The Journal of Machine Learning Research_ , 13(1):723–773, 2012.
  * Hendriks [1990] Harrie Hendriks.  Nonparametric estimation of a probability density on a Riemannian manifold using fourier expansions.  _The Annals of Statistics_ , pages 832–849, 1990.
  * Kantorovich [2006] Leonid V Kantorovich.  On the translocation of masses.  _Journal of mathematical sciences_ , 133(4):1381–1382, 2006.
  * Köhler et al. [2019] Jonas Köhler, Leon Klein, and Frank Noé.  Equivariant flows: sampling configurations for multi-body systems with symmetric energies.  _arXiv preprint arXiv:1910.00753_ , 2019.
  * Lei [2020] Jing Lei.  Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces.  _Bernoulli_ , 2020.
  * Liang [2021] Tengyuan Liang.  How well generative adversarial networks learn distributions.  _The Journal of Machine Learning Research_ , 22(1):10366–10406, 2021.
  * Mallasto et al. [2019] Anton Mallasto, Jes Frellsen, Wouter Boomsma, and Aasa Feragen.  (q, p)-wasserstein gans: Comparing ground metrics for wasserstein gans.  _arXiv preprint arXiv:1902.03642_ , 2019.
  * Mena and Niles-Weed [2019] Gonzalo Mena and Jonathan Niles-Weed.  Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem.  _Advances in neural information processing systems_ , 32, 2019.
  * Mroueh et al. [2017] Youssef Mroueh, Chun-Liang Li, Tom Sercu, Anant Raj, and Yu Cheng.  Sobolev gan.  _arXiv preprint arXiv:1711.04894_ , 2017.
  * Müller [1997] Alfred Müller.  Integral probability metrics and their generating classes of functions.  _Advances in applied probability_ , 29(2):429–443, 1997.
  * Niles-Weed and Berthet [2022] Jonathan Niles-Weed and Quentin Berthet.  Minimax estimation of smooth densities in wasserstein distance.  _The Annals of Statistics_ , 50(3):1519–1540, 2022.
  * Panaretos and Zemel [2019] Victor M Panaretos and Yoav Zemel.  Statistical aspects of wasserstein distances.  _Annual review of statistics and its application_ , 6:405–431, 2019.
  * Peyré et al. [2019] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  _Foundations and Trends® in Machine Learning_ , 11(5-6):355–607, 2019.
  * Rigollet and Stromme [2022] Philippe Rigollet and Austin J Stromme.  On the sample complexity of entropic optimal transport.  _arXiv preprint arXiv:2206.13472_ , 2022.
  * Salimans et al. [2018] Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas.  Improving gans using optimal transport.  _arXiv preprint arXiv:1803.05573_ , 2018.
  * Santambrogio [2015] Filippo Santambrogio.  Optimal transport for applied mathematicians.  _Birkäuser, NY_ , 55(58-63):94, 2015.
  * Singh and Póczos [2018] Shashank Singh and Barnabás Póczos.  Minimax distribution estimation in wasserstein distance.  _arXiv preprint arXiv:1802.08855_ , 2018.
  * Smola et al. [2007] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf.  A hilbert space embedding for distributions.  In _International conference on algorithmic learning theory_ , pages 13–31. Springer, 2007.
  * Sriperumbudur et al. [2010] Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert RG Lanckriet.  Hilbert space embeddings and metrics on probability measures.  _The Journal of Machine Learning Research_ , 11:1517–1561, 2010.
  * Sriperumbudur et al. [2011] Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet.  Universality, characteristic kernels and rkhs embedding of measures.  _Journal of Machine Learning Research_ , 12(7), 2011.
  * Sriperumbudur et al. [2012] Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet.  On the empirical estimation of integral probability metrics.  2012\.
  * Tahmasebi and Jegelka [2023] Behrooz Tahmasebi and Stefanie Jegelka.  The exact sample complexity gain from invariances for kernel regression on manifolds.  _arXiv preprint arXiv:2303.14269_ , 2023.
  * Tolstikhin et al. [2017] Ilya Tolstikhin, Bharath K Sriperumbudur, and Krikamol Muandet.  Minimax estimation of kernel mean embeddings.  _The Journal of Machine Learning Research_ , 18(1):3002–3048, 2017.
  * Tolstikhin et al. [2016] Ilya O Tolstikhin, Bharath K Sriperumbudur, and Bernhard Schölkopf.  Minimax estimation of maximum mean discrepancy with radial kernels.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Tsybakov [2009] Alexandre B. Tsybakov.  _Introduction to Nonparametric Estimation_.  Springer, 2009.
  * Villani [2021] Cédric Villani.  _Topics in optimal transportation_ , volume 58.  American Mathematical Soc., 2021.
  * Villani et al. [2009] Cédric Villani et al.  _Optimal transport: old and new_ , volume 338.  Springer, 2009.
  * Weed and Bach [2019] Jonathan Weed and Francis Bach.  Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance.  _Bernoulli_ , 2019.
  * Zhang et al. [2021] Jingyi Zhang, Wenxuan Zhong, and Ping Ma.  A review on modern computational optimal transport methods with applications in biomedical research.  _Modern Statistical Methods for Health Research_ , pages 279–300, 2021.

##  Appendix A Preliminaries for Proofs

This section reviews some essential preliminaries on group actions on
manifolds [46]. We consider a compact connected boundaryless smooth Riemannian
manifold $(\mathcal{M},g)$ with dimension $\dim(\mathcal{M})$. The Riemannian
metric $g$ allows us to define the volume element
$d\operatorname*{vol}_{g}(x)$ on $\mathcal{M}$, and without loss of
generality, we assume that it is normalized such that
$\operatorname*{vol}(\mathcal{M})=\int_{\mathcal{M}}d\operatorname*{vol}_{g}(x)=1$.
The volume element is also denoted by $dx$ whenever the choice of the
Riemannian metric is evident from the context.

The Laplace-Beltrami operator $\Delta_{g}$ is the unique continuous operator
satisfying the integration by parts formula:

$\displaystyle\int_{\mathcal{M}}\langle\nabla_{g}\phi(x),\nabla_{g}\psi(x)\rangle_{L^{2}(\mathcal{M})}d\operatorname*{vol}\nolimits_{g}(x)=\int_{\mathcal{M}}\Delta_{g}\phi(x)\psi(x)d\operatorname*{vol}\nolimits_{g}(x),$
(24)

for any smooth function $\phi,\psi:\mathcal{M}\to\mathbb{R}$. One can see that
the Euclidean Laplacian $\Delta=\sum_{i}\partial_{i}^{2}$ satisfies this
definition by the Green’s identities.

The Laplace-Beltrami operator eigenfunctions, denoted by $\phi_{\ell}$,
$\ell=0,1,\ldots$, are the the sequence of functions satisfying the equation
$\Delta_{g}\phi+\lambda_{\ell}\phi=0$ on the manifold $\mathcal{M}$, where
$0=\lambda_{0}<\lambda_{1}\leq\lambda_{2}\leq\ldots$ denote the eigenvalues of
$(-\Delta_{g})$. Let us assume that
$\|\phi_{\ell}\|_{L^{2}(\mathcal{M})}=\int_{\mathcal{M}}\phi^{2}_{\ell}(x)d\operatorname*{vol}_{g}(x)=1$,
i.e., the eigenfunctions are normalized in $L^{2}(\mathcal{M})$. One important
property of the Laplace-Beltrami eigenfunctions it that they constitute a
basis for the function space $L^{2}(\mathcal{M})$.

It can be shown that the sequence $\lambda_{\ell}\to\infty$ as
$\ell\to\infty$, thus it does not accumulate around any finite number.
Moreover, according to the celebrated Weyl’s law, the density of eigenvalues
is given by the following asymptotic formula:

$\displaystyle
N(\lambda):=\\#\\{\lambda_{\ell}\leq\lambda\\}=\frac{\omega_{\dim(\mathcal{M})}}{(2\pi)^{\dim(\mathcal{M})}}\operatorname*{vol}(\mathcal{M})\lambda^{\dim(\mathcal{M})/2}+O(\lambda^{(\dim(\mathcal{M})-1)/2}),$
(25)

where $\omega_{\dim(\mathcal{M})}$ is the volume of the
$\dim(\mathcal{M})$-dimensional ball in the Euclidean space
$\mathbb{R}^{\dim(\mathcal{M})}$ (with the usual metric). Even more, one can
show that Weyl’s law holds locally around each point on the manifold:

$\displaystyle
N_{x}(\lambda):=\sum_{\lambda_{\ell}\leq\lambda}\phi^{2}_{\ell}(x)=\frac{\omega_{\dim(\mathcal{M})}}{(2\pi)^{\dim(\mathcal{M})}}\operatorname*{vol}(\mathcal{M})\lambda^{\dim(\mathcal{M})/2}+O(\lambda^{(\dim(\mathcal{M})-1)/2}),$
(26)

where the error term is uniformly bounded for all $x\in\mathcal{M}$. Note that
integrating the above formula on the manifolds gives the original version of
Weyl’s law.

A Lie group $G$ acts on $\mathcal{M}$ isometrically if for all $\tau\in G$,
the corresponding map $x\mapsto\tau x$ on the manifold is an isometry. A
function $f:\mathcal{M}\to\mathcal{M}$ is called $G-$invariant, if and only if
one has $f(x)=f(\tau x)$, for all $\tau\in G$, in $L^{2}(\mathcal{M})$.

For any function $f\in L^{2}(\mathcal{M})$, one has
$f=\sum_{\ell=0}^{\infty}\langle
f,\phi_{\ell}\rangle_{L^{2}(\mathcal{M})}\phi_{\ell}$. However, for any
$G$-invariant function, one can show that many coefficients in the above
series are a priory known to be zero. Indeed, for any eigenspace of the
Laplace-Beltrami operator, such as $V_{\lambda}$, with eigenvalue $\lambda$,
there exists a subspace $V_{\lambda,G}\subseteq V_{\lambda}$ such that all
$G$-invariant functions $f\in V_{\lambda}$ can be written as a linear
combination of functions in $V_{\lambda,G}$ [46]. Without loss of generality,
we assume that the eigenfunctions $\phi_{\ell}$ are chosen such that for any
$\lambda$ there exists a subset of $\phi_{\ell}$ that forms an orthonormal
basis for $V_{\lambda,G}$. Let $\mathbbm{1}_{G}(\ell)$ indicate whether
$\phi_{\ell}\in V_{\lambda,G}$ (with one) or not (with zero). Let
$N_{x}(\lambda;G):=\sum_{\ell=0}^{\infty}\mathbbm{1}_{G}(\ell)\phi_{\ell}^{2}(x)$.

We are interested in asymptotic estimation formulae for $N_{x}(\lambda;G)$ to
study the gain of invariances. Note that if $G=\\{\text{id}_{G}\\}$, then
Weyl’s law provides such estimation. The following theorem shows how to extend
it to non-trivial groups.

######  Theorem 7 (Local Weyl’s law for $G$-invariant functions, [46]).

For any Lie group $G$ acting smoothly on a connected compact boundaryless
manifold $\mathcal{M}$, one has for all $x\in\mathcal{M}$,

$\displaystyle
N_{x}(\lambda;G)=\sum_{\lambda_{\ell}\leq\lambda}\mathbbm{1}_{G}(\ell)\phi^{2}_{\ell}(x)=\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda^{d/2}+O(\lambda^{(d-1)/2}),$
(27)

where $d:=\dim(\mathcal{M}/G)$ and $\operatorname*{vol}(\mathcal{M}/G)$ denote
the dimension and the volume of the principal part of the quotient space,
respectively. Note that one always has $N_{x}(\lambda;G)\leq N_{x}(\lambda)$.

A Hilbert space $\mathcal{H}\subseteq L^{2}(\mathcal{M})$ is called a
Reproducing Kernel Hilbert Spaces (RKHS) if and only if for any
$x\in\mathcal{M}$ and $f\in\mathcal{H}$, one has $|f(x)|\leq
C_{x}\|f\|_{\mathcal{H}}$ for some constant $C_{x}<\infty$. Associated with
$\mathcal{H}$, there exists a PDS kernel
$K:\mathcal{M}\times\mathcal{M}\to\mathbb{R}$ , and according to Mercer’s
theorem, it can be diagonalized in some basis in $L^{2}(\mathcal{M})$. In this
paper, for the sake of simplicity, we consider kernels that can be
diagonalized in the Laplace-Beltrami basis as follows:

$\displaystyle
K(x,y)=\sum_{\ell=0}^{\infty}\xi_{\ell}\phi_{\ell}(x)\phi_{\ell}(y),$ (28)

for some coefficients $\xi_{\ell}\in\mathbb{R}$. This includes dot-product
kernels over spheres. We further assume that the coefficients, for each
$\ell$, only depend on $\lambda_{\ell}$, thus we can denote them as
$\xi(\lambda)$, too. A set of sufficient conditions for kernels on manifolds
to satisfy such types of diagonalization is given in [46].

We also use the following definition of Sobolev spaces
$\mathcal{H}^{s}(\mathcal{M})$ for any $s\geq 0$:

$\displaystyle\mathcal{H}^{s}(\mathcal{M}):=\Big{\\{}f\in
L^{2}(\mathcal{M}):\|f\|_{\mathcal{H}^{s}(\mathcal{M})}^{2}:=\langle
f,\phi_{0}\rangle_{L^{2}(\mathcal{M})}^{2}+\sum_{\ell=1}^{\infty}\lambda_{\ell}^{s}\langle
f,\phi_{\ell}\rangle_{L^{2}(\mathcal{M})}^{2}<\infty\Big{\\}}.$ (29)

Sobolev spaces are indeed Hilbert space under the inner product:

$\displaystyle\langle
f_{1},f_{2}\rangle_{\mathcal{H}^{s}(\mathcal{M})}^{2}:=\langle
f_{1},\phi_{0}\rangle_{L^{2}(\mathcal{M})}\langle
f_{2},\phi_{0}\rangle_{L^{2}(\mathcal{M})}+\sum_{\ell=1}^{\infty}\lambda_{\ell}^{s}\langle
f_{1},\phi_{\ell}\rangle_{L^{2}(\mathcal{M})}\langle
f_{2},\phi_{\ell}\rangle_{L^{2}(\mathcal{M})}.$ (30)

Note that Sobolev spaces are Reproducing Kernel Hilbert Spaces if and only if
$s>d/2$ [46]. For any $0\leq\alpha\leq\beta<\infty$, one has
$\mathcal{H}^{\beta}(\mathcal{M})\subseteq\mathcal{H}^{\alpha}(\mathcal{M})\subseteq
L^{2}(\mathcal{M})$. Moreover, $H^{0}(\mathcal{M})=L^{2}(\mathcal{M})$.

##  Appendix B Proof of Theorem 1

###### Proof.

Let $\phi_{\ell}$, $\ell=0,1,\ldots$, denote the eigenfunctions of the
Laplace-Beltrami operator, corresponding to the eigenvalues
$0=\lambda_{0}<\lambda_{1}\leq\lambda_{2}\leq\ldots$. Each eigenspace is
denoted by $V_{\lambda_{\ell}}$, and its subspace of $G$-invariant
eigenfunctions is denoted by $V_{\lambda_{\ell},G}$ (see Appendix A for more
details). For any probability measure $\mu\in\mathcal{P}(\mathcal{M})$, define
$\mu_{\ell}=\int_{\mathcal{M}}\phi_{\ell}d\mu$ for each $\ell=0,1,\ldots$, and
note that $\mu_{0}=1$. Let
$dx=\frac{1}{\operatorname*{vol}(\mathcal{M})}d\operatorname*{vol}_{g}(x)$
denote the uniform measure on the manifold and define the inner-product in
$L^{2}(\mathcal{M})$ with respect to the measure
$d\operatorname*{vol}_{g}(x)$. If a probability measure $\mu$ is absolutely
continuous with respect to the uniform measure, then $\frac{d\mu}{dx}$ denotes
its Radon–Nikodym derivative.

######  Lemma 1.

Consider two Borel measures $\mu,\nu\in\mathcal{P}(\mathcal{M})$ with
$\int_{\mathcal{M}}d\mu=\int_{\mathcal{M}}d\nu=1$. Also, assume that
$\frac{d\mu}{dx},\frac{d\nu}{dx}\in L^{2}(\mathcal{M})$ with
$\operatorname*{vol}(\mathcal{M})=1$. Then,

$\displaystyle W_{1}(\mu,\nu)\leq D_{1}(\mu,\nu),$ (31)

where $D_{1}(\mu,\nu)$ is the Sobolev IPM with parameter $\alpha=1$.

###### Proof.

Note that $\operatorname*{Lip}(\mathcal{M})\subset L^{2}(\mathcal{M})$. By the
Rademacher’s theorem [17], any $f\in\operatorname*{Lip}(\mathcal{M})$ is
differentiable almost everywhere, and thus $|\nabla_{g}f(x)|_{g}\leq 1$ for
almost every $x\in\mathcal{M}$. Therefore,

$\displaystyle\|\nabla_{g}f\|_{L^{2}(\mathcal{M})}^{2}$
$\displaystyle\leq\int_{\mathcal{M}}|\nabla_{g}f(x)|_{g}^{2}d\text{vol}_{g}(x)\leq\int_{\mathcal{M}}d\text{vol}_{g}(x)=1.$
(32)

For any $f\in L^{2}(\mathcal{M})$, one can write
$f=\sum_{\ell=0}^{\infty}f_{\ell}\phi_{\ell}$ with $f_{\ell}:=\langle
f,\phi_{\ell}\rangle_{L^{2}(\mathcal{M})}$. Thus, we have

$\displaystyle W_{1}(\mu,\nu)$
$\displaystyle=\sup_{f\in\operatorname*{Lip}(\mathcal{M})}\Big{\\{}\int_{\mathcal{M}}fd\mu-\int_{\mathcal{M}}fd\nu\Big{\\}}$
(33) $\displaystyle\leq\sup_{\begin{subarray}{c}f\in L^{2}(\mathcal{M})\\\
\|\nabla_{g}f\|_{L^{2}(\mathcal{M})}^{2}\leq
1\end{subarray}}\Big{\\{}\int_{\mathcal{M}}fd\mu-\int_{\mathcal{M}}fd\nu\Big{\\}}.$
(34)

Now note that since $\mu_{0}=\nu_{0}$, one can restrict the above optimization
problem to functions with $f_{0}=0$. For those functions, we have
$\|f\|_{\mathcal{H}^{1}(\mathcal{M})}=\|\nabla_{g}f\|_{L^{2}(\mathcal{M})}=1$,
and thus we have

$\displaystyle
W_{1}(\mu,\nu)\leq\sup_{\begin{subarray}{c}f\in\mathcal{H}^{1}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{1}(\mathcal{M})\leq
1}\end{subarray}}\Big{\\{}\int_{\mathcal{M}}fd\mu-\int_{\mathcal{M}}fd\nu\Big{\\}}=D_{1}(\mu,nu).$
(35)

∎

To prove Theorem 1, we use Lemma 1. First, note that it is impossible to
immediately apply Lemma 1 since the unknown measure $\mu$ is not necessarily
absolutely continuous with respect to the uniform measure on the manifold.
Nevertheless, let us define the sequence

$\displaystyle\tilde{\mu}_{\ell}:=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}_{G}(\ell)\phi_{\ell}(X_{i}),$
(36)

for each $\ell=0,1,\ldots$, and let $\tilde{\mu}$ denote the probability
measure for which
$\mathbb{E}_{x\sim\tilde{\mu}}[\phi_{\ell}(x)]=\tilde{\mu}_{\ell}$.

Given the probability measure $\mu\in\mathcal{P}(\mathcal{M})$, define the
twisted measure $\mu_{\star}$ as follows:

$\displaystyle\frac{d\mu_{\star}}{dx}=\sum_{\ell=0}^{\infty}\exp(-\sigma\lambda_{\ell})\mu_{\ell}\phi_{\ell},$
(37)

where $\sigma$ is a fixed positive constant (to be set later). Note that for a
fixed $\sigma$, the new measure $\mu_{\star}$ is absolutely continuous with
respect to the uniform measure. Indeed, its density is even smooth (i.e.,
having infinitely many times continuous derivatives), since the tail of the
above summation goes to zero exponentially fast as $\ell\to\infty$. Also, note
that $\int_{\mathcal{M}}d\mu_{\star}=1$, and with a bit more consideration, we
can observe that $\mu_{\star}$ is a probability measure.

There is also another interpretation for the probability measure
$\mu_{\star}$. Let $X\sim\mu$ denote a sample from $\mu$, and consider the
heat diffusion corresponding to the Brownian motion on the manifold, started
from $X$ and stopped at time $t=\sigma$. The Brownian motion is assumed to be
independent of the sample $X$, and it can be shown that the law of process at
time $t=\sigma$ is the probability measure $\mu_{\star}$. Therefore, this
gives a natural coupling between the two measures $\mu$ and $\mu_{\star}$.

Hence, we can write

$\displaystyle W_{1}(\mu,\tilde{\mu})$ $\displaystyle\leq
W_{1}(\mu,\mu_{\star})+W_{1}(\mu_{\star},\tilde{\mu}_{\star})+W_{1}(\tilde{\mu}_{\star},\tilde{\mu})$
(38) $\displaystyle\leq
2C\sqrt{\sigma}+W_{1}(\mu_{\star},\tilde{\mu}_{\star}),$ (39)

where we use the fact that for any probability measure
$\nu\in\mathcal{P}(\mathcal{M})$, one has $W_{1}(\nu,\nu_{\star})\leq
W_{2}(\nu,\nu_{\star})\leq C\sqrt{\sigma}$ for some constant $C$ depending on
the manifold. The last inequality is due to the fact that the law of the
Brownian motion on the manifold at time $t=\sigma$ behaves locally the same as
the Gaussian distribution on Euclidean space.

Let us now bound $\mathbb{E}[W_{1}(\mu_{\star},\tilde{\mu}_{\star})]$. Since
the two probability measures $\mu_{\star},\tilde{\mu}_{\star}$ are absolutely
continuous with respect to the uniform measure on the manifold, we can use
Lemma 1 and Lemma 2; thus,

$\displaystyle\mathbb{E}[W_{1}(\mu_{\star},\tilde{\mu}_{\star})]\leq\sqrt{\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\exp(-2\sigma\lambda_{\ell})\frac{(\mu_{\ell}-\tilde{\mu}_{\ell})^{2}}{\lambda_{\ell}}\Big{]}}.$
(40)

Let us define

$\displaystyle
R(\lambda):=\mathbb{E}\Big{[}\sum_{\ell:\lambda_{\ell}\leq\lambda}(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}\Big{]},$
(41)

and note that we can rewrite Equation (40) as follows:

$\displaystyle\mathbb{E}[W_{1}(\mu_{\star},\tilde{\mu}_{\star})]\leq\sqrt{\int_{0^{+}}^{\infty}\exp(-2\sigma\lambda)\frac{dR(\lambda)}{\lambda}},$
(42)

where the above formula must be understood as a Riemann-Stieltjes integral.

Using integration by parts and Lemma 3, we have

$\displaystyle\int_{0^{+}}^{\infty}\exp(-2\sigma\lambda)\frac{dR(\lambda)}{\lambda}=\underbrace{\frac{R(\lambda)}{\lambda}\Big{|}_{0^{+}}^{\infty}}_{=0}+\int_{0^{+}}^{\infty}R(\lambda)\frac{2\sigma\lambda+1}{\lambda^{2}}\exp(-2\sigma\lambda)d\lambda.$
(43)

Now we use Lemma 3 and Theorem 7 to find an upper bound for the above
integral:

$\displaystyle\int_{0^{+}}^{\infty}R(\lambda)\frac{2\sigma\lambda+1}{\lambda^{2}}d\lambda$
$\displaystyle\lesssim\frac{1}{n}\int_{0^{+}}^{\infty}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda^{d/2}\frac{2\sigma\lambda+1}{\lambda^{2}}\exp(-2\sigma\lambda)d\lambda$
(44)
$\displaystyle=\frac{1}{n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\int_{0^{+}}^{\infty}(2\sigma\lambda^{d/2-1}+\lambda^{d/2-2})\exp(-2\sigma\lambda)d\lambda.$
(45)

By a change of variable in the above integral, we conclude that

$\displaystyle\int_{0^{+}}^{\infty}R(\lambda)\frac{2\sigma\lambda+1}{\lambda^{2}}d\lambda$
$\displaystyle\lesssim\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\sigma^{1-d/2}.$
(46)

Therefore,

$\displaystyle\mathbb{E}[W_{1}(\mu,\tilde{\mu})]\lesssim\sqrt{\sigma}+\sqrt{\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}}\sigma^{(2-d)/4}.$
(47)

To minimize the above upper bound, we consider the function
$p(\sigma)=\sqrt{\sigma}+\sqrt{\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}}\sigma^{(2-d)/4}$
for $\sigma\in(0,\infty)$ that achieved its minimum at

$\displaystyle\sigma=\sigma_{\text{opt}}=\Big{(}(1-d/2)^{2}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{2/d},$
(48)

and thus we have

$\displaystyle\mathbb{E}[W_{1}(\mu,\tilde{\mu})]\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{1/d},$
(49)

which completes the proof.

∎

##  Appendix C Proof of Theorem 2

###### Proof.

According to Lemma 1, we have the upper bound

$\displaystyle W_{1}(\mu,\nu)\leq D_{1}(\mu,\nu),$ (50)

for any measures $\frac{d\mu}{dx},\frac{d\nu}{dx}\in L^{2}(\mathcal{M})$. Now
consider the estimator $\mu^{\star}$ for $\mu$, for which we are given $n$
i.i.d samples, defined in the proof of Theorem 3. From the assumption, we have
$\frac{d\mu}{dx}\in\mathcal{H}^{s}(\mathcal{M})$ and clearly,
$\frac{d\tilde{\mu}}{dx}\in\mathcal{H}^{s}(\mathcal{M})$ (from its own
definition). Thus, we can use the proof of Theorem 3 specified for $\alpha=1$
to achieve the result for the Wasserstein distance of smooth distributions.

∎

##  Appendix D Proof of Theorem 3

###### Proof.

We first need to prove the following upper bound on the Sobolev IPMs.

######  Lemma 2.

For Borel measures $\mu,\nu$ with
$\int_{\mathcal{M}}d\mu=\int_{\mathcal{M}}d\mu=1$, such that
$\frac{d\mu}{dx},\frac{d\nu}{dx}\in L^{2}(\mathcal{M})$ and assuming
$\operatorname*{vol}(\mathcal{M})=1$, one has

$\displaystyle
D_{\alpha}^{2}(\mu,\nu)=\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-\nu_{\ell})^{2}}{\lambda^{\alpha}_{\ell}},$
(51)

for any $\alpha\geq 0$, where
$\mu_{\ell}=\mathbb{E}_{x\sim\mu}[\phi_{\ell}(x)]$ and
$\nu_{\ell}=\mathbb{E}_{x\sim\nu}[\phi_{\ell}(x)]$ for any $\ell$.

###### Proof.

Any function $f\in\mathcal{H}^{\alpha}(\mathcal{M})$ can be written as
$f=\sum_{\ell=0}^{\infty}f_{\ell}\phi_{\ell}$ with
$\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})}^{2}=f_{0}^{2}+\sum_{\ell=1}^{\infty}\lambda_{\ell}^{\alpha}f_{\ell}^{2}<\infty$.
From the definition,

$\displaystyle D_{\alpha}(\mu,\nu)$
$\displaystyle=\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})\leq
1}\end{subarray}}\Big{\\{}\int_{\mathcal{M}}fd\mu-\int_{\mathcal{M}}fd\nu\Big{\\}}$
(52)
$\displaystyle=\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})\leq
1}\end{subarray}}\Big{\\{}\int_{\mathcal{M}}f\frac{d\mu}{dx}dx-\int_{\mathcal{M}}f\frac{d\nu}{dx}dx\Big{\\}}$
(53)
$\displaystyle=\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})\leq
1}\end{subarray}}\Big{\langle}f,\frac{d\mu}{dx}-\frac{d\nu}{dx}\Big{\rangle}_{L^{2}(\mathcal{M})}$
(54)
$\displaystyle=\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})\leq
1}\end{subarray}}\sum_{\ell=0}^{\infty}f_{\ell}(\mu_{\ell}-\nu_{\ell})$ (55)
$\displaystyle\overset{(a)}{=}\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})\leq
1}\end{subarray}}\sum_{\ell=1}^{\infty}\lambda_{\ell}^{\alpha/2}f_{\ell}\times\frac{(\mu_{\ell}-\nu_{\ell})}{\lambda_{\ell}^{\alpha/2}}$
(56)
$\displaystyle\overset{(b)}{=}\sup_{\begin{subarray}{c}f\in\mathcal{H}^{\alpha}(\mathcal{M})\\\
\|f\|_{\mathcal{H}^{\alpha}(\mathcal{M})\leq
1}\end{subarray}}\sqrt{\underbrace{\sum_{\ell=1}^{\infty}\lambda_{\ell}^{\alpha}f_{\ell}^{2}}_{\leq
1}}\times\sqrt{\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-\nu_{\ell})^{2}}{\lambda_{\ell}^{\alpha}}}$
(57)
$\displaystyle=\sqrt{\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-\nu_{\ell})^{2}}{\lambda_{\ell}^{\alpha}}},$
(58)

where (a) is due to the fact that $\mu_{0}=\nu_{0}=1$, and (b) follows from
the Cauchy–Schwarz inequality. ∎

###### Proof of Theorem 3.

Given i.i.d. samples from a probability measure $\mu$ with
$\|\frac{d\mu}{dx}\|_{\mathcal{H}^{s}(\mathcal{M})}<\infty$, we propose the
following estimator. First, fix a parameter $T$ (to be set later) and let
$\mathbbm{1}_{G}(\ell;T)=\mathbbm{1}_{G}(\ell)\mathbbm{1}\\{\ell<T\\}$ for any
$\ell=0,1,\ldots$. Then, define the sequence

$\displaystyle\tilde{\mu}_{\ell}:=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}_{G}(\ell;T)\phi_{\ell}(X_{i}),$
(59)

for each $\ell$ and let
$\frac{d\tilde{\mu}}{dx}:=\sum_{\ell=0}^{\infty}\tilde{\mu}_{\ell}\phi_{\ell}$.
The measure $\tilde{\mu}$ is thus well-defined, and
$\int_{\mathcal{M}}d\tilde{\mu}=1$, but it is not necessarily a probability
measure since it can be a signed measure. However, due to the truncation of
the sum at $T$, we have
$\frac{d\tilde{\mu}}{dx}\in\mathcal{H}^{s}(\mathcal{M})$. Define a new
probability measure $\mu^{\star}$ as

$\displaystyle\mu^{\star}=\operatorname*{arg\,min}_{\nu\in\mathcal{P}(\mathcal{M})}D_{\alpha}(\nu,\tilde{\mu}).$
(60)

This shows that by the triangle inequality

$\displaystyle D_{\alpha}(\mu,\mu^{\star})\leq
D_{\alpha}(\mu,\tilde{\mu})+D_{\alpha}(\tilde{\mu},\mu^{\star})\leq
2D_{\alpha}(\mu,\tilde{\mu}),$ (61)

where in above, we used the definition of the probability measure
$\mu^{\star}$.

We claim that the estimated probability measure achieves the convergence rate
claimed in the theorem. To this end, we need to prove upper bounds on
$\mathbb{E}[D_{\alpha}(\mu,\tilde{\mu})]$. According to Lemma 2, one has

$\displaystyle\mathbb{E}[D_{\alpha}(\mu,\mu^{\star})]$ $\displaystyle\leq
2\mathbb{E}[D_{\alpha}(\mu,\tilde{\mu})]$ (62) $\displaystyle\leq
2\sqrt{\mathbb{E}[D^{2}_{\alpha}(\mu,\tilde{\mu})]}$ (63)
$\displaystyle=2\sqrt{\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}}.$
(64)

Note that

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{\ell=1}^{T-1}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}+\mathbb{E}\Big{[}\sum_{\ell\geq
T}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
(65)
$\displaystyle=\underbrace{\mathbb{E}\Big{[}\sum_{\ell=1}^{T-1}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}}_{\text{(I)}}+\underbrace{\sum_{\ell\geq
T}\frac{\mu_{\ell}^{2}}{\lambda^{\alpha}_{\ell}}}_{\text{(II)}},$ (66)

since $\tilde{\mu}_{\ell}=0$ for $\ell>T$. ∎

To upper bound the second term, we write

$\displaystyle\sum_{\ell\geq T}\frac{\mu_{\ell}^{2}}{\lambda^{\alpha}_{\ell}}$
$\displaystyle=\sum_{\ell>T}\mu_{\ell}^{2}\lambda^{s}_{\ell}\lambda^{-(s+\alpha)}_{\ell}\leq\lambda_{T}^{-(s+\alpha)}\sum_{\ell\geq
T}\mu_{\ell}^{2}\lambda^{s}_{\ell}\leq\lambda_{T}^{-(s+\alpha)}\Big{\|}\frac{d{\mu}}{dx}\Big{\|}^{2}_{\mathcal{H}^{s}(\mathcal{M})}.$
(67)

To bound the first term, we need to use the following lemma.

######  Lemma 3.

One has

$\displaystyle
R(\lambda):=\mathbb{E}\Big{[}\sum_{\ell:\lambda_{\ell}\leq\lambda}(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}\Big{]}\leq\frac{1}{n}\mathbb{E}_{x\sim\mu}\Big{[}N_{x}(\lambda;G)\Big{]},$
(68)

where $N_{x}(\lambda;G)$ is defined in Theorem 7.

###### Proof.

Note that the coefficients $\tilde{\mu}_{\ell}$ are empirical estimates of
$\mu_{\ell}$ given $n$ i.i.d. samples; thus

$\displaystyle
R(\lambda_{T})=\mathbb{E}\Big{[}\sum_{\ell:\lambda_{\ell}\leq\lambda_{T}}(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}\Big{]}$
$\displaystyle=\frac{1}{n}\Big{\\{}\sum_{\ell:\lambda_{\ell}\leq\lambda_{T}}\mathbbm{1}_{G}(\ell)\Big{(}\mathbb{E}_{x\sim\mu}[\phi^{2}_{\ell}(x)]-(\mathbb{E}_{x\sim\mu}[\phi_{\ell}(x)])^{2}\Big{)}\Big{\\}}$
(69)
$\displaystyle\leq\frac{1}{n}\mathbb{E}_{x\sim\mu}\Big{[}\sum_{\ell:\lambda_{\ell}\leq\lambda_{T}}\mathbbm{1}_{G}(\ell)\phi^{2}_{\ell}(x)\Big{]}$
(70)
$\displaystyle\leq\frac{1}{n}\mathbb{E}_{x\sim\mu}\Big{[}N_{x}(\lambda_{T};G)\Big{]}.$
(71)

∎

We use Lemma 3 to complete the proof. First, note that

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{T-1}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}\leq\int_{0^{+}}^{\lambda_{T}}\frac{dR(\lambda)}{\lambda^{\alpha}},$
(72)

where $R(\lambda)$ is defined in Lemma 3 and $dR(\lambda)$ denotes the
Stieltjes measure corresponding to $R(\lambda)$. By integration by parts, one
has

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{T-1}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}\leq\int_{0^{+}}^{\lambda_{T}}\frac{dR(\lambda)}{\lambda^{\alpha}}=\frac{R(\lambda)}{\lambda^{\alpha}}\Big{|}_{0^{+}}^{\lambda_{T}}+\alpha\int_{0^{+}}^{\lambda_{T}}\frac{R(\lambda)}{\lambda^{\alpha+1}}d\lambda.$
(73)

Now assume $\alpha<d/2$. By Theorem 7 and Lemma 3, we have

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{T-1}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
$\displaystyle\leq\frac{R(\lambda_{T})}{\lambda_{T}^{\alpha}}+\alpha\int_{0^{+}}^{\lambda_{T}}\frac{R(\lambda)}{\lambda^{\alpha+1}}d\lambda$
(74)
$\displaystyle\leq\frac{1}{n}\Big{\\{}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2-\alpha}+O(\lambda_{T}^{(d-1)/2-\alpha})$
(75)
$\displaystyle\quad+\alpha\int_{0^{+}}^{\lambda_{T}}\Big{\\{}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2-\alpha-1}+O(\lambda_{T}^{(d-1)/2-\alpha-1})\Big{\\}}d\lambda\Big{\\}}$
(76)
$\displaystyle\lesssim\frac{1}{n}\Big{(}1+\frac{\alpha}{d/2-\alpha}\Big{)}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2-\alpha},$
(77)

where in $\lesssim$ the constant is absolute. Plugging in this estimation into
Equation (66) results in

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
$\displaystyle\lesssim\frac{1}{n}\frac{d/2}{d/2-\alpha}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2-\alpha}+\lambda_{T}^{-(s+\alpha)}\Big{\|}\frac{d{\mu}}{dx}\Big{\|}^{2}_{\mathcal{H}^{s}(\mathcal{M})}.$
(78)

We can choose the parameter $\lambda_{T}\in(0,\infty)$ to minimize the above
upper bound.

Note that the function $p(\lambda)=c_{a}\lambda^{-a}+c_{b}\lambda^{b}$ with
$a,b,c_{a},c_{b}>0$ is minimized for $\lambda\in(0,\infty)$ when

$\displaystyle\lambda=\lambda_{\text{opt}}:=\Big{(}\frac{ac_{a}}{bc_{b}}\Big{)}^{1/(a+b)}.$
(79)

Taking $a=s+\alpha$, $b=d/2-\alpha$, and

$\displaystyle
c_{a}=\Big{\|}\frac{d{\mu}}{dx}\Big{\|}^{2}_{\mathcal{H}^{s}(\mathcal{M})},\quad
c_{b}=\frac{1}{n}\frac{d/2}{d/2-\alpha}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G),$
(80)

suggests to take

$\displaystyle\lambda_{T}=\Big{\\{}\Big{(}(s+\alpha)\|d{\mu}/dx\|^{2}_{\mathcal{H}^{s}(\mathcal{M})}\Big{)}\Big{/}\Big{(}\frac{d}{2n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\Big{)}\Big{\\}}^{1/(s+d/2)}.$
(81)

Therefore, we have the following upper bound

$\displaystyle\mathbb{E}\Big{[}$
$\displaystyle\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
(82)
$\displaystyle\lesssim\frac{1}{n}\frac{d/2}{d/2-\alpha}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\Big{\\{}\Big{(}(s+\alpha)\|d{\mu}/dx\|^{2}_{\mathcal{H}^{s}(\mathcal{M})}\Big{)}\Big{/}\Big{(}\frac{d}{2n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\Big{)}\Big{\\}}^{(d/2-\alpha)/(s+d/2)}$
(83)
$\displaystyle+\Big{\|}\frac{d{\mu}}{dx}\Big{\|}^{2}_{\mathcal{H}^{s}(\mathcal{M})}\Big{\\{}\Big{(}(s+\alpha)\|d{\mu}/dx\|^{2}_{\mathcal{H}^{\alpha}(\mathcal{M})}\Big{)}\Big{/}\Big{(}\frac{d}{2n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\Big{)}\Big{\\}}^{-(s+\alpha)/(s+d/2)},$
(84)

which shows that

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{s+\alpha}{s+d/2}}\leavevmode\nobreak\
\Big{\|}\frac{d\mu}{dx}\Big{\|}_{\mathcal{H}^{s}(\mathcal{M})}^{\frac{d-2\alpha}{s+d/2}}.$
(85)

This completes the proof for $\alpha<d/2$, since

$\displaystyle\mathbb{E}[D_{\alpha}(\mu,\mu^{\star})]\leq
2\sqrt{\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}}\lesssim\Big{(}\frac{\operatorname*{vol}(\mathcal{M}/G)}{n}\Big{)}^{\frac{s+\alpha}{2s+d}}\leavevmode\nobreak\
\Big{\|}\frac{d\mu}{dx}\Big{\|}_{\mathcal{H}^{s}(\mathcal{M})}^{\frac{d-2\alpha}{2s+d}}.$
(86)

Now, we study the case where $\alpha=d/2$. By Theorem 7 and Lemma 3, we have

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{T-1}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
$\displaystyle\leq\frac{R(\lambda_{T})}{\lambda_{T}^{\alpha}}+\alpha\int_{0^{+}}^{\lambda_{T}}\frac{R(\lambda)}{\lambda^{\alpha+1}}d\lambda$
(87)
$\displaystyle\leq\frac{\alpha}{n}\int_{\lambda_{1}}^{\lambda_{T}}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\frac{d\lambda}{\lambda}+O(1/n)$
(88)
$\displaystyle=\frac{\alpha}{n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\ln(\lambda_{T})+O(1/n).$
(89)

Thus, from Equation (66) we have

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
$\displaystyle\lesssim\frac{\alpha}{n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\ln(\lambda_{T})+\lambda_{T}^{-(s+\alpha)}\Big{\|}\frac{d{\mu}}{dx}\Big{\|}^{2}_{\mathcal{H}^{s}(\mathcal{M})}+O(1/n).$
(90)

To minimize the above upper bound as a function of $\lambda_{T}$, we consider
the function $p(\lambda)=c_{a}\lambda^{-a}+c_{b}\ln(\lambda)$ and assume that
$c_{b}$ is small enough. Note that the minimum of $p(\lambda)$ for
$\lambda\in(0,\infty)$ is achieved when

$\displaystyle\lambda=\lambda_{\text{opt}}:=\Big{(}\frac{ac_{a}}{c_{b}}\Big{)}^{1/a}.$
(91)

This means that for $a=s+\alpha$,
$c_{a}=\|d{\mu}/dx\|^{2}_{\mathcal{H}^{s}(\mathcal{M})}$, and
$c_{b}=\frac{\alpha}{n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)$,
we can take

$\displaystyle\lambda_{T}=\Big{\\{}\Big{(}(s+\alpha)\|d{\mu}/dx\|^{2}_{\mathcal{H}^{s}(\mathcal{M})}\Big{)}\Big{/}\Big{(}\frac{\alpha}{n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\Big{)}\Big{\\}}^{1/(s+d/2)},$
(92)

to achieve

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}$
$\displaystyle\lesssim\frac{d\log(n)}{(2s+d)n}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)+O(1/n).$
(93)

This completes the proof for $\alpha=d/2$, since

$\displaystyle\mathbb{E}[D_{\alpha}(\mu,\mu^{\star})]\leq
2\sqrt{\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\frac{(\mu_{\ell}-{\tilde{\mu}}_{\ell})^{2}}{\lambda^{\alpha}_{\ell}}\Big{]}}\lesssim\sqrt{\frac{\operatorname*{vol}(\mathcal{M}/G)\log(n)}{n}}.$
(94)

∎

##  Appendix E Proof of Theorem 4

###### Proof.

Note that a function $f\in\mathcal{H}$ can be written as
$f=\sum_{\ell=0}^{\infty}f_{\ell}\phi_{\ell}$ such that
$\|f\|^{2}_{\mathcal{H}}=\sum_{\ell=0}^{\infty}\frac{f_{\ell}^{2}}{\xi_{\ell}}<\infty$.
Thus, for any probability measures $\mu,\nu$ such that
$\frac{d\mu}{dx},\frac{d\nu}{dx}\in\mathcal{H}$, we have

$\displaystyle D_{\mathcal{H}}(\mu,\nu)$
$\displaystyle:=\sup_{\begin{subarray}{c}f\in\mathcal{H}\\\
\|f\|_{\mathcal{H}}\leq
1\end{subarray}}\Big{\\{}\mathbb{E}_{x\sim\mu}[f(x)]-\mathbb{E}_{x\sim\nu}[f(x)]\Big{\\}}$
(95) $\displaystyle=\sup_{\begin{subarray}{c}f\in\mathcal{H}\\\
\|f\|_{\mathcal{H}}\leq
1\end{subarray}}\Big{\\{}\sum_{\ell=1}^{\infty}f_{\ell}(\mu_{\ell}-\nu_{\ell})\Big{\\}}=\sqrt{\sum_{\ell=1}^{\infty}\xi_{\ell}(\mu_{\ell}-\nu_{\ell})^{2}}.$
(96)

Now consider the estimator $\tilde{\mu}$ that is defined similar to the proof
of Theorem 1; we have

$\displaystyle\tilde{\mu}_{\ell}:=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}_{G}(\ell)\phi_{\ell}(X_{i}),$
(97)

for each $\ell=0,1,\ldots$, and $\tilde{\mu}$ denotes the probability measure
for which $\mathbb{E}_{x\sim\tilde{\mu}}[\phi_{\ell}(x)]=\tilde{\mu}_{\ell}$.
Assume that $\xi_{\ell}$ depends only on $\lambda_{\ell}$, and thus denote it
by $\xi(\lambda)$. Using Lemma 3 and integration by parts, we have

$\displaystyle\mathbb{E}[D_{\mathcal{H}}(\mu,\tilde{\mu})]$
$\displaystyle\leq\sqrt{\mathbb{E}[D_{\mathcal{H}}(\mu,\tilde{\mu})^{2}]}=\sqrt{\mathbb{E}\Big{[}\sum_{\ell=1}^{\infty}\xi_{\ell}(\mu_{\ell}-\tilde{\mu}_{\ell})^{2}\Big{]}}$
(98) $\displaystyle=\sqrt{\int_{0^{+}}^{\infty}\xi(\lambda)dR(\lambda)}$ (99)
$\displaystyle\leq\sqrt{\frac{1}{n}\int_{0^{+}}^{\infty}\xi(\lambda)dN_{x}(\lambda;G)},$
(100)

which holds when $\xi(\lambda)$ is non-increasing. Now, note that

$\displaystyle\int_{0^{+}}^{\infty}\xi(\lambda)dN_{x}(\lambda;G)=\sum_{\ell=1}^{\infty}\mathbbm{1}_{G}(\ell)\xi(\lambda_{\ell}),$
(101)

and this completes the proof.

∎

##  Appendix F Proof of Theorem 5

###### Proof.

For any two probability measures $\mu,\nu$ such that
$\frac{d\mu}{dx},\frac{d\nu}{dx}\in L^{2}(\mathcal{M})$, we have

$\displaystyle D_{0}(\mu,\nu)$ $\displaystyle=\sup_{\begin{subarray}{c}f\in
L^{2}(\mathcal{M})\\\
\|h\|_{f^{2}(\mathcal{M})}=1\end{subarray}}\mathbb{E}_{\mu}[f]-\mathbb{E}_{\nu}[f]$
(102) $\displaystyle=\sup_{\begin{subarray}{c}f\in L^{2}(\mathcal{M})\\\
\|f\|_{L^{2}(\mathcal{M})}=1\end{subarray}}\langle
f,\frac{d\mu}{dx}-\frac{d\nu}{dx}\rangle_{L^{2}(\mathcal{M})}$ (103)
$\displaystyle=\Big{\|}\frac{d\mu}{dx}-\frac{d\nu}{dx}\Big{\|}_{L^{2}(\mathcal{M})}.$
(104)

Therefore, we can use the estimator in the proof of Theorem 3 for $\alpha=0$
to achieve the desired result. ∎

##  Appendix G Proof of Theorem 6

###### Proof.

Consider the estimator $\tilde{\mu}$ proposed in the proof of Theorem 3 with a
parameter $T$ (to be set). Let $\mu_{T}$ denote the measure obtained by
truncating the sum corresponding to $\mu$ at $T$. Note that for the estimator
$\tilde{\mu}$ we have

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-\frac{d\mu}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}\Big{]}\leq\underbrace{\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-\frac{d\mu_{T}}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}\Big{]}}_{\text{(I)}}+\underbrace{\Big{\|}\frac{d\mu_{T}}{dx}-\frac{d\mu}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}}_{\text{(II)}}.$
(105)

To bound the first term, we use the Cauchy–Schwarz inequality for low degree
functions; see the following lemma.

######  Lemma 4.

Assume that $f\in L^{2}(\mathcal{M})$ and
$f=\sum_{\ell=0}^{T}f_{\ell}\mathbbm{1}_{G}(\ell)\phi_{\ell}$. Then,

$\displaystyle\|f\|_{L^{\infty}(\mathcal{M})}\leq\|f\|_{L^{2}(\mathcal{M})}\sqrt{\sup_{x\in\mathcal{M}}N_{x}(\lambda;G)}.$
(106)

###### Proof.

By Theorem 7, we have

$\displaystyle\|f\|_{L^{\infty}(\mathcal{M})}$
$\displaystyle=\sup_{x\in\mathcal{M}}|f(x)|=\sup_{x\in\mathcal{M}}\Big{|}\sum_{\ell=0}^{T}f_{\ell}\mathbbm{1}_{G}(\ell)\phi_{\ell}\Big{|}$
(107)
$\displaystyle\leq\sqrt{\sum_{\ell=0}^{T}f_{\ell}^{2}}\sqrt{\sup_{x\in\mathcal{M}}\sum_{\ell=0}^{T}\mathbbm{1}_{G}(\ell)\phi_{\ell}(x)^{2}}$
(108)
$\displaystyle\leq\|f\|_{L^{2}(\mathcal{M})}\sqrt{\sup_{x\in\mathcal{M}}N_{x}(\lambda;G)}.$
(109)

∎

Now we use the above lemma and Lemma 3 to write

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-\frac{d\mu_{T}}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}\Big{]}$
$\displaystyle\leq\sqrt{\sup_{x\in\mathcal{M}}N_{x}(\lambda_{T};G)}\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}-\frac{d\mu_{T}}{dx}\Big{\|}_{L^{2}(\mathcal{M})}\Big{]}$
(110)
$\displaystyle\leq\sqrt{\frac{1}{n}\sup_{x\in\mathcal{M}}N_{x}(\lambda_{T};G)\times\mathbb{E}_{x\sim\mu}[N_{x}(\lambda_{T};G)]}.$
(111)

To bound the second term, we have

$\displaystyle\Big{\|}\frac{d\mu_{T}}{dx}-\frac{d\mu}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}$
$\displaystyle=\sup_{x\in\mathcal{M}}\Big{|}\sum_{\ell>T}\mu_{\ell}\mathbbm{1}_{G}(\ell)\phi_{\ell}\Big{|}$
(112)
$\displaystyle=\sup_{x\in\mathcal{M}}\Big{|}\sum_{\ell>T}\mu_{\ell}\mathbbm{1}_{G}(\ell)\lambda_{\ell}^{s/2}\phi_{\ell}\lambda_{\ell}^{-s/2}\Big{|}$
(113)
$\displaystyle\leq\sqrt{\sum_{\ell>T}\mu^{2}_{\ell}\lambda_{\ell}^{s}}\sqrt{\sup_{x\in\mathcal{M}}\sum_{\ell>T}\mathbbm{1}_{G}(\ell)\phi_{\ell}^{2}\lambda_{\ell}^{-s}}$
(114)
$\displaystyle\leq\|f\|_{\mathcal{H}^{s}(\mathcal{M})}\sqrt{\sup_{x\in\mathcal{M}}\sum_{\ell>T}\mathbbm{1}_{G}(\ell)\phi_{\ell}^{2}\lambda_{\ell}^{-s}}.$
(115)

Note that

$\displaystyle\sup_{x\in\mathcal{M}}\sum_{\ell>T}\mathbbm{1}_{G}(\ell)\phi_{\ell}^{2}\lambda_{\ell}^{-s}$
$\displaystyle=\sup_{x\in\mathcal{M}}\int_{\lambda_{T}}^{\infty}\lambda_{\ell}^{-s}dN_{x}(\lambda;G)$
(116)
$\displaystyle\leq\frac{d}{d-2s}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2-s}.$
(117)

Thus, we combine the two terms and obtain

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{d\tilde{\mu}}{dx}$
$\displaystyle-\frac{d\mu}{dx}\Big{\|}_{L^{\infty}(\mathcal{M})}\Big{]}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sup_{x\in\mathcal{M}}N_{x}(\lambda;G)\times\mathbb{E}_{x\sim\mu}[N_{x}(\lambda;G)]}+\|f\|_{\mathcal{H}^{s}(\mathcal{M})}\sqrt{\frac{d}{d-2s}\frac{\omega_{d}}{(2\pi)^{d}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2-s}}$
$\displaystyle\lesssim\frac{1}{\sqrt{n}}\operatorname*{vol}(\mathcal{M}/G)\lambda_{T}^{d/2}+\|f\|_{\mathcal{H}^{s}(\mathcal{M})}\sqrt{\operatorname*{vol}(\mathcal{M}/G)}\lambda_{T}^{d/4-s/2}.$

By minimizing the above upper bound as a function of $\lambda_{T}$, we obtain
the desired result.

∎