Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance

Introduction

The Wasserstein distance is a measure of the closeness of probability distributions on metric spaces which has proven extremely useful in data science and machine learning, particularly in the analysis of images [RTG00, SdGP+15, SL11] and text [KSKW15, ZLL+16]. This distance is especially useful in tasks such as classification and clustering, since it captures geometric features of the underlying data. Moreover, unlike other measures of distance between distributions, such as the Kullback-Leibler divergence or total variation distance, the Wasserstein distance between two measures is generally finite even when neither measure is absolutely continuous with respect to the other, a situation that often arises when considering empirical distributions arising in practice.

Concretely, the Wasserstein distance measures how closely two measures can be coupled, where closeness is measured with respect to the underlying metric. For $p\in[1,\infty)$, the Wasserstein distance of order $p$ between two distributions $\mu$ and $\nu$ on a metric space $(X,D)$ is defined as

where the infimum is taken over all couplings $\gamma$ of $\mu$ and $\nu$, that is, distributions on $X\times X$ whose first and second marginals agree with $\mu$ and $\nu$, respectively [Kan42]. It can be shown that $W_{p}$ is a metric on the space of probability measures on $X$ [Vil08, Chapter 6].

In statistical contexts, direct access to a distribution of interest $\mu$ is generally not available; instead, the statistician has access to i.i.d. samples from $\mu$, or, equivalently, to an empirical distribution $\hat{\mu}_{n}$. For $\hat{\mu}_{n}$ to serve as a reasonable proxy to $\mu$, we should insist that $\hat{\mu}_{n}$ and $\mu$ are close in the Wasserstein sense. In the large-$n$ limit, this is indeed the case: if $X$ is compact and separable and $\mu$ is a Borel measure, then for any $p\in[1,\infty)$,

This result follows from the fact that Wasserstein distances metrize weak convergence [Vil08, Corollary 6.13] and the fact that empirical measure $\hat{\mu}_{n}$ converges weakly to $\mu$ almost surely [Var58].

These results have been sharpened over the years, culminating in a tight almost sure limit theorem due to Dobrić and Yukich [DY95].

In short, these arguments establish that a $d$-dimensional measure yields a convergence rate in the $W_{1}$ distance of exactly $n^{-1/d}$. These results are in a sense disappointing, since they show that slow convergence is a necessary price to pay for high-dimensional data. However, they raise several questions about the behavior of the Wasserstein metric in practice:

When can faster rates be achieved for measures that are not absolutely continuous with respect to the Lebesgue measure?

Under what conditions can sharper finite-sample (i.e., non-asymptotic) rates be obtained?

Our goal in this work is to answer the above questions in a very general sense. We consider a bounded metric space $X$ subject to mild technical conditions and prove upper and lower bounds on the rate of convergence for $W_{p}(\mu,\hat{\mu}_{n})$ for all $p\in[1,\infty)$. Inspired by the bounds of [Dud68], we show essentially tight asymptotic convergence rates for a large class of measures. In particular, our upper and lower bounds improve on many existing results in the literature [Dud68, BLG14, DSS13, FG15], either in the generality with which they are applicable or the rates which are obtained. These results show that the rate of convergence of $W_{p}(\mu,\hat{\mu}_{n})$ depends on a notion of the intrinsic dimension of the measure $\mu$, which can be significantly smaller than the dimension of the metric space on which $\mu$ is defined.

Our second goal is to obtain finite-sample results which hold outside the asymptotic regime. A common phenomenon in practice is for a measure to exhibit different dimensional structure at different scales; this so-called multi-scale behavior arises in a range of applications [LMR16, WDCB05, SMB98]. We show that the convergence of $\hat{\mu}_{n}$ to $\mu$ in $W_{p}$ for such measures can exhibit wildly different rates as $n$ increases. In particular, they can enjoy a much faster convergence rate when $n$ is small than they do in the large-$n$ limit. We illustrate this phenomenon via a number of examples inspired by measures that arise in practice.

In both of the above regimes, we consider exclusively the question of how the expectation ${\rm I}\kern-1.79993pt{\rm E}[W_{p}(\mu,\hat{\mu}_{n})]$ behaves. Controlling this quantity suffices to understand the behavior of $W_{p}(\mu,\hat{\mu}_{n})$ because the Wasserstein distance concentrates very well around its expectation, a fact which we prove in Section 6. Combining this observation with the bounds on we prove on ${\rm I}\kern-1.79993pt{\rm E}[W_{p}(\mu,\hat{\mu}_{n})]$ yields sharp high-probability bounds.

We end by giving applications of our work to machine learning and statistics and sketch directions for future work.

Preliminaries

In this section, we present the mild assumptions on $X$ under which our results hold. We also give background on Wasserstein distances and compare our results to prior work.

We are concerned with measures on a compact metric space $X$. The first assumption is entirely standard and allows us to avoid many measure-theoretic difficulties:

The metric space $X$ is Polish, and all measures are Borel.

Since we limit ourselves to the compact case, $\operatorname{diam}(X)$ is necessarily finite, and for normalization purposes we assume the following.

Assumption 2 can always be made to hold by a simple rescaling of the metric.

2 Background on Wasserstein distances

Above, we defined the Wasserstein $p$ distance between two distributions $\mu$ and $\nu$ on $(X,D)$ as

A second definition, due to Monge [Mon81, San15], reads as follows:

where the infimum is taken over all transports $T:X\to X$ such that the pushforward measure $\mu\circ T^{-1}$ equals $\nu$. In general, this infimum in the Monge definition is not attained. This formulation has an easy geometric interpretation: the Wasserstein distance measures the cost of moving mass from the measure $\mu$ to the measure $\nu$ with respect to the metric of $X$.

The special case $W_{1}$, which is also known as the Kantorovich-Rubinstein distance [Vil08] or earth mover distance [RTG00], has a particularly simple dual representation:

where the supremum is taken over all $1$-Lipschitz functions on $X$ [KR58]. This dual representation makes $W_{1}$ significantly easier to bound [Vil08, Remark 6.6]. A more general dual formulation is also available for $W_{p}$ for $p\neq 1$, but it is less simple to manipulate; more details appear in Section 6.

