Estimation of Stochastic Optimal Transport Maps
Authors: Sloan Nietert
Ziv Goldfeld
Venue: NeurIPS 2025 poster ()
Keywords: optimal transport
map estimation
non-parametric statistics
robust statistics
Primary area: theory
TL;DR: We introduce a novel metric for evaluating the quality of (potentially stochastic) optimal transport maps, which enables efficient and robust estimation in previously unexplored regimes of practical significance.

Abstract: The optimal transport (OT) map is a geometry-driven transformation between high-dimensional probability distributions which underpins a wide range of tasks in statistics, applied probability, and machine learning. 
However, existing statistical theory for OT map estimation is quite restricted, hinging on Brenier's theorem (quadratic cost, absolutely continuous source) to guarantee existence and uniqueness of a deterministic OT map, on which various additional regularity assumptions are imposed to obtain quantitative error bounds. In many real‐world problems these conditions fail or cannot be certified, in which case optimal transportation is possible only via stochastic maps that can split mass.
To broaden the scope of map estimation theory to such settings, this work introduces a novel metric for evaluating the transportation quality of stochastic maps. Under this metric, we develop computationally efficient map estimators with near-optimal finite-sample risk bounds, subject to easy-to-verify minimal assumptions. Our analysis further accommodates common forms of adversarial sample contamination, yielding estimators with robust estimation guarantees. Empirical experiments are provided which validate our theory and demonstrate the utility of the proposed 
framework in settings where existing theory fails. These contributions constitute the first general-purpose theory for map estimation, compatible with a wide spectrum of real-world applications where optimal transport may be intrinsically stochastic.

