Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via  Barycentric Projections
Authors: NABARUN DEB
Promit Ghosal
Bodhisattva Sen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Discrete-discrete optimal transport
Kantorovich relaxation
Legendre-Fenchel dual
Semi-discrete Optimal Transport
Wasserstein barycenter
Wasserstein Distance.

Abstract: Optimal transport maps between two probability distributions $\mu$ and $\nu$ on $\R^d$ have found extensive applications in both machine learning and statistics. In practice, these maps need to be estimated from data sampled according to $\mu$ and $\nu$. Plug-in estimators are perhaps most popular in estimating transport  maps in the field of computational optimal transport. In this paper, we provide a comprehensive analysis of the rates of convergences for general plug-in estimators defined via barycentric projections. Our main contribution is a new stability estimate for barycentric projections which proceeds under minimal smoothness assumptions and can be used to analyze general plug-in estimators. We illustrate the usefulness of this stability estimate by first providing rates of convergence for the natural discrete-discrete and semi-discrete estimators of  optimal transport maps. We then use the same stability estimate to show that, under additional smoothness assumptions of Besov type or Sobolev type, wavelet based or kernel smoothed plug-in estimators respectively speed up the rates of convergence and significantly mitigate the curse of dimensionality suffered by the natural discrete-discrete/semi-discrete estimators. As a by-product of our analysis, we also obtain faster rates of convergence for plug-in estimators of $W_2(\mu,\nu)$, the Wasserstein distance between $\mu$ and $\nu$, under the aforementioned smoothness assumptions, thereby complementing recent results in Chizat et al. (2020). Finally, we illustrate the applicability of our results in obtaining rates of convergence for Wasserstein barycenters between two probability distributions and obtaining asymptotic detection thresholds for some recent optimal-transport based tests of independence. 

Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections
Nabarun Deb Columbia University
Promit Ghosal MIT
Bodhisattva Sen Columbia University
Abstract
Optimal transport maps between two probability distributions and Ted have found extensive applications both machine learning and statistics. In practice, these maps need to be estimated from data sampled according to μ and v. Plug- in estimators are perhaps most popular in estimating transport maps in the field of computational optimal transport. In this paper, we provide comprehensive analysis of the rates of convergences for general plug-in estimators defined via new stability estimate for
barycentric projections. Our main contribution barycentric projections which proceeds under minimal smoothness assumptions and can be used to analyze general plug-in estimators. We illustrate the usefulness of this stability estimate by first providing rates of convergence for the natural discrete- discrete and dini-eiseeete estimators optimal transport maps. We then use the same stability estimate to show that, under additional smoothness assumptions of Sobolev type or Besov type, kernel smoothed or wavelet based plug-in estimators respectively speed up the rates of convergence and significantly mitigate the curse dimensionality suffered by the natural discrete-discrrteesem---ieee As by-product of our analysis, we also obtain faster rates of convergence for plug-in in estimators of W2 (p,, 2)), the Wasserstein distance between f and 1/ under the aforementioned smoothness assumptions, thereby complementing recent results in Chizat et al. (2020). Finally, we illustrate the applicability of our results obtaining rates of convergence for Wasserstein barycenter between probability distributions and obtaining asymptotic detection thresholds for some recent optimal- transport based tests of independence.
estimators.
Introduction
Given two random variables X μr and Y v, where μ, v are probability measures on Rdd d > 1, the problem of finding "nice" map To(-) such that Tx(X) ~ has numerous applications
in machine learning such as domain adaptation and data integration 33
35
38
48
61
[12),
dimension reduction [12 66 900, generative models [60, 81 88 110), to name few. Of particular
interest is the case when To (.) is obtained by minimizing a cost function, a line work initiated by
Gaspard Monge [97] in 1781 (see (1.1) below), in which case (-(-) is termed an optimal transport (OT) map and has applications in shape matching/transte
problems 29 47 [07 [21], Bayesian statistics [46] 75 80 [08), econometrics [15 28 45 50 (54,, nonparametric statistical inference [39
113 [1:;; also see 1111 128 129 for book-length treatments on the subject. In this paper, we will focus the OT map obtained using the standard squared Euclidean cost function, i.e.,
To = argmin E
?
(1.I)
T:1 #μ=
where T#p = v/ means T(X) ~ 1/ for X ~ p. The estimation of To has attracted lot of interest in recent years due its myriad applications (as stated above) and interesting geometrical properties (see 19 (56] 91] and Definition [.I beloww. In practice, the main hurdle in constructing estimators for Tr is that the explicit forms of the measures (a, unknown; instead only random samples
X
Xm N
and Yi.... Yn
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

are available. A natural strategy in this scenario is to estimate To using Tm. where T Tm.n is computed as in (I.I) with μ and replaced by Pm and vn which are empirical approximations of μ and based on XI...., Xm and .I..... Yn respectively (see Definition 1.2). Such estimators are often called plug-in in estimators and have been used extensively; see
93 94 102 116).
The main goal of this paper is to study the rates of convergence of general plug-in estimators of To under unified framework. We show that when Pim and in, are chosen as fimm and 87 respectively, where um and Dn are the standard empirical distributions supported on m and n atoms, i.e.,
1
D : 1 Σ 5Y,
Pmn ==
5x.
and
(1.2)
Tm.x (appropriately defined using Definition 1.2) converges at a rate of m 2/4 + 12 2/4 for 2 4 in the sense of (L.8). This rate happens to be minimax optimal under minimal smoothness assumptions (see [72 Theorem 6]) but suffers from the curse of dimensionality. We next show that, if Ju and are known to admit sufficiently smooth densities, it is possible to apply kernel or wavelet based smoothing techniques on P... and 17 to obtain plug-in estimators that mitigate the aforementioned curse of dimensionality.
Our next contribution pertains to the estimation of W v) (the squared Wasserstein distance), see [.3p below, a quantity of independent interest in statistics and machine learning with applications
in structured prediction [51 [89). image analysis [8] 591 nonparametric testing [16 [06]. generative modeling [10, 196. etc. In this paper, we also obtain rates of convergence for plug-in estimators (m Pn) of W. (H, v/. We show that kernel smoothing An and f7 can be used to obtain plug-in in
estimators of W3 (1,, 2) that mitigate the curse of dimensionality
opposed
direct plug-in
approach using Pm and Dn (as used in 30 Theorem 2)). This provides an answer to the open question of estimating W2 (1, 2) when μ., admit smooth densities laid out in 30
1.1 Background on optimal transport
In this section, we present some basic concepts and results associated with the OT problem that will play crucial role in the sequel. Let (RR denote the of all Lebesgue absolutely continuous probability measures on dd and (2(I2)) be the set of probability measures with finite second moments. Then the 2- Wasserstein distance (squared) between μe, E (P( is defined as:
/ [s y|1 dm (x.
W = min
(1.3)
rell(u.))
where [1,,, v/) is the set of probability measures on Rd 1 with marginals and v. The optimization problem in (.3) is often called the Kantorovich relaxation (see (7)) of the optimization problem
in (I.1p. The existence of minimizer in (1.3 follows from [129. Theorem 4.
Proposition 1.1 (Brenier-McCamn polar factorization theorem, see 91 128).. Suppose μs E Pac (IRd). Then there exists p-a.e. (almost everywhere) unique function Tu(-) Rd - Rd,, which is the gradient of a real-valued d-variate convex function, say spo(-) Rdd - RR such that #o = V. Further, the distribution defined as (A x B) = p(An (To)- (B)) for all Borel sets A, C I2d is the unique minimizer 1.3 provided μ. V E (2(
Definition 1.1 (OT map and potential function). The function Ty Rd - Rd in Proposition 1.1 which satisfies To #o will be called the OT map from μ A convex function (pu(-) in Proposition 1.1 satisfying V = To will be termed an OT potential.
The next and final important ingredient is the alternate dual representation of (.3) which gives:
2 / ||=:|] dp(x)) + 2 [1/l1 du(y) - -min
1
2 W v)
Sar()), JEF
where
(1.4)
Sp,( = f dpp ddp+ S dv.
(1.5)
Here F denotes the space of convex functions on TRd which are also elements of L (n) and f*(() is the standard Feencdre-Feeccel dual defined as: I' (x:) = sup [y x [(v)),
for x E dom()).
(1.6)
yERd

---

1.2 Estimating OT map via barycentric projection
Recall the setting from the Introduction. Let pm Vn E P2 Here Jm, Vn need not be absolutely continuous and be very general. Intuitively, pm and inn be viewed some empirical approximation and v/ respectively.
Example 1.2 (Simple choices of jm and Vn), Let XI...., .. lid. and Yi..... Y t.i.d. ~ vi in which case a natural choice would be set Jmm = pm and Vn = =vn where Pm and Vn are the empirical distributions of XI...., Xm and Y,....,Y respectively, as defined in (1.2). . This is the standard choice adopted the discrete-discrete Kantorovich relaxation; see [704 Section 2.3].
Another popular choice is F'm Pmo Un
Fm μb Vn Vn. This is the semi-discrett Kantorovich problem and is popular when one of the measures is fully specified; see 55
natural way to estimate To(-), as defined (TI.. would be to approximate it using the OT map from i'mm Fzn However as Pm and Vn, may not be elements of Pac (IR),, Proposition 1.1 does not apply and an OT map may not exist from Pmm to 1/2. Such is the case in Example 1.2 in the
discrete-discrete case when m * n. To cireumvent this issue, leverage the notion of barycentric projections (see 3 Definition 5.4.2)) defined below:
Definition 1.2 (Barycentric projection). Define the set
x E Pa) fIl= dr dz. v).
F Tuin argmin
The optimization problem above the plug-in analog of the optimization problem on the right hand side of (I.3). Given any y E min define the barycentric projection of y as the conditional mean of given under y, i.e.
(m,n(x) = T7 (x) = Sy ydy(,, S, dr((x,))
for x E suupp (Jmm)
(1.7)
In general, I min need be a singleton which is why we index the barycentric projection Th (-) by I m'i.. Note that 77 (-) need not be transport map; however, if an OT map exists then it must be equal to T (-) (ae.a.e.). Our goal is to obtain stochastic upper bounds for
sup yE min
[ (x) To(x)]1 (x).
(1.8)
In addition, our proof techniques also yield rates of convergence for
W (Tm, D.)) - (2(
(1.9)
In this paper, we will focus on 2 2. Due to the canonical ordering of R, the case d = 1 can be handled easily using the classical Hungarian embedding theorem 82
1.3 Contributions
We provide new and flexible stability estimate Theorem 2.1 which yields a unified approach to obtaining rates of convergence for general plug-in estimators of the OT map To(-). Unlike existing stability estimates, Theorem Theorem[..Jholde holds for the barycentrie projection (which is the same as the OT map when it exists) and does not require any smoothness assumptions on fim V, or m (-); also see Remark 2.1 for comparison with the existing literature.
In Sections 2.1 and 2.2
we use Theorem 2.1 to bound (18 and [I.
In Section 2.1 we show that in both the discrete-discrete and cemi-discrete Kantorovich relaxation problems (see Example 1.2). the rate of convergence (1.8) is m -2dd + n 22dd for d > 4 when To is assumed to be Lipschitz (see Theorem 2.2). which is the minimax rate (see 72 Theorem 6)). To the best of our knowledge, rates of convergence for these natural estimators weren't previously established in the literature.

---

In Section 2.2 and Appendix A we show that the curse of dimensionality in the above rates can be mitigated provided μ and admit (uniform) Sobolev smooth densities (see Section 2.2) or Besov smooth densities (see Appendix Aj. In Section 2.2 our plug-in estimator is obtained by choosing jm (and Vn)) as the convolution of 7.mm (and vn) and smooth kernel with an
appropriate bandwidth. Under this choice, the rate of convergence in (T.8) is n - if 2ss 2 2 d, the rate of convergence becomes dimension-free and mitigates the curse of dimensionality. We also show the same rates of convergence mentioned above hold for (1.)) (see e.g., Proposition 2.6p which makes strong case in favor of incorporating smoothness the construction of plug-in estimators as was conjectured in 30). In Appendix A our plug-in estimator is obtained using natural wavelet based density estimators. The rate of
x
where denotes the degree of Sobolev smoothness (see Theorem 2.5 Clearly,
11e convergence in (1.8) turns out to be n 242z where 8 denotes the degree of Besov smoothness
(see Theorem A. Note that by choosing large enough, the exponent in the rate can be made arbitrarily close to 1/2, thereby reducing the curse of dimensionality.
3. In Section 2.3 we use discretization technique from [33 to construct discrete approximations to the smoothed ji and fn, from the previous paragraph that in turn yield computable plug-in estimators for To (provided one sample from Pm and 17,)) that also achieve the same statistical guarantees as the smoothed plug-in estimator from Section 2.2 (see Theorem 2.7). However the number of atoms required in the discretizations and correspondingly the computational complexity increases with the degree of smoothness; this highlights a statistical and computational trade-off.
4. We provide implications of our results in popular applications of OT such as estimating the barycenter of two multivariate probability distributions (see Theorem B.T in Appendix [B.T) and in nonparametric independence testing (see Theorem B.3 in Appendix B.2
1.4 Related work
Many recent works have focused on obtaining consistent estimators of To using the plug-in principle, see [26] [55] (in the semi- remi-discrete problem) and [41] 68 [32) (in the discrete-discret problem). In (55), the authors studied the rate of convergence of the cemi-diccrete optimal transport map from (absolutely continuous) to Pm This paper complements the aforementioned papers by studying the rates of convergence for general plug-in estimators
unified fashion. two other papers [9] Theorem 1.1] and 87, Section 4], the authors use a "Voronoi tessellation" approach to estimate To. however the rates obtained in this paper, even in the absence of smoothness, are strictly better than those in 19 87 Perhaps the most closely related paper to ours would be [67] In (67, the author uses variational techniques to arrive at stability estimates while we exploit the Lipschitz nature of the OT map (see Definition
I.1) Further the rates in this paper have exponents d A which are
strictly better than the exponents 2 obtained in 67 Proposition 1] under the same smoothness assumptions (Sobolev type of order s, see Definition 2.4 In another line of work [72] the authors use theoretical wavelet based estimators (not of the plug-in type) of To to obtain nearly minimax optimal rates of convergence. However these estimators, by themselves, are not transport maps between two probability measures, which makes them harder to interpret. In contrast, our focus is on obtaining rates of convergence for plug-in estimators, which are transport maps between natural approximations of and v. Such plug-in type strategies are lot more popular in computational 94 102 [16].
s+2
OT 30 67 93
In terms of obtaining rates of convergence for (1.9) some attempts include 109,116 where paramet- ric rates are obtained when μ,, v are known to finitely supported or are both Gaussian. In a related problem, bounds for W (pm (Fm ()) were obtained in 6 42
49 100 123 [3Л. Using these bounds,
for m = n. it is easy to get a n 1/d rate of convergence for (1.9) This rate was recently improved to n -2/d in 30 under no smoothness assumptions. Our rates coincide with the n 22/d rate from (30 under no smoothness assumptions. But further, show in this paper that the curse of dimensionality in the above rate can be mitigated by incorporating smoothness into the plug-in procedure.
2
Main results
Recall (o(-)) from Definition I.I
The following is our main result.

---

Theorem 2.1 (Stability estimate). Suppose that μ., E Pac (Ra) n P2(RR) and Nmm Un E P2( Assume that To(-) (as defined in (I.I) L-Lipschitz (L 0). Then.
/ /ITZ. (x) [ (m)(() S Liax / Wim on diis vtar
sup 7ET min
ve
Amm diin vstu)
+ +2L / vo(y) d(pn (w),
(2.1)
where v : To P8(.) is defined as in (16). and with S. (-) defined as in (.55) argmin jer fEF Spm.F (,), (f), V um vin ()) == argmin S
v pm Sr (-)
Dm who (f), and 'D denotes the space of real-
valued convex functions on IR
The proof of Theorem 2.1 (see Appendix C.1
starts along the same lines as the proof of the curvature
estimate in [56] Proposition 3.3]. This is followed by some careful manipulations of ( (,,-) (as
in (1.3p and an application of the conditional version of Jensen's 's inequality, see Cc.)) The final step
of the proof uses the dual representation in (1.) with techniques similar to some intermediate steps
in the proof of [92. Proposition 2] and 30 Lemma 3].
Remark 2.1 (Comparison with other stability estimates). Theorem 2.1 provides some important advantages to existing stability estimates in the literature. One of the earliest results in this direction can be found in (56 Proposition 3.3] but their bound involves push-forward constraint which makes it hard to use for rate of convergence analysis. A bound similar to Theorem 2.7 is presented in 155 Lemma 5.1] but there the authors assume the existence of an OT map from jmm to Vn. Therefore, it does not apply to the dixcrete-discrete problem where i'm F.m and V. Dr with & n. Overcoming all these limitations an important contribution of Theorem 2.7 and allows us to deal with popular plug-in estimators all in go. The stability estimate in [72] Proposition 10] on the other hand requires Jim Vn to be sufficiently smooth and hence it does not hold for discrete-discret or semi-discrete plug-in estimators (see Example] T.2). Further their result requires all the measures involved to be compactly supported unlike the much milder requirements of Theorem 2.1 However, shortcoming of Theorem 2. is that it is hard obtain rates faster than n n12 using it directly, whereas (72) can obtain rates arbitrarily close to n This is a price we pay for analyzing natural and popular plug-in estimators as opposed the (more intractable) wavelet based estimators [72].
Remark 2.2 (How to use Theorem 2.1 to obtain rates of convergence?). Note that the second term
on the right hand side of (2.I) under appropriate moment assumptions, is Op(m= - 112 + n -1/22 (free of dimension) by a direct application of Markov's 's inequality. We therefore focus on the first term. By 1.5).
T
p. ()), To
"i (.) E F. Further, by Caffarelli's regularity theory (20 depending
on the "smoothness" of Poms Uns it can be shown that there exists a further class of functions F. (see Remarks 2.3 and 2.6h such that V
am ()), V Tm (.) E F F.F.. Thus, we can bound the firsi term
on the right hand side of (2.I) as:
max / Wi di wid Wr
Hm. d(Fn -hhl
sup fEJNF, 1d -vhu
(2.2)
The right hand side of (2.2 can be bounded using the corresponding Dudley's 's entropy integral bounds using empirical process techniques; see (166) Lemmas 19.35-19.37].
To conclude, the two main steps in our strategy are identifying the family of functions F, and computing Dudley's entropy integral. Further, the more the smoothness of Tmm. V,, the smaller is the class of functions F, and smaller the supremum on the right hand side of (.2). This shows why better rates can be expected under smoothness assumptions.
2.1 Natural non-smooth plug-in estimators
In this case, discuss the rates of convergence for the discrete-discree problem and the semi- -ini-discrete problem, where no smoothness is available on jimm and 7n
Theorem 2.2. Suppose that Tol:) is L-p.hihci v compactly supported and E [exp([]|xx119)) < oo for some t > 0, a > 0.
5

---

(Discrete-discrete)) Set pm = mm and i/,, = Dr. Then the following holds:
/ | (x) TT(x))12 di ( (2) = Op (1/ (mmm,))) x (log (1 + maxfm, m))))mm)
sup Tef
(2.3)
mm1 1/2 + n11 m 1/2 log (1 + m) + n2 11/2 log (1 + n)
for d = 2,3,
(mm.))
where
r'
for d 4, for d 2 5,
(2.4)
m 22d + n2 22/d
and
(4x) (4x))+(44 ((2a: + 2da d) VO) for 4, for = 4, for d > 4.
tdaa" =
(a- V 7/22) -1
2(1 + +d=
The same bound holds for (Jhm, Pa) - W/2 (1,, v)l without assuming To(.) is Lipschitz. :Semi-discrete): Set Jim ,b, Vn in or Man Pms Vn u. Then the left hand side of 2.3 is (m.m)
Op(ra (n.a) x (log (1+ + n))44.))) ) or Op(ra (m(mmmmm) x (log (1+m)) respectively.
stronger result can be proved both p and v are compactly supported.
Corollary 2.3. Consider the setting from Theorem 2.2 and assume further that şa is compactly supported. Then, with r (m, defined as in (.4). we have:
/ / (x) T (x) < (r((m.)))
E
sup
LyET
for some constant 0, both the fiscrete-discres and semi-discrete settings from Theorem 2.2
brief description of the proof technique of Theorem 2.2 below, and the actual proof is presented in Appendix C.I
using Theorem 2.1 is provided in Remark 2.3
Remark 2.3 (Proof technique). The proof of Theorem 2.2 proceeds via the strategy outlined in Re- mark 2.2 We first show that F, (see Remark 2 can be chosen as a certain sub-class of convex functions which are in (v). We then use Dudley's entropy integral type bounds which in turn requires the bracketing entropy [226] Page 270] of Fa, recently proved in [83] Equation 26). This strategy is slightly different from that used in the proof of 130 Theorem 2]. where the authors assume that μt is compactly supported whereas we only assume the finiteness of E xx for some t 0, a O. The compactesss assumption μ allows one to further restrict F, the class of Lip- schitz functions. sehitzfunctions. This additional restriction does not seem to be immediate without the compactness assumption.
As discussed in Section 1.3 the exponents obtained in Theorem 2.2 are minimax optimal, up multiplicative logarithmic factors, under bare minimal smoothness assumptions (see [72] Theorem 6)). To the best of our knowledge, rates for the discrete-discrete case for m of and those for the semi-discrete case were not known previously in the literature. Our rates are also strictly better than those (for different estimators, based on space tessellations) obtained in 87 and require less stringent assumptions than those in [30]. In the next section, we show how smoothness assumptions can be leveraged to mitigate the curse of dimensionality in Theorem 2.2
2.2 Smooth kernel based plug-in estimator: mitigating the curse of dimensionality
In this section, we focus on kernel based density estimators for the probability densities associated with μ and v (see [57 58 99 103 (55.. We will show, using Theorem 2.1 that the corresponding estimators of (-) achieve (near) dimension-free rates under sufficient smoothness assumptions.
We first introduce the Sobolev class of functions which we will exploit in this subsection to construct estimators that achieve rates of convergence which mitigate the curse of dimensionality under sufficient smoothness.

---

Definition 2.4 (Uniform Sobolev class of functions). Let S S IR and f(-) be uniformly continuous on Ω and admits uniformly continuous derivatives up to order Q for some s E N. For any (m). ma) E No, let
0mh f
f.
For any k S 8, we further define,
Σ 110th (1)
Im|sk
The space (9)) is defined as the set of functions f(-) for which (I) < oc for all k S
For this subsection, assume that and y admit Sobolev smooth densities f.(() and fu(-) in the uniform norm (see Definition 2.4 above). Given & C Rd and N. let (*2 denote the set of Sobolev smooth functions on 52 of order s.
Assumption (A1) (Regularity of the densities). Suppose that
1. fu and fo are supported compact and convex subsets of R. say X and y respectively,
There exists s, . > such that fu(-) E (X; M) and fu(-) E ();; M) where (*;; M) the space of real valued functions supported on X such that for all f(-) E C* ; M), we have M- - fz) S M for all x E X and f| [o-(x) S M. Here (x))c=(()) the standard uniform Sobolev norm as defined in Definition 2.4 The space C); M) 3) is defined analogously.
We now define our estimators for f.(+) and fu(-) using the standard kernel density estimation technique (see 125 Section 1.2]). Set
m
(X Itm
Fu(x) = mhe
Σ Ka i=1
(2.5)
for some bandwidth parameter Am > and d-variate kernel Ka(-). We assume that Ka(-) is the fold product of univariate kernels, i.e., there exists kernel K(+) such that for == (WI...., Ud) E Rd. Ka(u)= = I K K(u)). We define (-) similarly with the same univariate kernel and bandwidth. Assumption (A2) (Regularity of the kernel). Assume that K() is symmetric, bounded, times differentiable kernel on Rd with all s + derivatives bounded and integrable. Further, suppose that (-)) of order 2s + 2, i.e.,
f u (()) du = 1(j = 0), for j
and / |1/22t22 K(u) du < co.
The above assumptions K-) are standard for estimating smooth densities and their derivatives of different orders in the kernel density estimation literature; see c.g. 57 588 69 [25]. There are
several natural ways to construct kernels satisfying Assumption (A2) see 125 Section 1.2.2]; an example is also provided in Example 2.4 below.
Example 2.4 (Example kernel satisfying Assumption (A2).. Let vm be the m-th Hermite polynomial IR (see (44). Then the kernel function defined as
2++2 K(u)
Σ
Um (0) exp(-u2/12 (0)))())))
satisfies Assumption (A2)
is evident from Assumption (A2) that K(-) may take some negative values. in which case, (-) (respectively fu(-)) may not be probability density. Consequently the barycentric projection (see Definition 1.2 between (-) and f-(-) is not well-defined. We get around this by projecting
7

---

fa(:) and f-) on an appropriate space of "smooth" probability densities (see (2.6). via an integral probability metric (see Definition b.5lbelow; also see [98 105 for examples, computational
procedures and applications of such metrics).
Definition 2.5 (Integral probability metric). Given class H of bounded functions IRd and two probability densities (.) and 92(.) on Rd, the integral probability metric/distance between 91 (-) and 92(-) with respect to H. defined as
/ MM))(())) - -2(())) dr
(gr 92: H); = sup +G)EN
Sufficient conditions on H. for :H) to be metric on the space of probability measures (not on the space of probability densities as they can be altered on set of Lebesgue measure O without altering the underlying probability measures) on R² have been discussed in [98]. Observe that the measure drr( (gr, 92: H) well defined even when gi(-) and g2(-) are not probability densities.
In Theorem 2.5 below, use H 2 N"). Note that any function in C (X, M²) can be extended to function in 2 M') (see f72) Theorem 23] and 1724 Theorem 1.105]). The fact that this choice of results in a metric follows from the argument
998 Page 8).
We are now in a position to describe the projection estimators for fx(+) and fx(),, and the rates achieved by the corresponding plug-in estimator.
Theorem 2.5. Assume that To(-) is L-Lipschitz and fp. fo are Lebesgue densities satisfying As-
sumption (AI) Also suppose that K-)) satisfies Assumption (A2) Define h. m
पोक log m
hn == n 4420 log n : [K(( du + Fix any M'
Consider any probability density
FM E (x;; (where M is defined as in Assumption (AI) which satisfies
dip (FW (FW fy: Cet (2))(()))) <
inf (X,TM) 120, f1=
(m.n) dip C + -d.
(2.6)
(m.a) is defined in 2.7 and dir(; (X; is the integral probability metric where dds defined in Definition| 2.5 We define FM' (-) analogously in (.6) with X, fy(:) replaced by Y, F.(.). Then the following conclusions hold.
1. Set M' = 8(1+TMM) if and Vn are the probability measures corresponding to the probability densities F.M (.) and Tad (-), then the following holds for some constant > 0:
/ [1iTAa To(x))12 (afz))?2mmmma (x) < Cr
(m.n)
E sup
LEE
m 1m2 + 11/2
for d < 2(s +2. 2).
where
d
(m.n).
m mm11/2 1/2 (log (1 m)) + 11/2 (log (1 + +)))
for d = 2(s +2), (2.7)
m - + n
++2
for d 2 +
The same bound also holds for E W2 (Am 1n)) (2(
2. f-)-) satisfies
lim max { (1 2 TM), n-000
sup (f)()) 2 )
(2.8)
xEX
for any E > 0, where L is any compact subset of X The same conclusion holds for Fa(() with x replaced by

---

In Theorem 2.5 we have shown that the plug-in estimator for Tb(-) using FM' (.) and for (-) (with M = 8(1= TM)) achieves rates that mitigate the curse of dimensionality under sufficient smoothness. In fact, fM (-) can be viewed
approximate minimizer of die (far: C over appropriate class of Sobolev smooth probability densities. This is carried out because fu() by itself may not probability density.
(X, M)))
Further note that Pm, n/ as specified in Theorem 2.5 are both smooth, and consequently i is a singleton and the supremum in Theorem 2.5 can be dropped. A brief description of the proof technique for Theorem 2.5 is presented in Remark 2.6 below and the actual proof is given in Appendix C.I
Remark 2.6 (Proof technique). The proof of Theorem 2.5 proceeds along the same lines as Re-
mark] 2.3 We first show that F. (see Remark 2.2) can be chosen as a certain subset of C (y+)))7). We then use Dudley's eniropy integral type bounds which in turn requires the bracketing entropy 126 Page 270] of the class of compactly supported Sobolev smooth functions which can be found in 127 Corollary 2.7.2].
We now explain the implications of both the parts of Theorem 2.5 in the following two remarks.
Remark 2.7 (Mitigating the curse of dimensionality). Theorem 2.5 shows that, under enough smoothness, iee, when 2(s + 2) > d, both the upper bounds for (18) and (.9) are Op(n-1/2 (1/2). This shows that, for large dimensions, provided j and admit smooth enough densities, it is possible to construct plug-in estimators that mitigate the curse of dimensionality. Note that similar estimator was analyzed in [67] Proposition 1] when m n.. However, the rates obtained in Theorem 2.3 are strictly better than those in 167 Proposition 1]. For m = n1 when 2(s + 2). 167 obtained rate of 2(++2)4d which worse than 1 obtained Theorem 2.5 For the other regimes, [67] obtains rates (up to log factors) of n -1/4 and n (142)a)2002))) which are both worse than the respective rates of n 1 and n - in Theorem 2.5
Remark 2.8 (Computational aspects of Theorem 2.5 Note that Fp (.) (with M'=
= 8(1 + TM))
hard to compute whereas (-)()) ) is computable easily linear time. Note that Fu(.) itself were probability density in (x;; TM), then we would have fa = FM'. establish that, does come close in part 2, from which we can easily derive the following:
= While Theorem 2.5 does not
lim P(F(() & C (X; = 00 72-000
The above shows that (2()) is indeed bounded below by (TM)-2 on X (any compact subset of the interior of X), and additionally belongs to C (Z²; TM) with probability converging to 1. This leads us conjecture that the natural density version of Tu(:), ie..
max (),(),
J max (x) dx.
should serve as a good proxy for F.M (-) and lead rates of convergence that mitigate the curse of dimensionality. From a computational perspective, the density specified above is easy to simulate from using an accept-reject algorithm without computing the integral in the denominator (see NTO Algorithm 4.31). However, our current proof technique does not provide rates of convergence for the above density estimator based on f.)()).
Another important implication of Theorem 2.5 is the bound obtained on [W2(Am, Vnn) W2(H, when μ * P. We first present the result and then describe the implication.
Proposition 2.6. Consider the setting in Theorem 2.5
Then, provided μ # v. the following holds:
W22 V.) W2(u, v))
Op(r.mmm)) (m.n)