3 Related work

Our work generalizes several strands of work on the convergence rates of the empirical measure in Wasserstein distances. The first strand, inaugurated by Dudley [Dud68], focuses on obtaining rates of convergence of $\hat{\mu}_{n}$ to $\mu$ based on the inherent dimension of the measure $\mu$. In that paper, Dudley obtained results matching the ones we present in Section 4 for the convergence of $\hat{\mu}_{n}$ to $\mu$ in $W_{1}$ distance, with a rate depending on the covering number of the support of $\mu$. Dudley’s argument relied extensively on the dual characterization of $W_{1}$ as a supremum over Lipschitz test functions, as in (1). As a result, his technique does not extend to $W_{p}$ for $p\neq 1$.

An extension of Dudley’s techniques to other values of $p$ appears in [BLG14]. Their approach is similar to ours, but our analysis is tighter: in the language of Section 4.2, they prove an upper bound based on the quantity $d_{M}$ whereas we obtain an upper bound based on the smaller quantity $d_{p}^{*}$.

We also note several other recent works [Boi11, BGV07] which have focused on obtaining tail bounds for the quantity $W_{p}(\mu,\hat{\mu}_{n})$. The arguments of [BGV07] rely on transportation inequalities such as the celebrated Bobkov-Götze inequality [BG99]. These arguments were simplified in [Boi11], but, as noted in [BLG14], the analysis becomes much easier if the development of tail bounds is divided into two steps: an estimate of the expectation ${\rm I}\kern-1.79993pt{\rm E}[W_{p}(\mu,\hat{\mu}_{n})]$ and a concentration bound showing how well $W_{p}(\mu,\hat{\mu}_{n})$ concentrates near that expectation. This is the approach we adopt: bounds on the expected value appear in Section 4 and 5, and concentration bounds are obtained in Section 6.

4 Notation

The metric on $X$ will always be denoted $D(\cdot,\cdot)$. Given a point $x\in X$ and $r>0$, denote by $B(x,r)$ the open ball of radius $r$ around $x$. The symbol $\log$ denotes the natural logarithm. The notation $f(n)\lesssim g(n)$ indicates that there exists a constant $C$, depending on $f$ and $g$ but not $n$, such that $f(n)\leq Cg(n)$ for all $n$.

Dyadic transport

We formalize these requirements in the following definition [Dav88, Section A]. Denote by $\mathcal{B}(X)$ the Borel subsets of $X$.

A dyadic partition of a set $S\subseteq X$ with parameter $\delta<1$ is a sequence $\{\mathcal{Q}^{k}\}_{1\leq k\leq k^{*}}$ with $\mathcal{Q}^{k}\subseteq\mathcal{B}(X)$ possessing the following properties:

The sets in $\mathcal{Q}^{k}$ form a partition of $S$.

If $Q\in\mathcal{Q}^{k}$, then $\operatorname{diam}(Q)\leq\delta^{k}$.

If $Q^{k+1}\in\mathcal{Q}^{k+1}$ and $Q^{k}\in\mathcal{Q}^{k}$, then either $Q^{k+1}\subseteq Q^{k}$ or $Q^{k+1}\cap Q^{k}=\emptyset$. That is, the $(k+1)$th partition is a refinement of the $k$th partition.

The following Proposition bounds $W_{p}^{p}(\mu,\nu)$ in terms of the mass $\mu$ and $\nu$ assign to elements of a dyadic partition.

Let $\mu$ and $\nu$ be two Borel probability measures on $X$, and let $S$ be a set such that $\mu(S)=\nu(S)=1$. If $\{\mathcal{Q}^{k}\}_{1\leq k\leq k^{*}}$ is a dyadic partition of $S$ with parameter $\delta$, then

Proposition 1 is stated for $W_{p}^{p}$, but can easily adapted to optimal transport with a general cost $c(\cdot,\cdot)$ by replacing the requirement that $\operatorname{diam}(Q)\leq\delta^{k}$ in Definition 1 by the requirement that $\sup_{x,y\in Q}c(x,y)\leq\delta^{k}$.

Boissard and Le Gouic [BLG14] used a version of Proposition 1 to prove a bound on $W_{p}^{p}(\mu,\hat{\mu}_{n})$ based on the covering number of the set $S$, a definition of which appears in Section 4, below. However, their results are not sharp, and they do not recover the rates obtained in [Dud68] for the case $p=1$. In Section 4, we show how to improve their argument to obtain sharper results, which extend the rates from [Dud68] to all $p\in[1,\infty)$.

Asymptotic upper and lower bounds

In this section, we show asymptotic upper and lower bounds for $W_{p}$ that hold for all $p\in[1,\infty)$. These bounds extend results of [Dud68] to the case $p\neq 1$ and improve the bounds of [BLG14] by focusing on a set $S$ to which $\mu$ assigns mass of almost $1$ rather than on the larger set $\operatorname{supp}(\mu)$. We will also show a broad class of measures for which our bounds are asymptotically tight.

To state our bounds we will define several notions of dimension of a measure.

Given a set $S\subseteq X$, the $\varepsilon$-covering number of $S$, denoted $\mathcal{N}_{\varepsilon}(S)$, is the minimum $m$ such that there exists $m$ closed balls $B_{1},\dots,B_{m}$ of diameter $\varepsilon$ such that $S\subseteq\bigcup_{1\leq i\leq m}B_{i}$. The $\varepsilon$-dimension of $S$ is the quantity

When working with measures instead of sets, it is convenient to be able to ignore a small fraction of the mass. The following definition appears in [Dud68], which notes a connection to the $\varepsilon;\delta$ entropy introduced by [PRR67].

Given a measure $\mu$ on $X$, the ($\varepsilon$, $\tau$)-covering number is

and the ($\varepsilon$, $\tau$)-dimension is

Note that $\mathcal{N}_{\varepsilon}(\mu)=\mathcal{N}_{\varepsilon}(\operatorname{supp}(\mu))$, and that $\mathcal{N}_{\varepsilon}(\mu,\tau)$ and $d_{\varepsilon}(\mu,\tau)$ increase as $\tau$ decreases.

We now define our main notions of dimension of a measure.

The upper and lower Wasserstein dimensions are respectively