Estimation of Stochastic Optimal Transport Maps
Sloan Nietert EPFL sloan. www.nnietttt@ppl.chetcc
Ziv Goldfeld Cornell University goldfeld@cornel] edu
Abstract
The optimal transport (OT) map is geometry-driven transformation between high-dimensional probability distributions which underpins a wide range of tasks in statistics, applied probability, and machine learning. However, existing statistical theory for OT map estimation is quite restricted, hinging on Brenier's is theorem (quadratic cost, absolutely continuous source) guarantee existence and unique- ness a deterministic OT map, on which various additional regularity assumptions are imposed obtain quantitative error bounds. In many weal-world problems these conditions fail or cannot be certified, in which case optimal transportation is possible only via stochastic maps that split mass. To broaden the scope of map estimation theory to such settings, this work introduces a novel metric for evaluating the transportation quality of stochastic maps. Under this metric, we develop computationally efficient map estimators with near-optimal fimite-sample risk bounds, subject to easy-to-verify minimal assumptions. Our analysis further accommodates common forms of adversarial sample contamination, yielding es- timators with robust estimation guarantees. Empirical experiments are provided which validate our theory and demonstrate the utility of the proposed framework in settings where existing theory fails. These contributions constitute the first general-purposs theory for map estimation, compatible with wide spectrum of real-world applications where optimal transport may be intrinsically stochastic.
1 Introduction
Optimal transport (OT) is a principled framework for comparing and transforming probability distributions according the geometry of the underlying metric space [Villani 2003 Santambrogio 2015). Central to OT theory is the transport map, which performs said transformation. For X. C R"
we say that T X' + y a transport map from source distribution μ E P(X)) to target E P()) the pushforward measure T.u o T coincides with v. An optimal transport map T*, if it exists, a solution the Monge OT problem from μ to 2,, which reads as follows for the p- p-Wasserstein cost:
inf T:Ta=v
[ T())
Monge maps are employed for many applications, including domain adaptation [Courty et al.) [017]] Redko al. 20199, single-cell genomics (Schiebinger al. 2019 Bunne al. [0033] style transfer
Kolkin et al. 2019 Mroueh| 2020), and generative modeling [Zhang et al. 2018 Vesseron et al.) 2025]. An important special case is when p = 2 and μ absolutely continuous with respect to (w.r.t)) the Lebesgue measure; then, Brenier's theorem guarantees the existence of a unique Monge map, often called the Brenier map, given as the gradient of a convex potential [Brenier [991]. More generally, existence of optimal maps is guaranteed if is absolutely continuous and uniqueness holds further >> (see, c.g., Section 2.4 of Villani 2003).
There is rich literature on formal guarantees for estimation of Brenier maps Hütter and Rigollet
2021 Pooladian and Niles- Weed 2021 Deb et al. 2021 Manole et al. 2024 (see related work).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, all of these works impose stringent regularity assumptions on the density of μi (e.g., two- sided bounds) and/or the unique Brenier map T (e.g., Lipschitzness and Hölder smoothness). This is because the quality of the estimator is measured by its (1)( distance from 7*, which inherently requires uniqueness (otherwise, the (1) metric is meaningless) and hinges on said regularity assumptions to obtain quantitative error bounds. However, such regularity assumptions are often impossible to verify in practice. Worse yet, many real-world applications violate the conditions of Brenier's 's theorem, whence deterministic Monge maps may not exist, and optimal transportation strategies require stochasticity. For instance, this is the case in domain adaptation whenever the source distribution lies on wwwe-ddienniional manifold than the target (Courty al.. 2017 Redko et al., 2019]. such as in text-to-ing text-to-image image or sketch-to -hotooo translation. Similarly, single-cell developmental trajectories branch over time, any measure- preserrvig map from an early snapshot to later one must be stochastic (Schiebinger et al. 2019]. As such scenarios far exceed the account of current OT map estimation theory, this work sets out close this gap by providing broadly applicable estimation framework that offers strong recovery guarantees for a breadth of applications.
1.1
New Framework for Stochastic OT Map Estimation and Contributions
The Kantorovich OT problem [Kantorovich] [942 relaxes that of Monge by allowing stochastic maps. Reparametrizing the standard formulation via couplings in terms of Markov kernels, reads as
(ff - (i--IIlddnll))d(a)) REK(X.)) Kg//mm
#
Proposed Ep framework (all W/ problems)
Wp(A, =
min
(2)
where w(-l-)) varies over Markov kernels (regular conditional prob- ability distributions) from X to y and Kill denotes the pushfor- ward measure J xc- (o(-(z)d((((z) (x) [ We propose a novel framework for stochastic OT map estimation by furnishing a suitable error metric. For source distribution μ E P(X'), target distribution v E P(Y). and kernel from X' to V. we define the transporlution error (r μu 2/) of x for the (p(,,)) problem by
Brenier's Thm
Brenier's Thm Regularity
[/ || (i-yylldae (Vdd(()))d((() Wo(mne)
+ Wp
Figure I: Previous map estima- tion theory only accounts for the inner circle, despite many OT map applications lying outside it. The proposed estimation frame- work under Ep covers all possi- ble Wp problems (subject to tail bounds for quantitative rates).
optimality gap
feasibility gap
where [c]+ = maxfc. 0} and (-) = k(-lz)). Under Ep, the quality of x is thus measured by its transportation cost overhead on top of the optimum (p(H. v/) (dubbed optimality gap). plus its p- Wasserstein gap from matching the target (the feasibility gap). While the Ep error metric naturally accounts for deterministic OT maps, does not require uniqueness or even existence thereof. This enables treating OT map estimation settings far beyond those accounted by existing theory, as illustrated in Figure [ to the right. Remarkably, beyond the broad coverage of the proposed framework, quantitative bounds on E, can be derived under minimal and easy-to-verify assumptions, rendering the guarantees applicable in practice.
Our technical contributions build upon a foundation of stability lemmas for E, established in Section 2 These characterize how E, responds to TV and Wasserstein perturbations of the input measures and to compositions of the kernel. In Section 3 we apply these to finite-sample estimation and computation. Here, our strongest result holds when v is sub-Gaussian and μ has bounded 2pth moments, but assuming no regularity of an optimal kernel. For i.i.d. samples Xi..... X, ~ ~ and Yi...., Y, ~ present rounding- based estimator R, which achieves (f μ4, v)] Öp.a (n (oannnn// -1/((+2))) with running time (I)))) dominated by a single, low-accuracy call to an entropic OT solver. We also observe a minimax lower bound of 22(n 11/(dv2))), showing that our rate is near-optimal.
'The standard Kantorovich OT problem optimizes cost over couplings æ e 11(,, v), but disintegration theorem yields that each such coupling can be decomposed as dr y) = du(x)) (d)))))())))) where (----) is a Markov kernel induced by conditioning on the left argument. When a coupling is induced by deterministic map I', i..., (Id, Tu, the corresponding kernel is given by K2 dr(=).

---

In Section 4 optimal kernel, a condition that is still significantly weaker than typical assumptions for Brenier map estimation when p- = 2. In particular, for the case of a Lipschitz optimal kernel Ki,, i.e., when Wp((K=) (1)))zr) X || - ='|l for all x. E X, we show that kernel estimation under Ep has the same statistical complexity as estimating μ and V under Wp. with rate Ö(n 1/(a22))). For this reduction, we employ an estimator based on Wasserstein distributionally robust optimization.
we examine the statistical landscape of estimation when there exists Hölder continuous
In Section 5 we show that effective kernel estimation is possible in the presence of adversarial data contamination. Historically, robust statistics has been well-studied under Huber's e-contamination model for global outliers, which is subsumed by TV e-corruptions of the input data [Huber 1964).
More recently, statisticians have examined robust estimation under localized Wasserstein corruptions of the input samples (Zhu et al. 2022 Chao and Dobriban 2023 Liu and Loh| [023). We consider a strong corruption model where the clean samples can be corrupted both in TV and under the
Wasserstein metric. This combination of local and global corruptions only has only explored recently
[Nietert et al.) 2023b, 2024, Pittas and Pensia 2024], and their interaction has required careful analysis. Here, stability of Ep enables us to cleanly decouple the two corruption types. Against an adversary with TV budget E and W, budget p. we show that a convolutional estimator achieves error //el/r + vdpp + (p.a(n-1/(d+2))
An accompanying minimax lower bound of Vde + d'/4p1/2 + n 1/(v2p)) implies a separation between robust map estimation under Ep and robust distribution estimation under Wp. where one can achieve linear dependence on p.
In Section O. we validate our theory with numerical simulations for two settings with irregular OT maps that are poorly suited for existing theory. These showease the performance of rounding estimator and the benefits of E, over LP, Overall, our results constitute a general-purpose theory for (possibly stochastic) OT map estimation, subject to minimal primitive assumptions. As such, it is capable of providing formal performance guarantees in the &, sense in various practically relevant settings.
Related work. Most related to this paper is a line of statistics work on the minimax sample
complexity of Brenier map estimation when p = 2, initiated by Hütter and Rigollet [2021]. Under density assumptions on μ and smoothness conditions the unique Brenier map T (in particular,
Lipschitzness), they obtain near-optimal risk bounds of the form I T [|ا 1 =
using empirical risk minimization for semi-dual objective. The myriad of follow-ups include Pooladian and Niles-Weed [202T]. [eb et al. [202T]. Manole al. [2024]. J. all of which impose density and smoothness assumptions, [Poladian et al. [023] considered the semi-discrete setting where the Brenier map is piecewise constant, employing an estimator based on entropic OT (EOT). Recently, [Balakrishnan and Manole (2025) provided refined guarantees that sidestep the typical density assumptions, but they still rely on the Brenier map being the gradient of a sufficiently regular convex potential. Lastly, variety of neural map estimators have been developed by the machine learning community (Seguy et al. 2018 Meng et al. 2019 Wang and Goldfeld 2024). with applications to domain adaptation, style transfer, trajectory estimation, and the like.
Two recent approaches for neural map estimation warrant further discussion. First is the Monge gap regularizer of Uscidda and Cuturi (2023). For the p- p-Wasserstein cost, this work proposes training a deterministic map estimator to minimize the objective JT ju. v) Mp(T: + D(T,H, v), where D is a statistical divergence and the Monge gap Mp is defined by
T()) - du(() - Tr))..
Mp(T:N)== = |1 |a-
They show that M, 2 O with equality if and only if T is e-cyclically monotone over suрр(μ). Con- sequently, Jp nullifies exactly when T optimal for the W, v) problem. The statistical analysis of that work accounts for consistency, under the assumption that a deterministic and continuous optimal map exists. In practice, they suggest taking D as an EOT cost, estimating W, with EOT, and substituting i and v with their empirical measures. Parameterizing T via a multilayer perceptron, they achieve competitive empirical performance on range of map estimation tasks. As we will show in Section 2 Ep and Jp are very connected; in particular, they coincide up to constant factors when W, We view & as better suited for quantitative statistical analysis, enabling rates which seem difficult to prove under Jn for general (and we are unaware of any existing rates proven under Jp). On the other hand, as discussed in Section 6. we find that J, is better suited for neural implementation, since its gradicnts seem to carry a stronger signal when far from optimality.
p = 1 and
3

---

22 (0.1)
T
1
T
S 8
T
(0.0)
Tall
Tg ] Wp 8
Figure 2: Diagrams of 2 maps and kernel for Wp(u,v). where in each is uniform over the blue T for (x) = ((-1) .22). We depict T the left, T(x) (-(-1)Lex/0) x2) in the center, and kernel H₂ (nif(((-1,x2)) (1,)))) on the right. While and x are far from T in an IP sense, they achieve & I (indeed, both T and achieve zero optimality gap and at most 6 feasibility gap). Taking å + 0, 7 becomes impossible
line connecting (0, 0) and (0, 1) and, in orange,
to recover from finite samples, whereas x can be estimated effectively.
Lastly, there an existing line of work on the design of neural estimators for stochastic OT maps [Korotin et al., 2023a b). They show that any optimal kernel is the solution of certain maximin problem, which they approximately solve via neural net parameterization and stochastic gradient ascent-descent. However, this maximin problem sometimes admits spurious solutions associated with suboptimal maps. general, these are more empirical works which do not address statistical rates.
1.2 Preliminaries
Notation. Let || denote the Euclidean norm on Rd and Idd be the d-dimensional unit ball. For measurable S C R2d write P(S) for the space of probability measures over S and diam(S) for its diameter. Let (S) denote those with finite şth moments, and write N(x,, Σ) for the multi-variate Gaussian distribution with mean & E IRd and covariance Σ E Rdxd, We say that E P(RR)) is sussu-GGanniaan if E, (exp([IxX]]//==) < Write M(S) for the space of finite signed measures on S, equipped with the TV norm ||/|TV [ and M+(S) for those which are non-negative. Let ün, 1 >i= 8x, be the empirical measure of n i.i.d. samples X,,..., X, from μ. We write abb = max b), a.b = min b}, and Sa, Zx. Ra for (in)equalities up to constant depending only on x (omitting x for absolute constants).
Kernels and their composition. Writing B()) for the Borel subsets of y. we recall that a Markov kernel к X(XX' )) is a map (A,r) B()) x X' + (A) E [0, 1] which is measurable in æ for fixed A and is a probability measure on for fixed Consequently, given any p P(X). the pushforward measure kyp(-) == f K- (-)d(((()) is well-defined probability measure on V. Moreover, fixing any intermediate space Z C Rd, kernels n. E K(Z,)) y) and À K((,' 2) can be composed to obtain the composite kernel x X K(X, )) defined by (K o A)(A)z) == J Kg (A))),,))..
Statistical distances and empirical convergence. We often use the following standard results.
Fact 1 - comparison). For μ4, P(X), we have Wp(u,v) v) & diim((X))lı vill/. Lemma (W, empirical convergence, Lei 2020). Ifq > p and μ E (I( then (M, (an).ann)) Ln)SSpaa E2 | (aaiva (1) -]] log² (n). If d > g > 2p, then E,,,(H, An)] Sp.o E | -
2 Basic Properties of the Error Functional
Before turning to estimation, we establish some fundamental properties of our error functional
1 E,(K:; p) == (ffllc-ll/ddada #_ Wolenm) - + Wy(rsppp))
(4)

---

This metric is natural because it vanishes for any optimal kernel, namely, pp(K;p,,) ) = 0 if and only minimizes (2). Further. it generalizes the existing L" benchmark, which applies only when an optimal deterministic map 7* exists.
Proposition (Relation L" loss). For any map T + y and T X + y minimizing (,, v) < 2| T (P)())
See Appendix A.1 for the proof. In Figure 2 show how L be arbitrarily large compared to Ep, failing to recognize the performance of map estimates that deviate pointwise from T
feasibility). An alternative version of &p weights the feasibility gap by regularization strength X. When = 0, the identity map is optimal, and, as - co, the constant kernel s(-lz) becomes optimal. Our setting is natural balance between these
Remark (Optimality
extremes.
Remark 2 (Reverse I,2 comparison). p = 2 and T is the gradient of an L-smooth convex potential, show in Appendix A.2 that || T. T.I. (10 E (LV & (T; ps, v) (W2(1, D) + (4,
We also compare Ep to the Monge gap objective discussed in Section The proof in Appendix A.3 essentially follows by the W, triangle inequality.
Lemma 2 (Comparison to Monge gap). For the alternative objective E, defined by
|f | dkl (v)d(()))(()) Wpl,, +W, +W,
E,
Monge gup
we have Ep 1 4. For p 1, we have / S & 28
We now examine stability of E, with respect perturbations of the source and target distributions. These stability results form the backbone for the estimation risk analysis of the estimators proposed in the subsequent sections. Their proofs in Appendix generraly follow via the L triangle inequality.
Lemma 3 (Stability in v). Fix P(X) and v' E P()). For each KC(, we have (k) - E/) S (w, S 2 ddia v' 1/
The Ep metric tolerates Wp perturbations μ when k is appropriately Hölder continuous. Lemma 4 (Wp stability in p1). Fix u. P(X). VEP(),, and x EEK, with Wp(Ke, Kar) S T||x-~1'11 for all x. x' E EX, where
S 1. Setting p = Wp J1), we have [E,(m; v) - E,(m; u4 w) S 2p + 2T.p In particular, the above holds with a whenever is induced by deterministic, L-Lipschitz map.
We can treat TV perturbations of the source measure when y is bounded. Lemma 5 (TV stability in μ). Fix p. u.p' u E P(X), E P(Y), and kernel E K(X,)). Setting E || - --4' llv, we have
(,; v) S 4 diiam)))) + 10E 14, v) + (,, In particular, we have E (N: S diam + (.:
That is, if pl and ja share substantial mass, and k. performs well on 14, then its performance o1' under E, cannot be substantially worse. In particular, the proof in Appendix A.6 decomposss μ = a + B where a is its shared mass with μ², and uses that, if ς is optimal for the Wp(u, v) problem, then it must also be optimal for the W,,a,, Kja) sub-problem.
Finally, we consider the behavior of &, when evaluated on composite kernels, which we employ in some of the subsequent kernel estimators.
Lemma 6 (Kernel composition). Fixing an intermediate space Z C R2, let μ P(X), K(X 2), and E K(Z,Y)) We then bound
| X; d; v) - Ep(n; Xuu,, v)l S In particular, for X induced by a deterministic map f 2, we have Ep fiH, (p(s: fap, v) 21l ld [|))()))
(ll===((dd==)ddull 222 =
This can be applied iteratively to analyze the composition of many kernels, peeling off one at a time.
5

---

The proof in Appendix B.1 has three steps. First, we control (p Pr. Px) Ōd(r"/P) using known bound of Genevay et al. 2019]. Then, using the support constraint and the softmax form in 7 we bound the TV Lipschitz constant of k. by Oa(r-1) )) which implies the kernel is W, Hölder continuous with exponent 1/p and constant Oa(r (1/P). Finally, we apply Lemmas and to bound 3 Finite-Sample Estimation and Computation
Under Ey. we can perform kernel estimation without regularity or existence of Brenier map. We analyze one estimator based on EOT using W, stability (Lemma and another based on rounding using TV stability (Lemma 5). The former is closer to existing estimators, but the latter achieves sharper rates under milder assumptions. Fixing 2 3, we have i.i.d. samples X1...., .......,....... Xn P(X) and ....... Yn V P()). whose empirical measures we denote by üi and i, respectively.
~ E
Entropic kernel estimator. As a warm-up, we recall the EOT problem, defined for > 0 by
inf /f || v/l v) 7 (DIL (1
(p,
(5)
xell(p,))
where the Kullback-Leibler (KL.) divergence is (kL(()
log dy if i < and +000
otherwise. This objective is strictly convex due to the KL. penalty, so a unique optimal coupling always exists (supposing that the value is finite). Most solvers for EOT use its equivalent dual formulation:
/ fdu f gdv -7 + /] (off))++(e)-lee-ll11 "appll""//ppppppppppppp dp(x)dd()))))+)))))))))))))))))) +
(p.(( sup
(6)
SEL (M) SEL (v)
The primal and dual structure of EOT is well-studied (see, e.g., Cuturi 2013 Genevay et al. 2019). In particular, if πr, minimizes ( then there exists maximizers fr, 9- for (6). termed entropic potentials, such that the conditional entropic kernel π (-(((<) can be written as
dr+ (ulv) = exp (()(x)) + (v) - || - y //T du(y) exp (g, (v) - x - -yll")/ du(y)
eeep ((g((g))))))))))))))))))) - |> 1---y' (P)/T) dv(y')
By this result, we may assume that the entropic kernel is defined over all x Rdd. We show that, diam (X' U Y)) is bounded, the empirical entropic kernel achieves vanishing Ep error.
Theorem 1 (Entropic kernel estimator), Assume N, C [0,1] 1]d and set d=/4n (/(dd44))) log Let 7,,. be the optimal coupling for Sp.r (Pr Dn). ). Then, the conditional kernel &., defined by (Rn)a = (-1x) satisfies BlEp(Rni u, v)) Sp.d n (2ppd//p))) (ng).
Ep(nni v) S (Rii An, P.)) + (a((p//)()))))) MP) + O(p) = Ōa(T2/P + (p/T) + p).
where م Wp p1) V (p v). Applying Lemmal to bound م and tuning gives the theorem. Note that 5 controls a bias-variancs trade-off (T + overfits, while 7 - xc blurs out all structure).
To understand the quality of this bound, we compare to Brenier map estimation with p 2. Here, the conditional kernel is usually converted into a deterministic map T, via barycentric projection, which sends x to the mean of Y ~ (- Existing work has derived variety of 2 estimation guarantees for this estimator with respect to the Brenier map T** In particular, Pooladian and Niles Weed [202] show that E I - T [|^> Sa n (=(++)//((d+a+t)) log T E Ca+1 for < a S and VI" has cigenvalues bounded from above and below. For the sake of comparison, we can take formal limit as a - 0 (although not covered by their theory) to obtain a rate of n. 1/(44+4) which is always worse than our n 11((dvv)) rate (which does not require p = 2 nor the existence of T*)).
Improved rounding estimator. While guarantees for the entropic kernel estimator from Theorem I are compelling, we can achieve sharper rates using the following rounding estimator, via an analysis based TV stability of E,- The estimator is specified by an accuracy 5 ' trimming radius R > 0, partition P of d and collection of centers Cp {cr) such that each cp P. This induces a rounding function rp Rd + Cp which, for each P E P, maps E P to cp. Given empirical measures fr, and in, we proceed as follows:
1. Round fnn onto P. taking p/, (rp) )1pn

---

2. Compute preliminary kernel R, C(Cpp,upplis which pushes pl onto i/ and is near- optimal for the Wp problem. satisfying ff || y (2) (x) S W, 2n, + 6.
Return kernel Ki. = Kn o rp, which, given x E Rd, rounds to (p) before applying Ki.
For simple choice P. this procedure achieves low E error when μ and v are Sab-Gaassian. With more complex partition, we can support j with only bounded 2pth moments.
and take P as the regular partition of Rd into cubes of side length v. Then, for R. v, and ö tuned independently of μ and v, we have (Rip μ4, w]] = Op.a(n (1/(422)))) For an alternative, non-uniform partition, this guarantee still holds if the sub-Gausianitty assumption on is relaxed to [| S 1. In both cases, computation is dominated by Step 2 which. if implemented via an EOT solver, runs time o(Css0
Theorem 2 (Rounding estimator). Let J., be
d)n2toa()) where Coo m
||
Yýll- -
This improved n -1((+2pp) rate is near-optimal; indeed, when is a point mass, the problem reduces to estimation of v under Wp. for which there are existing minimax lower hounds of order n --1/(dv2p) (Singh and Póczos 2018) (see Appendix [B.2 for full details). We also note that the tail bounds on ja and / can be weakened further under our analysis, but not without worsening the rate.
We sketch the proof when μ is sub-Gaussian, full derivation. We first show, for the cubic partition P with side length r, that μú, = (rp) Pa and
O, and diam()) S 1; Appendix B.3 for the
μ' (rp): /u converge in TV at rate vr-d/n. Here, r -d arises as a bound on the number of relevant partition blocks. We then bound
Ep(Rni = ER orpip,
S (niini + vdr
(Lemma 6
S Wplu, Un) + (nr")) to2 + vdr
(Lemmas 3 and 5
Applying Lemma [ and tuning r gives the theorem. The general sub- Gaussian case follows by a similar argument. If only has bounded 2pth moments, we can still achieve TV convergence at comparable rate by employing a partition whose bins increase in size away from the origin.
Remark 3 (One-dimensional refinements). Given the gap between our n- (d((2pp)) upper bound and the n -1/dd2p)) lower bound of Singh and Póczos 2018], it is natural to ask if the lower bound can be improved. At least when 1. this impossible ble. In Appendix [B.4] we improve the rate from Theorem 2 to n 1/2 when d = 1, using stability of &, under the Kolmogorov-Smimoy metric.
4 Improved Statistical Guarantees with Hölder Continuous Optimal Kernels
For p 2, many existing works assume the existence of Brenier map 7* whose gradient has eigenvalues bounded from above and below (in particular, such a 7* is Lipschitz). For example, Balakrishnan and Manole (2025] show that neiihot estimator achieves E ||f (2()) =
O(n 1/(d))) matching the W2 empirical convergence rate. Of course, by Proposition T this guarantee also holds under &g. In this section, we treat general p 2 1 under the related but distinetly weaker assumption that (,(,, admits optimal kernel which is Hölder continuous under Wp
Assumption 1. There exists L 2 such that W (p(s,, (E)) < L| - x l|" for all xr x' E X.
(0, 1), and an optimal kernel n² E K)( for (p,
Here, we propose an estimator based on Wasserstein distributionally robust optimization (WDRO):
& (á, D]
arg arg min (' A)
sup
(1; D),
where ju, & are any proxies for μ. (potentially their empirical measures). This estimator is computa- tionally inefficient but allows us to better understand the statistical limits of estimation.
Theorem (WDRO estimator). Under Assumption [ suppose Wp 4) S Pu and W, v) S pu. Then the estimate & 2 [û, i achieves (R:R;; p, v) Lpf + Pv Pv.
7

---

Proof. Using the WDRO problem structure and our stability lemmas, we bound
()) S (p; + 2p,
(Lemma 3)
S sup
Ep 0) 2pr
(Wp(u,, ()) S pp)
I w.w MSn
sup Ep(ksill 2pc w wi M)
(optimality of R)
sup H N'EP(R"): W,, w,
Ep(Ksi 11 20r
(Wp triangle inequality)
S 4 + 4pp + 2pv.
(Lemma
as desired.
This gives information-theoreee reduction from kernel estimation under Ep estimation of μ and y under W,. i.e., if we can estimate μ up to eπror Pa and v up to eπror Pv. then we can find a kernel first apply Theorem
with error OLLp + Pu + Pv). Focusing on the Lipschitz case with a using the plug-in estimators μ = Pn.
Dn.
Corollary 1 (Plug-in estimators). Under Assumption ] with a = and L = 0(1), suppose H.U. E (R.(( Then taking ja = ft, and = Un. P can be tuned achieve Ep Ep H. Opa(n -1/dV2p)) with probability 0.9, which is minimax optimal up to logarithmic factors.
Plugging in p = 2. we recover the I,2 rate of Balakrishnan and Manole (025): however, this result holds under significantly weaker assumption and for general p 1. If further ia and are compactly supported with smooth densities, we can employ wavelet-based distribution estimators (see, e.g., Weed and Berthet (2019), Manole al. (2024) attain faster rates.
Corollary 2 (Wavelet estimators). Under Assumption with = 1 and L = O(), suppose that H.VE E P(00, 1)d) admit Lebesgue densities f.g g E (*0, 11.) Then taking ji and i as appropriate wavelet-based estimators, one tune ō to achieve & (R: with probability 0.9, which is minimax optimal up to logarithmic factors.
Opa(n Opa((nI(L+s/vi) [[+++/////((++))////)))))
Balakrishnan and Manole 2025 also reduce map estimation distribution estimation, so they prove a variety of similar guarantees. However, unlike our derivation, their analysis relies crucially on the structure of the Brenier map as the gradient of sufficiently regular convex potential.
Remark 4 (Lipschitz regularization). Wasserstein DRO is known to be closely related to Lipschitz regularization (see, e.g., Gao et al., (022). So perhaps expectedly, one can show for p = a = 1 that the guarantees of ÂDRO are matched by the estimator which minimizes the regularized empirical risk k + & (k:; üi 0) + A Lip(x + Ky; W.). For deterministic map estimation, González-San et al. [002]] considered related neural estimators that enforced Lipschitz constraints on the estimated map. In general, minimizing the unregularized empirical risk ε or, by Lemma 2 the corresponding Monge gap objective, achieves good rates whenever the obtained minimizer has small Lipschitz constant (whether this arises due to explicit constraints or implicit optimization bias). This gives a partial explanation for the empirical success of the Monge gap regularizer for neural map estimation.
5 Robust Estimation with Adversarial Corruptions
The previous sections allowed us to handle sampling error under Ep. We now address local and global adversarial perturbations of the data points with minimal technical overhead, thanks to the strong stability properties of & in both TV and W,.
Formal corruption model and assumptions. As discussed in the introduction, TV and Wp perturba- tions have historically been studied separately in robust statistics to model outliers and adversarial examples, respectively, with the former dating back to Huber [1964]. Our work adopts recent combined model permitting both local and global perturbations of the input data [Nictert et al. 2023b). Here, clean i.i.d. data from the unknown distributions fa P(X))) and E P()') are first nudged by small local perturbations (namely, in Wasserstein distance with budget 2 0) and then partially overwritten by global outliers (in TV, with allowed fraction [0, 1). More precisely, letting
X X1...., Xn. itd.
μ and Y1, .I...., Yn / denote the clean samples, observe K,...,K,, X and
iid.
8

---

Pi..... F, E 3 such that 2,2 EiEs |X XiIl" V A EiET |X, -x,l I p" for some S,T S [n]] with |51,17] 2 (1 E)m.
Write An: Mi, and 8x,, fn, for the clean and corrupted empirical measures for μ and v, respectively. We further suppose that μ is I-sub-Gaussian and y C [0, 1J.. These assumptions can be relaxed at the cost of estimation complexity, as in Section We impose them to focus on the new aspects of adversarial robustness without distractions.
An initial idea is to combine the Section Slpprocchss,, since the entropic kernel used W, stability and the rounding estimator used TV stability. This is viable, however our entropic kernel analysis requires that X' U U is bounded. To avoid this, we employ a similar approach to the rounding estimator, but replace deterministic rounding with Gaussian convolution. Defining the kernel N N Naxx, a² Ta) and letting K > 3] denote (any) optimal kernel for the Wy(a, 3) problem, we consider
Aeone Iin 1/ = KG P. - 1 o N
That is, we find an optimal kernel for the convolved (P ih, in)) problem and compose it with the convolution kernel. The initial convolution of ür ensures that the inner kernel is defined over all of R. potentially outside the support of A., The subsequent composition ensures that the outer kemel sufficiently continuous, as needed to apply Lemma We prove the following in Appendix D
Theorem (Robust estimation guarantee). Under the setting above, we have
(Renni S Vdek + vdputs + P - Op,a(n -das))
for tumed a = (p, d, d.p). Also, the naive estimator (Fmalt)s = 6n satisfies (f v) S Vd. By selecting between the two estimators according which bound is smaller, we achieve an error bound of (vde* + vāpzts + p Opa(n )тक>) A Vd. Moreover up to constants, no estimator can achieve worst-case expected error less than (vde+ + +d1/4p1/2 + (v2s) vd.
The upper bound follows by a remarkably straightforward application of our stability lemmas. For the d=/4 p1/2 term in the L.B, we construct a pair of instances (with all distributions supported on two points) which are indistinguishable from p-corrupted samples and such that kernel achieves error o(d2/4 2/2) on both. Interestingly, this vp dependence rules out lossless reduction from estimation under Ep to distribution estimation under Wp- That is, our rounding estimator from Section (
achieves Ep ((n-1/(4+2p) but the guarantee that Wp pa) V Wp(Pn. alone cannot imply a rate faster than Ö(n 11/2d44)))) Finally, although the convolved OT problem for our estimator may not be efficiently solvable, we show in Appendix D that an additional rounding
step enables efficient computation, mirroring the proof of Theorem 2
Experiments
To empirically validate theory, irregularities limit the utility of the L objective and prevent application of cxisting theory. For Setting A, we fix y and uniform discrete measures over N 2000 points, obtained as i.i.d. samples from Uni x [0, 1]d-1) and 1
experiments in two synthetic settings with OT maps whose
2 Unif([-13 x [0, 1]d-1) + 2 Unif((1} x [0. 10,1)_1),, respectively. In the N + limit, the optimal kernel satisfies K ((0.22.4) Unif([(-1,, 11, (1, (1,z) For our discrete μ and v, there an optimal deterministic map T induced by permutation, but it is highly oscillatory. For Setting B. we set μ and as discrete distributions over N samples from Uni 11()) and ft Unif([-1, 1J(), respectively, where f(x) x + (sign(z1),... ( pushes each orthant of the cube away from the origin. Here, the OT map discontinuous but Lipschitz within each orthant.
Now, for each setting and sample size n E {10, 20,..., 100), we take n i.i.d. samples from ju and v and compute the kernel estimate & ground (Section 3). (Specifically, the NN estimator first computes an optimal W1 map T, from (n, to i Then, ANN maps each x E Rdd to the image of its nearest source point under T,,) We then compute the L' error |! I and the E errors E (fNN, jr, v). & (Around; μr, v). Since fa and v are discrete, these can be computed using finite sums and the default Python Optimal Transport solver (Flamary et al. 2.21]. Repeating this process for K = 100 iterations, we compute mean errors for each sample size and dimension d E {3. 5, 10), along with bootstrapped 10% and 90% quantiles (via 1000 bootstrap resamples). In Figure 3 (left), compare the E, L
nearest-neighhor map estimate TNN [Manole et al.) 2024 and the rounding

---

L: for NN Estimator (Secting
Es: Rounding (Setting
E:: NN Rounding (Setting
100
Emer
d-3
10
d-2. NN
6-2.
NN
11
rounding
rounding
NN
10a
1x
rounding
rourding
6-10,
3-10. NN
6-10. NN
2x
rounding
rounding
10P
10a
10a
10P
10
10
( samples]
(A samples]
n samples)
Figure 3: &L and L performance of neirest-n and rounding estimators in two settings.
performance of the NN estimator under Setting A (where the latter is well-defined since each NN is a deterministic map). As expected, L performance is quite poor, with error always greater than Although we currently lack formal guarantees for the NN estimator (and our setting lies outside of existing theory), it achieves strong & performance, with faster rates in lower dimensions. In Figure Tigure (center), we compare the NN and rounding estimators under &,, the latter enjoying formal Empirically, the NN estimator performs better, but this gap diminishes in high dimensions. We suspect that low-dimensional performance of the rounding estimator is more sensitive its side-length hyperparameter, which we have simply set n 1/((+))) as per the proof of e Theorem 2 Finally, in Figure 3 (right) we turn to Setting B, again comparing PNN and ground under n E, and observing similar trends. We note that all experiments were performed on an MI MacBook Air with 16GB RAM and 8 CPU cores. See Appendix for full experiment details and two additional experiments (one with larger parameter settings, but no bootstrapping. and one in two dimensions, so that our estimator can be visualized).
guarantees by Theorem 2
Remark 5 (Neural map estimation). Given the connections between Ey and the Monge gap objective discussed in Sections [ and [2] one could consider training neural map estimator to minimize an empirical E, objective, perhaps after approximating the W, terms via EOT. However, while both E, and the Monge gap objective nullify on optimal maps, they behave quite differently when far from optimality. Indeed, gradients of the feasibility gap term in Ep push towards the identity map (since it achieves the minimum transport cost of zero), while gradients of the Monge gap push towards the much larger set of c-cyclically monotone maps. In preliminary tests, we found that the Monge gap objective led to significantly more stable training dynamics, which we attribute to this difference. Thus, we maintain our recommendation of Ep as evaluation metric, enabling provable error guarantees under weaker assumptions, rather than training objective for neural map estimation. Still, we hope that our analysis under Ep might inspire regularization methods in the future.
7 Discussion
This work proposed a novel error metric Ep which broadens the scope of OT map estimation research to support stochastic maps, sidestepping existence, uniqueness, and regularity issues faced by existing approaches and treating p # We developed an efficient rounding estimator with near-optimal rates under E, and characterized the minimax rate for Lipschitz continuous kernels. Our analysis extends naturally to adversarial corruptions, and our theory is supported by numerical simulations.
There are two clear open questions. First, what is the minimax finite-sample risk for estimation under Ep, say for Jl, v E P(0, 1]d) We have established that the correct rate lies between n - 1/(v2pp) and n 2p/ The slower rate mirrors that attained by bounding ( 14)] without analyzing sampling error multiple geometric scales. Can multi-scale approach extend to kernel estimation and improve the current upper bound in Section 3 Second, under the setting of Section 4 with a = 1, where there exists an optimal Lipschitz kernel, can a computationally efficient estimator achieve the optimal 1/(v2pp) rate? Our experiments demonstrate strong empirical performance of the NN estimator in varied settings, so it seems to be a promising candidate to attain such a guarantee.
Finally, our objective can naturally be extended to many OT variants, including EOT, weak OT [Gozlan et al. [017], conditional OT (Hosseini et al., 2205), and adapted OT [Bartl et al. 2024]. Adapting our toolkit of stability lemmas to such settings an interesting direction for future work.
10

---

Acknowledgments and Disclosure of Funding
Goldfeld is partially supported by NSF grants CCF-2046018, DMS-2210368, and CCF-2308446, and the IBM Academic Award.
References
S. Balakrishnan and T. Manole. Stability bounds for smooth optimal transport maps and their statistical implications. arXiv preprint 1rXiv:2502.12326, 2025.
D. Bartl, M. Beiglböck, and G. Pammer. The Wasserstein space of stochastic processes. Journal of the European Mathematical Society, 2024.
Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communica- tions on pure and applied mathematics, 44(4):375-417 1991.
C. Bunne, S. G. Stark, G. Gut, J. S. Del Castillo, M. Levesque, K.-V. Lehmann, L. Pelkmans, A. Krause, and G. Rätsch, Learning single-cell perturbation responses using neural optimal transport. Nature methods, 20(11):1559-176 2023.
Chao and E. Dobriban. Statistical estimation under distribution shift: Wasserstein perturbations and minimax theory. arXiv preprint arXiv:2308. 01883, 2023.
N. Courty, R. Flamary, A. Habrard, and A. Rakotomamoniy. Optimal transport for domain adaptation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 39(9):1853-186; 2017, doi: 10.1 20.1009//AMM.201..2266
M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems (NeurIPS), 2013.
N. Deb, P. Ghosal, and B. Sen. Rates of estimation of optimal transport maps using plug-in estimators via barycentric projections. Advances in Neural Information Processing Systems, 34:29736-29753, 2021.
R. Flamary, N. Courty, A. Gramfort, M. Alaya, A. Boisbunon, S. Chambon, L. Chapel, A. Corenflos, K. Fatras, N. Fournier, L. Gautheron, N. T. Gayraud, H. Janati, A. Rakotomamonjy. Redko, A. Rolet, A. Schutz, V. Seguy, D. Sutherland, R. Tavenard, A. Tong, and T. Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
R. Gao, X. Chen, and A. J. Kleywegt. Wasserstein distributionally robust optimization and variation regularization. Operations Research (Forthcoming). 2022.
A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyré. Sample complexity of sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics (AISTA7S), pages 1577-1583, 2019.
Z. Goldfeld, K. Greenewald, J. Niles Weed, and Y. Polyanskiy, Convergence of smoothed empirical measures with applications to entropy estimation. IEEE Transactions on Information Theory, 66 11:4368-4391 2020.
A. González-Sanz L. De Lara, L. Béthune, and J.-M. Loubes. Gan estimation of lipschitz optimal transport maps. arXiv preprint arXiv:2202.07665, 2022.
N. Gozlan, C. Roberto, P.-M. Samson, and P. Tetali. Kantorovich duality for general transport costs and applications. Journal of Functional Analysis, 273(11):3327-344) 2017.
B. Hosseini, A. W. Hsu, and Taghvaei. Conditional optimal transport on function spaces. SIAM/ASA Journal on Uncertainty Quantification, 13(1):304-333 2025.
Huber. Robust Estimation Location Parameter. The Annals of Mathematical Statistics, 35 (1):73-101, 1964.
J.-C. Hütter and P. Rigollet. Minimax estimation of smooth optimal transport maps. 2021.

---

L. V. Kantorovich. On the translocation of masses. In Doklady Akademii Nauk USSR, volume 37, pages 199-201, 1942.
N. Kolkin, J. Salavon, and G. Shakhnarovich. Style transfer by relaxed optimal transport and self- similarity. In Proceedings the pages 10051-10060, 2019.
the IEEE/CVF conference computer vision and pattern recognition,
A. Korotin, D. Selikhanovych, and E. Burnaev. Kernel neural optimal transport. In International Conference on Learning Representations (ICLR), 2023a.
A. Korotin, D. Selikhanovych, and E. Burnaev. Neural optimal transport. International Conference Learning Representations (ICLR), 2023b.
J. Lei. Convergence and concentration of empirical measures under Wasserstein distance in un- bounded functional spaces. Bernoulli, 26(1):767-798, 2020.
W. Li and R. H. Nochetto. Quantitative stabilitt and error estimates for optimal transport plans. IMA Journal of Numerical Analysis, 41(3):1941-1963 2021.
Z. Liu and P.-L. Loh. Robust W-GAN- estimation under Wasserstein contamination. Information and Inference: A Journal of the IMA, 12(1):312-362, 2023.
Y. Luo, Y. Xie, and X. Huo. Improved rate of first order algorithms for entropic optimal transport. In International Conference Artificial Intelligence and Statistics, pages 3723-2750) PMLR, 2023.
Manole, S. Balakrishnan, J. Niles-Weed, and L. Wasserman. Plugin estimation of smooth optimal transport maps, The Annals of Statistics, 52(3):966-998, 2024.
P. Massart. The tight constant in the dvorettky--iiefer-wollwiii inequality. The Annals of Probability, pages 1269-1283, 1990.
C. Meng, Y. Ke. J. Zhang, M. Zhang, W. Zhong, and P. Ma. Large-scale optimal transport map estimation using projection pursuit. Advances Neural Information Processing Systems, 32, 2019.
Y. Mroueh. Wasserstein style transfer. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
S. Nietert, R. Cummings, and Z. Goldfeld. Robust estimation under the Wasserstein distance. arXiv preprint arXiv:2302.0/237, 2023a.
S. Nietert, Z. Goldfeld, and S. Shafiee. Outlier-robust Wasserstein DRO. In Advances in Neural Information Processing Systems, 2023b.
S. Nietert, Z. Goldfeld, and S. Shafiee. Robust distribution estimation with local and global adversarial corruptions. In Conference on Learning Theory (COLT), 2024.
Pittas and Pensia. Optimal robust estimation under local and global corruptions: Stronger adversary and smaller error. arXiv preprint arXiv:2410.1720 2024.
A.-A. Pooladian and J. Niles- Entropic estimation of optimal transport maps. arXiv preprint arXiv:2109. /2004, 2021.
A.-A. Pooladian, V. Divol, and J. Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In International Conference on Machine Learning, pages 28128- 28150. PMLR, 2023.
A. Redko, N. Courty, R. Flamary, and D. Tuia. Optimal transport for multi-source domain adap- tation. International Journal of Computer Vision, 19233199233,993, 2019. doi: 10.1007) sl 111263011-1116-4
Rigollet. 18.5997:
High dimensional statistics lecture notes.
https://ocw
mit mit.edu///eee X1B244222221000000777292222222 B1101__MM11111__1111110 S997S15 CourseNotes. 2015. Lecture
2015/
notes for MIT course 18.5997, Spring 2015.
12

---

F. Santambrogio. Optimal Transport for Applied Mathematicians. Birkhäuser, 2015.
G. Schiebinger, J. Shu, B. T. Tabaka, J. Ashouri, D. J. Cleary, V. Subramanian, and et al. Optimal- transport analysis of single-cell gene expression identifies developmental trajectories reprogram- ming. Cell, 176(4):28-943.e))
2019, doi: ce000//.ee...211.011...
V. Seguy, B. B. Damodaran, R. Flamary, N. Courty, A. Rolet, and M. Blondel. Large scale optimal transport and mapping estimation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings, 2018.
S. Singh and Póczos. Minimax distribution estimation in Wasserstein distance. arXiv preprint arXiv:1802.08855 2018.
D. Toneian. Measurable selection in optimal transport and Skorokhod embeddings. PhD thesis, Wien, 2019.
Uscidda and M. Cuturi. The monge gap: A regularizer to learn all transport maps. International Conference Machine Learning (ICML), 2023.
N. Vesseron, L. Béthune, and M. Cuturi. Sample and map from single convex potential: Generation using conjugate moment measures. arXiv preprint 2.kiv:2503.10577 2025.
C. Villani. Topics in Optimal Transportation. Graduate Studies in Mathematics, American Mathe- matical Society, 2003.
Wang and Z. Goldfeld. Neural estimation of entropic optimal transport. In IEEE International Symposium on Information Theeory (ISTT-2024), 2024.
J. Weed and Q. Berthet. Estimation of smooth densities in Wasserstein distance. In Conference Learning Theory (COLT), 2019.
L. Zhang, L. Wang, et al. Monge-ampleer flow for generative modeling. 1809. 10188, 2018.
arXiv preprint
B. Zhu, Jiao, and Steinhardt. Generalized resilience and robust statistics. The Annals of Statistics, 50(4):2256 2283, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, we summarized the key aspects of our new framework, our new results in this setting, and our accompanying experiments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We fully state all assumptions and describe two main open questions in the conclusion.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
All formal claims have precise statements and full proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All such details appear in the experiments section and accompanying appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
All data synthetic and full code provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/ppulli//guu /tte://uuuddeeoooouuuubmmiibia ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Our experiments section and appendix are comprehensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide error bars and explain how they are produced via bootstrapping.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: These details appear in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://wwwrrrrrooo///////ccsshaa
Answer: [Yes]
Justification: We abide by the ethics code.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work primarily theoretical and does not have any clear or immediate societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurd/: /00p://ccc...cc.eeeee//////////0 for what should or should not be described.
20

---

A Proofs for Section 2
A.1 Proof of Proposition
Clearly, (K; μ1, v/ = if i. minimizes (2). On the other hand, if (K, (,v) O, then Kz/u = V. Thus, K is feasible for ( with optimal objective value, i.e. it is minimizer.
Further, T* is an optimal map, then Wp(,.v) = | Id (1 and Tÿ pu== u. We thus bound
p,,) |||T Id [|(())) Wplm, 20 + Wp(Tsp.
[IIT ld (L)())) -|7 - Td [xp(W)] + Wp(Ta,,T?N)
s T 7 ((P))))))
as desired.
A.2 Reverse 2 comparison (Remark)
Suppose that there exists unique Brenier map of the form T* Vy, where &p IR + I is convex and twice differentiable such that Hi Lla. Fixing any map T + y, we abbreviate (2(T; uz, v). By the definition of Eg, we have W2(Tzu, S Let À K()), )/) be kernel
which achieves this bound, and take x oo T. By construction, we have Kgll = v and
/ My =((dn(ulo)dp(()) $
-W2(u,) (ʃʃ [ 2 =0(/d((s)) -W2(u, v)
S 2E.
Consequently, have
Jf [ly =1Bdm(o)))d((())) W2(u, 2)² s 28 (Jʃ [ly - x ==Pam(olo)ddttt)) + Wacnne))
2 (2W2 + 2s)
Thus, by Proposition 3.1 Li and Nochetto 2021 }, we have
/f
Te s L (lʃ lly - x =(ddn(ll=)d((a) W2(H, 133
s 4T. (W2(H, v) + 8).
Finally, we bound
IT - --.1.ll < (/ʃ Ilv ( +
I / ALE +E)
(LV1) (W2(H,
as desired,
21

---

A.3 Proof of Lemma 2
First, we bound Ep in terms of En. computing
(1; |ly =I| =lIddau 3
(pp(a v)
(Wp(T,,,
x [JS [1v - = = -Wp(u,
+ 22Wp(Teu,)) v)
< [// 11y - =0 Wy(n, Tan)p
+ 2W 2W,((T
= [ʃ] 11 - (u==Ildd - Wp(a,Tau))
+ +2,p(Tuu,))
< 2²2- [1y - =llx
- "p(,)Te)) + Wp(TeN,
<2- $ (k: (e::ppp00 p,v)
where the second inequality uses that [a /p 1iip-bb/pp bb/p]+ S [a - 6/ for all a, b 2 0, and the penultimate inequality uses that f s 22/p1 in IR2. This implies the claimed bound of Ep S 48% When p = the above gives & s 2Ei, and we similarly bound
// [ly - = (w)p((() WI(H. + W, (TgH.2)
(k: p,
[/] 1ly x =ldda=())dd)(()) Wi Trn)
[f ll ==Ildk(()()dp()) Walce
+ +2W,(TTp,.)
S 28, p.))
as desired.
A.4
Proof of Lemma
We simply bound
(e Ey (1, v'1 s (W(u, Wy(m, e/), (W)(spp) - (y
< 2W,((,,'))
< 22diam)))ll -V'lTv,
where the final inequality uses Fact
A.5 Proof of Lemma 4
While the key ideas of this proof are straightforward, measurability issues require some care (we encourage the reader to skip such details
initial read). In what follows, we equip all spaces of distributions with the weak topology and always employ Borel measurability. By the definition of Markov kernel, x E X'
(A) is a measurable function for each measurable A C y. Thus, (x. E X² + (Rz (A), Ker (B) is measurable for fixed, measurable A, B C ), implying that (x. .²) X² - (Kz, R ) P())) is measurable. Therefore, by Theorem 3.0.8 Toneian [2019]. ) there exists a measurable map (Ir x') E X22 + "iz,'' E [[Kx,, Kar) such that a is an OT plan for Wp,(Kn, k.r)) for all x. x' E X.
Now, let To E [[(H, p²) be an OT plan for Wy u²), and define the joint law x by 7(A x B C D) = MsxX Ne. (C x D)dTo(z, x')), which is well-defined due to the measurability argument above. Taking (X, Y, Y') n, our construction ensures the following:
22

---

X ~ je and X' ~ pl such that E|||X - x1 = p",
xx and Y xx such that E| x = Wx(
Consequently, bound
B - = E[E[IY X
= EE| (FX,
S
(Hölder continuity of st)
- L' B
(Jensen's 's inequality, < a S 1)
Moreover, using Minkoswki's inequality, we compute
B[JlY - - -EIII' x1112 s E|J|X - X'II1 - y'1l s p Lpp
Finally, we bound [Wplu, -W,l', S Wplu, /4) S P and
(K(Ki)) Wp(Kipd' v) (P((Fau, S B[IlY- - s Lpp.
The definition of Ep and these bounds give the lemma.
A.6 Proof of Lemma
To show this result, we prove slightly more general lemma.
Fix p. E P(X), EE (())), and kernel k K(XX y) with Wplu, kaprp + 78 and (n(KFH, T for some T 2 0. Then, setting = || μ w/llTV. we have Ep(m: < diam))))) 1/p + 3r.
Lemma
s
Proof. In what follows, encourage the reader to focus the p 1 case, where computations are more direct. Write e = || / |Tv. By the TV bound, there exist a. 3, E M (X') with ((x)= =1 and (xx) (x) such that μ = 7 + a and y 7 B.
First, we note that x must perform well on y. Specifically, we have
|/ || (d) (v))
/ʃ |/= - yII wIPdna()dd(())) - /f || y/l y1(ddx(()dda(z)
(7 a)
Wolm, KEH)P +7" -Wp(a,
(error bound for def. of Wp)
<WoTT WP(TsAA77)" Wa(a, - WP-WW,a,, (p(ak,Kaa)
= 7
WD)(T +7"
(Wp(7, +T)²
(l, $1)
23

---

Now, letting x' be an optimal kernel for the Wy(n', problem and writing D = diamm()) we have
[ lly =I (x)
Wp((',v)
= -(ʃ llv -|| =
(ll 11 1 $
=
(optimality of
(/ I1 - =1l==lldd /ʃ - =l===
- 9)
(/ l1 - = /ʃ - - $
([U/ [10 -
- -1f1lo- - 177
[[/ 11 (vy==(/dxx,,))d3(c)) (ʃʃ I
+T
[[/ b1 - [l===//drcc(w))B(aaa
// ly (1)dd((()))())
#
(Wo((e7)(4))) + +))²+ ||]
(Pd |1 y' (v/ (1')(())
((W,(M)))) (47) +) + +EDD)$
(Fact !
(W,(k) K()) + De
(Cp E1)
The first inequality uses that (AP + BP)1/P - (aP + bP) < ([A alF + BB- 2/ which can The
be obtained by rearranging the Ep triangle inequality and using that A [A a] + second inequality uses the previous bound and the fact that k' is feasible for the W x(7) problem. The third uses the W, triangle inequality and Minkoswki's inequality.
We next bound W, (K47, k(n)) Let I[(z,, M) be optimal plan for (p(KzH, and define A (1 e)P()) by X(-) I (+)))))d)x))) By construction, (K A) S (p(Kyp, v) Moreover, both À and Kÿ7 are submeasures of y with mass E, and so they must share common mass at least 2s. This implies that their TV distance at most E, and so Fact gives that
Wp m47) <T W,(A, k47) < Det.
(8)
Thus, the previous bound on the optimality gap can be tightened to
(ʃf - [w===
Similarly, bound the feasibility gap by
W (p 2/p
Wp(K47 + neB, ReB 14,3)p
(1' = 7 B, v)
Wp + (P K(P < nd + (T + D
(joint convexity of Wg)
(Fact and Eq. 8
$ (27 + DEŽtO
(lp S A
Combining, have that Ep(:: n², v) < 37 + 1/P, as desired.
24

---

A.7 Proof of Lemma 6
First, we note that (ig()p)) (k N)a by the definition of kernel composition. This implies that the two feasibility gaps coincide. Moreover, by Minkowski's inequality, we have
[/] ly =II"dx=
(sʃ Ilv
(/fllv==/Padee =I1'd(k ))x(v)d((x))
(// ||= (3 =))dd(())d)((())
and
(W Wplu, & Wplu, Aaa)) S (fʃ (lIPdd(()
Combining these two error bounds gives the lemma.
B Proofs for Section 3
B.1 Proof of Theorem 1
By the support constraint, cost ||x w/12 is pcll- over X' V. Thus, by Theorem
1 of Genevay et al. 2019]. we have
Sp.r Pn) S Wp 2r + 27d (odeepdd/222
Since क.. achieves the left hand side above and KI. divergence is non-negative, have
|| f "ll
& Wpliin Da) + 2rd (ellool(pppP 2rdlog(e-puP/
Taking pth roots and noting that (Rn) Dn. this implies that
(e Epii Pms Pn) & 22d 22 (1-22-17-1) 1-1]] s 4(Td)} log(e"dr dr
Now, by 77. (Ra)z is obtained by applying softmax to v(x) = ((gr (Y;) - 1|- Y. P)1))) ER"
Since the E,, foo Lipschitz constant of the softmax operation is S 1, we have
(1(rm)2 (Rn)w/lIV I = (1l(()) - v(2')ll S 1) - x'112
for all x, [0, 1]d. Thus, by Fact I Rn is Hölder continuous under Wp with exponent 1/p and
constant 2/dr-1/2 Applying Lemma now gives
Ep(Kni u1 s Ep (, Pa) + Wp(Cn,u)
En Pins Pn) + (W, (V, Wp(u, < 4(rd) log(e"dr + 4Wd - + 2W, Rn)) + Wp(u,
Taking expectations, applying
appllyig Lemma] 1 and plugging gives the theorem.
B.2 Minimax Lower Bound under Sampling
Fix μ do. so that the constant kernel defined by Ko v/is optimal. Note that the error Ep (k: p, 1/) of any kernel x is thus lower bounded by the feasibility gap (r v). Since we only observe i.i.d. samples from an upper bound for namample distribution estimation of under Wy. However, the minimax lower bound of [Singh and Póczos (2018) implies that no distribution estimator can achieve W, error less than -1/(2vd] for all 1)0,1)
P[0, 1] any upper bound on an estimator for this problem instance also gives
25

---

B.3 Proof of Theorem 2
We start with some helpful lemmas.
Lemma 8 (Rigollet 2015), Theorem 1.14), Let μr E P(R) be -sub-Gaussian, Then, for X1, 12...... Xx sampled i..dd from μt, we have maxi=l,....n X, S (ogg(())))) with probability at least 1
Lemma 9. Let P(RR)) be I-sub-Gaussiag and let P denote the regular partition of TR. into cubes of side-length r 0. Then, for any choice of rounding map Tp, we have
(1 154m
Bll((r))<(A> x][[T]] = =
n1
Proof. Let denote ball of radius R = v log(n) centered at the origin, so that p( 2 1/n by Lemma 8. Write Pn for the subset of partition blocks P P which intersect B, and note that |Pal S vol $ (3R/r) We then bound
1 Blll(r))<(An WllT
=
E
(Ann -]]
2
PEP
1
E
(1in x)PP++
Σ
Klin -M)(P)
2
PEPR
PEPiPR
Pn
I
Σ Pn(P) + m(P)
PEPiPR
Pn
+ IRR" B)
(3 2 log (1) )dy jdy-d
24
5
as desired.
Lemma 10. There exists a partition P parameterized by 8 > 0 such that, for all μ E ((TR.) with E, [|] < 1 and any rounding map rp, we have [[]l rvll = Ö ///d//n and [|rp - ld Le(w)> S 6.
Proof. Let No be minimal -coverig of the unit ball, denoted So. In particular, this implies that [Xol < 8-d, Now, take Pu to be the Voronoi partition of So induced by Xu, so that Po has at most 5-4 cells of diameter most 65. Then for each integer >> 0, set S; = 2' 2 So. and let P. be the dilated partition ((2'P) n S, P E Poj. By construction, [P.] < 8-d and each P E P. Moreover, by Markov's inequality, we have
has diameter at most 2 66, for all
((S)) < Pr > 1 = Pr(IX 2(++1)6-1) < 2( (1100((+1)
26

---

for each 1>>0000000 0. We thus bound
20
Bll((p))((
- =
1(u - (-)
PEP:
0= PEP:
vu(P)
i= PEP:
(P.))(())
S <60'))+
1+ Σ 2
i=1
S (68
Similarly, we bound
|rp Id (dll) x
(PP) diam
1=0 PEP:
$
8
(2' 66) (((:)
1=0
1
Σ
20+1-1
1=0
2 6,
as desired.
We now prove the theorem. First, note that for D /4log(n), we have max;= ||||| < DS with probability at least 1/n, by Lemma Now, for a general partition P. we bound
(p M4 v) = (k, orp; 14, v)
s EKiini pl, v) + 2 ||r Id (()))))
(Lemma 6
s Ey nL, (m)) + ||r - ld (e)(())) + (v, Dn))
(Lemmal
2 (((r))((-(p))) P diam(supp((a)) 5 + ||rp Id (d|le)))) + Wp(y, in),
where the last inequality follows by Lemma and our choice of kn. Applying this bound for the regular cube partition and taking expectations, we bound
(R v)] & D
+ + 5 + +dr Wp(v,Dn)
54p- + 8b + Vdr Ōp(n -aaa)))))
54
(Lemmas and
72
Taking r -1/(d+pp)) we obtain EiE, 1u, v) Ô (p 11((4+2p)) + 81/p. The same rate is obtained under bounded 2pth moments by using the alternative partition from Lemma [0 Thus, to achieve the desired rate, it suffices to solve the preliminary OT problem to accuracy = p/((+2))
Computational complexity is dominated by this OT computation. The source and target distributions are both supported points, and we require accuracy ō n -P/(42pp) Computing the relevant
27

---

cost matrix requires time Onn²d). Using a state of the art OT solver based on entropic OT (e.g., Luo et al. 2023) gives running time of O n²//n///)) /8) = n2 where Coc is the largest distance between a source point and target point.
B.4
One-Dimensional Refinements (Remark
In one dimension, OT maps can expressed concisely in terms of CDFs; in particular, if y and have strictly increasing CDFs F2 and Fu. respectively, then the map (x) (F)( solves the Wp(μ,1) 1/) problem for all p 2 1. As a result, many OT-based inference tasks become more analytically tractable when d = I, including map estimation. In fact, minor adjustments to folklore techniques imply that the optimal risk of n -1/(2p) is achievable when d = 1. We now provide clean derivation of this risk bound using the Kolmogorov-Sminng Smiiroo (KS) distance.
The KS distance is a useful alternative to the TV metric in one dimension, defined via || - vllks = SUPtER (1r v)0(0o 4D] F| Felloo. We always have || - v/lks S || - =/|TV, since || - TV can alternatively be expressed as supa meas. 1/ (A)]- A comparison with W, mirroring Fact[is is direct.
Lemma 11 (Wp-KS comparison). For v. P(O,, we have W) S Dil w 1/p
Proof. Writing F, G for the CDFs of and v, with generalized inverses F and G-1, we bound
W)(u, = / |F (w) -G G=1(w)
< DP-1 [ | (F- G Gu)(ul
DP-1 /0" [F(x) -(z))d( G(z)ldr
DLIl wllks.
Taking pth roots gives the statement.
The KS distance admits useful empirical convergence guarantees not shared by the TV distance. Fact 2 (KS empirical convergence, Massart 1990). For all μ E P(RR, [B[] in lkss] S $1/Vn.
Moreover, for fixed μ and there exists optimal kernel for W,, 2) (namely, based on CDFs as above), which near-optimal for all p' in a KS neighborhood of μu, as shown next.
Lemma 12 (KS corruptions in μ)) For x, C R. fix μ E ((2)) and v E P(Y). There exists an optimal kernel x* K(X,Y) for the (p(p,v) v) problem such that, for all μ¹ E PP(),, we have
; v) S diam ( 1/lls/
Proof. Write F. F', G. for the CDFs of 14, nL, and v, respectively, and let ε ||I y'llks
1'Ilo Write = diam(() and suppose without loss of generality that ) = [0. D). For now,
suppose further that 1/E = 3M is multiple of 3 (without loss of generality) and that F is continuous (which will be relaxed). We consider the kernel induced by the map T* G o F, where G-1 is the generalized inverse of G with G-) defined as 0 for q < 0 and 1 for q 2 1. In particular, we compare T" with the optimal kernel G-2 F" for the Wp , ,P) problem, bounding
[ IG G
GF G- (F) <
G (x)))
(u + - G (u)
3M-1
((it))=
Σ
G- - G G-
1=0
3M
< E Σ
( ()+ G 1)=)}²
0=0
28

---

Here, the first equality uses that Fig' Uni 1]), and the second inequality uses that G-1 is monotonic. is discontinuous, one should replace with the kernel f which coincides with F' where continuous and, at any point x where there is a jump from pi to p2, satisfies F/5 = Uni P2]). By this choice, we have F [ni 1)), and one can do the same for F to obtain F such that Wo (Fere, F2 S &. At this point, we can derive the same bound as above. Now, writing A, = G ((i 3) G (iE), we have
G (F(x)) ( G-
(F(())
3M 2
Σ
A
M
M
M-1
A
31
Σ
A
31
+
Σ
A
3i+1
1=
i=0
M
M
M
A 3i+1
+
+
D
D
t=0
i=Ul
A31-1
A3i
P
M
A34+1
<ED'
+
D
Y=
O(De
Thus, have (G Fi v) G G F' F'ller()) & De desired.
Together, the three results stated above yield our desired risk bound.
Proposition 2. Let XI,...,X, fn which, given ün and nn. returns the optimal kernel for Wp 2n) given by Lemma 12 achieves risk (Bni n1 v)]
Lid. ~ E P(R) and Vi....,,Y, lid VE P(OO, 11). Then the estimator
-111(2pp)))
Proof. By Fact 2 we have that E|ll - Pn lksl S n 1/2, Consequently, we bound
Ep u1 u,,) S (hin ,r, Dn)) + (p(u,
|| P.
1/p KS + W,, D,).
Taking expectations and applying Fact and and Lemma gives the desired rate.
Unfortunately, we are unaware any multivariate extension of the KS distance that obeys a useful comparison inequality with Wp (like Fact 11] while maintaining strong empirical convergence guarantees (like Fact inhibiting the further development of this approach.
C Additional Details for Section
We note that the minimax lower bounds in Corollaries [ and follow by combining the reduction to distribution estimation from Appendix B.2 with existing lower bounds for distribution estimation under W, from (Singh and Póczos 2018 and Weed and Berthet (2099 respectively.
D Proofs for Section
We first recall some basic facts used throughout.
Fact 3 (TV contraction under Markov kernels), For u. E P(X) and kernel x E K((,)) V), we have [|sy - kiyl/TTV |||| v||tv.
This follows by the data processing inequality.
29

---

Fact 4 (Wp contraction under convolution). For μ, E P(X), we have Wplusa, - Wp(p, v). where denotes convolution between probability measures.
This follows by considering the couplings (X + Z, Z') of and which set Z = Z'
Fact 5 (TV discrete empirical convergence). For a finite set S with [S] = k, any distribution (S) exhibits empirical convergence in TV at rate BlllA, mllTv] S /k/n.
To simplify discussion our corruption model, we employ the e-outlier- p- Wasserstein distance
Wo(n', (H, == min E IAllSel
min )'E(RR)) 1N'-vIlVVSe
Wp(k,
The second equality follows from the observation that, if Ef| YII S c and = probability at least E, then the random variable =1= - x + X1(X + X') satisfies E||X - [1] S c. See Nietert et al. [2023a] for thorough examination of W in the context of robust statisties. Under the setting of Section S our corruption model be equivalently stated as follows: given the standard empirical measures A., E P(t') and 0g P())), we observe corrupted versions Pn (()) and jr,, E PV)) such that Wş Pa) (5 Da) S p.
X' with
For this setting, we handle sampling error using the following lemma, which mirrors Lemma Lemma 13 (Prop. 2 of Goldfeld al. 2020). Fix > 0 and I-sub-Gaussian μ E ((RR). Then, the nasample empirical measure Pn satisfies E [l (n rr] S (3((1V=")//m
In order to apply our W, stability result, Lemma 4 we use that any kernel become continuous if one first applies Gaussian convolution.
Lemma 14. Fix R E K(X,V)) > 0, and let R No, Then, for all x, E X, we have Wp ( S diam()))lla -x' o/1l/(2)))
Proof. We simply compute
Wp(Ke, Rer) S diam (iam()))l<s{NN?? - -N2- NH
(Fact I
diam()")ll -N2
(data processing ineq.)
< diam()")[A((z, 0²(2) -N(x'' Ia)
diam()))]l= x' 2211'/p220)-
where the final inequality follows by the closed form of KI. divergence between Gaussians, combined with Pinsker's inequality.
We split the proof of Theorem into the upper bound (Appendix D.1 and lower bound (Ap- pendix D.2..
D.1 Proof of Theorem 4 (Upper Bound)
To start, decompose N No No N for 01, be tuned later. By corruption model, there exists an intermediate measure 1L, E P(R") such that || - pL, l| S and Wy,(hh ūnn) < p. By Facts 3 and 4 these bounds are preserved under convolution, so [|N (ūn - 16llTTV & s and W,(NP' pny No jnn) & p. By the TV triangle inequality, we have [INE (p -/.lllr S = + || (u (r... We conclude that WN(N;" ün, N, μ)) S p.
By the symmetric nature of WJ. there must also exist P(RR) such that W2(NT' H, a) S p and ||a - No* 1T TT.
Now set <g[NNf pm. - 7... so that (R NR Pn, Py)) O. Using this, the TV bound above, and the fact that No. in, (NN' Rn), we have (R; No a, in) S diam())) /r
Applying Lemma 6 this gives
( ( a pn) S Vdri +E2-wooo3u S Vdri vd+por
30

---

Consequently, by Lemma 4 and Lemma 14
we have that
Ep(R o N No u, v,) 2
p p pli
;a; p (V
$ vdri + (v 0/) / + Vd+
Tuning 02 gives
Ep o N u, Pn) S Vdri + vdp +p.
Apply Lemma once more, we bound
Ep(Ro N p. 2n) x vdr + Vdp + + vd+ po1
S v + Vdp +p+ v d pol Vd /dl (n Am)
Taking expectations and applying Lemma 13 yields
(REp(R No; ; ;,,,, S vdei + vdp +p+ / E Bi (μ p
( #
S dd + vdp +p+ p
Tuning ai then gives
o No; M, 1,)) S Vi + vdpati + p Opa(n atoy),
Finally, we note that Wp 2n) I p vde due to the support bound. Thus, Lemma gives
BiEp(R o No ; v) s (R o : (n)) Wn 2n) + (P((,.)))
S Bl No 1n)) vdsi + (
S Va + vdp + +p+ Op.(n ad2o),
as desired.
For the null estimator, let n² be an optimal kernel for the Wp(u,, v) problem and bound
E(Rmunii 1, = [//
=II'd [[]f -00-~111pp [
-
+ Wy(do,
1 [J] [1yl| Iulddnn())dd())) $7
WW(6o,
(Minkowski's inequality)
S 2vd.
( C [0, 10,
desired.
D.2 Proof of Theorem 4 (Lower Bound)
Since 1/r and n 1/(dv2p) are less than Vd, it suffices to prove a lower bound of Vds 1/24//2 A vd + n 1/(dv2p), We inherit the n 1/(v22p) sampling eтror term of the lower bound from the Dirac mass construction described in Appendix B.2] For the remaining terms, we prove lower bounds which hold even in the infinite-sample population limit, and even when only the source measure is corrupted. Here, an estimator can be viewed map A from P(X)) x P(Y) + KC(, }) mapping the corrupted source measure J4, guaranteed to satisfy WE (5 J1) S p. and the clean target measure v to kernel estimate Rifū, v). For X' Bd (which, in particular, forces each μ P(X) to and y
be
1] prove that
sup (((li, Vdst + pàdd A Vd. (EP(X)) REP(X) NEP()' W (م.
sup
The choice y 1Jdt rather than [0, 1 is solely to simplify notation in one of our constructions and can be revented without loss. Finally, it suffices to lower bound the supremum by v/d when 0 and Vdp A Vdd when 0, separately, which we do presently.
31

---

TV lower bound. Fix target measure y = (1 =)ou + Edg. where (1,...,)) .1) E R.. Consider the candidate clean measures μ4 and μl2 6g. Because they are within TV distance e, the observation ji is compatible with both candidates. Abbreviating & = Ri(a, u). we have
[// 11v =II' (1)) "
E1(K; + (x; z
Woluiees)
+Wo(ka(2)))
/ʃʃ 11v x1I'd Wp((zgdo.
2 (1 - +) (flolPdro(())
+ Wo(lipou, v)
2 5) Wo 0o) + +(1 (1-=))-Wp(a))) Wp(3000))) v)
2 (1 5) (80, v)
> (1 8) + vd
1
2P Vd.
Thus, we must have Ep v) V (x; Z Vde desired.
Wp lower bound. For the remaining bound, we first argue that, for any kernel i. its performance for the (,,,,)) problem cannot suffer much if we compose it with the Euclidean projection onto supp(v), denoted by projsupp(e)-
Lemma 15. For E P(X), E P()), and E K((,))) we have
Ep(projsupp()) oz; or. v) < (k;
Proof. Write = projsupp(v) and E,(K; Fix coupling X, Y. such that (X, sd,, Y v. and [B[| Z || = (y 2i S e". Taking Z' f(2), we then bound
E[[|X //1111// < Ei|| X 211211/2 + B|ll 2 - 7'/1i///
EIII //p + E - 1(2)
I Wpln, v) + + -- -
S Wp(() + 2c.
Similarly, we have
Wo(Kgu,)) < E - 11pp1//
< B 7 Y 1p + F[|l z 1'/1/1/0
< E + = 2E.
Thus, the sum of these two errors is at most 4s, as desired.
Now, fix target measure v 1/06g + 16. where y = (1,.... 1), and take e E [0, 1] to tuned later. Then, for each 0 < 1/2, define measure μ4, = (1/2 - 1)ō-ey
(1/2 + 1)8 Now, fix any kernel C((,' (+y]), where the codomain restriction is without loss of generality due
to Lemma 15 Note that its performance each μe is determined by the two-point distributions
32

---

R+ == Kity = (1 - a+ ( + a=dey. In particular. for 0 S t < 1/2, we compute
=
+ - l|llll
[[(11=)[1-c)++ +
Wp(KyMe; D)D
+ +
-Ily- -Ily-(-v)11 (wp((- Ber(a-) + (2 + Ber(a+). Ber ())
=(2d) (, + (3 +++) a+). Ber (
( }
WylSeys 14) [1(1-=/"/)"=((1-0011111
= ("(o0(00==""==aa)0t++===+
Wp(d-cy cy. Rー) (11++ l
= d (a_ (1 - (1-c)),,
|f [ly - 2lIddd (5
k_ + ( + f) W (dey: K+)
d [(2 t) (a (1 + c + (1 a1-
(1 c)P
+ ( - () - 0) + (1 - -1+
Writing a- - a.., we next bound
Wp(Kspte v) + Wp v)
V2d (2 t) +)a + (2 + ++++ - 2 + 2 - 211
2 22dt a+ - --1
(subadditivity of a + dP/P)
2d A
and we simplify
JI lly (x) = di
/1 -a+
(1+c)² + 1-a a_ +at (1 c)P)
2
2
/1+ A
1-4
= d
(1 + c)p
+
(1 c)p
2
2
Wp(Ho. = vd(1- cc.
Thus, we further bound
[/] |lv -:| x.Ipddxz (w)dkoo))))))()) Wp(Ho.u)
1 c)p
1+ A
1-A
(1 c)p
(1
- -1
2
2
Vd
1+ A
(1 + c)P
1-A
(1
c)p
-
2
2
33

---

Algorithm 1: Randomized Rounding for Efficient OT Kernel Estimation
Input: n. corrupted source points S _ Rd and target points T [ [0, 1] budgets 2 0, e E [0, 1]
1: m - n² -- n -1/(4+2), +- 34/(2+d) (nd)-1/(d-2) + +p-/2d
2: 5' - {projs (X² Zz) 1= where each X² ~ and ZN~NN are sampled independently
3: Compute kernel K E ((5"7)) s.t. Kg Uni((S") = Uni((T)
|| y v)ldR(ylæ) S WS""", +T
WES'
4: Return E (C(R, defined by A = R o projs o No
Combining, this gives
Ep(K: Pc. v) + Epp
Vd
1 +
(1+c)² + 1-A (1 - d)p (1-c)p
- -1+ v2dt 1
2
Vā
1+ A
(1+c) 1-A
(1 c)
- -1+ v2dt# A
2
2
VaclA + 1) + 2dtt
A//12)
vafc(1- (2]) + |/
2 // (//22
Now, supposing that p < Vd, we can safely take = t//r p1/2d-1/4/2 while ensuring that e E [0, 1] and t 1/2]. which were the only constraints on our construction. Otherwise, we take e= 11/p = 1/2. In either case, we have Wp (t) = f1/r 2ev/ (p A vī)/2 S p. Thus, the observation jı Mo is compatible with both μ 140 and μe under our corruption model. This gives the desired minimax lower bound of R(ydc A (1/2) 22dd// vd).
D.3 Efficient Computation
We now introduce Algorithm to achieve efficient computation, focusing on p = 1 where we match the rate of Theorem Here, we identify finite sets with their uniform distributions when convenient.
Theorem 5 (Efficient implementation). Under the setting of Section 5 with p = 1, the kernel matches
returned by Algorithm maathhhs the risk bound of Theorem Using an entropic OT solver for Step 3, Algorithm [ runs in time O((Cro + d)n)+ou(1)), where C.o maxi,j |X; Y, Moreover, & can evaluated (i.e., given x E we can sample Y ~ Ra)) in time O(nd).
The proof below employs similar analysis to that of Theorem 4 with multiple applications of Lemma to account for various sampling errors along with TV contamination. We restrict to p = due to the worsened scaling of Lemma 5 for p 1.
Proof. Set a Ng = projs a, and BT, = Uni By construction, S' is sampled i.i.d.
from B, Fact 5 gives that E[[] 9m Bmllrv] = B|Ei|| 3m [s'l Vn/m. Moreover,
(r)js(()) x=(dd(()) = Σ
projss( + +2) x + +>)==>= x1)dN*(=)
wEs"
Σ WES
|| x + +1|ldN
(# E S)
/1laIlAN((>)
2 Vdo.
34

---

Now, we restate our guarantee for A; namely, we have:
If - (ll=-vlla((/e)dBBmme S W1 Vnn) +
Thus, by Lemma 7 we have
(k; S vdll3 BmllTV
and, applying Lemma we obtain
Ei projs; a, in,) 2 vdll3 Bm lIv + Vdo.
Now, write j E P(R))) for an intermediate measure such that || BT S e and W, W Pn) S p. Noting that N2 Pa. have by Fact that ||a Nº pl p/llTV S E. Thus, Lemma gives
( o projs: No pha Bn) S dde + valls BallIV + vdo.
Applying Lemma 6 once more, we obtain
(R o projs N?? pla Pn) S vde + Vdll IT + Vdo.
By Lemma 14 the fact that this latest kernel begins with the convolution No/2 ensures that O(v L-Liscchitz w.t.t W1. Moreover, by Fact have WI(N, 1la / Ra) s Wi(k's Pm)) S p. Thus, Lemma gives
(R o projs oN N// (n. vde + vā BmlliV vdl + p+ Vdp
Next, we apply Lemma and Lemma to bound & (R projs NN; va)
28 (R o projs o /2/2 11 Un) + vdo
2 33 (k o projs / No/2 Mn: Dn)) Vdo Vdll/ fun)llTV
vdp vālls Bmllrv val Va Pn)l
<vde+ Vdo
Finally, we correct the target measure, using Lemma to bound
(K o projs No; ; n, v) < & (K o projg :N in, ;,, + (W,(
$ Vds + Vdo + vdp + Vd Bm +
Pn) + Wp(Pn, v)
Taking expectations, using our early bound on the first TV distance, and applying Lemma 13 for the second TV distance, and applying Lemma for the Wasserstein distance, obtain
El (R projg oN"; ;1,, v)
Svde+ Vdl + vdp
dn
d3d v vo-d//n + Cp.am pven log²
Our choice of a, m, and 7 ensure that the desired risk bound holds.
Computational complexity is dominated by the OT computation at Step 3. The source and target distributions are both supported n points, and we require accuracy 7 -dd((2+)) Computing the relevant cost matrix requires time (n) Using a state of the art OT solver based on entropic OT (e.g., Luo al., 2023) gives running time O(Cren²/T) 2(t=nn+) where C.o the largest distance between point in S and point in T. Combining these two gives the first bound. Evaluation complexity dominated by the projection step, which can be computed in brute-force manner using O(nd) time.
35

---

Rounding
malny Bounding
Peasibiiy Sept MN Rounding
H1
201 M4
1:11
Dets, M8
2-13 MM
Figure & (left), optimality gap (middle), and feasibility gap (right) performance of nearest- neighbor and rounding estimators for Setting A.
Samples Transport
sage
Sagel sertie nasppl
Destination of Source Under Ectimated Kemee tn 2003
munded muce
Sectraatoon tranperr pinn
Figure 5: Visual depiction of rounding kernel estimator on checkerboard dataset.
E
Additional Experiments
All code needed to reproduce our experiments and figures is available ltttss//giithu com/ sbnietert/mme wwtteert/apppeeeeeeeeeee est instimation Here, we include two additional experiments beyond those in the main body, one with higher dimensions and sample sizes, and one dimension two, for visualization.
First, in Figure 3, we repeat the Setting A experiments from Section (Figure 3 middle), but with N 10000, dimensions d (5, 10, 15), and sample sizes {100, 200,.... ... T000). To extend to these larger parameters, we reduced the number of iterations to T and omitted the bootstrapped error bars. Also, we include the decomposition components, the latter of which is measurably larger. As predicted by our analysis, our error rates worsen with dimension.
& into its optimality gap and feasibility gap
Finally, in Figure we provide a visual depiction of the rounding estimator on toy checkerboard dataset. In the top left, present souree measure (orange) and target measure (green). For the top right plot, we sampled n = 100 source and target samples, rounded the source samples onto a regular grid with side length = n 1/((++) (orange), and computed an OT plan (light blue) from the rounded source samples to the target samples (green). For the bottom left, rounded the full source distribution onto the same grid (orange), route these according to the same OT plan (light blue), reaching destination measure (red) that approximates the target distribution (green).
36


Reviews:
[{"review_id": "RioxULtyOA", "reviewer": "Reviewer_YnBD", "summary": "This paper develops a new theoretical framework for estimating _stochastic_ optimal transport (OT) maps. It broadens the classical deterministic Monge setting where OT maps existence is due to Brenier’s theorem, and it encompass scenarios where no unique deterministic map exists. Their framework relies on breaking down the estimation error into an _optimality gap_ (the excess transport cost over the true OT value) and a _feasibility gap_ (the Wasserstein distance between the map’s push-forward and the true target). \n\nThe analysis consists of breaking the overall error into two parts:\n\n- The optimality gap: This is characterized by studying the **entropic kernel estimator**, which is used to study the optimality gap, leveraging entropic OT with a bias–variance trade-off and its sample complexity has been studied by Genevay et al. 2019 and Peyre et al. 2013.\n- The feasibility gap: This is characterized by the **rounding estimator**, which discretizes the source, trims the target, solves a near-optimal discrete OT problem, then “rounds” back to the continuous domain. The sample complexity of this is analyzed Hölder continuous kernels.", "questions": "**Questions to the Authors**\n\nI think the work tackles an important problem of studying finite-sample bounds for stochastic OT problems. I have the following question:\n- As an OT practitioner, I have the following question, could the finite-sample rates inform how OT maps are parametrized and fitted?   Could you characterize the error functional (i.e. which error term dominates when) at different sample ranges? \n- Does this sample complexity bounds hold for conditional OT maps where there is a family of OT maps is fitted instead of a single one? If not, could the authors provide intuition on how it may generalize to conditional OT problems?", "limitations": "Not relevant", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is very well written.\n- Studies an important problem of characterizing OT maps when Brenier theorem does not hold, which is a common occurrence in real-world, finite-sample settings.\n- The proposed error functional is general, and it applies when no deterministic OT map exists, covering fully stochastic real-world settings common in domain adaptation and single-cell genomics.\n- Finite-sample upper bounds match minimax lower bounds under the assumption of sub-Gaussianity (or finite moments) without requiring density smoothness.\n- The stability lemmas for the error functional enable decouple the local (Wasserstein) and global (TV) robustness, yielding optimal rates under strong corruption models.\n- The rates are corroborated empirically. Both entropic and rounding estimators are implemented via existing entropic OT solvers or discrete OT routines.\n\n\n**Weaknesses**\n- None that I can point to. \n- Given my limited expertise in theory of OT, I cannot judge the novelty of the theoretical claims made in this work. I hope that the other reviewers and the AC could evaluate these aspects.", "was_revised": true, "final_justification": "The authors have provided satisfactory answers to my questions. Note that I am not an OT theory expert, please consider my opinion as a view point of an OT practitioner.", "rebuttal": "We thank the reviewer for their thoughtful feedback and clarifying questions.\n\n**Summary clarification:** We wanted to point out that bounding both gaps is required in the analysis of both the entropic kernel estimator and the rounding estimator. If we were to distinguish the estimators’ analysis, we would say that the entropic kernel estimator relies on stability of $\\\\mathcal{E}\\_p$ under Wasserstein perturbations, while the rounding estimator relies on TV stability. We will mention this distinction at the start of Section 3. Also, the analysis of the rounding estimator does not require Hölder continuous kernels (that case is treated by a separate DRO estimator introduced in Section 4).\n\n**Q1a “could the finite-sample rates inform how OT maps are parametrized and fitted?”:**\nWe agree that using this work to inform map estimation in practice is a very natural direction. As noted by Reviewer RJR5, there is a promising approach for neural map estimation using the so-called “Monge gap” [A], which we will discuss in the updated related work. When specialized to $p=1$, this work aims to learn a parameterized map $T$ minimizing the following:\n$$\\mathcal{E}’\\_1(T;P,Q) := \\underbrace{\\mathbb{E}\\_P[\\\\|T(X) - X\\\\|] - W\\_1(P,T\\_\\sharp P)}\\_{\\text{Monge gap}} + \\Delta(T\\_\\sharp P,Q),$$\nwhere $\\Delta$ is some statistical divergence. In practice, they substitute $P$ and $Q$ with their empirical versions and use entropic OT (EOT) distances to approximate both $W\\_1$ and $\\Delta$, achieving impressive empirical results. We emphasize that these approximations preclude meaningful statistical guarantees without accounting for implicit bias or other regularization, since an optimal map for the empirical problem can perform arbitrarily bad on the population problem.\n\nWe can show that, when $\\Delta = W\\_1$, the Monge gap objective $\\mathcal{E}’\\_1$ and our $\\mathcal{E}\\_1$ coincide up to a constant multiplicative factor of 2. Qualitatively similar results hold for $p>1$, though there is no longer a precise equivalence. Thus, the approach in [A] is quite close to performing empirical risk minimization with our transportation error (up to the use of EOT that is necessary for large-scale data sets). We will include this derivation in a new remark for Section 2. In some sense, this shows that our approach already lends itself to map fitting in practice. Moreover, if we were to directly plug in our $\\mathcal{E}\\_p$ objective into the neural map estimation experiments from [A] (substituting OT with EOT for tractability), we have the benefit of only having to perform back propagation through one EOT problem instead of two. We are optimistic that this will lead to a performance boost in practice. In the updated manuscript, we will supplement our synthetic experiments, which validated our theory, with a large-scale experiment that compares our performance to the Monge gap approach when learning maps for single-cell genomic data (mirroring the setup of Section 6.4 in [A]). Zooming out, we feel that our framework provides a solid statistical foundation for the practical approach to map estimation established in [A], and we hope that our theoretical insights will boost further practical developments.\n\nSecond, our rounding estimation approach can be applied in a black-box way on top of any existing map estimator, including a neural estimator. In the added experiments with single-cell genomic data, we will take the resulting neural estimators and see how their test performance varies if we add on this rounding step, for varied choices of rounding partition (namely, tuning the size of the partition cells). It will be interesting to see if there is extra performance to be eked out of existing methods via the regularizing effect of rounding.\n\nThird, we call the reviewer’s attention to our Remark 4, which draws parallels between our DRO procedure and existing Lipschitz regularization techniques.\n\nFinally, we remark that our current synthetic experiments were computationally bottlenecked by high-precision OT computations, which were necessary to validate our statistical guarantees. The Monge gap work sidesteps these by using EOT with a fixed precision, trading some accuracy for scalability. Another regularization approach which may be worth future exploration is that of sliced OT, where one works only with low dimensional projections of the data distributions. We will add a remark to the end of Section 2 on extensions of our framework to regularized OT problems, which are key for large-scale applications.\n\n**Q1b “Could you characterize the error functional (i.e. which error term dominates when) at different sample ranges?”:** \nThis is an interesting question to explore. The answer would appear to depend on quite a few factors, including the kernel estimator, the sample size, the source distribution, and the target distribution. We are unaware of any simple primitive conditions that would help distinguish the case. To investigate this, we will update all of our experiments to separate the contributions of the two error terms and include some discussion on the resulting balance. For our existing synthetic experiments, we note that the feasibility gap was typically larger than the optimality gap, but we will also include this fine-grained data for the neural estimation experiments promised above.\n\n**Q2, extension to conditional OT:**\nThis is a great question, certainly of relevance in important applications. In general, we believe that our framework is modular enough to apply to a wide-range of OT variants, including conditional OT. For this case, one could extend existing conditional OT works to measure performance with an $\\mathcal{E}\\_2$-type functional instead of $L^2$. Depending on the modeling assumptions, one could statistically investigate questions of finite-sample risk. We expect meaningful bounds to require additional regularity assumptions on the relationship between contexts and maps/kernels. We view this as a promising direction for future research and will add a discussion to the summary of our final version.\n\n[A]: Uscidda & Cuturi. “The Monge Gap: A Regularizer to Learn All Transport Maps”. ICML 2023."}, {"review_id": "kbTMw7lG83", "reviewer": "Reviewer_Q4zc", "summary": "This paper introduces a refined $p$-Wasserstein-type error functional that incorporates an additional transportation kernel. Various forms of stability for marginal distributions with respect to the $p$-Wasserstein distance are established. Furthermore, the author studies the error when the reference transportation is close to the optimal one, under certain regularity assumptions. A synthetic experiment with a discontinuous optimal transport map is performed to test the accuracy of this error functional.", "questions": "In Section 4, line 243, the authors assume Hölder continuity of the optimal kernel for the $W_p$ problem. This seems quite limiting, as it may not hold in practice. Could the authors provide justification for this assumption?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis article is mathematically sophisticated and sound, with a well-organized presentation. The refined error functional sheds new light on the errors in approximating optimal transport, providing insights that were not captured in previous results.\n\nWeakness:\nEven though the new error functional $\\mathcal{E}_p(\\kappa; \\mu, \\nu)$ can be used to analyze the error near optimal transport maps (for instance, for the minimizer in the entropic estimator in Section 3), it does not appear to provide an algorithm for obtaining better approximations or a more scalable method for large data sets.", "was_revised": true, "final_justification": "The paper is well written and makes strong theoretical contributions. The authors provided clear and satisfactory responses to reviewers' concerns. It seems that there will be supporting experiments coming up; therefore, I recommend a weak acceptance at the moment.", "rebuttal": "We thank the reviewer for their thoughtful feedback and clarifying questions.\n\nWeakness: The reviewer fairly points out that we do not use our methods to design more accurate / scalable algorithms for truly large scale settings. As a minor point, we note that our framework opens the door for analysis of future algorithms under far weaker assumptions than currently standard. But, more importantly, we are optimistic that our techniques may have immediate applications for neural map estimation with large-scale data, via a connection to the Monge gap discussed below.\n\nAs noted by Reviewer RJR5, there is a promising approach for neural map estimation using the so-called “Monge gap” [A], which we will discuss in the updated related work. When specialized to $p=1$, this work aims to learn a parameterized map $T$ minimizing the following:\n$$\\\\mathcal{E}’\\_1(T;P,Q) := \\underbrace{\\mathbb{E}\\_P[\\\\|T(X) - X\\\\|] - W\\_1(P,T\\_\\sharp P)}\\_{\\text{Monge gap}} + \\Delta(T\\_\\sharp P,Q),$$\nwhere $\\Delta$ is some statistical divergence. In practice, they substitute P and Q with their empirical versions and use entropic OT (EOT) distances to approximate both $W\\_1$ and $\\Delta$, achieving impressive empirical results. We emphasize that these approximations preclude meaningful statistical guarantees without accounting for implicit bias or other regularization, since an optimal map for the empirical problem can perform arbitrarily bad on the population problem.\n\nWe can show that, when $\\Delta = W\\_1$, the Monge gap objective $\\mathcal{E}’\\_1$ and our $\\mathcal{E}\\_1$ coincide up to a constant multiplicative factor of 2. Qualitatively similar results hold for $p>1$, though there is no longer a precise equivalence. Thus, the approach in [A] is quite close to performing empirical risk minimization with our transportation error (up to the use of EOT that is necessary for large-scale data sets). We will include this derivation in a new remark for Section 2. In some sense, this shows that our approach already lends itself to map fitting in practice. Moreover, if we were to directly plug in our $\\mathcal{E}\\_p$ objective into the neural map estimation experiments from [A] (substituting OT with EOT for tractability), we have the benefit of only having to perform back propagation through one EOT problem instead of two. We are optimistic that this will lead to a performance boost in practice. In the updated manuscript, we will supplement our synthetic experiments, which validated our theory, with a large-scale experiment that compares our performance to the Monge gap approach when learning maps for single-cell genomic data (mirroring the setup of Section 6.4 in [A]). Zooming out, we feel that our framework provides a solid statistical foundation for the practical approach to map estimation established in [A], and we hope that our theoretical insights will boost further practical developments.\n\nSecond, our rounding estimation approach can be applied in a black-box way on top of any existing map estimator, including a neural estimator. In the added experiments with single-cell genomic data, we will take the resulting neural estimators and see how their test performance varies if we add on this rounding step, for varied choices of rounding partition (namely, tuning the size of the partition cells). It will be interesting to see if there is extra performance to be eked out of existing methods via the regularizing effect of rounding.\n\n**Question, Hölder continuity:** This is indeed a strong assumption, but it is in fact weaker than nearly all of the existing work on statistical rates for $L^2$ map estimation (with the exception of the non-comparable setup in [B] that requires $T^\\star$ to be piecewise-constant). We agree that this is of less practical interest, which is why we focused on the unrestricted setting first, but we wanted to include this setting since it covered a large set of related work. There are some theoretical results when $p=2$ that guarantee the existence of a regular Brenier map (Caffarelli’s regularity theory - see, e.g., Theorem 3 of [C]), but these are admittedly not quantitative.\n\nWe also note that our approach to robustifying estimation to Wasserstein perturbations (for Section 5) uses a black-box method for turning any kernel into a Hölder continuous kernel via Gaussian convolution (at the cost of introducing some bias). Thus, the continuity condition can be of practical interest even if it does not hold exactly in practice.\n\n[A]: Uscidda & Cuturi. “The Monge Gap: A Regularizer to Learn All Transport Maps”. ICML 2023.\n[B]: A.-A. Pooladian, V. Divol, and J. Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. ICML 2023.\n[C]: Manole, Balakrishnan, Niles-Weed, & Wasserman. Plugin estimation of smooth optimal transport maps. The Annals of Statistics, 2024."}, {"review_id": "SZARx2j0Xd", "reviewer": "Reviewer_LQyn", "summary": "The authors find optimal map $\\pi_{\\tau,n}$ in Entropic OT problem statement between data distributions and represent conditional kernel between data distributions through this map. Having armed with the kernel, they build a novel error metric $\\epsilon_{p}$  for validation of Optimal Transport (OT) solvers  that demonstrates better performance than $L_{p}$ with increasing of number of samples. Also, they create rounding estimator to increase the efficiency of developed methodology, providing comparison with nearest-neighbour estimator in two settings.", "questions": "1) Why do you use this error metric as validation function and not use as a training objective?\n\n2) Since barycentric projection is averaging of data, it seems that is poor representation for map. Is there opportunity to learn 2 neural networks, while the first approximates map the second learns conditional kernel?\n\n3) Is your error unbiased? Could you show the proof of this fact, please\n\n4) Why do you pay your attention on Entropic OT to get transport plan? Is there any ways to get transport plan to obtain map without barycentric projection?\n\n5) If I am not mistaken, the theory fails if we remove sub-Gaussian requirement, yes?\n\n6) I poorly understood sense of rounding-based estimators. Could you explain what is the main motivation of rounding-based estimator?\n\n\n7) Could you provide high-dimensional experiments with MNIST or CIFAR-10 dataset, please?", "limitations": "The method has the same limitations as Entropic OT (see weakness 1).", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**strengths**\n\n1) The developed error does not require uniqueness or even existence of OT map.\n \n2) The developed error $\\epsilon_{1}$ demonstrates better performance than $L_{1}$\n\n**weaknesses**\n\n1) They solve Entropic OT to define conditional kernel in error metric. As far as known, Entropic OT has some drawbacks such as instability (exponents in  KL regularization),  sharpening of generated data (barycentric projection is averaging) and  tuning of hyper parameters.\n\n2)  Although the proposed methodology is applicable for any $p\\neq2$, the authors demonstrate experiments only for $p=1$. (see Fig.3)\n\n3)  Since 10 is the highest dimension for the experiments (see Sec.6, line 334), there is no confidence that this methodology is scalable. There is no Image experiments with MNIST or CIFAR-10 dataset.\n\n4) This methodology is applicable only for $\\sigma^{2}$-sub Gaussian data distribution.(line 120)", "was_revised": true, "final_justification": "Unfortunately, I remain my score unchanged. I really appreciate experiments, but I am sure that large-scale domain adaptation experiments would significantly improve the quality of this paper. \n\nSincerely", "rebuttal": "We thank the reviewer for their thoughtful feedback and clarifying questions.\n\n**Weakness 1:** “They solve Entropic OT to define conditional kernel in error metric. As far as known, Entropic OT has some drawbacks such as instability (exponents in KL regularization), sharpening of generated data (barycentric projection is averaging) and tuning of hyper parameters.”\nThe reviewer is fair to point out some known drawbacks of EOT. We want to emphasize that EOT is not part of our error metric, and our guarantees for the entropic kernel estimator in Section 3 are strictly worse than those for the rounding estimator. Nonetheless, EOT remains widely used in practice, so we wanted to comment on its performance when applied to our estimation task. We also would like to clarify that our estimators do not use barycentric projection.\n\n**Weakness 2, p=1 for experiments:** We chose p=1 for the experiments to emphasize the application of our framework even when uniqueness of the OT map fails dramatically (when p=1, there are many optimal maps). However, this is not a contributing factor to computation - we will include an updated set of experiments for p=2 in the updated appendix. Indeed, OT solvers with high accuracy guarantees are mostly agnostic to the choice of cost. For the cases of p=1,2, there are also efficient neural solvers using input-Lipschitz and input-convex neural networks, respectively. (See further discussion in response to the next weakness.)\n\n**Weakness 3, scalability concerns:** The reviewer fairly points out that we do not use our methods in truly large scale settings. As a minor point, we note that our framework opens up the potential for analysis of future algorithms under far weaker assumptions than currently standard. But, more importantly, we are confident that our techniques may have immediate applications for neural map estimation with large-scale data, via a connection to the Monge gap discussed below.\nAs noted by Reviewer RJR5, there is a promising approach for neural map estimation using the so-called “Monge gap” [A], which we will discuss in the updated related work. When specialized to $p=1$, this work aims to learn a parameterized map $T$ minimizing the following:\n$$\\mathcal{E}’\\_1(T;P,Q) := \\underbrace{\\mathbb{E}\\_P[\\\\|T(X) - X\\\\|] - W\\_1(P,T\\_\\sharp P)}\\_{\\text{Monge gap}} + \\Delta(T\\_\\sharp P,Q),$$\nwhere $\\Delta$ is some statistical divergence. In practice, they substitute P and Q with their empirical versions and use entropic OT (EOT) distances to approximate both $W\\_1$ and $\\Delta$, achieving impressive empirical results. We emphasize that these approximations preclude meaningful statistical guarantees without accounting for implicit bias or other regularization, since an optimal map for the empirical problem can perform arbitrarily bad on the population problem.\n\nWe can show that, when $\\Delta = W\\_1$, the Monge gap objective $\\mathcal{E}’_1$ and our $\\mathcal{E}_1$ coincide up to a constant multiplicative factor of 2. Qualitatively similar results hold for $p>1$, though there is no longer a precise equivalence. Thus, the approach in [A] is quite close to performing empirical risk minimization with our transportation error (up to the use of EOT that is necessary for large-scale data sets). We will include this derivation in a new remark for Section 2. In some sense, this shows that our approach already lends itself to map fitting in practice. Moreover, if we were to directly plug in our $\\mathcal{E}_p$ objective into the neural map estimation experiments from [A] (substituting OT with EOT for tractability), we have the benefit of only having to perform back propagation through one EOT problem instead of two. We are optimistic that this will lead to a performance boost in practice. In the updated manuscript, we will supplement our synthetic experiments, which validated our theory, with a large-scale experiment that compares our performance to the Monge gap approach when learning maps for single-cell genomic data (mirroring the setup of Section 6.4 in [A]). Zooming out, we feel that our framework provides a solid statistical foundation for the practical approach to map estimation established in [A], and we hope that our theoretical insights will boost further practical developments.\n\nSecond, our rounding estimation approach can be applied in a black-box way on top of any existing map estimator, including a neural estimator. In the added experiments with single-cell genomic data, we will take the resulting neural estimators and see how their test performance varies if we add on this rounding step, for varied choices of rounding partition (namely, tuning the size of the partition cells). It will be interesting to see if there is extra performance to be eked out of existing methods via the regularizing effect of rounding.\n\nThird, we remark that our current synthetic experiments were computationally bottlenecked by high-precision OT computations, which were necessary to validate our statistical guarantees. The Monge gap work sidesteps these by using EOT with a fixed precision, trading some accuracy for scalability. Another regularization approach which may be worth future exploration is that of sliced OT, where one works only with low dimensional projections of the data distributions. Finally, one could also employ neural OT solvers, which compute W1 and W2 using neural parameterizations of Lipschitz and convex function classes, respectively. We will add a remark to the end of Section 2 on extensions of our framework to regularized/approximate OT problems, which are key for large-scale applications.\n\nFinally, we will add an appendix section which pushes the dimension and sample count as high as possible for our existing high-precision, synthetic experiments. We expect that they can be pushed a fair bit further if bootstrapping is omitted. \n\n**Weakness 4, sub-Gaussianity:** As noted in Theorem 2, we can relax the sub-Gaussianity assumption on $\\mu$ by using a non-uniform partition for the rounding algorithm. One can also employ weaker tail bounds on $\\nu$, but we expect that these will necessarily worsen the achievable risk (as remarked after Theorem 2). We note that the existing statistics literature generally required bounded support, a stronger assumption.\n\n**Q1, evaluation vs optimization objective:** This is certainly a natural question. Since we were primarily focused on statistical guarantees, we knew that performing empirical risk minimization with $\\mathcal{E}\\_p$ as our objective was unfortunately out of the question, since the optimal empirical map can perform arbitrarily poorly on the population measures. However, our approach in Section 4, using Wasserstein distributionally robust optimization, does use $\\mathcal{E}\\_p$ as an objective for robust optimization (and can be interpreted as a regularized version of ERM, see Remark 4). Finally, we hope that our promised large-scale experiments above, which compare to the Monge gap approach, will shed some empirical light on the merit of $\\mathcal{E}\\_p$ for neural map estimation.\n\n**Q2a, barycentric projection:** We agree that barycentric projection is problematic. This is a feature of some prior work, but we emphasize that none of our estimators use barycentric projection. We would appreciate if the reviewer could point out which part of our text caused this confusion (namely, the wrong impression that barycentric projection was employed in our error metric or estimators) and we will work to elucidate it for the final version.\n\n**Q2b, two neural networks:** We kindly ask that the reviewer clarify this suggestion (we are happy to discuss further during the discussion period).\n\n**Q3, unbiasedness:** It is unclear to us what a suitable notion of unbiasedness would be for this paper's setting (since we are not comparing the estimated map to a fixed optimal map $T^\\star$). Does the reviewer have any particular definition in mind?\n\n**Q4, EOT & barycentric projection:** As mentioned above, we do not perform barycentric projection, and our best estimation guarantees do not use EOT.\n\n**Q5, sub-Gaussianity:** We point the reviewer to our response for Weakness 4.\n\n**Q6, intuition for rounding:** At a high-level, our rounding procedure allows us to extend a map learned from a discrete point set to the full source domain, while also serving to reduce variance. Recall that the rounding estimator bins the source points into bins of a tuned size, learns a map from the binned points to the (untouched) target points, and, given a new point, sends it to the destination of its bin under the learned map. The variance reduction intuition is as follows: at high spatial resolution, OT analysis is typically dominated by sampling variance terms, and binning serves to keep our analysis at a moderate spatial resolution. Of course, binning also introduces some bias. Balancing these factors was the key to our proof of Theorem 2. We include this approach because it achieves sharper statistical rates than the estimator using EOT.\n\n**Q7, large-scale experiments:** As mentioned above, the role of our current experiments was to validate our statistical rates, requiring high-precision OT computations that were a bottleneck to very high-dimensions / sample sizes. Please see our response to the scalability concern above for a new set of neural estimation experiments to be included in the revised manuscript. We hope that the single-cell genomics experiment is satisfactory as a large-scale example. This is a compelling option due to the existence of past results to benchmark against.\n\n**Limitations, EOT:** Please see previous responses on EOT.\n\n[A]: Uscidda & Cuturi. “The Monge Gap: A Regularizer to Learn All Transport Maps”. ICML 2023."}, {"review_id": "2rBuDgTeX0", "reviewer": "Reviewer_RJR5", "summary": "This paper introduces a new measure of error for transition kernels $\\kappa(y|x)$ used as stochastic transportation maps between $\\nu$ and $\\mu$, coined *Transportation Error* $\\mathcal{E}_{p}(\\kappa,\\mu,\\nu)$ which decomposes transportation cost into two terms:\n- the *optimality gap* induces by the mapping $\\kappa$ and the optimal $T^*$\n- the *feasibility gap* that quantifies the failure to meet the pushforward constraint $\\nu = T\\sharp \\mu$\n\nThis decomposition has several advantages:\n- better models of errors under TV or Wasserstein perturbations\n- \"weaker\" convergence than $L_p$ - which is strength for estimation from finite samples, like for Wasserstein cost\n- stability to perturbations wrt $\\nu$\n- stability to perturbations wrt $\\mu$\n- \"kernel decomposition\" property to link errors of $\\kappa_1$ and $\\kappa_2$ with $\\kappa_1\\circ\\kappa_2$ \n\nFinally, the authors propose an algorithm whose sample complexity approaches the optimal minimax rate. This algorithms relies on the convexity property of entropy-regularized OT, which yield a consistent estimator, well defined outside the support of the \"train set\".", "questions": "### Toy-ish experiments\n\nI'd be curious to see how your estimator behaves beyond the N=2,000 points limit, which is very small by today's standards. Can you plot results for $N\\geq 10^4$ points [you may reduce or remove bootstrap if computational budget is an issue]?  \n\nAlso, other \"challenging\" OT problems are documented in literature, with discontinuous OT maps. For example, the ones in Fig 3 of Makkuva et al. Also, the \"checkerboard\" dataset, used in e.g. Vesseron et al. It could be interesting to see how your estimator behaves on these datasets.   \n\n[Makkuva et al] Makkuva, Ashok, Amirhossein Taghvaei, Sewoong Oh, and Jason Lee. \"Optimal transport mapping via input convex neural networks.\" In International Conference on Machine Learning, pp. 6672-6681. PMLR, 2020.\n\nI'd be willing to increase my score if these experiments are done.  \n\n### Extension to deep learning\n\nNote that one of the paper's selling points is: \"*Adopting Ep as our objective enables kernel estimation without regularity or even existence of a Brenier map*\". Many folks in the deep learning community care about an objective which is:\n- statistically consistent, so it can be estimated from a finite sample in minibatch setup (as you did)  \n- is differentiable so it can be used as a loss function in a deep learning context\ne.g. with a kernel $\\kappa$ represented as a neural network.  \n  \nCan you discuss the use of $\\mathcal{E}_p$ in this context?", "limitations": "Some limitations are discussed, including the \"surprising\" efficiency of the NN estimator.  However, these experiments are toy, so while the transportation error $\\mathcal{E}_p$ is certainly a convincing theoretical tool, its practical relevance to \"large scale\" scenarios and realistic datasets still needs to be demonstrated. A lengthy discussion on this topic would be welcome.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\nThe problem is well-exposed and well-motivated. To the best of my knowledge, this approach is new.   \n  \nThe flow is clear, and as pedagogical as one can be on these topics (e.g. Figure 2).  \n  \nFrom the paper: \"Adopting $\\mathcal{E}_{p}(\\kappa,\\mu,\\nu)$ as our objective enables kernel estimation without regularity or even existence of a Brenier map\" which may simplify assumptions or algorithms built upon it.  \n\nThe algorithm proposed starts with a textbook application of the properties of entropy-regularized OT, based on the work of Genevay et al, and then apply \"rounding\" trick to achieve better rates.  \n\nWhen $p\\geq 2$, using a Wasserstein distributionally robust optimization program, authors relaxed the frequent Lipschitz continuity assumption put on $T$ and $T^{-1}$. \n\nCode is given.  \n\n## Weaknesses\n\n### Missing related work\n\nThe proposed *Transportation Error* is closely related to the *Monge Gap* [Uscida & Cuturi] which performs a similar-looking decomposition between a *fitting term* $\\Delta(T\\sharp \\nu, \\mu)$ (playing the same role as the *feasibility gap*) and a *c-optimality* term which measures how different $T$ is from $T^*$ on the induced transportation cost. I acknowledge that their decomposition is not quite the same, nonetheless, the differences could be discussed and highlighted.  \n\n[Uscida & Cuturi] Uscidda, Théo, and Marco Cuturi. \"The monge gap: A regularizer to learn all transport maps.\" In International Conference on Machine Learning, pp. 34709-34733. PMLR, 2023.\n\n### Toy experiments\n\nPlease see the \"questions\" section.  \n\n## Recommendation\n\nOverall, the paper is clear and introduces a novel tool to measure the optimality of transition kernels $\\kappa$ used as stochastic transportation maps. These transportation maps are paramount to some modern generative models (e.g. GAN-like or flow matching). This paper introduces a new tool to evaluate their quality, with appealing theoretical properties, and a practical algorithm to evaluate it. I believe the NeurIPS community will find it useful.", "was_revised": true, "final_justification": "I am satisfied by the answers of authors, in particular the efforts they put in comparing their work with the one of Uscida & Cuturi.\n\nI increased my rating, upon the assumption that the additional experiments promised by the authors are present in the camera ready version.", "rebuttal": "We thank the reviewer for their thoughtful feedback and clarifying questions.\n\n**Weakness, Monge gap literature:** Thank you for bringing up this work, which is indeed quite relevant. When specialized to $p=1$, the Monge gap paper [A] aims to learn a parameterized map $T$ minimizing the following:\n$$\\mathcal{E}’\\_1(T;P,Q) := \\underbrace{\\mathbb{E}\\_P[\\\\|T(X) - X\\\\|] - W\\_1(P,T\\_\\sharp P)}\\_{\\text{Monge gap}} + \\Delta(T\\_\\sharp P,Q),$$\nwhere $\\Delta$ is some statistical divergence. In practice, they substitute $P$ and $Q$ with their empirical versions and use entropic OT (EOT) distances to approximate both $W\\_1$ and $\\Delta$, achieving impressive empirical results. We emphasize that these approximations preclude meaningful statistical guarantees without accounting for implicit bias or other regularization, since an optimal map for the empirical problem can perform arbitrarily bad on the population problem.\n\nWe can show that, when $\\Delta = W\\_1$, the Monge gap objective $\\mathcal{E}’\\_1$ and our $\\mathcal{E}\\_1$ coincide up to a constant multiplicative factor of 2. Qualitatively similar results hold for $p>1$, though there is no longer a precise equivalence. Thus, the approach in [A] is quite close to performing empirical risk minimization with our transportation error (up to the use of EOT that is necessary for large-scale data sets). We will include this derivation in a new remark for Section 2. In some sense, this shows that our approach already lends itself to map fitting in practice. Moreover, if we were to directly plug in our $\\mathcal{E}\\_p$ objective into the neural map estimation experiments from [A] (substituting OT with EOT for tractability), we have the benefit of only having to perform back propagation through one EOT problem instead of two. We are optimistic that this will lead to a performance boost in practice. In the updated manuscript, we will supplement our synthetic experiments, which validated our theory, with a large-scale experiment that compares our performance to the Monge gap approach when learning maps for single-cell genomic data (mirroring the setup of Section 6.4 in [A]). Zooming out, we feel that our framework provides a solid statistical foundation for the practical approach to map estimation established in [A], and we hope that our theoretical insights will boost further practical developments.\n\nSecond, our rounding estimation approach can be applied in a black-box way on top of any existing map estimator, including a neural estimator. In the added experiments with single-cell genomic data, we will take the resulting neural estimators and see how their test performance varies if we add on this rounding step, for varied choices of rounding partition (namely, tuning the size of the partition cells). It will be interesting to see if there is extra performance to be eked out of existing methods via the regularizing effect of rounding.\n\nThird, we call the reviewer’s attention to our Remark 4, which draws parallels between our DRO procedure and existing Lipschitz regularization techniques.\n\nFinally, we remark that our current synthetic experiments were computationally bottlenecked by high-precision OT computations, which were necessary to validate our statistical guarantees. The Monge gap work sidesteps these by using EOT with a fixed precision, trading some accuracy for scalability. Another regularization approach which may be worth future exploration is that of sliced OT, where one works only with low dimensional projections of the data distributions. We will add a remark to the end of Section 2 on extensions of our framework to regularized OT problems, which are key for large-scale applications.\n\n**Question, toy experiments:** We agree that our initial synthetic benchmarks were somewhat limited. In addition to the proposals above, we are happy to include the recommended toy setting in the revised manuscript. \n\n**Question, deep learning extensions:** We hope that our response above re: Monge gap is satisfactory. In particular, we note that our proposal with the rounding estimator relies on our extension to stochastic maps and is rooted in deep learning (of course, empirical evaluation awaits). One could hope for a neural estimator that involves a more explicit parameterization of kernels, rather than an indirect approach via rounding. This is an interesting question for future research which we will include as an open direction in the updated conclusion. Certainly, well-crafted regularization would be essential, in order to prevent variance terms from exploding due to the very high-dimensional search space in this formulation.\n\n[A]: Uscidda & Cuturi. “The Monge Gap: A Regularizer to Learn All Transport Maps”. ICML 2023."}]

Author rebuttal:

Meta-review: The work studies consistent estimators for stochastic transport maps. This is an interesting and novel problem as the existing literature is focused on estimation of (deterministic) Monge maps. The idea is to define a so-called transportation error, which quantifies the optimality of any given stochastic transport map (kernel). It is simply a sum of a feasibility and an optimality term. Firstly, it is shown that the entropic OT based kernel is consistent as per this transportation error. A new rounding esitmator is also presented along with its consistency in theorem2. This new estimator turns out to be optimal nearly matching the lower bounds. One key feature is no regulairty assumptions are made. Under the (regulairty) assumption of holder conts kernels, a DRO based estimator is also analyzed.

The reviewers also broadly agree that all these results are interesting and will be useful for the ML community. The paper is also well written with a clear flow and organization. 

As promised in the rebuttal, it will help if the related work with monge gap and the additional simulations are included in the final version.
Decision: Accept (poster)