---

Proposition 2 (see Appendix C.I for a proof) shows an interesting distinction between the + case and the μ case. For μ. v, the best possible exponent is n = for z 3 (see [31 Theorem 3] where the result was established under more general Besov smoothness assumptions).
On the contrary, when μA * v, Proposition 2.6 establishes a rate of n n for the Wasserstein distance which is strictly better than the minimax achievable rate mentioned above when μ = v. This observation complements (30 Corollary 1] where the authors make a similar remark for the special case of s = 0.
2.3 Discretized plug-in estimator under smoothness assumptions
In Section 2.T we discussed how smoothness can be incorporated into the plug-in procedure to get faster rates of convergence. Such plug-in estimators are popular in the computational OT literature (see 77 25 36)). However, even after (.) FM (-). f.(-) Fb (.) are calculated,
M,, as in Theorem 2.5 cannot be computed explicitly from data if [x(+) and [2()) are continuous
densities. This is contrast to T from Theorem 2.2 the discrete-discrete case which is explicitly computable using a standard linear program, but achieves worse rates of convergence. This is not unexpected. Thanks to the no free lunch principle, better statistical accuracy is naturally accompanied by heavier computational challenges. Therefore, under smoothness assumptions as in Section 2.2 which are computable in polynomial time (with complexity increasing with smoothness) provided (-(()) and (-) can be sampled from, and also attain rates that mitigate the curse of dimensionality.
goal here is to construct estimators,
Construction: We will illustrate the discretized estimator using the kernel based estimator from Sec- tion 2.2 Similar results also hold for the wavelet based estimator from Appendix A Recall the kernel density estimators (-) and (-) (see (266)) Sample M 2 raadom points from both (-) and f-). Let Mm, and Fn.M denote the standard empirical measures on the M points sampled from fa(()) and f.(-) respectively. Finally construct 7m,, = Thi,, as in Definition 1.2 with am 7.m, and in2 = Pr.M. It should be pointed out that a similar construction was also used in [I31 Section 6] for estimating probability densities under the Wasserstein loss. Based on this construction, the main result of this section is as follows:
Theorem 2.7. Consider the setting in Theorem 2.5 and the same construction of T above. For simplicity, let's 's also assume m = Accordingly set M = 2 Then I min is singleton and consequently the following conclusion holds for some constant C 0:
E [| - To(x)]l² dF (x)
< Cr
(n.))
The same rates also hold for TE (Tm; (n) Wz
The proof of Theorem 2.7 is given in Appendix C.1 Once the empirical measures Pm.M and
Un.M have been obtained, explicit computation of Tm,n as described above requires O(M*)
O(n 36642) steps using the Hungarian algorithm, see [73]. This highlights the statistical versus computational trade-off, i.e., in order to mitigate the curse of dimensionality in convergence rates by exploiting smoothness, the computational complexity gets progressively worse by polynomial factors n. should be mentioned that (approximate) algorithms faster than the Hungarian algorithm stated to name few. Due to space constraints, avoid detailed
above, can be found in [ 36 53 discussion on this.
In the above construction, sampling from the smoothed kernel densities Fz(-) and f.(()) is crucial. If we would simply draw M bootstrap samples from the empirical distributions Pmn. and D,,, the rates of convergence wouldn't 't improve from those observed in Theorem 2.2 no matter how large M is.
Acknowledgments and Disclosure of Funding
We would like to thank the reviewers for their constructive suggestions that greatly helped improve the quality of the paper. The third author is supported by NSF Grant DMS-2015376.
10

---

References
[1] Pankaj K Agarwal and R Sharathkumar. Approximation algorithms for bipartite matching with metric and geometric costs. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 555-564, 2014.
[2] Martial Agueh and Guillaume Carlier. Barycenters the wasserstein space. SIAM Journal on Mathematical Analysis, 43(2))904-922 2011.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows in metric spaces and in the space of probability measures. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, second edition, 2008
[4] Ery Arias-Castro, David Mason, and Bruno Pelletier. On the estimation of the gradient lines of a density and the consistency of the mean-shift algorithm. The Journal of Machine Learning Research, 17(1):1477-511, 2016.
[5] Arnab Auddy, Nabarun Deb, and Sagnik Nandy. Exact detection thresholds for chatterjee's correlation. arXiv preprini arXiv:2104.151 2021.
[6] Franck Barthe and Charles Bordenave. Combinatorial optimization over two random point sets. In Séminaire de Probabilités XLV, volume 2078 of Lecture Notes in Math., pages 483-535. Springer, Cham, 2013.
[7] Jean-David Benamou and Yann Brenier. A computational fluid mechanics solution to the monge-kantorovich mass transfer problem. Numerische Mathematik, 84(3):375-393, 2000.
[8] Jean-David Benamou, Brittany D Froese, and Adam M Oberman. Numerical solution of the optimal transportation problem using the monge-ampère equation. Journal of Computational Physics, 260:107-126, 2014.
[9] Robert.J J Berman. Convergence rates for discretized monge-ampère equations and quantitative stability of optimal transport. Foundations of Computational Mathematics, pages 1-42, 2020.
[10] Espen Bernton, Pierre Jacob, Mathieu Gerber, and Christian P Robert. Inference generative models using the Wasserstein distance. arXiv preprint arXiv: 17010000155550 1416, 188):9 2017.
[11] T. B. Berrett and R. Samworth. Nonparametric independence testing via mutual information. Biometrika, 106(3)5447-566, 2019.
[12] Jérémie Bigot, Raúl Gouet, Thierry Klein, Alfredo López, et al. Geodesic PCA in the Wasserstein space by convex PCA. Annales de l'Instilut Henri Poincaré, Probabilités et Statistiques, volume 53, pages 1-26. Institut Henri Poincaré, 2017.
[13] Jérémie Bigot, Raúl Gouet, Thierry Klein, Alfredo Lopez, al. Upper and lower risk bounds for estimating the wasserstein barycenter of random measures on the real line. Electronic journal of statistics, 12()):253--289,, 2018.
[14] Jérémie Bigot and Thierry Klein. Characterization of barycenters in the wasserstein space by averaging optimal transport maps. ESAIM: Probability and Statistics, 22:35-57, 2018.
[15] Adrien Blanchet and Guillaume Carlier. Optimal transport and cournot-nash equilibria, Math- ematics of Operations Research, 41(1):125-145, 2016.
[16] Melf Boeckel, Vladimir Spokoiny, and Alexandra Suvorikova. Multivariate brenier cumu- lative distribution functions and their application non non-parametric testing. arXiv preprint arXiv:1809.04000 040900 2018.
[17] Emmanuel Boissard, Thibaut Le Gouic, Jean Loubes, et al. Distribution's template estimate with wasserstein metrics. Bernoulli, 21(2):740-759, 2015.
[18] Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 20/ SIGGRAPH Asia Conference, pages 1-12, 2011.