Note that the monotonicity of $d_{\varepsilon}(\mu,\tau)$ in $\tau$ implies that the limit in the definition of $d_{*}(\mu)$ exists. The definition of $d_{p}^{*}$ is complicated by the fact that the behavior of the Wasserstein distance is very different when the dimension is small. For convenience we only treat the case where the dimension is larger than $2p$. We note that the monotonicity of $d_{\varepsilon}(\mu,\tau)$ in $\tau$ also implies that $d_{*}\leq d_{p}^{*}$ for all $p$.

Our definition of the upper Wasserstein dimension is new. Dudley [Dud68] considered measures satisfying a bound of the form $\mathcal{N}_{\varepsilon}(\mu,\varepsilon^{\frac{s}{s-2}})\leq C\varepsilon^{-s}$ for all sufficiently small $\varepsilon$; the definition of $d_{p}^{*}(\mu)$ is the correct generalization to the $p\neq 1$ case. The lower Wasserstein dimension was introduced by Young [You82], who credits the idea to Ledrappier [Led81], in the context of dynamical systems. The term Wasserstein dimension is ours, and is justified by Theorem 1 below.

2 Comparison with other notions of dimension

To make it easier to interpret the quantities $d_{p}^{*}(\mu)$ and $d_{*}(\mu)$, we sketch here their relationship with two other well known notions of dimensions for the measure $\mu$, the Minkowski dimension (also known as the Minkowski-Bouligand or box-counting dimension) and the Hausdorff dimension. Both quantities have long been studied in fractal and metric geometry [Fal04].

The Minkowski dimension of a set $S$ is the quantity

Given a measure $\mu$, the Minkowski and Hausdorff dimensions of $\mu$ are respectively

We note that the quantities $d_{M}(\mu)$ and $d_{H}(\mu)$ are upper and lower bounds on the Wasserstein dimensions.

None of the inequalities in Proposition 2 can be replaced by equalities. Examples of measures $\mu$ for which $d_{H}(\mu)<d_{*}(\mu)$ are complicated; one appears in [KLP11, Remark 7.8]. It is much easier to find examples in which $d_{*}(\mu)$, $d^{*}_{p}(\mu)$, and $d_{M}(\mu)$ do not agree. For instance, it is easy to see that $d_{*}(\mu)=0$ for any discrete measure, but the countable set $S:=\left(\{k^{-1}\}_{k=1}^{\infty}\right)^{d}\subset^{d}$ has Minkowski dimension $d/2$. By choosing $d>4p$ and choosing a measure $\mu$ supported on $S$ with appropriately slow decay, one can ensure that $d^{*}_{p}(\mu)$ is strictly less than $d/2$, and hence strictly between $d_{*}(\mu)$ and $d_{M}(\mu)$.

3 Main result

With these definitions in place, we can state our main asymptotic bound.

Let $p\in[1,\infty)$. If $s>d_{p}^{*}(\mu)$, then

The upper and lower bounds are proved below and are corollaries of more precise results with explicit constants (Propositions 5 and 6). Note that the lower bound does not merely hold in expectation. Indeed, such a lower bound holds for any discrete measure supported on at most $n$ points.

Theorem 1 improves on several existing results. For the upper bound, Dudley [Dud68] showed that, if $s>d_{1}^{*}(\mu)$, then

but his proof technique applied only to $p=1$. Boissard and Le Gouic [BLG14] extended this bound to all $p$, but only if $s>d_{M}(\mu)\geq 2p$. Since $d^{*}_{p}(\mu)\leq d_{M}(\mu)$ with some measures exhibiting strict inequality, our result is sharper.

Dudley [Dud68] proved a lower bound for $W_{1}$—and hence, by monotonicity of $W_{p}$ in $p$, for $W_{p}$ for all $p\in[1,\infty)$—based on the quantity

which is easily seen to be smaller than $d_{*}(\mu)$, with strict inequality possible. Our argument is a simple extension of his.

4 Proof of upper bound

The upper bound of Theorem 1 follows from Proposition 5, below.

To apply the bound of Proposition 1, we need to show the existence of a suitable dyadic partition. The following Proposition is an extension of [BLG14, Lemma 2.1] and shows that we can choose a dyadic partition which provides an almost optimal covering of subsets of $S$.

Fix $S\in\mathcal{B}(X)$. Let $k^{*}$ be any positive integer for which the covering number $\mathcal{N}_{3^{-(k^{*}+1)}}(S)$ is finite, and let $\{S_{k}\}_{1\leq k\leq k^{*}}$ be a sequence of Borel subsets $S$. There exists a dyadic partition of $S$ with parameter $\delta=1/3$ such that for $1\leq k\leq k^{*}$, the number of sets in $\mathcal{Q}^{k}$ intersecting $S_{k}$ is at most $\mathcal{N}_{3^{-(k+1)}}(S_{k})$.

Let $Q(S)=\{i:Q_{i}^{k}\cap S\neq\emptyset\}$, and write

Since $n\hat{\mu}_{n}(Q_{i}^{k})$ is a Binomial random variable with parameters $(n,\mu(Q_{i}^{k}))$, we have the bound [BK13]

Applying the first bound on $S^{\prime}$ and the second bound on $X\setminus S^{\prime}$ yields

Since the second sum contains $|Q(S)|$ terms and $\sum_{i\in Q(S)}\mu(Q_{i}^{k})=\mu(S^{\prime})\leq 1$, the final bound follows from Cauchy-Schwarz. ∎

The key step in proving the upper bound of Theorem 1 is giving a bound for ${\rm I}\kern-1.79993pt{\rm E}[W_{p}^{p}(\mu,\hat{\mu}_{n})]$ in terms of the quantity $d_{\varepsilon}(\mu,\varepsilon^{\frac{sp}{s-2p}})$, which appears in the definition of $d_{p}^{*}$.

Let $p\in[1,\infty)$. Suppose there exists an $\varepsilon^{\prime}\leq 1$ and $s>2p$ such that

for all $\varepsilon\leq\varepsilon^{\prime}$. Then

