Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation Peter Matthew Jacobs, Jeff M. Phillips Abstract Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size n n from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems ( d ∈ { 2 , 3 } ) \left(d\in\{2,3\}\right) , algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of n n and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to ε \varepsilon -additive error in expectation with respect to the sampling; we allow O ⁡ ( 1 ) O(1) computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under α \alpha -Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate W 2 2 ​ ( P , Q ) W_{2}^{2}(P,Q) within ε \varepsilon error in ε − max ⁡ ( 2 , d + 1 + o ⁡ ( 1 ) 1 + α ) \varepsilon^{-\max(2,\frac{d+1+o(1)}{1+\alpha})} time for 0 < α < 1 0<\alpha<1 Hölder smooth distributions P , Q P,Q on ( 0 , 1 ) d (0,1)^{d} ; an optimal Θ ⁡ ( ε − 2 ) \Theta(\varepsilon^{-2}) for α > 1 / 2 \alpha>1/2 when d = 2 d=2 and nearly optimal as α → 1 \alpha\to 1 when d = 3 d=3 . 1 Introduction In data analysis and machine learning tasks such as parameter estimation via Minimum Distance Estimation (see for example 4 ) or non-parametric two-sample hypothesis testing (see for example 18 ), require comparison of underlying unknown probability distributions P,Q\in\mathcal{P}(\mathbb{R}^{d}) . The squared Wasserstein distance, W_{2}^{2}(P,Q) , is one increasingly popular choice for this task. When P,Q are supported on \mathbb{R}^{d} with finite second moments it is defined as W_{2}^{2}(P,Q):=\inf_{\gamma\in\Pi(P,Q)}\mathbb{E}_{(X,Y)\sim\gamma}\|X-Y\|_{2}^{2}, where \Pi(P,Q) is the set of couplings of P,Q (joint distributions over \mathbb{R}^{d}\times\mathbb{R}^{d} with marginals P and Q respectively). A standard approach for estimating W_{2}^{2}(P,Q) is to collect n random samples from P and Q , construct empirical measures \hat{P}_{n},\hat{Q}_{n} , and use the plug-in estimator W_{2}^{2}(\hat{P}_{n},\hat{Q}_{n}) . When n is large this is computationally burdensome. The best known computational algorithm can estimate W_{2}^{2}(\hat{P}_{n},\hat{Q}_{n}) (even in the non uniformly discrete case) with additive error \varepsilon in runtime O(n\left(\frac{\Delta_{\infty}}{\varepsilon}\right)^{2}) ( 13 ) where \Delta_{\infty} is the maximum squared distance between pairs of points across the two point sets. In this paper we take the position that analysis should start with a distributional assumption on the input P,Q , and that it should aim for computationally efficient algorithms. While there is value in considering algorithms for computation of Wasserstein distance between discrete point sets (e.g., P_{n},Q_{n} of size n ), we argue that often P_{n} and Q_{n} should be considered as empirical measures from unknown distributions P,Q . This means that the target accuracy of computing W_{2}^{2}(P_{n},Q_{n}) should aim to match that induced by the sample. Finally, towards connecting this all together, we assume it takes O(1) time to create one additional sample from P or Q . The average loss of a randomized algorithm now takes into consideration both statistical error, and computational cost. A randomized algorithm in this context is a procedure \widehat{A} which takes as input a precision parameter \varepsilon , and randomly returns an output \hat{A}(\varepsilon) in time O(f(\varepsilon)) , which on average is \varepsilon close to W_{2}^{2}(P,Q) . We summarize this in the next definition. Definition 1.1 . (Computational-Statistical Runtime (CSR)) Suppose P and Q are two probability distributions on \mathbb{R}^{d} for which we can access random samples at O(1) cost each draw. We say a randomized algorithm \{\widehat{A}(\varepsilon)\mid\varepsilon>0\} achieves the O(f(\varepsilon)) Computational-Statistical Runtime if for every \varepsilon>0 , \widehat{A}(\varepsilon) has runtime O(f(\varepsilon)) and achieves \mathbb{E}|\widehat{A}(\varepsilon)-W_{2}^{2}(P,Q)|\leq\varepsilon where the expectation is with respect to all sources of randomness induced by the algorithm. Crucially, to achieve a CSR of O(f(\varepsilon)) , the algorithm itself must not only choose how to use samples, but also how many of them to gather in the first place. Ultimately, this aligns with the typical challenge faced by the practitioner: choosing an algorithm to estimate the underlying quantity (in this case W_{2}^{2}(P,Q) ) up to \varepsilon error while minimizing the time to do so, including the cost of collecting samples. Or alternatively, if one already has n samples P_{n},Q_{n} , this perspective advocates to treat them as estimates \hat{P}_{n},\hat{Q}_{n} of some unknown true distribution P,Q , and then the goal is to solve W_{2}^{2}(\hat{P}_{n},\hat{Q}_{n}) up to \varepsilon error, where \varepsilon is determined by \mathbb{E}|W_{2}^{2}(P,Q)-W_{2}^{2}(\hat{P}_{n},\hat{Q}_{n})|=\varepsilon . As error \varepsilon scales with the diameters of the supports of P and Q , in order to prove \varepsilon -additive error, we need an assumption that \Delta_{\infty}=\max_{x,x^{\prime}\in\mathsf{dom}(P)\cup\mathsf{dom}(Q)}\|x-x^{\prime}\|^{2} is bounded where \mathsf{dom}(P) denotes the support of the measure P . We henceforth assume the dimension d is constant, and P,Q are defined on [0,1]^{d} , so \Delta_{\infty}=O(1) . Alternatively, we could bound error in terms of \varepsilon\Delta_{\infty} . Table 1: \varepsilon -approximate W_{2}^{2} on [0,1]^{d} Ref. Notes \tilde{O}(\cdot) Time 12 uw n^{3} 1 uw,2d n^{3/2}/\varepsilon^{3/2} 2 n^{2}/\varepsilon^{2} 11 n^{5/2}/\varepsilon 13 n^{2}/\varepsilon + n/\varepsilon^{2} 13 2d n/\varepsilon^{2} 14 uw,2d n^{5/4}\,\mathrm{poly}(1/\varepsilon) Related Work. A long line of works focuses purely on the computational problem, exactly or \varepsilon -approximately, computing the W_{2}^{2} between discrete measures on [0,1]^{d} of size n ; see Table 1 . The Hungarian algorithm ( 12 ) achieves O(n^{3}) runtime in the case that the discrete measures are uniform. The unweighted ( uw ) matching problem was improved in \mathbb{R}^{2} ( 2d ) to \tilde{O}((n/\varepsilon)^{3/2}) by 1 and then \tilde{O}(n^{5/4}\mathsf{poly}(1/\varepsilon)) by 14 (where \tilde{O} denotes absorption of logarithmic factors in the asymptotic notation). For general W_{2}^{2} computation, the Greenkhorn algorithm was originally shown to achieve \tilde{O}(n^{2}/\varepsilon^{3}) ( 2 ) and then an improved analysis in 15 yielded \tilde{O}(n^{2}/\varepsilon^{2}) . 11 uses accelerated gradient descent which 15 shows achieves \tilde{O}(n^{5/2}/\varepsilon) . 15 separately provide an adaptive primal dual accelerated mirror descent algorithm achieving O(n^{2}\sqrt{\gamma}/\epsilon) where \gamma=O(n) , in line with the worst case bound of 11 . 13 then uses graph-scaling algorithms to achieve time O(n^{2}/\varepsilon+n/\varepsilon^{2}) for general Optimal Transport computation and which improves to \tilde{O}(n/\varepsilon^{2}) in \mathbb{R}^{2} . But these works do not address statistical accuracy for the underlying quantity W_{2}^{2}(P,Q) ; they assume the n locations signify ground truth. On the statistical side, the dyadic partitioning argument presented by 22 plus triangle inequality for W_{2} implies that when \hat{P}_{n} and \hat{Q}_{n} are empirical measures from P,Q respectively, \mathbb{E}|W_{2}^{2}(\hat{P}_{n},\hat{Q}_{n})-W_{2}^{2}(P,Q)| is O(n^{-1/4}) when d<4 and and \tilde{O}(n^{-1/d}) for d\geq 4 , (bounded \Delta_{\infty} allows to convert W_{2} closeness to W_{2}^{2} closeness). 9 improves upon this, showing that \mathbb{E}|W_{2}^{2}(\hat{P}_{n},\hat{Q}_{n})-W_{2}^{2}(P,Q)| is O(n^{-1/2}) when d<4 and \tilde{O}(n^{-2/d}) for d\geq 4 . Thus \varepsilon error needs n=\tilde{O}(1/\varepsilon^{\max(2,d/2)}) . Alternatives to the traditional empirical measure plug-in approach rely on Besov smoothness ( 16 ) of P,Q . For hardness results, 17 imply that the number of samples needed to estimate W_{2}^{2}(P,Q) up to \varepsilon in mean absolute error is \Omega(1/\varepsilon^{2}) . A simple, well-known (folklore) algorithm which achieves the CSR of O(1/\varepsilon^{2}) in the 1 dimensional case works by collecting n=1/\varepsilon^{2} , and then sorting the sample from P ( p_{(1)}1/2 in \mathbb{R}^{2} and and \varepsilon^{-2} in \mathbb{R}^{3} when \alpha\to 1 . Method Notes CSR in \mathbb{R}^{d} in \mathbb{R}^{2} in \mathbb{R}^{3} Sinkhorn 9 \varepsilon^{-(d^{\prime}+5.5)} \varepsilon^{-7.5} \varepsilon^{-7.5} SH + Richardson Extrap 9 \varepsilon^{-\frac{(d^{\prime}+11)}{2}} \varepsilon^{-6.5} \varepsilon^{-6.5} Entropic OT 9 \varepsilon^{-\max(6,d+2)} \varepsilon^{-6} \varepsilon^{-6} Empirical Plugin + 13 \varepsilon^{-(\max(d,4)+1-\mathbb{I}(d=2))} \varepsilon^{-4} \varepsilon^{-5} Our Result [Corollary 4.1.3 ] \varepsilon^{-\max(2,d+1)} \varepsilon^{-3} \varepsilon^{-4} Our Result [Theorem 4.1 ] \alpha -Höl \varepsilon^{-\max(2,\frac{d+1}{1+\alpha})} \varepsilon^{-2} \varepsilon^{-2} Contributions. We introduce what we call the Sample-Sketch-Solve paradigm for achieving fasts CSRs for W_{2}^{2}(P,Q) with P,Q supported on (0,1)^{d} , and the distributions possess Hölder smooth densities. The paradigm operates in three phases: (1) it samples n points from distributions P and Q ; (2) it sketches these samples into a compressed representation; and (3) it solves for the (approximately) optimal transportation plan on the compressed representation. In particular, our compressed representation is a regular Cartesian grid on [0,1]^{d} , with L divisions on each dimension. Each sample within a grid cell is mapped to the center so that there are \max(n,L^{d}) total atoms. We set L=\Theta(\varepsilon^{-\frac{1}{1+\alpha}}) when P and Q are \alpha -Hölder smooth. This regular grid structure is useful in two ways: for achieving a high level of precision in approximating W_{2}^{2}(P,Q) when P and Q are smooth using the sketched measures, and for efficiently solving for the Optimal Transport cost between the sketched measures. In Section 2 , we present new bounds on the error in approximating W_{2}^{2}(P,Q) between continuous probability distributions using this grid based discretization. We consider Holder smoothness constraints on the probability densities of P,Q , and rely on a novel, direct coupling based argument via a recent result of 10 on the regularity of the Brenier map. Still, our result here is not trivially obtainable using the triangle inequality, and is instead a result of a midpoint rule type cancellation of first order terms. Thus we crucially rely on mapping to the center point of the bounded diameter grid cells of our sketch. Then in Section 3 we outline a new approach for efficient exact computation of W_{2}^{2}(P,Q) that leverages (1) P,Q are supported on a regular grid with L splits per axis, and (2) each atom has normalized weight a multiple of 1/n . In this setting we can use the regular grid structure and the decomposable nature of W_{2}^{2} to leverage a result of 3 to transform the problem into a (d+1) -partite graph min-cost flow problem. Then given the control on the weights and the bounded grid structure, we control the capacities of this flow problem, and in turn apply a fast algorithm of 21 . This results in a L^{d+1+o(1)} exact algorithm for Wasserstein distance computation on our sketch. Finally, in Section 4 we put these pieces together, for \alpha -Hölder distributions, to obtain the O(1/\varepsilon^{2}) CSR algorithm for \varepsilon -additive error for W_{2}^{2}(P,Q) in \mathbb{R}^{2} when \alpha>1/2 , nearly O( 1/\varepsilon^{2}) in \mathbb{R}^{3} when \alpha\to 1 , and in general O(\varepsilon^{-\max(2,\frac{d+1+o(1)}{1+\alpha})}) in \mathbb{R}^{d} for 0<\alpha<1 ; we also separately analyze the general non-smooth case. Table 2 displays the CSRs for the general case and \alpha Hölder ( \alpha -Höl ) case. 1.1 Preliminaries For a function f:A\subseteq\mathbb{R}^{d}\to\mathbb{R}^{z} , |f|_{C^{0,\alpha}(A)}:=\sup_{x,y\in A,x\neq y}\frac{\|f(x)-f(y)\|}{\|x-y\|^{\alpha}} denotes the \alpha -Hölder semi-norm of f where 0<\alpha\leq 1 . When |f|_{C^{0,\alpha}(A)}<\infty , we call f \alpha -Hölder smooth ( 20 ; 19 ) . The higher the value of \alpha , the higher the level of smoothness. The \alpha=1 case is referred to as Lipchitz smoothness. Note that on bounded domains, by the Mean Value Theorem if f is differentiable with upper bounded derivative, it is Lipchitz smooth. For 0<\alpha\leq 1 , f\in C^{1,\alpha}(A) means f is differentiable and its gradient \nabla f is \alpha -Hölder smooth. When we say a probability distribution P supported on (0,1)^{d} is \alpha -Hölder smooth for some 0<\alpha\leq 1 , we mean it possesses a probability density function \mu which is \alpha -Hölder smooth on (0,1)^{d} . That is, for any Borel measurable subset of (0,1)^{d} , A , P(A)=\int_{x\in A}\mu(x)dx , and for some C>0 , |\mu|_{C^{0,\alpha}((0,1)^{d})}=\sup_{x,y\in(0,1)^{d},x\neq y}\frac{|\mu(x)-\mu(y)|}{\|x-y\|^{\alpha}}=C<\infty . We encapsulate these common parameterizations in the following assumption: Assumption 1.2 . P,Q are probability measures on (0,1)^{d} with densities \mu and \nu respectively satisfying for some C>1 and for some 0<\alpha<1 , 1. P and Q are \alpha -Hölder smooth: |\mu|_{C^{0,\alpha}((0,1)^{d})}+|\nu|_{C^{0,\alpha}((0,1)^{d})}\leq C 2. P and Q bounded above and below: C^{-1}\leq\mu(x),\nu(x)\leq C for x\in(0,1)^{d} When P,Q satisfy both parts of this assumption we say they are ( \alpha,C) -controlled . Gridding. Consider h>0 such that L=\frac{1}{h} is an integer, \mathcal{G}_{h} denotes the partition of (0,1)^{d} constructed by partitioning each axis into intervals of width h . Let \bar{G}^{d}_{h}\subset(0,1)^{d} be the 1/h^{d} points at the center of these grid cells. G_{h}:(0,1)^{d}\to\bar{G}_{h}^{d} is the function that projects a point to the center of the grid cell in \mathcal{G}_{h} containing it. Pushforward. If f:(0,1)^{d}\to Z for some set Z is a Borel measurable map, and P is a Borel probability measure on (0,1)^{d} , the notation f\#P denotes the pushforward . Specifically for measurable A\subseteq Z , f\#P(A)=P(x\in(0,1)^{d}:f(x)\in A) . \mathrm{Id}_{A} refers to the identity map defined on A . 2 Grid Based Discretization Error Bounds In this section we provide an improved upper bound on the error in approximating W_{2}^{2}(P,Q) by constructing discrete measures G_{h}\#P and G_{h}\#Q and using the plug-in approach W_{2}^{2}(G_{h}\#P,G_{h}\#Q) . Note that G_{h}\#P (resp. G_{h}\#Q ) are the measures constructed from P (resp. Q ) by collapsing all mass within each grid cell in each of the O(h^{d}) grid cells in \mathcal{G}_{h} onto the center of each cell. For Entropic Optimal transport this subject was addressed by 9 but the case with \lambda=0 (i.e no entropic regularization, which corresponds to W_{2}^{2} ) has not been considered. We show a continuum of approximation depending on the smoothness level of the probability measures P,Q . Our proof relies on regularity results guaranteeing the smoothness of the optimal transport map which deterministically pushes forward P into Q . We first remind the reader of the famous Theorem due to 5 guaranteeing the existence of such a map. Existing Result 2.1 ((Brenier) Theorem 1.16 of 8 ) . If P,Q are defined on \mathbb{R}^{d} with bounded second moments, and P possesses a probability density, then there exists a convex function u:\mathbb{R}^{d}\to\mathbb{R} and corresponding function Z:\mathbb{R}^{d}\to\mathbb{R}^{d}\times\mathbb{R}^{d} , defined by Z(x):=(x,\nabla u(x)) such that Z\#P is the unique coupling of P and Q achieving the infima in the definition of W_{2}^{2}(P,Q) . By Result 2.1 , (\nabla u)\#P=Q and T:=\nabla u is thus referred to as the optimal transport map. Note that by a change of measure (when Brenier’s Theorem applies), W_{2}^{2}(P,Q)=\int_{x\in\mathbb{R}^{d}}\|x-T(x)\|_{2}^{2}P(dx) . 6 ; 7 initiated the study of the regularity of the optimal transport map. We use a new contribution in transport map regularity theory due to 10 which establishes the global \alpha -Hölder smoothness of \nabla u when P and Q have \alpha -Hölder densities themselves. Existing Result 2.2 (Global Regularity of Brenier Map for Convex Domains via 10 Theorem 5.1) . Suppose P and Q satisfy Assumption 1.2 for some C>1 , 0<\alpha<1 . Then the convex functions u,v of Brenier’s Theorem satisfy u\in C^{1,1-\xi}((0,1)^{d}) and v\in C^{1,1-\xi}((0,1)^{d}) and |\nabla u|_{C^{0,1-\xi}((0,1)^{d})}+|\nabla v|_{C^{0,1-\xi}((0,1)^{d})}\leq M for any 0<\xi<1 where M depends only on d,\alpha,C,\xi . In particular the Optimal Transport maps \nabla u and \nabla v are (1-\xi) -Hölder continuous for any 0<\xi<1 . Before we proceed to the main result, we need a corollary. Corollary 2.2.1 . Let P,Q be (\alpha,C) -controlled for some C>1 and 0<\alpha<1 , with optimal transportation map T_{\mu} from P to Q (resp. T_{\nu} from Q to P ), and displacement function \ell_{\mu}(x)=x-T_{\mu}(x) (resp. \ell_{\nu}(x)=x-T_{\nu}(x)) . Then \|\ell_{\mu}(x)-\ell_{\mu}(G_{h}(x))\|\leq Kh^{1-\xi} (resp. \|\ell_{\nu}(x)-\ell_{\nu}(G_{h}(x))\|\leq Kh^{1-\xi} ) for any 0<\xi<1 , and where K is a constant that depends only on d , C,\alpha,\xi . Proof. Since P,Q are (\alpha,C) -controlled, Existing Result 2.2 holds. This means the OT map, T_{\mu} , (which is equivalently \nabla u where u is the convex function from Existing Result 2.2 ), is (1-\xi) -Hölder continuous for any 0<\xi<1 . Since the identity function, f(x)=x , is Lipchitz continuous, it is also (1-\xi) -Hölder continuous; also the sum of two (1-\xi) -Hölder continuous functions is also (1-\xi) -Hölder. Hence the difference between x and T_{\mu}(x) , \ell_{\mu}(x) , is (1-\xi) -Hölder for any \xi\in(0,1) . The argument is analogous for \ell_{\nu} . ∎ Now we state our main contribution of this section. Theorem 2.3 . If P and Q are (\alpha,C) -controlled (Assumption 1.2 ) for some C>1,0<\alpha<1 , then for some constant K depending only on d,C,\alpha , and every h>0 \left|W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\right|\leq Kh^{1+\alpha} Here we show the proof of the upper bound W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\leq Kh^{1+\alpha} . The argument for the lower bound W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\geq-Kh^{1+\alpha} is similar (see appendix Section A for complete details). In the argument below note that we repeatedly use the general constant K to indicate a constant depending only on d,C and \alpha . proof of upper bound. The proof will proceed in three phases. First, we will define a transportation plan \pi which couples G_{h}\#P with G_{h}\#Q and show it is indeed a valid coupling. Second, we will use this coupling to upper bound W_{2}^{2}(G_{h}\#P,G_{h}\#Q) by W_{2}^{2}(P,Q)+remainder . Third, we leverage properties of the scale of the grid cells, and the \alpha -Hölderness of both \mu,\nu and the Brenier maps’ to bound each term in the remainder by either either Kh^{2} or Kh^{1+\alpha} . Phase 1: Consider the probability measure \pi:=S\#\gamma where S:(0,1)^{d}\times(0,1)^{d}\to(0,1)^{d}\times(0,1)^{d} is defined as S(x,y)=(G_{h}(x),G_{h}(y)) and \gamma is an optimal coupling of P,Q under squared Euclidean cost. \pi projects the mass of \gamma onto the grid cell centers, and thus since \gamma couples P and Q , \pi is a valid coupling for G_{h}\#P_{\mu} and G_{h}\#P_{\nu} . We now formalize this by proving that the marginals are preserved. That is, for any A\subseteq(0,1)^{d} , \begin{split}\pi(A\times(0,1)^{d})&=\gamma(S^{-1}(A\times(0,1)^{d}))\\ &=\gamma((x,y)\in(0,1)^{2d}:x\in G_{h}^{-1}(A),y\in(0,1)^{d})\\ &=P(G_{h}^{-1}(A))=G_{h}\#P(A)\end{split} and similarly \pi((0,1)^{d}\times A)=G_{h}\#Q(A) . Phase 2: We can now state W_{2}^{2}(G_{h}\#P,G_{h}\#Q)\leq\mathbb{E}_{(X,Y)\sim\pi}\|X-Y\|_{2}^{2}=\int_{x\in(0,1)^{d},y\in(0,1)^{d}}\|G_{h}(x)-G_{h}(y)\|_{2}^{2}d\gamma(x,y). Applying Brenier’s theorem we can write \gamma=(\mathrm{Id}_{(0,1)^{d}},T_{\mu})\#P where T_{\mu} is the OT map (pushing P to Q ) and so the above integral upper bound becomes (after change of measure) W_{2}^{2}(G_{h}\#P,G_{h}\#Q)\leq\int_{x\in(0,1)^{d}}\|G_{h}(x)-G_{h}(T_{\mu}(x))\|_{2}^{2}\mu(x)dx. To isolate the contribution of W_{2}^{2}(P,Q) to the integral on RHS, we denote \Delta z=z-G_{h}(z) for z\in(0,1)^{d} so that G_{h}(x)-G_{h}(T_{\mu}(x))=\left(x-T_{\mu}(x)\right)-(\Delta x-\Delta T_{\mu}(x)). Thus using Brenier’s Theorem and expanding the square in the integral using the above identity, and using that W_{2}^{2}(P,Q)=\int_{x}(x-T_{\mu}(x))^{2}\mu(x)dx , we have W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\leq\int_{x}\|\Delta x-\Delta T_{\mu}(x)\|_{2}^{2}-2\langle x-T_{\mu}(x),\Delta x-\Delta T_{\mu}(x)\rangle\mu(x)dx. Phase 3: We will use three properties: [P1] For all x\in(0,1)^{d} , \|\Delta x\|_{2}=\|x-G_{h}(x)\|\leq\sqrt{d}h . [P2] The Brenier displacement \ell_{\mu}(x):=x-T_{\mu}(x) takes values in the bounded domain (-1,1)^{d} . [P3] Since P,Q are (\alpha,C) -controlled, by Corollary 2.2.1 , the Brenier displacement \ell_{\mu}(x)=x-T_{\mu}(x) satisfies \|\ell(x)-\ell(G_{h}(x))\|\leq Kh^{\alpha} (by setting \xi=1-\alpha ). [P4] Since P,Q are (\alpha,C) -controlled, \mu(x)\leq C=O(1) . Additionally, as \mu is \alpha -Hölder, |\mu(x)-\mu(G_{h}(x))|\leq Kh^{\alpha} . The first term in the remainder, \int_{x}\|\Delta x-\Delta T_{\mu}(x)\|_{2}^{2}dx , scales as Kh^{2} by triangle inequality yielding \|\Delta x-\Delta T_{\mu}(x)\|\leq\|\Delta x\|+\|\Delta T_{\mu}(x)\| and then application of [ P1 ]. We are left with W_{2}^{2}(G_{h}\#P_{\mu},G_{h}\#P_{\nu})-W_{2}^{2}(P_{\mu},P_{\nu})\leq Kh^{2}-2\int_{x\in(0,1)^{d}}\langle x-T_{\mu}(x),\Delta x-\Delta T_{\mu}(x)\rangle\mu(x)dx. (1) It remains to bound the absolute value of the remaining integral. We have \displaystyle|\int_{x}\langle x-T_{\mu}(x),\Delta x-\Delta T_{\mu}(x)\rangle\mu(x)dx| \displaystyle\leq \displaystyle|\int_{x}\langle x-T_{\mu}(x),\Delta x\rangle\mu(x)dx|+|\int_{x}\langle x-T_{\mu}(x),\Delta T_{\mu}(x)\rangle\mu(x)dx|. The second of these terms we can show is symmetric to the first by using from Brenier’s Theorem that the optimal coupling is unique. In particular, we can re-write \gamma=(\mathrm{Id}_{(0,1)^{d}},T_{\mu})\#P from above in the other direction as \gamma=(T_{\nu},\mathrm{Id}_{(0,1)^{d}})\#Q (where T_{\nu} is the OT map pushing Q to P ). Then we can rewrite this by first integrating over the coupling measure, and then swapping the direction: \displaystyle\int_{x\in(0,1)^{d}}\langle x-T_{\mu}(x),\Delta T_{\mu}(x)\rangle\mu(x)dx \displaystyle=\int_{(x,y)\in(0,1)^{d}\times(0,1)^{d}}\langle x-y,\Delta y\rangle d\gamma(x,y) \displaystyle=\int_{y\in(0,1)^{d}}\langle T_{\nu}(y)-y,\Delta y\rangle\nu(y)dy. Now the two terms we need to bound |\int_{x\in(0,1)^{d}}\langle x-T_{\mu}(x),\Delta x\rangle\mu(x)dx| and |\int_{y\in(0,1)^{d}}\langle T_{\nu}(y)-y,\Delta y\rangle\nu(y)dy| are symmetric to each other, and just show how to bound the first term. We arbitrarily label the cells C_{1},\dots,C_{(1/h)^{d}} (without loss of generality assuming 1/h is an integer), and the corresponding cell centers as c_{1},\dots,c_{(1/h)^{d}} . Observe that for every j , \int_{C_{j}}\langle\ell_{\mu}(c_{j}),x-c_{j}\rangle\mu(c_{j})=0 since C_{j} is the grid cell centered at c_{j} . We can now rewrite this first term, and subtract this 0 expression: \displaystyle|\int_{x\in(0,1)^{d}}\langle x-T_{\mu}(x),\Delta x\rangle\mu(x)|dx \displaystyle=\left|\int_{x\in(0,1)^{d}}\langle\ell_{\mu}(x),\Delta x\rangle\mu(x)dx-\int_{x\in(0,1)^{d}}\sum_{j}\mathbb{I}(x\in C_{j})\langle\ell_{\mu}(c_{j}),x-c_{j}\rangle\mu(c_{j})dx\right| \displaystyle\leq\sum_{j}\int_{x\in C_{j}}\left|\langle\ell_{\mu}(x),x-c_{j}\rangle\mu(x)-\langle\ell_{\mu}(c_{j}),x-c_{j}\rangle\mu(c_{j})\right|dx (by Tri Ineq) \displaystyle\leq\sum_{j}\int_{x\in C_{j}}|\langle\ell_{\mu}(x),x-c_{j}\rangle\mu(x)-\langle\ell_{\mu}(x),x-c_{j}\rangle\mu(c_{j})+\langle\ell_{\mu}(x),x-c_{j}\rangle\mu(c_{j})-\langle\ell_{\mu}(c_{j}),x-c_{j}\rangle\mu(c_{j})|dx by \pm\langle\ell_{\mu}(x),x-c_{j}\rangle\mu(c_{j}) \displaystyle\leq\sum_{j}\int_{C_{j}}|\langle\ell_{\mu}(x),x-c_{j}\rangle(\mu(x)-\mu(c_{j}))|dx+\int_{C_{j}}|\langle\ell_{\mu}(x)-\ell_{\mu}(c_{j}),x-c_{j}\rangle\mu(c_{j})|dx by Tri Ineq \displaystyle\leq\sum_{j}\int_{C_{j}}\|\ell_{\mu}(x)\|_{2}\|x-c_{j}\|_{2}|\mu(x)-\mu(c_{j})|dx+\int_{C_{j}}\|\ell_{\mu}(x)-\ell_{\mu}(c_{j})\|_{2}\|x-c_{j}\|_{2}|\mu(c_{j})|dx by Cauchy-Schwarz \displaystyle\leq K\left(\sum_{j}\int_{C_{j}}h|\mu(x)-\mu(c_{j})|dx+\int_{C_{j}}h\|\ell_{\mu}(x)-\ell_{\mu}(c_{j})\|dx\right) by [ P2 ] and [ P4 ] \displaystyle\leq K\sum_{j}Vol(C_{j})h^{1+\alpha}=Kh^{1+\alpha} by [ P3 ] and [ P4 ] Thus |\int_{x\in(0,1)^{d}}\langle x-T_{\mu}(x),\Delta(x)\rangle\mu(x)dx|\leq Kh^{1+\alpha} . An analagous argument yields |\int_{y\in(0,1)^{d}}\langle T_{\nu}(y)-y,\Delta y\rangle\nu(y)dy|\leq Kh^{1+\alpha} . The upper bound W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\leq Kh^{1+\alpha} follows from these and Equation 1 . ∎ Just by using that |x-y|\leq\frac{|x^{2}-y^{2}|}{x+y} , we additionally have the following Lemma. Lemma 2.4 . Assuming P,Q are (\alpha,C) -controlled for some C>1 and 0<\alpha<1 and W_{2}(P,Q)>\varepsilon>0 then for some constant K depending only on d,c,\alpha and every h>0 , \left|W_{2}(G_{h}\#P,G_{h}\#Q)-W_{2}(P,Q)\right|\leq\frac{Kh^{1+\alpha}}{\varepsilon} Proof. Using Theorem 2.3 |W_{2}(G_{h}\#P,G_{h}\#Q)-W_{2}(P,Q)|\leq\frac{|W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)|}{W_{2}(G_{h}\#P,G_{h}\#Q)+W_{2}(P,Q)}\leq\frac{Kh^{1+\alpha}}{\varepsilon} ∎ 2.1 Non-Smooth Case Note that the \alpha\to 0 bound of O(h) holds for any distributions P and Q , regardless of their level of smoothness. We prove this below. Lemma 2.5 . If P and Q are probability measures on (0,1)^{d} , then for h>0 |W_{2}(G_{h}\#P,G_{h}\#Q)-W_{2}(P,Q)|\leq h\left(2\sqrt{d}\right). Proof. Let \pi_{P}=(\mathrm{Id}_{(0,1)^{d}},G_{h})\#P and \pi_{Q}=(\mathrm{Id}_{(0,1)^{d}},G_{h})\#Q . Then \pi_{P} is a coupling of P and G_{h}\#P and \pi_{Q} is a coupling of Q and G_{h}\#Q . Using a change of measure we thus have W_{2}^{2}(G_{h}\#P,P)\leq\int_{x\in(0,1)^{d}}\|x-G_{h}(x)\|_{2}^{2}P(dx)=\sum_{j}\int_{x\in C_{j}}\|x-c_{j}\|_{2}^{2}P(dx)\leq dh^{2} , and likewise W_{2}^{2}(G_{h}\#Q,Q)\leq dh^{2} . By triangle inequality for W_{2} the result follows. ∎ It is not hard to show that W_{2}(G_{h}\#P,P)=\Theta(h) when P is for example the uniform distribution on (0,1)^{d} . And thus the brute force best bound one can obtain using the triangle inequality for W_{2} is \left|W_{2}(G_{h}\#P,G_{h}\#Q)-W_{2}(P,Q)\right|=O(h). 3 Efficient Exact Computation on a Regular Grid In this section we isolate a structured regime in which the squared Wasserstein distance admits a substantially faster exact algorithm. Let L,k\in\mathbb{N} , and recall that \bar{G}_{1/L}^{d} are the centers of a regular grid on (0,1)^{d} . Let P=\sum_{x\in\bar{G}^{d}_{1/L}}p_{x}\,\delta_{x},\qquad Q=\sum_{x\in\bar{G}^{d}_{1/L}}q_{x}\,\delta_{x} be probability measures supported on \bar{G}^{d}_{1/L} , with p_{x},q_{x}\in\frac{1}{k}\mathbb{Z}_{\geq 0} for every grid point x . After aggregating repeated support points, the input can be viewed as a pair of d -dimensional histograms on regular L^{d} axis-aligned bins of (0,1)^{d} . The squared Euclidean ground cost is separable on this grid. Indeed, if x=\left(\frac{2a_{1}+1}{2L},\ldots,\frac{2a_{d}+1}{2L}\right),\qquad y=\left(\frac{2b_{1}+1}{2L},\ldots,\frac{2b_{d}+1}{2L}\right), with a_{1},\ldots,a_{d},b_{1},\ldots,b_{d}\in\{0,1,\ldots,L-1\} , then \|x-y\|_{2}^{2}=\frac{1}{L^{2}}\sum_{\ell=1}^{d}(a_{\ell}-b_{\ell})^{2}. Therefore the cost has the separable form required by the exact reduction of 3 , which maps optimal transport between d -dimensional histograms with separable ground cost to an equivalent uncapacitated minimum-cost flow problem on a (d+1) -partite graph. Instantiating their construction with L^{d} histogram bins yields a graph with (d+1)L^{d} vertices and m:=dL^{d+1} arcs. Theorem 3.1 . Assume L,k\in\mathbb{N} . Let P and Q be probability measures supported on the cell-center grid \bar{G}^{d}_{1/L}\subset[0,1]^{d} and assume every mass is an integer multiple of 1/k . Then W^{2}_{2}(P,Q) , for every fixed dimension d , can be computed exactly in time (dL^{d+1})^{1+o(1)}\log L\,\log k. For for every fixed dimension d , this is \tilde{O}(L^{d+1+o(1)}) where \tilde{O}(\cdot) hides logarithmic factors of L,k . Proof. By the exact reduction of 3 , it suffices to solve the resulting uncapacitated minimum-cost flow instance on a (d+1) -partite graph with m=dL^{d+1} arcs. In this reduction, each arc cost is one coordinate contribution to the squared Euclidean cost, hence is of the form \frac{(a_{\ell}-b_{\ell})^{2}}{L^{2}} for some coordinate index \ell and some integers a_{\ell},b_{\ell}\in\{0,1,\ldots,L-1\} . Therefore every arc cost is a multiple of 1/L^{2} . Next scale every supply and demand by k . Because each histogram mass lies in \frac{1}{k}\mathbb{Z}_{\geq 0} , all node imbalances become integral; moreover, since P and Q are probability measures, the total amount of flow becomes exactly k . Now also scale every arc cost by L^{2} . After this rescaling, all costs become integral, and every cost is at most \max_{0\leq a_{\ell},b_{\ell}\leq L-1}(a_{\ell}-b_{\ell})^{2}\leq(L-1)^{2}1,0<\alpha<1 ) on (0,1)^{d} , for which we can draw random samples in O(1) time each. For constant dimension d and \varepsilon>0 , we can compute \hat{A}(\varepsilon) so that in expectation |\hat{A}(\varepsilon)-W_{2}^{2}(P,Q)|\leq\varepsilon , in time \tilde{O}((1/\varepsilon)^{\max\left(2,\frac{d+1+o(1)}{1+\alpha}\right)}). Proof. The proof follows the three phases of the sample-sketch-solve paradigm. We start by sampling n=O(1/\varepsilon^{\max(2,d/2)}) samples from both P and Q to produce discrete measures \hat{P}_{n},\hat{Q}_{n} , respectively. Next we apply a grid-based discretization with an edge length h=O(\varepsilon^{\frac{1}{1+\alpha}}) to obtain G_{h}\#\hat{P}_{n} and G_{h}\#\hat{Q}_{n} . By Theorem 2.3 we have |W^{2}_{2}(P,Q)-W^{2}_{2}(G_{h}\#P,G_{h}\#Q)|\leq Kh^{1+\alpha}=\varepsilon/2 . Since G_{h}\#\hat{P}_{n} is an empirical measure of n independent samples of G_{h}\#P and G_{h}\#\hat{Q}_{n} is an empirical measure of n independent samples of G_{h}\#Q , by 9 Theorem 2 we have \mathbb{E}|W^{2}_{2}(G_{h}\#P,G_{h}\#Q)-W^{2}_{2}(G_{h}\#\hat{P}_{n},G_{h}\#\hat{Q}_{n})|\leq\varepsilon/2 where the expectation is with respect to the sampling from P and Q . Thus with \hat{A}(\varepsilon):=W_{2}^{2}(G_{h}\#\hat{P}_{n},G_{h}\#\hat{Q}_{n}) and applying triangle inequality, \displaystyle\mathbb{E}|W_{2}^{2}(P,Q)-\hat{A}(\varepsilon)| \displaystyle= \displaystyle\mathbb{E}|W^{2}_{2}(P,Q)-W^{2}_{2}(G_{h}\#\hat{P}_{n},G_{h}\#\hat{Q}_{n})| \displaystyle\leq \displaystyle|W^{2}_{2}(P,Q)-W^{2}_{2}(G_{h}\#P,G_{h}\#Q)|+\mathbb{E}|W^{2}_{2}(G_{h}\#P,G_{h}\#Q)-W^{2}_{2}(G_{h}\#\hat{P}_{n},G_{h}\#\hat{Q}_{n})| \displaystyle\leq\varepsilon. Finally, now the distributions G_{h}\#\hat{P}_{n},G_{h}\#\hat{Q}_{n} lie on a regular Cartesian grid \bar{G}^{d}_{1/L} with L=1/h=O(1/\varepsilon^{1/(1+\alpha)}) and each atom has mass that is an integer multiple of 1/n with n=O(1/\varepsilon^{\max(2,d/2)}) . Thus we can invoke Theorem 3.1 to exactly compute W_{2}^{2}(G_{h}\#\hat{P}_{n},G_{h}\#\hat{Q}_{n}) in L^{d+1+o(1)}\log n=1/\varepsilon^{(d+1+o(1))/(1+\alpha)} time. Adding in the \tilde{O}(1/\varepsilon^{\max(2,d/2)}) time for n samples completes the proof. ∎ We now provide the following corollaries about how this analysis is exactly or nearly optimal for d=2,3 dimensions. Corollary 4.1.1 . Let P and Q be (\alpha,C) -controlled distributions on (0,1)^{d} for d=2 , for which we can draw random samples in O(1) time each. For \alpha>1/2 and \varepsilon>0 , we can compute \hat{A}(\varepsilon) so that in expectation |\hat{A}(\varepsilon)-W_{2}^{2}(P,Q)|\leq\varepsilon , in time \tilde{O}(1/\varepsilon^{2}) . Corollary 4.1.2 . Let P and Q be (\alpha,C) -controlled distributions on (0,1)^{d} for d=3 , for which we can draw random samples in O(1) time each. For \varepsilon>0 , we can compute \hat{A}(\varepsilon) so that in expectation |\hat{A}(\varepsilon)-W_{2}^{2}(P,Q)|\leq\varepsilon , in time \varepsilon^{-\frac{4+o(1)}{1+\alpha}} , which approaches \varepsilon^{-(2+o(1))} as \alpha\to 1 . 4.1 Non-Smooth Case When we do not have a bound on the smoothness of P,Q , then we can use Lemma 2.5 , and as a result Theorem 4.1 behaves as with \alpha=0 with a CSR of \varepsilon^{-\max(2,d+1+o(1))} . Corollary 4.1.3 . Let P and Q be distributions on (0,1)^{d} , for which we can draw random samples in O(1) time each. For constant dimension d and \varepsilon>0 , we can compute \hat{A}(\varepsilon) so that in expectation |\hat{A}(\varepsilon)-W_{2}^{2}(P,Q)|\leq\varepsilon , in time \tilde{O}(\varepsilon^{-\max\!\big(2,\;d+1+o(1)\big)}). For d=2 the CSR is 1/\varepsilon^{3+o(1)} and for d=3 it is 1/\varepsilon^{4+o(1)} . Appendix A Discretization Error for W_{2}^{2} In this section we prove the following theorem: See 2.3 In the main body of the paper, we already proved the upper bound W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\leq Kh^{1+\alpha}. It remains to prove the corresponding lower bound W_{2}^{2}(G_{h}\#P,G_{h}\#Q)-W_{2}^{2}(P,Q)\geq-Kh^{1+\alpha}, and we take this up in the next Subsection. A.1 Proof of Discretization Error Lower Bound As we did in the upper bound proof, we continue to assume without loss of generality that \frac{1}{h} is an integer. Lemma A.1 (Discretization Error Lower Bound) . If P and Q are (\alpha,C) controlled (Assumption 1.2 ) for some C>1 , 0<\alpha<1 , then for some constant K depending only on d,C,\alpha , and every h>0 , W_{2}^{2}(P,Q)\leq W_{2}^{2}(G_{h}\#P,G_{h}\#Q)+Kh^{1+\alpha}. Note that the below argument only relies on smoothness of the densities, not at all on the transport maps. Existing Result 2.2 , which guarantees the smoothness of the transport maps, uses that the densities are bounded below. Since we do not use transport map smoothness in the lower bound argument, we do not need the densities to be bounded below. In particular, only for the sake of consistency with the assumption of the upper bound does Theorem A.1 say P,Q are (\alpha,C) controlled. This is stronger than what is nescessary for the lower bound argument. The lower bound argument uses only the smoothness of the density \mu associated to P and \nu associated to Q . This argument has a similar flavor to the upper bound argument. We find a coupling for P and Q , call it \Gamma , derived from an optimal coupling \pi^{*} for G_{h}P and G_{h}Q . Then we extract the cost W_{2}^{2}(G_{h}\#P,G_{h}\#Q) from the cost of \Gamma , and upper bound the leftover quantity utilizing the smoothness of the densities. Proof. Let \pi^{*} be an optimal coupling between the discrete measures G_{h}\#P and G_{h}\#Q . We define a probability measure \Gamma on (0,1)^{2d} by defining the probability density function \gamma:(0,1)^{2d}\to\mathbb{R} as \gamma(x,y)=\sum_{i}\sum_{j}\mathbb{I}(x\in C_{i})\mathbb{I}(y\in C_{j})\frac{\pi^{*}\left(c_{i},c_{j}\right)}{P(C_{i})Q(C_{j})}\mu(x)\nu(y). (2) and setting, for A\subseteq(0,1)^{2d} , \Gamma(A)=\int_{(x,y)\in A}\gamma(x,y)d(x,y) . Within C_{i}\times C_{j} , \Gamma retains the shape of the independent coupling P\times Q , but rescales the measure to be the amount of measure transferred between the center of C_{i} and C_{j} under the optimal coupling between the measures snapped onto the grid cell centers. We now show \Gamma is indeed a coupling of P and Q , and then we extract the quantity W_{2}^{2}(G_{h}\#P,G_{h}\#Q) from the cost of \Gamma . But first, note that \begin{split}\int_{(x,y)\in(0,1)^{2d}}\gamma(x,y)d(x,y)&=\int_{x\in(0,1)^{d}}\int_{y\in(0,1)^{d}}\gamma(x,y)dydx=\\ &=\sum_{i}\sum_{j}\int_{x\in C_{i}}\int_{y\in C_{j}}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\mu(x)\nu(y)dydx\\ &=\sum_{i}\sum_{j}\pi^{*}(c_{i},c_{j})\\ &=1.\end{split} (3) where in the last inequality we used that \pi^{*} is a probabilty measure supported on (c_{i})_{i\in h^{d}}\times(c_{j})_{j\in h^{d}} . Thus \gamma is indeed a probability density on (0,1)^{2d} . Additionally, for A\subseteq(0,1)^{d} , we have that \begin{split}\Gamma(A\times(0,1)^{d})&=\sum_{i}\Gamma(\left(A\cap C_{i}\right)\times(0,1)^{d})\\ &=\sum_{i}\sum_{j}\int_{x\in A\cap C_{i}}\int_{y\in C_{j}}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\mu(x)\nu(y)dydx\\ &=\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}P(A\cap C_{i})Q(C_{j})\\ &=\sum_{i}\frac{P(A\cap C_{i})}{P(C_{i})}\sum_{j}\pi^{*}(c_{i},c_{j})\\ &=\sum_{i}\frac{P(A\cap C_{i})}{P(C_{i})}G_{h}\#P(c_{i})\\ &=\sum_{i}\frac{P(A\cap C_{i})}{P(C_{i})}P(C_{i})\\ &=P(A).\end{split} (4) where we used that \pi^{*} is a coupling between G_{h}\#P and G_{h}\#Q and then the definition of G_{h}\#P . By a symmetric argument, for A\subseteq(0,1)^{d} , \Gamma((0,1)^{d}\times A)=Q(A). In particular \Gamma is a coupling of P and Q . Thus we have that \begin{split}W_{2}^{2}(P,Q)\leq\int_{(x,y)\in(0,1)^{2d}}\|x-y\|_{2}^{2}\gamma(x,y)d(x,y)=&\\ \sum_{i}\sum_{j}\int_{x\in C_{i}}\int_{y\in C_{j}}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\|x-y\|_{2}^{2}\mu(x)\nu(y)dydx\end{split} (5) Now we extract the cost W_{2}^{2}(G_{h}\#P,G_{h}\#Q) from the cost of \Gamma . Using that for each i\in[(1/h)^{d}],j\in[(1/h)^{d}] , x,y\in(0,1)^{d} , x-y=(x-c_{i})+(c_{j}-y)+(c_{i}-c_{j}) , we have that \begin{split}\|x-y\|_{2}^{2}=\|x-c_{i}\|_{2}^{2}+\|c_{j}-y\|_{2}^{2}+\|c_{i}-c_{j}\|_{2}^{2}+2\langle x-c_{i},c_{j}-y\rangle+2\langle x-c_{i},c_{i}-c_{j}\rangle+&\\ 2\langle c_{j}-y,c_{i}-c_{j}\rangle.\end{split} (6) Expanding \|x-y\|_{2}^{2} in this way in equation 5 , we have that \begin{split}W_{2}^{2}(P,Q)\leq\sum_{i}\sum_{j}\int_{x\in C_{i}}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})}\|x-c_{i}\|_{2}^{2}\mu(x)dx+&\\ \sum_{i}\sum_{j}\int_{y\in C_{j}}\frac{\pi^{*}(c_{i},c_{j})}{Q(C_{j})}\|y-c_{j}\|_{2}^{2}\nu(y)dy+&\\ \sum_{i}\sum_{j}\pi^{*}(c_{i},c_{j})\|c_{i}-c_{j}\|_{2}^{2}+&\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle x-c_{i},c_{j}-y\rangle+\langle x-c_{i},c_{i}-c_{j}\rangle+\langle c_{j}-y,c_{i}-c_{j}\rangle\right)\mu(x)\nu(y)dydx.\end{split} (7) \|x-c_{i}\|_{2}^{2}\leq Kh^{2} for x\in C_{i} and likewise \|y-c_{j}\|_{2}^{2}\leq Kh^{2} for y\in C_{j} for general constant K depending only on d . Thus the total of the first two terms on the RHS of equation 7 is bounded by Kh^{2} . Since \pi^{*} is an optimal coupling between G_{h}\#P and G_{h}\#Q , the third term on RHS of equation 7 is exactly W_{2}^{2}(G_{h}\#P,G_{h}\#Q) . Thus we have that \begin{split}W_{2}^{2}(P,Q)\leq W_{2}^{2}(G_{h}\#P,G_{h}\#Q)+Kh^{2}+\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle x-c_{i},c_{j}-y\rangle+\langle x-c_{i},c_{i}-c_{j}\rangle+\langle c_{j}-y,c_{i}-c_{j}\rangle\right)\mu(x)\nu(y)dydx.\end{split} (8) By Cauchy-Schwarz, and again using that the diameter of C_{i},C_{j} is at most Kh , we have that \begin{split}\left|2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle x-c_{i},c_{j}-y\rangle\right)\right|\leq&\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\|x-c_{i}\|_{2}\|c_{j}-y\|_{2}\mu(x)\nu(y)dydx\leq&\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\left(\int_{x\in C_{i}}\|x-c_{i}\|_{2}\mu(x)dx\right)\left(\int_{y\in C_{j}}\|c_{j}-y\|_{2}\nu(y)dy\right)\leq&\\ Kh^{2}\sum_{i}\sum_{j}\pi^{*}(c_{i},c_{j})\leq&\\ Kh^{2}.\end{split} (9) By Equations 8 and 9 , we have that \begin{split}W_{2}^{2}(P,Q)\leq W_{2}^{2}(G_{h}\#P,G_{h}\#Q)+Kh^{2}+&\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle x-c_{i},c_{i}-c_{j}\rangle+\langle c_{j}-y,c_{i}-c_{j}\rangle\right)\mu(x)\nu(y)dydx.\end{split} (10) To handle the first remaining integrand, we express \mu(x)=\mu(x)-\mu(c_{i})+\mu(c_{i}) . Then we have that \begin{split}2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle x-c_{i},c_{i}-c_{j}\rangle\right)\mu(x)\nu(y)dydx=&\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})}\int_{x\in C_{i}}\langle x-c_{i},c_{i}-c_{j}\rangle\mu(c_{j})dx+&\\ 2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})}\int_{x\in C_{i}}\langle x-c_{i},c_{i}-c_{j}\rangle(\mu(x)-\mu(c_{i}))dx\end{split} (11) The first integrand above is zero due to symmetry of the linear term about c_{i} . The second term in absolute value is handled using Cauchy-Schwarz and the \alpha -Hölder continuity of \mu , yielding for this term an upper bound of Kh^{1+\alpha} where K depens only on d,C . Here we have used that \|c_{i}-c_{j}\|_{2} is upper bounded for all i,j by a constant depending only on d . Hence \left|2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle x-c_{i},c_{i}-c_{j}\rangle\right)\mu(x)\nu(y)dydx\right|\leq Kh^{1+\alpha}. By an analgous argument using the \alpha -H"older continuity of \nu , we have that \left|2\sum_{i}\sum_{j}\frac{\pi^{*}(c_{i},c_{j})}{P(C_{i})Q(C_{j})}\int_{x\in C_{i}}\int_{y\in C_{j}}\left(\langle c_{j}-y,c_{i}-c_{j}\rangle\right)\mu(x)\nu(y)dydx\right|\leq Kh^{1+\alpha}. Using these and Equation 10 , we conclude that for some K depending only d,C , W_{2}^{2}(P,Q)\leq W_{2}^{2}(G_{h}\#P,G_{h}\#Q)+Kh^{1+\alpha}. ∎ LLM Use Disclosure In addition to standard help with formatting or phrasing, we used LLM to search literature. This included the help in producing a complete related work, and contextualizing results. Crucially it also helped us identify the [ 3 ] paper which transforms the sketched representation into integral flow problem which can be solved efficiently. We of course reviewed all literature and techniques before integrating into the paper.