---

[19] Yann Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math., 44(4)3375-477, 1991.
[20] Luis A. Caffarelli. Boundary regularity of maps with convex potentials. Comm. Pure Appl. Math.,
1992.
[21] Luis A. Caffarelli. The regularity of mappings with a convex potential. Amer. Math. Soc., 5(1):99-104, 1992.
[22] Luis A. Caffarelli. Boundary regularity of maps with convex potentials. II. Ann. of Math. (2), 144(3):453 496,,496,66. 1996.
[23] Guillaume Carlier and Ivar Ekeland. Matching for teams. Economic theory, 42(2):397-418. 2010.
[24] Guillaume Carlier, Adam Oberman, and Edouard Oudet. Numerical methods for matching for teams and wasserstein barycenters. ESAIM: Mathematical Modelling and Numerical Analysis, 49(6):1621-1642 2015.
[25] Rick Chartrand, Brendt Wohlberg, Kevin Vixie, and Erik Bollt. gradient descent solution to the kongeekantoroviic problem. Applied Mathematical Sciences, 3(22): 2009.
[26] Victor Chernozhukov, Alfred Galichon, Mare Hallin, and Mare Henry. Monge-Kantorovics depth, quantiles, ranks and signs. Ann. Statist., 45(1):223-256, 2017.
[27] Sinho Chewi, Tyler Maunu, Philippe Rigollet, and Austin J Stromme. Gradient descent algorithms for bures- wassertennnn barycenters. In Conference on Learning Theory, pages 1276-1304. PMLR, 2020.
[28] Pierre-André Chiappori, Robert McCann, and Lars P Nesheim. Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness. Economic Theory, 17 2010.
[29] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavve Xavier Vialard. Scaling algo- rithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563-
2609, 2018.
[30] Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xavia Vialard, and Gabriel Peyré. Faster Wasserstein distance estimation with the sinkhorn divergence. Advances in Neural Information Processing Systems, 33, 2020.
[31] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging Laheled and Unlabeled Data for Consistent Fair Binary Classification. In NeurlPS 20/9 33th Annual Conference on Neural Information Processing Systems, Vancouver, Canada, December 2019.
[32] Sebastian Claici, Edward Chien, and Justin Solomon. Stochastic wasserstein barycenters. In International Conference on Machine Learning, pages 999-1008. PMLR, 2018
[33] Albert Cohen. Numerical analysis of wavelet methods, volume of Studies in Mathematics and its Applications. North-Holland Publishing Co., Amsterdam, 2003.
[34] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribu- tion optimal transportation for domain adaptation. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 3733-3742. Curran Associates Inc., 2017.
[35] Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamoniy. Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 2016.
[36] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292- 22000, 2013.
12