The assumption that $s>2p$ implies that the first term in the above bound is asymptotically larger than the second term. Note also that $C_{1}$ decreases as $s$ increases, so that as long as $s$ is bounded away from $2p$, the constant $C_{1}$ has no dependence on the dimension $s$. On the other hand, $C_{2}$ does depend exponentially on $s$, even though the term $C_{2}n^{-1/2}$ is asymptotically negligible.

The presence of two terms in the upper bound of Proposition 5 is a consequence of the weakness of the assumption that the bound on $d_{\varepsilon}$ holds only for $\varepsilon$ sufficiently small rather than for all $\varepsilon$. In Proposition 10, below, we remove the $n^{-1/2}$ term by adopting a stronger assumption on $d_{\varepsilon}$.

If $n<(27/\varepsilon^{\prime})^{s}$, then the second term is larger than $1$, so the bound holds from the trivial fact that $W^{p}_{p}(\mu,\nu)\leq\operatorname{diam}(X)\leq 1$ for any measures $\mu,\nu$ supported on $X$. We therefore assume that $n\geq(27/\varepsilon^{\prime})^{s}$.

Hence for $k\geq k^{\prime}$, there exists a set $T_{k}$ of mass at least $1-3^{-\alpha k^{\prime}}$ such that

Applying Proposition 3 with $S_{k}=T_{k^{\prime}}$ for $k<k^{\prime}$ and $S_{k}=T_{k+1}$ for $k\geq k^{\prime}$ implies the existence of a dyadic partition $\{\mathcal{Q}^{k}\}_{1\leq k\leq k^{*}}$ of $X$ such that the number of sets of $\mathcal{Q}^{k}$ intersecting $S_{k}$ is at most $\mathcal{N}_{3^{-(k+1)}}(S_{k})$.

Using this dyadic partition in Proposition 1 and applying Proposition 4 yields

Since $\mathcal{N}_{\varepsilon}(T)$ increases as $\varepsilon$ decreases, for $k\leq k^{\prime}-1$ we have the bound

By construction, the sets $T_{k}$ also satisfy for $k\geq k^{\prime}$

Combining these bounds with the bound $\sum_{k=1}^{k^{*}}3^{-(k-1)p}\leq 3/2$ for $p\geq 1$ yields

The choice of $k^{*}$ implies that $3^{(k^{*}+2)s}\leq n$ and that $3^{-k^{*}p}\leq 3^{3p}n^{-p/s}$, and the choice of $k^{\prime}$ implies that $\alpha k^{\prime}>p\frac{\log n}{s\log 3}-3\alpha$, so that $3^{-\alpha k^{\prime}}<3^{3\alpha}n^{-p/s}$. Combining these estimates yields

Plugging in the definitions of $C_{1}$ and $C_{2}$ then yields the claim. ∎

If $s>d_{p}^{*}(\mu)$, then there exists an $\varepsilon^{\prime}$ such that $d_{\varepsilon}(\mu,\varepsilon^{\frac{sp}{s-2p}k})\leq s$ for all $\varepsilon\leq\varepsilon^{\prime}$. Apply Proposition 5. ∎

5 Proof of lower bound

Our asymptotic lower bounds involving $d_{*}(\mu)$ follow from a much simpler argument. One striking feature of this lower bound is that it actually holds not merely for the empirical measure $\hat{\mu}_{n}$ but indeed for any measure $\nu$ supported on at most $n$ atoms. That such lower bounds are often tight for empirical measures is a rather surprising fact, which has been noted several times, including in Dudley’s original paper [CR12, Klo12, DSS13, Dud68, BLG14].

The following Proposition is adapted from [Dud68] and forms the core of the lower bound.

Suppose that there exist positive constants $\varepsilon^{\prime}$, $\tau$, and $t$ such that

for all $\varepsilon\leq\varepsilon^{\prime}$. If $n>{\varepsilon^{\prime}}^{-t}$ and $\nu$ is any measure supported on at most $n$ points, then

Choose $\varepsilon=n^{-1/t}/2$, and let $S=\bigcup_{x\in\operatorname{supp}(\nu)}B(x,\varepsilon/2)$. Since $\mathcal{N}^{\prime}_{\varepsilon}(\mu,\tau)\geq\varepsilon^{-t}>n$, we must have $\mu(S)<1-\tau$. Therefore, if $X\sim\mu$, then $D(X,\operatorname{supp}(\nu))\geq\varepsilon/2$ with probability at least $\tau$. Hence if $(X,Y)$ is any coupling of $\mu$ and $\nu$,

Proposition 6 immediately implies the desired asymptotic lower bound.

If $t<d_{*}(\mu)$ and $\nu$ is any measure supported on at most $n$ points, then

By the definition of $d_{*}(\mu)$, for any $t<d_{*}(\mu)$, there exist constants $\varepsilon^{\prime}$ and $\tau$ as in the statement of Proposition 6. The claim follows. ∎

6 Regular spaces

The remark after Proposition 2 establishes that $d_{*}(\mu)$ and $d^{*}_{p}(\mu)$ do not agree in general. However, these dimensions do agree whenever the measure is sufficiently well behaved. In this section, we give several broad classes of examples for which they do match, and for which our bounds are therefore sharp.

The following Proposition gives a simple condition under which this agreement occurs.

Let $\mathcal{H}^{d}$ be the $d$-dimensional Hausdorff measure on a closed set $S$. If $\mu\ll\mathcal{H}^{d}$ and $\operatorname{supp}(\mu)\subseteq S$, then for any $p\in[1,d/2]$,

In particular, if $d=d_{M}(S)$, then $d_{*}(\mu)=d^{*}_{p}(\mu)=d$.

Limiting our attention to sets for which the Hausdorff measure is well behaved motivates the following definition, which appears in [GL07].

A set $S$ is regular of dimension $d$ if it is compact and there exists constants $c$ and $r_{0}$ such that the $d$-dimensional Hausdorff measure $\mathcal{H}^{d}$ on $S$ satisfies

It is well known (see, e.g., [Mat99, Theorem 5.7]) that $d_{M}(S)=d$ if $S$ is regular of dimension $d$. We therefore obtain the following simple characterization.

If the support of $\mu$ is a regular set of dimension $d$ and $\mu\ll\mathcal{H}^{d}$, then for any $p\in[1,d/2]$,