---

[37] Marco Cuturi and Amaud Doucet. Fast computation of wasserstein barycenters, In Interna- tional conference on machine learning. pages 685-693 PMLR, 2014.
[38] Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: joint distribution optimal transport for unsupervised domain adaptation. In Proceedings of the European Conference on Computer Vision (ECCV), pages 447-464 2018.
[39] Nabarun Deb, Bhaswar B Bhattacharya, and Bodhisattva Sen. Efficiency lower bounds for distribution-fiee free hotelling-tyPe two-sample tests based on optimal transport. arXiv preprint 2XXi::214401186 2021.
[40] Nabarun Deb, Promit Ghosal, and Bodhisattva Sen. Measuring association on topological spaces using kernels and geometric graphs. arXiv preprint arXiv:2010.01768, 2020.
[41] Nabarun Deb and Bodhisattva Sen. Multivariate rank- distribution nonparametric testing using measure transportation. Journal of the American Statistical Association, (jstt accepted):1-45, 2021.
[42] Steffen Dereich, Michael Scheutzow, and Reik Schottstedt. Constructive quantization: approx- imation by empirical measures. Aun. Inst. Henri Poincaré Probab. Stat., 49(4):1183-12)) 2013.
[43] David L.. Donoho, lain M. Johnstone, Gérard Kerkyacharian, and Dominique Picard. Density estimation by wavelet thresholding. Ann. Statist., 24(2):508-539, 1996.
[44] Dominique Drouet Mari and Samuel Kotz. Correlation and dependence. Imperial College Press, London; distributed by World Scientific Publishing Co., Inc., River Edge, NJ, 2001.
[45] Ivar Ekeland, Alfred Galichon, and Marc Henry. Optimal transportation and the falsifiability of incompletely specified economic models. Economic Theory, 42(2))355-374, 2010.
[46] Tarek A El Moselhy and Youssef M Marzouk. Bayesian inference with optimal maps. Journal of Computational Physics, 231(23):7115-755 2012.
[47] Sira Ferradans, Nicolas Papadakis, Gabriel Peyré, and Jean-François Aujol. Regularized discrete optimal transport. SIAM Journal on Imaging Sciences, 733):1853-1822 2014.
[48] Aden Forrow, Jan-Christian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2465.. PMLR, 2019.
[49] Nicolas Fournier and Arnaud Guillin. On the rate convergence in Wasserstein distance of the empirical measure. Probab. Theory Related Fields, 162(3-4):707-738, 2015.
[50] Terry L Friesz and Enrique Fernandez. A model of optimal transport maintenance with demand responsiveness. Transportation Research Part Methodological, 13(4:3317-339 1979.
[51] Charlie Frogner. Chiyuan Zhang. Hossein Mobahi, Mauricio Araya-Polo, and Tomaso Poggio. Learning with a Wasserstein loss. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' page 2053-2061 Cambridge, MA, USA, 2015, MIT Press.
[52] Kenji Fukumizu, Bharath K Sriperumbudur, Arthur Gretton, and Bernhard Schölkopf. Charac- teristic kernels on groups and semigroups. In NIPS, pages 473-480, 2008
[53] Harold N Gabow and Robert E Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013-100 1989.
[54] Alfred Galichon. Optimal transport methods in economics. Princeton University Press, 2016.
[55] Promit Ghosal and Bodhisativa Sen. Multivariate ranks and quantiles using optimal transporta- tion and applications to goodness-of-fit testing. arXiv preprint arXiv: 1005:09000003400 2019.
13

---

[56] Nicola Gigli. On Hölder contiuuty-in-timee of the optimal transport map towards measures along curve. Proc. Edinb. Math. Soc. (2), 54(2):401-409, 2011.
[57] Evarist Giné and Richard Nickl. Uniform central limit theorems for kernel density estimators. Probab. Theory Related Fields, 141(3-4):333-88,, 2008.
[58] Evarist Giné and Richard Nickl. Mathematical foundations of infmiitedddmennionnal statistical models. Cambridge Series in Statistical and Probabilistic Mathematics, [40]. Cambridge University Press, New York, 2016.
[59] Joan Glaunes, Alain Trouvé, and Laurent Younes. Diffeomorphic matching of distributions: A new approach for unlabelled point-sets and sub-manifolds matching. Proceedings of the 2004 IEEE Computer Society Conference Computer Vision and Pattern Recognition, 2004. CVPR 2004., volume 2, pages II-II. IEEE, 2004.
[60] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Advances in Neural Information Processing Systems 27, pages 2672-2680, 2014.
[61] Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. Domain adaptation for object recognition: An unsupervised approach. In 20/1 International Conference on Computer Vision, pages 999-1006. IEEE, 2011.
[62] Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean-Michel Loubes. Obtaining faimness using optimal transport theory. In International Conference on Machine Learning, pages 2357-2365. PMLR, 2019.
[63] A. Gretton, R. Herbrich, A. Smola, O. Bousquet, and B. Schölkopf. Kernel methods for measuring independence. J. Much. Learn. Res., 6:2075-2129 (electronic), 2005.
[64] Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. In International conference on algorithmic learning theory, pages 63-77. Springer, 2005.
[65] Arthur Gretton, Kenji Fukumizu, Choon Hui Teo, Le Song, Bernhard Schölkopf, Alexander J Smola, et al. A kernel statistical test of independence. In Nips, volume 20, pages 585-592. Citeseer, 2007.
[66] Florian Gunsilius and Susanne M Schennach. Independent nonlinear component analysis. Technical report, cemmap working paper, 2019.
[67] Florian Gunsilius. the convergence rate of potentials of brenier maps. Econometric Theory, pages 2021.
[68] Mare Hallin, Eustasio Del Barrio, Juan Cuesta-Albertos, and Carlos Matrán. Distribution and quantile functions, ranks and signs in dimension d: A measure transportation approach. The Annals of Statistics, 1392))1139-1165, 2021.
[69] Bruce E. Hansen. Uniform convergence rates for kernel estimation with dependent data. Econometric Theory, 24(3):72--748, 2008
2008.
[70] Wolfgang Härdle, Gerard Kerkyacharian, Dominique Picard, and Alexander Tsybakov. Wavelets, approximation, and statistical applications, volume 129 of Lecture Notes in Statistics. Springer-Verlag, New York, 1998.
[71] Ruth Heller, Yair Heller, and Malka Gorfine. A consistent multivariate test of association based on ranks of distances. Biometrika, 100(2)503-510, 2013.
[72] Jan-Christian Hütter and Philippe Rigollet. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2): 106-1116611110 1194, 2021.
[73] Roy Jonker and Anton Volgenant. shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing. 38(4):325-340, 1987.
14

---

[74] Julie Josse and Susan Holmes. Measuring multivariate association and beyond. Stat. Surv., 10:132-167, 2016.
[75] Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabás Póczos, and Eric P. Xing. Neural architecture search with bayesian optimisation and optimal transport. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 2020-2029, Red Hook, NY. USA, 2018. Curran Associates Inc.
[76] L. V. Kantorovich, On a problem of Monge, Zap. Nauchn. Sem. S.-Peterburg. Oldel. Mat. Inst. Steklow. (POMT), 3 312or.... Predst. Din. Sist. Komb. i Algoritm. Metody. 11):15-16, 2004.
[77] L. Kantorovitch. On the translocation of masses. C. R. (Doklady) Acad. Sci. URSS (N.S.), 37:199-201, 1942.
[78] Kerkyacharian and D. Picard. Density estimation Besov spaces. Statist. Probab, Lett., 13(1):15-24, 1992.
[79] Ilmun Kim, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimality of permuta- tion tests. arXiv preprint arXiv:2003./3208, 2020.
[80] Sanggyun Kim, Rui Ma, Diego Mesa, and Todd P Coleman. Efficient bayesian inference methods via convex optimization and optimal transport. In 2013 IEEE International Symposium on Information Theory, pages 2259-2263. IEEE, 2013.
[81] Diederik P. Kingma and Max Welling. auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[82] J. Komlós, P. Major, and G. Tusnády. An approximation of partial sums of independent RV's, and the sample DF. II. Z. Wahhscheimlichkeesshhherre und Verw. Gebiete, 34(1):33-55 1976.
[83] Gil Kur, Fuchang Gao, Adityanand Guntuboyina, and Bodhisattva Sen. Convex regression in multidimensions: Suboptimality of least squares estimators. arXiv preprint arXiv:2006.02044, 2020.
[84] Pierre Simon Laplace. Théorie analytique des probabilités. Courcier, 1820.
[85] Thibaut Le Gouic and Jean-Michel Loubes. Existence and consistency of wasserstein barycen-
ters. Probability Theory and Related Fields, 168(3)9001-917, 2017.
[86] Tong Li and Ming Yuan. On the optimality of gaussian kernel based nonparametric tests against smooth alternatives. arXiv preprint
2019.
[87] Wenbo Li and Ricardo Nochetto. Quantitative stability and error estimates for optimal transport plans. IMA Journal of Numerical Analysis, 2020.
[88] Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In International Conference on Machine Learning, pages 1718-1727. PMLR, 2015.
[89] Giulia Luise, Alessandro Rudi, Massimiliano Pontil, and Carlo Ciliberto. Differential prop- erties of sinkhorn approximation for learning with Wasserstein distance. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 5864-5874, Red Hook, NY, USA, 2018. Curran Associates Inc
[90] Valentina Masarotto, Victor M Panaretos, and Yoav Zemel. Procrustes metrics covariance operators and optimal transportation of gaussian processes. Sankhyd A, 81(1):122-113, 2019.
[91] Robert J. McCann. Existence and uniqueness of monotone measure- maps. Duke Math. J., 80(2):309-323, 1995.
[92] Gonzalo Mena and Jonathan Viles-Weed Statistical bounds for entropic optimal transport: Sample complexity and the central limit theorem. Advances in Neural Information Processing Systems, 32, 2019.
15