The following Proposition, which appears in [GL07], shows that many well behaved sets are regular, and so implies the existence of many examples for which our results are tight.

The following sets are regular of dimension $d$:

Nonempty, compact convex sets spanned by an affine space of dimension $d$,

Relative boundaries of nonempty, compact convex sets of dimension $d+1$,

Compact $d$-dimensional differentiable manifolds,

Self-similar sets with similarity dimension $d$.

Moreover, regularity is preserved under finite unions and bi-Lipschitz maps.

Finite-sample bounds and multiscale behavior

The results of Section 4 imply that for any sufficiently regular $d$-dimensional measure $\mu$, the empirical measure $\hat{\mu}_{n}$ approaches $\mu$ in $W_{p}$ at a rate of approximately $n^{-1/d}$. For example, if $\mu$ is absolutely continuous with respect to the Lebesgue measure on $^{d}$, Dudley showed that the slow $n^{-1/d}$ rate is unavoidable [Dud68]. Faster rates can be obtained if $\mu$ is singular: for instance, if $\mu$ is a sum of a finite number of Dirac masses, then Proposition 1 can be used to show that $\hat{\mu}_{n}$ approaches $\mu$ at a much faster $n^{-1/2p}$ rate, independent of the ambient dimension.

However, what should one expect if $\mu$ is approximately a sum of Dirac masses (or, in general, approximately low dimensional)? Suppose for instance that $\mu$ is the convolution of a sum of Dirac masses with an isotropic Gaussian of small variance. Since $\mu$ has a density, $W_{p}(\mu,\hat{\mu}_{n})$ must scale like $n^{-1/d}$ eventually, but it is possible that the convergence of $\hat{\mu}_{n}$ to $\mu$ should improve due to the fact that $\mu$ is almost singular.

It turns out that this is indeed the case, as we show in this Section. We begin by proving a sharper version of Proposition 5 better suited to non-asymptotic results. In the second half of this Section, we show how this non-asymptotic bound can be used to prove faster convergence rates in the finite-sample regime for situations like the one described above.

The statement of Proposition 5 only assumes a bound on the quantity $d_{\varepsilon}(\mu,\tau)$ for sufficiently small $\varepsilon$. It is therefore well suited to establishing results of an asymptotic nature. On the other hand, the resulting bound did not give any indication of the behavior in the small-$n$ regime, since the bound was vacuous for $n\lesssim(\varepsilon^{\prime})^{-2}$.

If we have stronger control over $d_{\varepsilon}(\mu,\tau)$, then the proof of Proposition 5 can be modified to yield a finite-sample result. In particular, if we can control $d_{\varepsilon}(\mu,\tau)$ for all $\varepsilon$ larger than a certain threshold, we can prove an upper bound without the $n^{-1/2}$ term present in Proposition 5.

Fix $p\in[1,\infty)$. Write $d_{\geq\varepsilon}(\mu,\tau)=\sup_{\varepsilon^{\prime}\in[\varepsilon,1/9]}d_{\varepsilon}(\mu,\tau)$, and let $d_{n}=\inf_{\varepsilon>0}\max\{d_{\geq\varepsilon}(\mu,\varepsilon^{p}),\frac{\log n}{-\log\varepsilon}\}$. If $d_{n}>2p$, then

As in Proposition 5, the constant $C_{1}$ is independent of the dimension as long as $d_{n}$ is bounded away from $2p$.

Fix an arbitrary $\varepsilon$, and let $d=\max\{d_{\geq\varepsilon}(\mu,\varepsilon^{p}),\frac{\log n}{-\log\varepsilon}\}$, where $d>2p$. If $n^{-1/d}\geq 1/27$, then the bound $W^{p}_{p}(\mu,\hat{\mu}_{n})\leq C_{1}n^{-p/d}$ is trivial, so assume that $n>3^{3d}$.

Let $k^{*}=\left\lfloor\frac{\log n}{d\log 3}\right\rfloor-2$. As in the proof of Proposition 5, we can choose sets $S_{1},\dots,S_{k^{*}}$ such that $\mu(S_{k})\geq 1-\varepsilon^{p}$ and $\mathcal{N}_{3^{-(k+1)}}(S_{k})=\mathcal{N}_{3^{-(k+1)}}(\mu,\varepsilon^{p})$ for $1\leq k\leq k^{*}$. Applying Proposition 3 to construct an appropriate dyadic partition and using Propositions 1 and 4 yields

By the definition of $k^{*}$, for $1\leq k\leq k^{*}$,

so $3^{-(k+1)}\geq\varepsilon$. Hence $3\varepsilon^{p}\leq 3^{-k^{*}p}$ and $\mathcal{N}_{3^{-(k+1)}}(\mu,\varepsilon^{p})\leq 3^{(k+1)d}$ for $1\leq k\leq k^{*}$, and applying the bound $\sum_{k=1}^{k^{*}}3^{-(k-1)p}\leq 3/2$ for $p\geq 1$ yields

where in the last step we have used the fact that $d\geq d_{n}$ and $\frac{1}{3^{\frac{d}{2}-p}-1}$ is decreasing in $d$.

Taking the infimum over all possible choices of $\varepsilon$ yields the bound. ∎

Note in the proof of Proposition 10 that we in fact only needed control over $d_{\varepsilon^{\prime}}(\mu,\tau)$ for $\varepsilon^{\prime}$ of the form $3^{-k}$ for $k$ a positive integer, though for simplicity we have assumed that we can bound $d_{\varepsilon^{\prime}}(\mu,\tau)$ for all $\varepsilon^{\prime}\in[\varepsilon,1/9]$.

Let $\delta_{n}$ be a nonincreasing sequence in $(0,1)$ with the following properties:

the bound $\delta_{n}\geq n^{-1}$ holds for all $n\geq 2$ (i.e., $\delta_{n}$ does not decrease too quickly)

the sequence $\frac{\log n}{-\log\delta_{n}}$ is nondecreasing (i.e., the rate of decrease of $\delta_{n}$ slows), and