---

[93] Quentin Mérigot. A multiscale approach to optimal transport. In Computer Graphics Forum, volume 30, pages 1583-1592. Wiley Online Library, 2011.
[94] Quentin Merigot and Boris Thibert. Optimal transport: discretization and algorithms. Hand- book of Numerical Analysis 22 Geometric PDES (arXiv preprini S.Xiv:2003.008555) 2020.
[95] Yves Meyer. Ondelettes opérateurs. I. Actualités Mathématiques. [Current Mathematical Topics]. Hermann, Paris, 1990. Ondelettes. [Wavelets].
[96] Shakir Mohamed and Balaji Lakshminarayanan. Proceedings of the International Conference in Learning Representations, 2017.
Learning in implicit generative models. In
[97] Gaspard Monge. Mémoire la théorie des déblais des remblais. Histoire de l'Académie Royale des Sciences de Paris, pages 666-704, 1781.
[98] Alfred Müller. Integral probability metrics and their generating classes of functions. Adv. in Appl. Probab., 29(2):429 443, 1997.
[99] É. A. Nadaraja. On non-parametric estimates of density functions and regression. Teor Verojatnost. Primenen., 10:199-203, 1965.
[100] Jonathan Niles-Weed and Philippe Rigollet. Estimation of Wasserstein distances in the spiked transport model. arXiv preprint arXivv1909.07553 2019.
[101] Nadia Oudjane and Christian Musso. L2-density estimation with negative kernels. In ISPA 2005. Proceedings of the 4th International Symposium on Image and Signal Processing and Analysis, 2005., pages 34-39. IEEE, 2005.
[102] Nicolas Papadakis, Gabriel Peyré. and Edouard Oudet. Optimal transport with proximal splitting. SIAM Journal on Imaging Sciences, 7(1):212-238, 2014.
[103] Emanuel Parzen. On estimation of a probability density function and mode. Ann. Math. Statist.,
33: 13:1065-1076, 1962.
[104] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning. 11(5-6)3355-677 2019.
[105] Svetlozar T Rachev. The monge-kantorovich mass transference problem and its stochastic applications. Theory of Probability Its Applications, 2944):64 1985.
[106] Aaditya Ramdas, Nicolás Gareía Trillos, and Marco Cuturi. On Wasserstein two-sample
testing and related families of nonparametric tests. Entropy, 19(2):47,01111
[107] Sebastian Reich. A dynamical systems framework for intermittent data assimilation. BIT Numerical Mathematics, 51(1):235- 249, 2011.
[108] Sebastian Reich. A nonparametric ensemble transform method for bayesian inference. SIAM Journal on Scientific Computing, 35(4):A2013 2013.
[109] Thomas Rippl, Axel Munk, and Anja Sturm. Limit laws of the empirical Wasserstein distance: Gaussian distributions. Multivariate Anal., 151 151:90-109, 2016.
[110] Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving GANs using optimal transport. arXiv preprint arXiv: 2018.
[111] Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58- 63):94, 2015.
[112] Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-scale optimal transport and mapping estimation. In Proceedings of the International Conference in Learning Representations, 2018.
[113] Hongjian Shi, Mathias Drton, and Fang Han. Distribution-fies consistent independence tests via center-outward ranks and signs. Journal of the American Statistical Association, pages 1-16, 2020.
16

---