there exist constants $c>1$ and $\alpha\in[-1,0)$ such that $\frac{1}{c}n^{\alpha}\leq\delta_{n}\leq cn^{\alpha}$ for all $n$ sufficiently large (i.e., $\delta_{n}$ eventually decreases polynomially in $n$).

for all $p\in[1,\infty)$, all $n\geq 1$, and any measure $\nu$ supported on at most $n$ points.

Proposition 10 only holds when $d_{n}>2p$, so for completeness we conclude this section by providing a second bound that can be used when Prposition 10 does not apply. The following bound is always valid and is sharper when the asymptotic dimension of $\mu$ is small.

Let $m_{n}=\inf_{\varepsilon>0}\max\{\mathcal{N}_{\varepsilon}(\mu,\varepsilon^{p}),n\varepsilon^{2p}\}$. Then

Fix an arbitrary $\varepsilon$, and let $m=\max\{\mathcal{N}_{\varepsilon}(\mu,\varepsilon^{p}),n\varepsilon^{2p}\}$. If $\varepsilon\geq 1/9$, then the bound $W_{p}^{p}(\mu,\hat{\mu}_{n})\leq C_{1}\sqrt{\frac{m}{n}}$ is trivial, so assume $\varepsilon<1/9$.

Let k^{*}=\Big{\lfloor}\frac{-\log\varepsilon}{\log 3}\Big{\rfloor}-1. Following the proof of Proposition 10, we have

The monotonicity of $\mathcal{N}_{\varepsilon}(\mu,\tau)$ implies that $\mathcal{N}_{3^{-(k+1)}}(\mu,\varepsilon^{p})\leq\mathcal{N}_{\varepsilon}(\mu,\varepsilon^{p})\leq m$ for all $k\leq k^{*}$. Plugging in this estimate and applying the bound $\sum_{k=1}^{k^{*}}3^{-(k-1)p}\leq 3/2$ for $p\geq 1$ yields

On the other hand, $3^{-k^{*}p}=9^{p}3^{-(k^{*}+2)p}<9^{p}\varepsilon^{p}\leq 9^{p}\sqrt{\frac{m}{n}}$, so

Taking the infimum over all possible choices of $\varepsilon$ yields the bound. ∎

2 Clusterable distributions

We now return to the situation described in the introduction to this Section and analyze the case where $\mu$ is like a sum of Dirac masses. This is the simplest example of where multiscale behavior can occur. We validate the intuition presented above: when $\mu$ is approximately discrete, in the sense that it is supported on balls of small radius, then the convergence of $\hat{\mu}_{n}$ to $\mu$ enjoys the fast $n^{-1/2p}$ rate until $n$ is large even $\mu$ is absolutely continuous with respect to the Lebesgue measure. We show that a similar phenomenon occurs when $\mu$ is the convolution of a discrete distribution with a small Gaussian, where we show that it is enough that most of the mass of $\mu$ is near a discrete distribution, even though the support is unbounded.

A distribution $\mu$ is $(m,\Delta)$-clusterable if $\operatorname{supp}(\mu)$ lies in the union of $m$ balls of radius at most $\Delta$.

Intuitively, the measure $\mu$ looks like a sum of $m$ Dirac measures at “large scales,” with high-dimensional information arriving only when we consider scales smaller than $\Delta$.

If $\mu$ is $(m,\Delta)$ clusterable, then for all $n\leq m(2\Delta)^{-2p}$,

Since $\operatorname{supp}(\mu)$ lies in the union of $m$ balls of radius at most $\Delta$, we have $\mathcal{N}_{2\Delta}(\mu)\leq m$. Therefore if $n\leq m(2\Delta)^{-2p}$, then

and the claim follows from Proposition 12. ∎

We can apply the above result to “Diracs plus Gaussian” case described in the introduction to this Section. We first require a simple Lemma, which allows us bound the mass of a Gaussian outside of a small ball.

If $Z\sim\mathcal{N}(0,\Sigma)$, then for any $c\geq 5$,

Proposition 13 and Lemma 1 yield the following claim.

Since the measure $\mu$ is absolutely continuous with respect to the Lebesgue measure, if $d>2p$, then asymptotically we have

which is slower than the $n^{-1/2}$ rate obtainable for small $n$.

Let $c=2\sqrt{p\log\frac{1}{\sigma}}$, which by assumption is at least $5$. By Lemma 1, all but at most $e^{-c^{2}/4}=\sigma^{p}$ mass lies within balls of radius $c\sigma$ around the mixture centers. Therefore $\mathcal{N}_{2c\sigma}(\mu,(2c\sigma)^{p})\leq\mathcal{N}_{2c\sigma}(\mu,\sigma^{p})\leq m$. If $n\leq m(16\sigma^{2}p\log\frac{1}{\sigma})^{-p}=m(2c\sigma)^{-2p}$, then we obtain

and the claim follows from Proposition 12. ∎

3 Approximately low-dimensional sets

We now broaden considerably to the general case where $\mu$ is supported on an approximately low-dimensional set.

For any $S\subseteq X$, the $\varepsilon$-fattening of $S$ is

If $S^{\prime}\subset S_{\varepsilon}$ for some $S$, then $S^{\prime}$ is close to $S$ in the sense that every point of $S^{\prime}$ is within $\varepsilon$ of some point in $S$. In particular, $S^{\prime}\subset S_{\varepsilon}$ if the Hausdorff distance between $S^{\prime}$ and $S$ is at most $\varepsilon$.

Measures supported on $S_{\varepsilon}$ are “close” to measures supported on $S$, and if $S$ is low-dimensional, then we obtain correspondingly better finite-sample rates.

Suppose $\operatorname{supp}(\mu)\subseteq S_{\varepsilon}$ for some $\varepsilon>0$ and set $S$ satisfying

for all $\varepsilon^{\prime}\leq 1/27$ and for some $d>2p$. Then for all $n\leq(3\varepsilon)^{-d}$,

Given any covering of $S$ by balls $B_{1},\dots,B_{m}$ of diameter $\varepsilon^{\prime}$, the $\varepsilon$-fattenings $(B_{1})_{\varepsilon},\dots,(B_{m})_{\varepsilon}$ provide a covering of $S_{\varepsilon}$ by balls of diameter $\varepsilon^{\prime}+2\varepsilon$. This implies for all $\varepsilon^{\prime}\geq\varepsilon$ that

Therefore, if $n\leq(3\varepsilon)^{-d}$, then

We can also relax the requirement that $\operatorname{supp}(\mu)\subseteq S_{\varepsilon}$ to the statement that $\mu$ is concentrated near $S$.

for all $\varepsilon\leq 1/27$, for some $d>2p$. Suppose there exists a positive constant $\sigma$ such that $\mu$ satisfies

for all $\varepsilon>0$. If $p\log\frac{1}{\sigma}\geq\frac{1}{18}$, then for all $n\leq\left(18p\sigma^{2}\log\frac{1}{\sigma}\right)^{-d/2}$,

In other words, we again get the fast $n^{-p/d}$ rate until $n$ is of order approximately $\sigma^{-d}$.

Let $\varepsilon=\sqrt{2p\sigma^{2}\log\frac{1}{\sigma}}$. As in the proof of Proposition 15, the assumptions imply that

we conclude that as long as $n\leq\left(18p\sigma^{2}\log\frac{1}{\sigma}\right)^{-d/2}$, then

and the claim follows from Proposition 10. ∎

The condition appearing in Proposition 16 is notable because it resembles the guarantee of an isoperimetric inequality [Led05]. Such inequalities are an important topic in modern geometric probability theory, and possess a close connection to the $W_{1}$ distance [BG99].

It is a striking fact about such inequalities that they are intimately connected to the concentration properties of $1$-Lipschitz functions.

then for any set $A$ with $\mu(A)\geq 1/2$,

Conversely, if (3) holds for all sets $A$ with $\mu(A)\geq 1/2$, then (2) holds for any $1$-Lipschitz function $f$ with median $m_{f}$.

The conditions of Proposition 17 have been used recently to show concentration bounds for the $W_{1}$ distance [BGV07]. Here, we show that if $\mu$ possesses the property described above, then $\hat{\mu}_{n}$ enjoys a fast rate of convergence to $\mu$ for any $p$, as long as $\mu$ assigns a constant fraction of mass to a low-dimensional set.

Suppose that $\mu$ satisfies either of the two equivalent conditions of Proposition 17 with some $\sigma$ satisfying $p\log\frac{1}{\sigma}\geq\frac{1}{18}$. If $S$ is a set satisfying

for all $\varepsilon$, for some $d>2p$ and $\mu(S)\geq 1/2$, then for all $n\leq\left(18p\sigma^{2}\log\frac{1}{\sigma}\right)^{-d/2}$,

Concentration

In addition to proving bounds on the expected value of the quantity $W_{p}^{p}(\mu,\hat{\mu}_{n})$, we also show that it concentrates well around its expectation. Previous work [BGV07, Boi11] has sought to obtain tail bounds of the form

where $\psi_{n}(t)$ is some function exhibiting subgaussian decay. The results of [BGV07] appear to obtain this rate, but the constants involved depend on $n$ and the ambient dimension of the space in a way that makes the results difficult to interpret.

We follow a different approach, which more clearly emphasizes the dependence of the tail on $n$ and the dimension. The results of Sections 4 and 5, above, yield bounds on the expected value ${\rm I}\kern-1.79993pt{\rm E}[W_{p}^{p}(\mu,\hat{\mu}_{n})]$. As we have seen, the convergence of this quantity to may be slow when the dimension is large. On the other hand, we show below that, as long as $X$ is bounded, the quantity $W_{p}^{p}(\mu,\hat{\mu}_{n})$ concentrates well around its expectation independent of the dimension. The argument is standard [Tal92] and is significantly easier to obtain than the above bounds on the expected value.

We require the following dual formulation [RR90, R9̈1].

The following claims are standard, and we provide a proof in Appendix A for completeness.

Given any pair of probability measures $\mu$ and $\nu$ on $X$ and any $p\in[1,\infty)$, the following duality holds:

where the supremum is taken over all bounded continuous functions on $X$ and $f^{c}$ is the $c$-transform of $f$ with respect to $D(\cdot,\cdot)^{p}$. Moreover, if $\operatorname{diam}(X)\leq 1$, then we can take $0\leq f(x)\leq 1$ for all $x\in X$.

We then obtain a concentration result via a standard bounded difference argument.

Let $\hat{\mu}_{n}$ be the empirical distribution corresponding to the i.i.d. samples $X_{1},\dots,X_{n}\sim\mu$. We abbreviate $W_{p}^{p}(\mu,\hat{\mu}_{n})$ by $W$. By Proposition 19, we can write

or, writing $W$ explicitly as a function of $X_{1},\dots X_{n}$,

For any $x_{1},\dots,x_{n},x_{n}^{\prime}\in X$, we have

Applying McDiarmid’s inequality [McD89] yields the bound. ∎

Applications

In this section, we sketch two applications of our work to machine learning and statistics.

is as good as possible for a wide class of functions $f$. This problem possesses close connections to optimal quantization, since the points $x_{1},\dots,x_{n}$ naturally serve as a finite approximation to the underlying measure [GL07, Pag98].

Recalling (1), we immediately see that the first claim corresponds to the fact that ${\rm I}\kern-1.79993pt{\rm E}W_{1}(\mu,\hat{\mu}_{n})\lesssim n^{-1/s}$, which follows from Corollary 1 and Proposition 8.

For the second claim, we first note that by choosing $f(x)=c$ to be a constant function, we have

Since such an $f$ is Lipschitz, by choosing $c$ arbitrarily large we obtain that

unless $\sum_{i=1}^{n}\alpha_{i}=1$. It therefore suffices to prove the claim when $\sum_{i=1}^{n}\alpha_{i}=1$. In this case, setting

and again applying (1) yields that this claim is equivalent to the fact that $W_{1}(\mu,\nu)\gtrsim n^{-1/t}$. Since $\nu$ is supported on at most $n$ points, this follows from Corollary 2 and Proposition 8. ∎

2 k𝑘k-means clustering

on the basis of $n=C_{2}k^{2+\frac{4}{d}}$ samples. Corollary 2 implies that this dependence on $k$ is asymptotically optimal.