[114] Hongjian Shi, Mare Hallin, Mathias Drton, and Fang Han. Rate-optiman optimmalt of consistent distribution-free free tests of independence based on center-outward ranks and signs. arXiv preprint UrXiv:2007.02/880 2020.
[115] Bernard W. Silverman. Weak and strong uniform consistency of the kernel estimate of density and its derivatives. Ann. Statist,, 611):177-184 1978.
[116] Max Sommerfeld and Axel Munk. Inference for empirical Wasserstein distances on finite spaces. J. R. Stat. Soc. Ser. B. Stat. Methodol,, 80(1):219-25) 238, 2018.
[117) Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet. On the empirical estimation of integral probability metrics. Electron. J. Stat., 6:1550-1599, 2012.
[118] Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf. and Gert R. G. Lanckriet. Hilbert space embeddings and metrics on probability measures. J. Mach. Learn. Res., 11:151--161,, 2010.
[119] Sanvesh Srivastava, Volkan Cevher, Quoc Dinh, and David Dunson. Wasp: Scalable bayes via barycenters of subset posteriors. In Artificial Intelligence and Statistics, pages 912-920.
PMLR, 2015.
[120] Sanvesh Srivastava, Cheng Li, and David Dunson. Scalable bayes via barycenter in wasser- stein space. The Journal of Machine Learning Research, 19(1):312 2018
[121] Zhengyu Su, Yalin Wang, Rui Shi, Wei Zeng, Jian Sun, Feng Luo, and Xianfeng Gu. Optimal mass transport for shape matching and comparison. IEEE transactions on pattern analysis and machine intelligence,
2015.
[122] G. Székely, M. Rizzo, and N. K. Bakirov. Measuring and testing dependence by correlation of distances. Ann. Statist., 35()):276--2794 -7994, 2007.
[123] M. Talagrand. The transportation cost from the uniform measure to the empirical measure in dimension 3. Ann. Probab., 22(2):99-959, 1994.
[124] Hans Triebel. Theory of function spaces. III, volume 100 of Monographs in Mathematics. Birkhäuser Verlag, Basel, 2006.
[125] Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics. Springer, New York, 2009. Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
[126] A. W. van der Vaart. Asymptotic statisties, volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1998.
[127] Aad W. van der Vaart and Jon A. Wellner. Weak convergence and empirical processes. Springer Series in Statisties. Verlag,r-Verlag, New York, 1996. With applications to statistics.
[128] Cédric Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathemat- ics. American Mathematical Society, Providence, RI, 2003.
[129] Cédric Villani. Optimal transport, volume 338 of Grundlehren der Mathematischen Wis- senschaften [F (Fundamental Principles of Mathematical Sciences]. Springer-Vert Verlag, Berlin, 2009, Old and new.
[130] Gilbert G. Walter. Approximation of the delta function by wavelets. J. Approx. Theory, 71(3)3329343, 1992.
[131] Jonathan Weed and Quentin Berthet. Estimation of smooth densities in Wasserstein distance. In Conference Learning Theory, pages 31 11-13119, PMLR, 2019.
[132] Yoav Zemel and Victor M. Panaretos. Fréchet means and Procrustes analysis in Wasserstein space. Bernoulli, 25(2):932-976, 2019.
1. For all authors...
17

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] In fact, in the Contributions Section (see Section I.3). have referenced the exact Theoorem//ropositionn where the claims made in the abstract and the introduction have been substantiated.
(b) Did you describe the limitations of your work? [Yes] See Remark 2. where we compare our main result Theorem B.I with existing results in the literature. There, we clearly discuss the advantages and disadvantages of our result compared to, e.g., a similar result in [72).
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is exclusively a theoretical nature and does not have any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All our results accompanied with the full set of assumptions required for them to hold.
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs of all our results can be found in the supplementary file.
3. you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [N/A] This work is exclusively of theoretical nature. We have not run any experiments for this paper.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [N/A]
4. you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] This work is exclusively of a theoretical nature. We have not used any existing or curating assets in this paper.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if ap- plicable? [N/A] This work is exclusively of a theoretical nature. We have not used any crowdsoureing and neither have we conducted research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
18