Our results show that a much simpler procedure suffices in high dimensions. As long as $d\geq 4$, the empirical measure $\hat{\mu}_{k}$ satisfies

for any $s>d$, and Proposition 20 then implies that

This shows that clustering a measure $\mu$ into $k$ pieces on the basis of $k$ i.i.d. samples from $\mu$ is asymptotically optimal, and enjoys concentration properties even better than the ones implied by [CR12].

Conclusion and Future Work

Our focus in this work has been to obtain sharper rates than previously available for the convergence of $\hat{\mu}_{n}$ to $\hat{\mu}$ in Wasserstein distance, both in asymptotic and finite-sample settings. Our results give theoretical support to a phenomenon observed in practice: even though $W_{p}(\mu,\hat{\mu}_{n})$ can converge very slowly for measures supported on a high-dimensional metric space, many measures arising in applications are intrinsically low dimensional, at least approximately, and therefore enjoy reasonably fast rates of convergence.

Our work leaves open whether slightly different versions of the Wasserstein distance can converge faster in general. Recently, a version of the Wasserstein distance with an entropic penalty has been proposed and shown to have attractive theoretical properties and practical performance [SdGP+15, Cut13, CDPS17, RCP16]. It is possible that these objects achieve better rates than the vanilla Wasserstein distance in the high-dimensional setting.

We also do not consider here empirical measures other than the simple $\hat{\mu}_{n}$. In practice, a technique known as importance sampling [Buc13] is often used to reduce the variance of estimates produced on the basis of random samples from a distribution. As noted in Section 7.1, if $\mu$ is sufficiently regular, then no discrete measure on $n$ points can achieve better asymptotic performance than the empirical measure $\hat{\mu}_{n}$. However, we conjecture that many reasonable sampling techniques should produce measures that are also asymptotically no worse than $\hat{\mu}_{n}$. We leave this question for future work.

Acknowledgments

We thank Guillaume Carlier, Marco Cuturi, and Gabriel Peyré for discussions related to this work. JW would like to thank FB for his hospitality at INRIA, where this research was conducted.

Appendix A Omitted proofs

We begin by giving an informal outline of the idea of the proof.

Consider a partition $\{Q_{i}\}_{i\in\mathcal{I}}$ of $X$, for some index set $\mathcal{I}$. The measures $\mu$ and $\nu$ both induce measures on each set in the partition. We will transport $\mu$ to $\nu$ by first moving mass between sets in this partition, and then moving mass within each set in the partition. If $\mu(Q_{i})\neq\nu(Q_{i})$ for one of the sets $Q_{i}$, we we need to transport an amount of mass equal to $|\mu(Q_{i})-\nu(Q_{i})|$ into or out of $Q_{i}$. In total, we can transport the mass that $\mu$ assigns to each set in the partition to its proper set under $\nu$ for a total cost of

where we use the fact that $\operatorname{diam}(S)\leq\operatorname{diam}(X)\leq 1$ by assumption.

After the first step of the transport plan, $\mu$ has been transported so that each set in the partition contains the correct total amount of mass. It therefore suffices in the second step to properly arrange the mass within each set. Moving the mass within $Q_{i}$ cannot cost more than $\operatorname{diam}(Q_{i})$, so the total cost of arranging the mass within each set is at most

We have obtained a transport of $\mu$ to $\nu$ for a total cost of approximately

This “single scale” bound is generally not tight, but a more refined bound can be obtained by applying the above argument recursively: instead of naively bounding the cost of moving the mass within $Q_{i}$ by the quantity $\operatorname{diam}(Q_{i})$, we can partition $Q_{i}$ into smaller sets and estimate the cost of moving the mass within $Q_{i}$ by first moving it between the sets of the partition before moving it within each smaller set. Iterating the argument $k^{*}$ times yields the bound.

We now show how to make the above argument precise. Given two measures $\mu$ and $\nu$ on $X$, write $\mathcal{C}(\mu,\nu)$ for the set of couplings between $\mu$ and $\nu$; that is, for the set of measures on $X\times X$ whose projection onto the first and second coordinate correspond to $\mu$ and $\nu$ respectively.

Fix a $k^{*}\geq 1$. We will define two sequences of measure $\pi_{k}$ and $\rho_{k}$ on $X$ for $1\leq k\leq k^{*}$ such that $\sum_{k=1}^{k^{*}}\pi_{k}\leq\mu$ and $\sum_{k=1}^{k^{*}}\rho_{k}\leq\nu$. Given such a sequence, we set $\mu_{1}=\mu$ and $\nu_{1}=\nu$ and write

Note that if $\gamma_{k}\in\mathcal{C}(\pi_{k},\rho_{k})$ for $1\leq k\leq k^{*}$ and $\gamma_{k^{*}+1}\in\mathcal{C}(\mu_{k^{*}+1},\nu_{k^{*}+1})$, then

Note that $0\leq\pi_{k}\leq\mu_{k}$ and $0\leq\rho_{k}\leq\nu_{k}$ for all $k$, hence $0\leq\mu_{k}\leq\mu$ and $0\leq\nu_{k}\leq\nu$ for all $k$ as well.

If $\alpha$ and $\beta$ are two measures on $X$ such that

We can now obtain the final bound. By Lemmas A.1 and A.2,

A.2 Proof of Proposition 2

We prove the inequalities in order. If $d<d_{H}(\mu)$, then by [Fal97, Proposition 10.3] there exists a compact set $K$ with positive mass and a $r_{0}>0$ such that

for all $r\leq r_{0}$ and all $x\in K$. (See also the proof of [GL07, Corollary 12.16].) Let $\tau<\mu(K)/2$. If $S$ is any set with $\mu(S)\geq 1-\tau$, then $\mu(S\cap K)>\mu(K)/2$. If $\mathcal{N}_{\varepsilon}(S)=N$, then in particular there exists a covering of $S\cap K$ by at most $N$ balls of radius $\varepsilon$ whose centers all lie in $K$. Indeed, any set of diameter at most $\varepsilon$ which intersects $S\cap K$ is contained in a ball of radius $\varepsilon$ whose center is in $K$. If $\varepsilon\leq r_{0}$, then each such ball satisfies $\mu(B(x,r))\leq\varepsilon^{d}$, so