Reviews:
[{"review_id": "xHo3FX7as0", "reviewer": "Reviewer_TNQz", "summary": "This paper analyze the statistical behavior of the general plug-in estimators of OT defined by barycentric projections. The authors provide a thorough analysis of the rate of convergence for the transport cost and the transport map. They also consider kernel smoothed plug-in estimators and relate its rate of convergence to the smoothness of the densities, which alleviates the curse of dimensionality suffered by the plug-in estimator.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. The upper bound on the stability of the transport map defined via barycentric projections is new. The rate of convergence of the smoothed plug-in estimators is quite interesting since it reflects the smoothness of the densities.\n2. The paper has an extensive related work section discussing clearly the relationship of their work to previous ones.\n3. The paper is technically solid. The theoretical results are well explained and the intuition are nicely conveyed.\n4. The authors also design a discretized version of the smoothed plug-in estimator which enjoys the same rate of convergence and can be computed in practice.\n\nMajor comments:\n\n1. In the construction of discretized plug-in estimator on line 255, the procedure to obtain samples from the kernel density estimators is not discussed. This should also appear in the complexity analysis of computing $\\tilde T_{n,m}$ especially when the ambient dimension is high.\n2. In Theorem 2.6, the number of samples M is set to be $n^{\\frac{s+2}{2}}$. In practice, the smoothness s is unknown. It would be better to discuss how to select s in practice.\n3. An important selling point of this paper is, in my opinion, a discretized plug-in estimator which enjoys a good rate of convergence and can be computed in practice. It is expected to see some experimental results supporting this claim.\n\n\nMinor comments:\n\n1. On line 227 the squared 2-Wasserstein distance is considered, while the square is dropped in Proposition 2.5.\n2. Section 3.2 feels rushed. It would be better to explain more on the intuition behind rHSIC.\n\n-----\nUpdates: the authors addressed most of my concerns in the response. While I do believe adding the experiments on the discretized plug-in estimator will be a good addition to the paper, I also think the current version is already a good paper. Hence, I am keeping my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See comments above for suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "U1e2JdBLCs", "reviewer": "Reviewer_NLrD", "summary": "In standard OT problem, marginal distributions of the data are unknown. The current work considers plug-in estimation using Barycentric projection and derived rate of estimation. The idea of Barycentric projection is to plug the estimated marginal distributions of the data in the OT problem. Conditional mean of given us estimated and rate of estimation is derived. Various plug-in estimators of density of are considered such as empirical CDF and kernel density estimator.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work is new and results are strong and important. Paper written is clear and of good quality.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The concern is why the smoothness of the densities of are the same? In practice, the densities may have different smoothness degrees. Meanwhile, how to make it adaptive since selection of is a problem. \n\nAnother concern is the motivation of using OT for estimating conditional mean, compared with various nonparametric approaches in literature such as local polynomial, smoothing spline, etc.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "QZniXXKPl3P", "reviewer": "Reviewer_XWVX", "summary": "This article proposes a study on the rates of estimation of Brenier maps using the plug in \"barycentric mapping\" estimator. As a consequence of this study authors obtain rates of convergence for $W_2^{2}$ in various context (depending on the regularity of the measures and on the setting: discrete-discrete of semi-discrete). They apply their results for Wasserstein barycenter estimation and Nonparametric independence testing.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the one hand, from a theoretical point of view, I find the different results very interesting  on the other hand I find that this article does not really fit in the scope of a machine learning conference. Moreover I think that the article could benefit from an improvement in its writing (see below).\n\nOverall the introduction and the problem are well presented. The main result is also quite interesting: it justifies the use of barycentric mapping as an \"approximation\" of the optimal Monge map. This result has many practical consequences, especially when barycentric mapping is used as a proxy for the Monge map (as in [1,2,3] or in domain adaptation where barycentric mapping is at the heart of many methods e.g. [4]). This opens, in my opinion, many practical perspectives. It also offers new justifications for the recent results concerning the estimation of $W_2^{2}$.\n\nMy main criticism concerning this article is that it does not really fit, in my opinion, in the scope of a machine learning conference but is more adapted to a \"mathematical journal\" format such as Annals of Statistics. First, no experience is given in the paper. I understand the purpose of purely theoretical papers but I think that a ML paper should contain at least one or two small experiments validating/illustrating the different approaches when possible (see my last comment). \n\nMore importantly, the majority of the paper's contributions are in fact in supplementary material which is exclusively made up of proofs, quite specific and complex. So the paper is not really 8 pages long, but more like 20 pages of quite extensive mathematics. Consequently, given the time constraints inherent to NeurIPS, it seems to me quite reasonable to say that most ML reviewers cannot certify that all the proofs in such a paper are correct. Since these proofs are the main core of the paper, it is reasonable to think that it is difficult to judge the quality of the paper in such a setting. This argument would be invalid, however, if the above mentioned proofs were written with care and with a bit of hand-holding. However, the paper contains a lot of proofs without context or discussion and some \"proofs by omission\" based on other results. \n\nIndeed, the proofs are not self-contained, making the task of reviewing them very difficult, even for someone used to handling the tools of optimal transport. There are many calls in the proofs to results/equations of other papers without discussion or context. In the different proofs of the supplementary, there are no less than 12 calls to other results, which is, I think, a lot (\"see Proposition 2 in [16]\", \"see Theorem 2.10 in [7]\", \"Note that by [15, Equation 26]\"). Although it is common to write a proof by appealing to other results, this is usually the case when the result is \"somewhat known\" or by explaining a bit the outline of these results. In many cases here, these results are very specific and are not discussed. It is also difficult to say, without reading the whole articles in question, if the assumptions of the different theorems referred to are really applicable in these specific cases. For example  [13, Theorem 17] for Step I of the supplementary (row 95) calls for a theorem which itself has many assumptions and it is difficult to see if these assumptions are validated here, because no explanation or context is given. Some other proofs are not very elaborated (row 79-80) \"The general strategy to bound the term in (A.20) is derived from some intermediate steps in the proofs of [5, Lemmas 3 and 4]. We still present a sketch here for completeness.\"\n\nFinally, the paper ends  on a theorem without any conclusion, which I find rather clumsy. No discussion or perspective is given about the \"Application\" part (which is actually another theoretical part). For example, it is rather difficult to understand the interest of the \"Nonparametric independence testing\" section: what is \"the permutation principle as is necessary for the usual HSIC\" ? Why understanding \"the local power of $\\phi_{n,\\alpha}$; under \"changing sequence of alternatives converging to the null\" \" is a practical, interesting problem ? \nIn this section, for example, it would have been valuable to include a small experiment showing the interest of the main result for this problem. Another question that could be interesting is the practical comparison between the barycentric mapping estimator compared to the \"Sinkhorn divergence\" one of (Chizat, 2020). It seems to me that it is somehow harder to compute the barycentric mapping, since this is a standard OT problem, while the Sinkhorn divergence is easier due to the regularization and the complexity of Sinkhorn’s algorithm. On the other hand, for real data, maybe the estimator based on the barycentric mapping would better behave ?\n\nFor all these reasons I rather recommend rejecting this paper. I find the results interesting but I don't think it is, as it stands, a suitable paper for a Machine Learning conference. I admit that some of my comments are quite subjective (\"what a ML paper should be\") so I am wiling to change my opinion.\n\n[1] Michaël Perrot, Nicolas Courty, Rémi Flamary, Amaury Habrard. Mapping estimation for discrete optimal transport\n[2] Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, Mathieu Blondel. Large-Scale Optimal Transport and Mapping Estimation\n[3] Elsa Cazelles, Felipe Tobar, Joaquin Fontbona. Streaming computation of optimal weak transport barycenters\n[4] Nicolas Courty, Rémi Flamary, Amaury Habrard, Alain Rakotomamonjy. Joint Distribution Optimal Transportation for Domain Adaptation\n\n----- After Rebuttal -----\n\nI thank the authors for their response. After reading the rebuttal I decided to increase my score to 5. I agree that this paper proposes interesting new theoretical results and I agree with the other reviewers on this point. However, I think it would benefit from a rewrite of the proofs (to be as self-content as possible since it is the core of the paper) and of the \"Application\" part which does not seem to me to be detailed enough as it is. I also think that this paper deserves a conclusion in order to give some perspective on the different results. That's why I don't increase my final grade more widely. However, I do not object to the acceptance of this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors did not provide any potential negative societal impact of their work however, it is difficult for me to foresee these impacts..", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "PhURqAS_fhf", "reviewer": "Reviewer_7wET", "summary": "This paper studies the problem of estimating an optimal transport map between two probability distributions on Euclidean space, given IID samples from each of the distributions. The main result (Theorem 2.1) gives a general upper bound, in terms of the dual representation of the 2-Wasserstein distance. This is used to give upper bounds, in probability, on the rate of decay of the estimation risk both for the plugging in empirical distributions in the absence of smoothness assumptions and for kernel estimates under smoothness assumptions. Finally, implications for two applications (Wasserstein barycenter estimation and nonparametric independence testing) are discussed.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think the paper's contributions are clearly sufficiently novel and relevant for acceptance. However, I think the paper would be rather difficult to read for all but a very small subset of the NeurIPS community.\n\nMain Comments:\n1) I found the paper rather notationally dense, and, in my opinion, the paper would benefit from providing more intuition in several places, especially around the definition (Definition 1.2) of the barycentric projection, the loss function (Eq. (1.8)), and the main result (Theorem 2.1). It would be helpful, for example, if there was some prose describing why Eq. (1.8) is a good loss function to upper bound, and what the roles of the terms appearing in Inequality (2.1) are.\n\n2) In Theorem 2.4, it seems that the exact rate at which the bandwidth h_n vanishes does not affect the ultimate convergence rate, as long as it is slower than (log(n)/n)^{-1/(2s+d)}. It seems counterintuitive to me that a very large bandwidth, e.g. h_n = 1/log(n), would not slow the convergence rate. Could the authors provide any intuition for this phenomenon?\n\nMinor Comments:\n1) Line 40: The sentence \"T_{m,n} converges at a rate of m^{-2/d} + n^{-2/d}\" isn't really meaningful unless a loss or error metric is specified. Especially for nonparametric problems such as this, different metrics likely lead to different convergence rates. Hence, I suggest adding a brief description of the error metric here, or at least pointing the reader to Eq. (1.8).\n2) In several places, such as Eqs. (2.1) and (2.2), it is impossible to visually distinguish the \\overline's and \\tilde's over \\mu and \\nu without zooming in quite a bit. This left me confused for a while trying to figure out the difference. Is it possible to make these notations more visually distinct?\n3) Line 78: Typo: \"distributions on X_1, . . . , X_m\" -> \"distributions of X_1, . . . , X_m\"\n4) Could the authors comment on how specific the results in this paper are to 2-Wasserstein, as opposed to general p-Wasserstein, distances?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper gives a reasonable discussion of its limitations. I don't foresee any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "8VriIeQtae", "reviewer": "Reviewer_yWvi", "summary": "Summary\n=======\n\nContext:\n--------\n\nThis paper tackles the problem of estimating the rate of convergence of empirical Monge maps\n(through its Kantorovich barycentric map approximator) to the true Monge map for \nabsolutely continuous Lebesgue measures. \n\n\nContribution\n------------\n\n- The authors provide new rates of convergence of the barycentric map using standard \nempirical plug-in estimators (O(n^{-2/d}))\n- If the measures are regular enough (Holder smooth), the dependence on the dimension\ncompletely vanishes (which was established for Gaussian distributions https://arxiv.org/pdf/1905.10155.pdf)\n- The authors propose to take advantage of this smoothness result to sample from smoothened distributions\n(using a Kernel density estimator) and provide the sufficient conditions to obtain a desired rate. Higher\nsmoothness however requires more samples: a tradeoff between statistical accuracy and computational cost\ncannot be avoided.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "review\n======\n\nGeneral assessment\n------------------\n\nFor a purely theoretical paper, this paper is vey well structured and easy to read. Transitions are smooth, and theorems\nare fairly well motivated and interpreted. Even though one may wonder whether a journal would have been more appropriate\nfor this paper, the theoretical contributions of this paper are novel and are certainly valuable for the OT community at Neurips.\nMy only main concern is the lack of clarity of how can proposition 2.5 hold, which suggests that the rate of convergence of W2\nis significantly different when mu = nu (see point (5) below). This is the only point -- pre-rebuttal -- retaining me from increasing my score.\nI would appreciate if the authors could shed some light on this: are there any assumptions mismatch between this setting and the one from [119] that would explain this disparity ? Otherwise shifting the samples of a distribution slightly would lead to better convergence rates. \n\nSpecific comments\n-----------------\n\n1) In remark 2.1, the authors mention that theorem 2.1 doesn't require compactly supported measures\nunlike previous results (of [69]). Still, for all the derived convergence rates (subsequent theorems), at least one \nof the  measures needs to have a compact support for a uniform bound of the potential function. While requiring less\nassumptions on the measures to obtain similar stability results is certainly an improvement over the literature, I'm wondering\nwhether Theorem 2.1 can be used to obtain convergence rates (or any other simpler and interpretable upper bounds)\nwithout assuming compacity of any of the measures. \n\n2) Still on compacity: how would an assumption on the tail of the measures compare with the compacity assumption ? Could\nthe uniform norm be substitued with a less stringent norm in the technical derivations so as to generalize the known convergence\nrates for Gaussians for example ? \n\n3) Throughout the paper, T0 is assumed L-lipschitz. However the regularity of T0 can also be seen as a consequence of\nthe regularity of the measures themselves which begs the question: are there any sufficient conditions on the measures\nthat guarantee an L-lipschitz T0 without assuming \"too much\" smoothness on the measures. \n\n4) The constant C in the corollary seems to be obtained through existence theorems of arbitrary constants C1 and C2. Do we have\nany bounds on these constants and their dependence on the parameters of the problem ? Perhaps the diameter of the bounded supports ?\n\n5) in L 248, authors mention that T_m,n of theorem 2.4 cannot be computed from the data, is this because T_m,n is a continuous\nbarycentric map derived from the continuous measures given by the KDE ? If so, I think the dependence on m,n should be slightly different\n(in terms of notation) to distinguish it from the empirical map. \n\n6) I find the result of proposition 2.5 quite intriguing. [119] provided a lower bound on the convergence rate for the case mu = nu, \nthat is a rate that cannot be beaten by any estimator. Prop 2.5 shows that this rate can be improved (significantly) if mu != nu. \nThis suggests that If I take a measure mu and shift its mean by a certain\nvalue, I would need less samples to approximate the W2 value. Am I missing something here ? \n\n7) A minor remark on the appendix: please use a different notation for \\bar{nu}, distinguishing it from  \\tilde{nu}\nis quite challenging specially when verifying the proofs. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers insisted on the high quality of the theoretical results, even if some numerical simulations would have been welcome (these could have been provided in the supplementary material). They also appreciated the quality of the rebuttal, which clarified some important questions. Some raised the issue that the part of the proof in the supplementary was lacking clarity and details, and this should be improved in the final version. I thus strongly urge the authors to take into account the feedback of the reviewers to improve the quality of the paper. For these reasons (lacks of numerical simulation and clarity of the proofs), after a discussion with the reviewers and in agreement with them, I decided to support acceptance but not for a spotlight. 
Decision: Accept (Poster)