The Fundamental Limits of Valid Transport Map Estimation Sivaraman Balakrishnan†‡
arXiv:2606.30574v1 [cs.LG] 29 Jun 2026
Department of Statistics and Data Science† Machine Learning Department‡ Carnegie Mellon University, Pittsburgh, PA 15213.
June 30, 2026 Abstract Many modern generative modeling methods, including diffusion models, normalizing flows, and flow matching, estimate transport maps or plans between distributions without explicitly targeting an optimal transport (OT) map. In applications like generative modeling, the transport cost itself is irrelevant, and this makes it natural to target maps which are more tractable from either a statistical or computational standpoint. In this short note, we formalize the task of estimating any valid transport map in a rigorous minimax framework. One consequence of this framing is that it yields sample complexity lower bounds for any method whose learned object is evaluated as a transport map or plan, including flow matching and diffusion-based generative models, in settings where direct analysis would be challenging due to the analytic complexity of the methods and their target maps. We observe that, under standard, though strong, stability assumptions from the OT literature, estimating any valid transport map is statistically as hard as estimating the OT map. We complement these results with some examples showing that when these stability assumptions fail, alternative transport maps can be learned substantially more accurately than the OT map. Our minimax framing provides a rigorous foundation for understanding the statistical limits of modern transport-based generative methods and clarifies when targeting sub-optimal maps can provide real statistical advantages.
1
Introduction
Learning transformations between probability distributions is a central problem in modern statistics and machine learning. Such transformations provide a mechanism for mapping a simple reference distribution (e.g., a Gaussian) to a complex target distribution. A wide variety of modern generative modeling methods can be interpreted through this lens. For example, normalizing flows explicitly parameterize invertible transport maps between distributions [8, 22, 24], while diffusion models and score-based generative models construct stochastic processes that implicitly define transformations between a reference distribution and the target distribution [11, 25, 26]. More recent approaches such as flow matching and rectified flows also explicitly frame generative modeling as learning transport maps between distributions [1, 16, 17]. These methods have demonstrated remarkable empirical success across a wide range of generative modeling tasks. A classical mathematical formulation of the problem of transforming one distribution to another is given by optimal transport (OT) [28, 29]. In this framework, the optimal transport map between two distributions is defined as the map that pushes one distribution to the other 1
while minimizing a specified transport cost. Optimal transport has become an important tool in machine learning and statistics, with applications ranging from generative modeling and domain adaptation to distributional robustness and fairness [23]. Part of the success of OT is that it pins down a clear target of inference, enabling us to delve deeper into statistical and computational issues. At the same time, computing or estimating optimal transport maps from samples can be challenging, particularly in high dimensions. In many applications, the transport cost itself is irrelevant. The goal is simply to produce samples from a target distribution or to transform data between domains; any valid transport map that pushes the source distribution to the target distribution suffices. This observation motivates the widespread use of methods that do not explicitly target the optimal transport map, but instead learn alternative transport mechanisms. Indeed, many modern generative modeling methods – including diffusion models, flow matching, and various triangular or autoregressive transport maps – can be interpreted as learning transport maps or stochastic transport plans that are generally sub-optimal with respect to the classical OT objective. This raises a natural question: is learning an arbitrary transport map statistically easier than learning the optimal transport map? A common intuition is that this should be the case. Optimal transport maps can be sensitive to perturbations in the underlying distributions, and estimating them from samples often requires strong regularity assumptions [5, 10]. In contrast, modern generative modeling methods often appear empirically stable and effective even in settings where optimal transport maps may be difficult to estimate. These observations have led to a belief that learning a “good enough” transport map may be fundamentally easier, both computationally and statistically, than learning the optimal one. Despite this intuition, the statistical difficulty of estimating general transport maps has not been systematically studied. While there is a growing literature on the statistical estimation of optimal transport maps [6, 12, 18], much less is known about the fundamental limits of estimating arbitrary transport maps between distributions. Moreover, for many modern generative modeling methods the target map is analytically complex, making it difficult to study their statistical properties directly. In this paper, we introduce a simple minimax framework for studying the statistical limits of transport map estimation. Instead of focusing on the optimal transport map, we consider the broader problem of estimating a measurable map that transports one distribution to another. We measure performance using natural notions of risk that quantify the discrepancy between the estimated transport map and the set of valid transport maps. Our main results show that the task of estimating a valid transport map lends itself quite naturally to statistical analysis. Intuitively, any successful transport map estimator must at least induce an accurate estimate of the target distribution in Wasserstein distance, and the difficulty of this latter task serves as a fundamental limit for the estimation of a transport map. Since the optimal transport map is itself a valid transport map, estimating a valid map is never harder than estimating the optimal one. Stability assumptions commonly imposed in the literature on OT map estimation ensure that the OT map varies smoothly with the underlying distributions. Under these stability assumptions, the risk of OT map estimation is upper bounded by the risk of estimating the target distribution in the Wasserstein sense. We show in this paper that, under stability assumptions, estimating a valid transport map and estimating the optimal transport map have the same statistical difficulty. At the same time, our results also show that the equivalence between optimal and suboptimal transport maps can fail in the absence of stability. We provide simple examples in which the optimal transport map is either moderately or highly unstable and statistically difficult to estimate, while alternative transport maps can be learned at substantially faster 2
rates. This separation demonstrates that the potential advantages of modern transport-based generative methods arise precisely in regimes where stability assumptions break down. Our framing immediately yields new lower bounds for a range of modern generative modeling methods. In particular, our results imply sample complexity lower bounds for formulations of methods such as flow matching and diffusion-based generative models whose learned object is evaluated as a transport map or plan. Directly analyzing the statistical limits of these methods would be challenging due to the analytic complexity of the transformations they learn. By instead studying the broader problem of valid transport map estimation, we obtain these bounds in a unified and conceptually simple manner. Taken together, our results provide a principled statistical perspective on the problem of learning transport maps. The minimax framework introduced here grounds the discussion of statistical limits in modern transport-based generative modeling and helps identify settings in which targeting sub-optimal transport maps can provide genuine statistical advantages.
1.1
Notation
For a metric space E, we write P(E) for the set of Borel probability measures on E. For p ≥ 1, we write Pp (Rd ) for the set of probability measures on Rd with finite pth moment. Given probability measures µ, ν ∈ P(Rd ), we write Π(µ, ν) for the set of couplings ν. The R of µ and p p-Wasserstein distance is denoted by Wp , so that WpRp (µ, ν) = inf ∥x − y∥ dπ(x, y). π∈Π(µ,ν) 2 √ 2 We use ρ(P, Q) for the Hellinger affinity, ρ(P, Q) := dP dQ, and H (P, Q) := 1 − ρ(P, Q) for the squared Hellinger distance. Finally, for nonnegative sequences an , bn , we write an ≲ bn if an ≤ Cbn for a constant C independent of n, and write an ≍ bn if both an ≲ bn and bn ≲ an . We write an ≪ bn when the ratio an /bn is chosen sufficiently small.
2
Background
Inspired by methods in generative modeling and by the growing literature in statistical optimal transport, we focus on the following setup. We have a known source distribution µ, and i.i.d. samples Y1 , . . . , Yn from an unknown target distribution ν both supported on Rd . Our goal is to estimate a transport map T . Informally, a transport map T : Rd → Rd between µ and ν is a map such that for X ∼ µ, we have that T (X) ∼ ν. More formally, a transport map between µ and ν is a Borel-measurable function such that T# µ := µ(T −1 (·)) = ν. If µ is non-atomic there is always at least one valid transport map between µ and ν 1 . There are often many transport maps between µ and ν. Given this non-uniqueness, the literature on optimal transport has focused on a particular choice of transport map. Given a cost c : Rd × Rd → R (most popularly, the squared Euclidean distance), the OT map is defined as: Z T0 := arg min c(X, T (X))dµ(X). T :T# µ=ν
Brenier’s celebrated polar factorization theorem [4] shows that, for the squared Euclidean cost under appropriate regularity conditions, any valid transport map can be decomposed into the composition of the OT map with a measure-preserving map (i.e. a map which maps µ onto itself). These facts highlight that the OT map is a natural parsimonious choice to target. 1
Throughout, whenever we study deterministic maps, we assume either that µ is non-atomic, so that valid maps to all target distributions under consideration exist, or else we use the convention that the infimum over an empty set is +∞.
3
On the other hand, methods like diffusion models learn stochastic maps (i.e. couplings) between the source and target. A coupling π is a joint distribution on Rd × Rd with first marginal µ and second marginal ν, and it prescribes a randomized transport plan between µ and ν. More formally, we denote the set of couplings as Π(µ, ν), i.e. Π(µ, ν) = {π ∈ P(Rd × Rd ) : π(· × Rd ) = µ, π(Rd × ·) = ν}. Unlike transport maps, couplings always exist. Once again a canonical choice is an OT coupling π0 (i.e. a coupling that minimizes a prescribed cost on average). For costs which satisfy certain regularity conditions (the squared Euclidean cost being an example), when the source µ is absolutely continuous with respect to the Lebesgue measure, the OT coupling is unique and it is concentrated on a graph (i.e. corresponds directly to a unique OT map).
2.1
The Minimax Framework
We first briefly review the minimax framework for OT map estimation which has been used in a series of prior works [2, 3, 6, 12, 18]. The minimax framework provides a foundation for comparing estimators of the OT map based on their sample efficiency. This framework also allows the statistician to characterize the fundamental limits of estimation from random samples and consequently to reason about optimal estimators. The literature on OT maps has largely focused on the squared Euclidean risk. Concretely, given an estimator Tb, we can evaluate it by comparing it to the OT map T0 via its loss: Z b LOT (T ) := ∥Tb(X) − T0 (X)∥22 dµ(X). Though we primarily focus on the squared Euclidean loss, the results we develop in this paper also naturally extend to general Lp losses for p > 1. To evaluate stochastic methods it makes sense to generalize this loss to: Z S π ) := W22 (b π (·|X), π0 (·|X))dµ(X). LOT (b We focus the main paper on deterministic transport maps and briefly address the extension of our results to stochastic maps in Appendix B. The loss is a random variable (since the estimator Tb is sample dependent), and it is standard to instead focus on studying the risk (its expected value): ROT (Tb) = ELOT (Tb). While this loss and risk are reasonable as a benchmark for estimating the OT map, they are of course not reasonable measures to study procedures like rectified flow or normalizing flows, which explicitly target alternative non-optimal maps. In this paper, we focus instead on the following loss and risk: Z Lvalid (Tb) = inf ∥Tb(X) − T (X)∥22 dµ(X) , Rvalid (Tb) = ELvalid (Tb) T# µ=ν
This loss measures how close Tb is to the set of valid transport maps, rather than to a specific canonical choice. Equivalently, Lvalid is the squared L2 (µ) distance from Tb to the set T : T# µ = ν. It is clear that: LOT (Tb) ≥ Lvalid (Tb),
and ROT (Tb) ≥ Rvalid (Tb), 4
and part of the purpose of this note is to understand the gap between these quantities. We will show both that Rvalid is amenable to analysis and also does provide some insights into when targeting suboptimal maps can be useful. With a notion of risk in place, the main object of study is often the minimax risk, i.e. Mvalid (N) = inf sup Rvalid (Tb) and MOT (N) = inf sup ROT (Tb), Tb ν∈N
Tb ν∈N
where N is some collection of potential target distributions2 . Prior work [9, 12] has used variants of this definition, where rather than restrict the class of target distributions N, they restrict the source distribution µ and the optimal transport map T0 between µ and ν to satisfy regularity conditions. Other work [2, 18] has used both regularity of the transport map and direct restrictions on the class of target distributions.
2.2
Statistical Estimation of OT Maps
There is by now a substantial literature on the statistical estimation of OT maps from samples; see, for instance, [6, 12, 18] and the recent survey [3]. Some of this literature studies estimators which first estimate the underlying distributions and then plug these estimates into the OT problem. The analysis of these estimators often rests on a strong regularity condition on the population OT map. A representative assumption is that the OT map from µ to ν is of the form T0 = ∇φ0 , where the so-called Brenier potential φ0 is both smooth and strongly convex. For instance, when φ0 is twice differentiable, one may assume that for some constants 0 < α ≤ β < ∞, αI ⪯ ∇2 φ0 (x) ⪯ βI,
x ∈ Rd .
This condition is restrictive, but it appears naturally in several classical settings, for example through Caffarelli-type regularity and contraction results for log-concave measures [5, 10]. A key consequence of this regularity condition is that under it the OT map is stable with respect to perturbations of the input distributions. We recall one version of this fact (see Theorem 3 in [2]). Given probability measures µ and νb, where µ is absolutely continuous with respect to the Lebesgue measure, let TbOT denote the OT map from µ to νb. Lemma 1 (Stability of the OT map). Suppose that ν = (∇φ0 )# µ, where φ0 is α-strongly convex and β-smooth. Then, for any probability measure νb with finite second moments, Z β ∥TbOT (x) − T0 (x)∥22 dµ(x) ≤ W22 (b ν , ν). α When µ is absolutely continuous every distribution νb corresponds to a transport map TbOT which pushes µ onto νb. Consequently, this extraordinary stability shows that, under the above regularity assumptions, when α, β are fixed estimating the OT map is no harder than estimating the target distribution in Wasserstein distance.
3
Main Results
With the necessary background in place we now proceed to discuss our main results. In Section 3.1 we discuss some basic properties of the loss Lvalid which show that it is often 2
Throughout the paper, we suppress the dependence of these risks on the known source distribution µ and on the sample size n.
5
amenable to direct analysis. In Section 3.2 we discuss the implications of this basic result, providing both new lower bounds as well as enabling a direct comparison with existing results on OT map estimation. In Section 3.3 we prove a pair of minimax lower bounds, which highlight the possibility of separations between the OT and valid map minimax risks. We focus throughout on the multivariate case when d ≥ 2 and defer treatment of the special onedimensional case to Appendix A. We defer detailed proofs of various claims to Appendix C.
3.1
Structural Results
We first give a simple structural result which shows that the projection risk defined above is closely related to the Wasserstein distance between the distribution induced by the estimator and the target distribution. Lemma 2 (Projection risk and Wasserstein distance). Let µ, ν ∈ Pp (Rd ), and let Tb : Rd → Rd be a measurable map such that νb := Tb# µ ∈ Pp (Rd ). Then Z Lvalid,p (Tb) := inf
T# µ=ν
∥Tb(x) − T (x)∥p2 dµ(x) ≥ Wpp (b ν , ν).
(1)
Moreover, suppose that there exists an OT map S : Rd → Rd transporting νb to ν, i.e. Z ν (z) = Wpp (b ν , ν). S# νb = ν and ∥z − S(z)∥p2 db Then equality holds in (1). For p > 1, there is an OT map S : Rd → Rd transporting νb to ν whenever νb is absolutely continuous with respect to the Lebesgue measure. Consequently, at least when the estimator induces an absolutely continuous distribution, the valid map loss Lvalid is exactly the Wasserstein error of the induced distribution νb = Tb# µ.
3.2
Implications
The structural result above has a useful consequence: estimating a valid transport map contains, as a subproblem, estimating the target distribution in Wasserstein distance. This observation is independent of optimality, convexity, smoothness, or the particular algorithm used to construct the map. It therefore gives immediate lower bounds for procedures such as rectified flow, flow matching, normalizing flows, and stochastic transport variants, whenever their output is evaluated as a map or plan from the source distribution to the target distribution. Let Y1 , . . . , Yn ∼ ν be i.i.d., and let N ⊆ P2 (Rd ) be a class of possible target distributions. Define the minimax squared-Wasserstein distribution-estimation risk MW2 (N) := inf sup Eν W22 (b ν , ν), νb ν∈N
where the infimum is over all measurable distribution estimators based on Y1 , . . . , Yn . The following result is an immediate consequence of Lemma 2. Lemma 3 (Distribution estimation is a subproblem). For any known source distribution µ ∈ P2 (Rd ) and any target class N ⊆ P2 (Rd ), Mvalid (N) ≥ MW2 (N). 6
(2)
Consequences for rectified flow and related map estimators. Rectified flow and related estimators [1, 16, 17] output a data-dependent velocity field vbt and then define a terminal map TbRF by solving d b bt ), Xt = vbt (X dt
b0 = x, X
b1 , TbRF (x) := X
whenever this ODE is well-posed. Once the terminal map is constructed, it is simply a map estimator in the sense above. Therefore Lemma 3 gives Z 2 b ∥TRF (x) − T (x)∥2 dµ(x) ≥ MW2 (N), (3) inf sup Eν inf v b ν∈N
T# µ=ν
where the infimum is over any class of data-dependent vector-field estimators whose terminal maps are measurable. This lower bound is algorithm-independent: it does not depend on how the velocity field is parameterized, optimized, or regularized. The same statement applies to flow matching, normalizing flows, triangular flows, and any other deterministic transport estimator after replacing TbRF by its terminal map. For stochastic diffusion-type estimators, Lemma 9 gives the corresponding result for the stochastic projection loss. A concrete smooth-density lower bound For illustration we now instantiate the preceding reduction in a canonical non-parametric setting using known minimax lower bounds for Wasserstein distribution estimation. Let Ω = [0, 1]d , and for s ≥ 0, L > 0, and m > 0, define Z s s f (x) dx = 1 , Np′ ,q (L; m) := f ∈ Bp′ ,q (L) : f ≥ m, Ω
where Bps′ ,q (L) denotes the usual Besov ball on Ω. Abusing notation slightly, we use the same notation for the corresponding collection of measures. This is the smooth-density model studied by Niles-Weed and Berthet [21], and their results, together with Lemma 3 immediately implies the following corollary: Corollary 1 (Smooth-density lower bound for valid transport estimation). Fix d ≥ 1, s ≥ 0, 2 ≤ p′ < ∞, and 1 ≤ q ≤ ∞, and suppose the above class is nonempty. For every known source distribution µ ∈ P2 (Rd ), we have 2(1+s) n− d+2s , d ≥ 2, Mvalid Nsp′ ,q (L; m) ≳ (4) −1 n , d = 1. We note that the same lower bound holds for every restricted subclass of deterministic estimators. Under related but stronger smoothness assumptions, the recent work of Mena et al. [19] (see their Theorem 8) showed that the rectified flow map can be estimated at the slower rate of n−2s/(2s+d−1) . Corollary 1 gives a complementary lower bound for any estimator whose output is evaluated through the valid map loss. Since the loss to any specified population transport map, including the rectified flow map when it is well-defined, dominates the valid map loss, the same lower bound applies to such target-specific map estimation problems as well. This result highlights that in the standard non-parametric setups that have been studied in the OT map estimation literature, the curse of dimensionality is unavoidable, and targeting any (even sub-optimal) transport map does not alleviate these challenges. 7
Relation to stability assumptions for OT map estimation Past work summarized in Lemma 1 has shown that, under smoothness and strong convexity of the Brenier potential, estimating the OT map can be reduced to estimating the underlying distributions in Wasserstein distance. The following proposition summarizes the implications of Lemmas 1 and 2. Proposition 1 (Stability sandwiches the three risks). Suppose that µ is absolutely continuous and that, for every ν ∈ N, the quadratic OT map Tν from µ to ν exists. Assume further that there is a constant Cstab < ∞ such that, for every distribution estimator νb under consideration, the plug-in OT map Tνb satisfies Z ∥Tνb(x) − Tν (x)∥22 dµ(x) ≤ Cstab W22 (b ν , ν) (5) for all ν ∈ N. Then MW2 (N) ≤ Mvalid (N) ≤ MOT (N) ≤ Cstab MW2 (N).
(6)
This proposition shows that in any model where a stability inequality of the form (5) holds and the Wasserstein distribution-estimation rate is known, valid map estimation, OT-map estimation, and Wasserstein distribution estimation all have the same minimax rate up to the stability constant. This result summarizes the formal sense in which targeting a sub-optimal transport map cannot yield any significant statistical benefit over targeting the OT map in stable regimes.
3.3
Separations between Valid Transport and OT
The preceding results show that, under sufficiently strong stability assumptions, estimating a valid transport map is no easier than estimating the optimal transport map. We now show that this conclusion can fail once stability is weakened. The key insight is not that valid transport maps avoid the need to estimate the target distribution: Lemma 2 shows that they do not. Rather, the key insight is that the OT map can be unstable to small perturbations of the target distribution, and in these cases the OT map risk can be substantially larger than the valid map risk. 3.3.1
Polynomial Separation with a Benign Source
We follow a classical scheme in proving minimax lower bounds of reducing from estimation to testing. The following two-point reduction forms the basis for our minimax risk comparisons. Lemma 4 (Two-point reduction). Let N = {ν0 , ν1 }, let Ti := Tνi be the corresponding OT maps, and set ∆2OT := ∥T0 − T1 ∥2L2 (µ) . Let en := inf max νi⊗n (ψ ̸= i) ψ i∈{0,1}
be the minimax testing error for distinguishing ν0 from ν1 . Then 1 MOT (N) ≥ ∆2OT en . 4 8
(7)
T0 νθ = Rθ# ν0
source µ
ν0
wedge of mass ≍θ
two separated half-disks
Tθ Figure 1: The rotating two-component construction. The target distributions differ by a small rotation, so their squared Wasserstein distance is ≲ θ2 . However, the sign boundary in the source rotates, and a wedge of source mass of order θ is sent to the opposite component. This ensures that the squared L2 (µ) distance between the OT maps is of order θ. Moreover, for any maps S0 , S1 satisfying Si# µ = νi , Mvalid (N) ≤ ∥S0 − S1 ∥2L2 (µ) .
(8)
In particular, Mvalid (N) ≤
inf
S0# µ=ν0 , S1# µ=ν1
∥S0 − S1 ∥2L2 (µ) .
To show a risk separation we need three ingredients: the targets must be statistically hard to distinguish, their OT maps must be far apart, and the two target distributions must admit valid transports from µ that are close as maps. Our first construction is inspired by a well-known construction showing the Hölder irregularity of the OT map (see, for instance, Section 2.4 in the paper [13]). However, some careful modifications are needed to ensure that the resulting construction yields a valid minimax lower bound. Let D ⊂ R2 be the unit disk and let µ be the uniform distribution on D. Fix constants a > 1 and, for θ ∈ [0, π/4], write uθ = (cos θ, sin θ),
Tθ (x) := x + a sgn(x · uθ )uθ ,
νθ := (Tθ )# µ.
The map Tθ is the gradient, µ-a.e., of the convex potential 1 φθ (x) := ∥x∥22 + a|x · uθ |. 2 Consequently Tθ is the OT map from µ to νθ . Geometrically, Tθ sends the two half-disks cut out by the line x · uθ = 0 to two separated half-disks of radius 1, centered at +auθ and −auθ . This construction is illustrated in Figure 1. The following lemma analyzes this construction: Lemma 5. There are constants 0 < c < C < ∞, depending only on a, such that for all sufficiently small θ > 0, ∥Tθ − T0 ∥2L2 (µ) ≍ θ, 9
(9)
while W22 (νθ , ν0 ) ≲ θ2 ,
(10)
H 2 (νθ , ν0 ) ≲ θ.
(11)
and
Lemmas 4 and 5 together yield the following result: Theorem 1 (Polynomial separation with a benign source). Let µ be the uniform distribution on the unit disk in R2 . There exist constants c, C > 0 such that for every sufficiently large n there is a two-point target class Nn = {ν0 , νθn },
θn = κ/n,
with κ > 0 sufficiently small, for which MOT (Nn ) ≳
1 , n
(12)
Mvalid (Nn ) ≲
1 . n2
(13)
and
In particular, MOT (Nn ) ≳ n. Mvalid (Nn ) The source distribution µ in Theorem 1 is quite benign: it is bounded above and below on a convex domain, and we believe with a bit more analytic effort the source could be replaced by a standard Normal distribution. To place this result in context, a line of work [7, 13, 15, 20] has shown that for source measures which are upper and lower bounded on a so-called “John domain” (which includes convex domains as a special case), OT maps to (arbitrary, compactly supported) targets ν, η satisfy stability bounds of the form: ∥Tν − Tη ∥L2 (µ) ≲ W2 (ν, η)1/6 . This stability rules out the most extreme form of instability (exhibited in Theorem 2) for fixed regular sources: the OT risk cannot remain bounded away from zero while the valid map risk becomes exponentially small. Nevertheless, the preceding construction shows that polynomial amplifications of the valid map risk are already possible for benign source distributions. 3.3.2
An Exponential Separation for Adversarial Sources
The previous example uses a fixed, regular source. It gives a polynomial separation, but the Hölder stability of OT maps for regular sources prevents the most extreme behavior. If we allow the source distribution to be more adversarially chosen a much larger separation is possible. Once again we follow a classical scheme to prove a minimax lower bound (see Theorem 2.15 of Tsybakov [27]) of constructing a collection of distributions, indexed by a hypercube, where adjacent distributions on the hypercube are difficult to distinguish. 10
Lemma 6 (Assouad lower bound). Let {Pσ : σ ∈ {±1}M } be a family of distributions, and let Tσ : X → Rd , σ ∈ {±1}M , be a corresponding family of maps. Let µ be a probability measure on X , and let G1 , . . . , GM ⊆ X be disjoint measurable sets. For σ ∈ {±1}M , let σ (j) denote the vector obtained from σ by flipping the jth coordinate. Suppose that for each j = 1, . . . , M there exists ∆j > 0 such that Z ∥Tσ (x) − Tσ(j) (x)∥22 dµ(x) ≥ ∆j (14) Gj
for every σ ∈ {±1}M . Suppose also that the Hellinger affinities satisfy Z q ⊗n ⊗n dPσ⊗n dPσ⊗n ρ(Pσ , Pσ(j) ) := (j) ≥ ρ0
(15)
for every σ and every j, where ρ0 ∈ (0, 1]. Then Z inf
sup
Tb σ∈{±1}M
Eσ
∥Tb(x) − Tσ (x)∥22 dµ(x) ≥
1−
p
M
1 − ρ20 X ∆j . 8
(16)
j=1
Here the infimum is over all estimators Tb based on n observations from Pσ . Our construction is inspired by another classical example (see, for instance, Section 1.1 in the paper [13] or Figure 2 in [14]) where the OT map is non-unique and consequently unstable to perturbations in the Wasserstein sense. However, once again several careful adjustments are needed to this basic construction to prove a statistical minimax lower bound. Our construction is illustrated in Figure 2. Let ε = 1/n. Fix a constant a > 0 and set θn = exp(−n). We first describe the source distribution. Choose points u1 < · · · < un , where uj = 4εj. Associated with each uj define two source centers (which we refer to as a block) xj,L = (uj − ε, 0),
xj,R = (uj + ε, 0).
Choose a radius rn > 0 satisfying rn ≪ εθn . Let Bj,L and Bj,R be the Euclidean balls of radius rn centered at xj,L and xj,R . Define µ to be the probability distribution which assigns mass ε/2 uniformly to each of these 2n balls. We now define the collection of target distributions. For each sign vector σ = (σ1 , . . . , σn ) ∈ {±1}n , define two target centers (which we also refer to as a block) associated with the center uj by σ σ yj,R = (uj + θn , σj a), yj,L = (uj − θn , −σj a), σ and y σ , and let νσ assign mass ε/2 uniformly to each of the balls of radius rn centered at yj,L j,R over all j = 1, . . . , n. Let Nn := {νσ : σ ∈ {±1}n }.
With the source distribution and target class in place, Lemma 11 in the Appendix analyzes this construction to control the desired transport map separation and Hellinger distances. Lemma 11 and Lemma 6 together yield the following conclusion: 11
each source ball has mass ε/2
···
source µ u1
··· uj
u2
···
target νσ
un
···
uj u1 u2 un the orientation of each target pair encodes the sign σj
Figure 2: Illustration of the exponential-separation construction. The source distribution µ is supported on n well-separated blocks, with block j consisting of two small balls centered at (uj − ε, 0) and (uj + ε, 0). For each sign vector σ ∈ {±1}n , the target distribution νσ places two small balls near (uj − θn , −σj a) and (uj + θn , σj a). Each block encodes one hidden bit σj . Theorem 2 (Exponential separation). For every sufficiently large n the source distribution µ and target class Nn described above ensure that: MOT (Nn ) ≳ 1,
(17)
Mvalid (Nn ) ≲ exp(−2n).
(18)
while
Consequently, MOT (Nn ) ≳ exp(2n). Mvalid (Nn ) The construction in Theorem 2 is intentionally adversarial. The source distribution changes with n, consists of many tiny components, and the radius rn must be much smaller than the horizontal perturbation scale θn = exp(−n). Thus the source geometry and density become increasingly ill-conditioned. This is exactly what allows an exponential valid map improvement without contradicting qualitative or quantitative stability results for fixed regular sources. The two examples we have given identify two different regimes. For a fixed regular source on a convex domain, OT stability rules out catastrophic instability, but it still permits polynomial separations between the OT map risk and valid map risk. With a more adversarial source distribution the OT map can be forced to encode many nearly invisible bits and OT map estimation can have constant risk while a fixed valid transport map is exponentially accurate.
4
Discussion
In practice, using diffusion and flow models involves a range of design decisions that can significantly influence the quality of generated samples. These include choices about neural network architectures, discretization schemes, noise schedules, and optimizer hyperparameters. Ultimately, these choices can serve to inject bias and regularize the methods in favorable ways, pulling them away from the idealized goal of approximating an unregularized transport map 12
or plan. Given some of the results of this paper on the hardness of approximating even a valid transport map in some settings, it seems likely that explaining the statistical benefits of these methods in these challenging settings will require a deeper understanding of these practical design choices. To distinguish optimal transport from sub-optimal transport, we considered a pair of idealized constructions. These examples are useful because they isolate a specific mechanism: the optimal transport map may encode a fragile global matching structure, while many nonoptimal transports can avoid this matching and still push the source distribution to the target. A difficult but natural question is to understand the extent to which real data distributions fall into stable or unstable regimes of this kind. Stability is not simply a property of the source distribution or the target distribution in isolation; it depends on the interaction between the two, and on the geometry of their supports. This issue seems particularly relevant for modern generative modeling. Classical regularity theory gives strong stability guarantees under convexity, density, and curvature assumptions and recent quantitative stability results show that even fairly weak geometric assumptions can imply polynomial control of the OT map [7, 13, 15, 20]. On the other hand, these assumptions are far from the geometry of realistic data distributions, which often have multiple modes, thin or lower-dimensional structure, and unevenly separated components. A useful direction for future work would be to develop datadriven diagnostics that distinguish stable from unstable transport problems. Such a diagnostic could distinguish when the optimal transport map is a statistically reasonable target, from situations when sub-optimal transport mechanisms are not merely computationally convenient but statistically preferable. We focused on the ability of various methods to estimate valid transport maps. This provides a principled framework for comparison, even when methods target different population quantities. However, one should be cautious when interpreting the practical implications of our results: in generative modeling, the objectives of sample quality and diversity are often only weakly correlated with the goal of estimating a transport map. Developing alternative formulations for these practical goals that still facilitate rigorous mathematical analysis is an interesting direction for future work. Finally, our framework also seems to lend itself naturally to the creation of computational separations. We focused here on statistical separations: regimes where the tasks of estimating optimal and sub-optimal transport maps have different sample complexities. A complementary question is whether there are settings where finding a valid sub-optimal transport map can be rigorously shown to be computationally easier than finding the optimal one.
Acknowledgements We are grateful to Narayanaswamy Balakrishnan, Arun Kuchibhotla, Gonzalo Mena, Andrej Risteski, Dejan Slepcev and Larry Wasserman for helpful discussions. We used ChatGPT to improve, proofread and produce figures for this manuscript. This research was supported in part by the NSF grant DMS-2310632.
References [1] M. S. Albergo, N. M. Boffi, and E. Vanden-Eijnden. Stochastic interpolants: A unifying framework for flows and diffusions. Journal of Machine Learning Research, 26(209):1–80, 2025. 13
[2] S. Balakrishnan and T. Manole. Stability bounds for smooth optimal transport maps and their statistical implications. Electronic Journal of Statistics, 2026. To appear. [3] S. Balakrishnan, T. Manole, and L. Wasserman. Statistical inference for optimal transport maps: Recent advances and perspectives. Statistical Science, 2025. [4] Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics, 44:375–417, 1991. [5] L. A. Caffarelli. The Regularity of Mappings with a Convex Potential. Journal of the American Mathematical Society, 5:99–104, 1992. [6] 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, 2021. [7] A. Delalande and Q. Merigot. Quantitative stability of optimal transport maps under variations of the target measure. Duke Mathematical Journal, 172(17):3321–3357, 2023. [8] L. Dinh, J. Sohl-Dickstein, and S. Bengio. Density estimation using real NVP. In International Conference on Learning Representations, 2017. [9] V. Divol, J. Niles-Weed, and A.-A. Pooladian. Optimal transport map estimation in general function spaces. The Annals of Statistics, 2022. [10] A. Figalli. The Monge–Ampère Equation and Its Applications. Zurich Lectures in Advanced Mathematics. European Mathematical Society, Zürich, 2017. [11] J. Ho, A. Jain, and P. Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, volume 33, pages 6840–6851. Curran Associates, Inc., 2020. [12] J.-C. Hütter and P. Rigollet. Minimax rates of estimation for smooth optimal transport maps. The Annals of Statistics, 49:1166–1194, 2021. [13] C. Letrouit. Lectures on quantitative stability of optimal transport, May 2025. Notes du Cours Peccot, Collège de France, May–June 2025. Preliminary version. [14] C. Letrouit. Unstable optimal transport maps. Comptes Rendus. Mathématique, 364: 333–344, 2026. [15] C. Letrouit and Q. Mérigot. Gluing methods for quantitative stability of optimal transport maps, 2024. [16] Y. Lipman, R. T. Q. Chen, H. Ben-Hamu, M. Nickel, and M. Le. Flow matching for generative modeling. In The Eleventh International Conference on Learning Representations, 2023. [17] X. Liu, C. Gong, and Q. Liu. Flow straight and fast: Learning to generate and transfer data with rectified flow. In The Eleventh International Conference on Learning Representations, 2023. [18] T. 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. 14
[19] G. Mena, A. K. Kuchibhotla, and L. Wasserman. Statistical properties of Rectified Flow. arXiv.2511.03193, 2025. [20] Q. Mérigot, A. Delalande, and F. Chazal. Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space. In International Conference on Artificial Intelligence and Statistics, pages 3186–3196. PMLR, 2020. [21] J. Niles-Weed and Q. Berthet. Minimax estimation of smooth densities in wasserstein distance. The Annals of Statistics, 50(3):1519–1540, 2022. [22] G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed, and B. Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57):1–64, 2021. [23] G. Peyré and M. Cuturi. Computational optimal transport with applications to data sciences. Foundations and Trends in Machine Learning, 11(5-6):355–607, 2019. [24] D. Rezende and S. Mohamed. Variational inference with normalizing flows. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1530–1538. PMLR, 2015. [25] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2256–2265. PMLR, 2015. [26] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021. [27] A. B. Tsybakov. Introduction to Nonparametric Estimation. Springer Science & Business Media, 2008. [28] C. Villani. Topics in Optimal Transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003. [29] C. Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin, Heidelberg, 2009.
15
A
The One-Dimensional Case
The one-dimensional case of transport is special and in this section we discuss it briefly. In higher dimensions, stability of the OT map is a nontrivial regularity property. In one dimension, however, monotonicity gives an exact stability identity. Throughout this subsection assume that d = 1 and that the source distribution µ is nonatomic. For any η ∈ P2 (R), let Fη denote its distribution function and let Fη−1 (t) := inf{x ∈ R : Fη (x) ≥ t},
0 < t < 1,
denote its generalized inverse. Define the monotone rearrangement from µ to η by Tη (x) := Fη−1 (Fµ (x)). Then Tη# µ = η, and Tη is the one-dimensional optimal transport map from µ to η for the squared Euclidean cost. In particular, if the true target is ν, then the OT map is T0 = Tν = Fν−1 ◦ Fµ . The following observation shows that in one dimension any estimator can be replaced by a monotone estimator whose OT-map error is exactly the Wasserstein error of the induced target distribution. Lemma 7 (Monotonization in one dimension). Let Tb : R → R be any measurable estimator, and write νb := Tb# µ. Define its monotone rearrangement by Te := Tνb = Fνb−1 ◦ Fµ . Then Te# µ = νb, and Z
|Te(x) − T0 (x)|2 dµ(x) = W22 (b ν , ν).
(19)
Moreover, Z inf
T# µ=ν
|Te(x) − T (x)|2 dµ(x) = W22 (b ν , ν).
(20)
Proof. Since µ is non-atomic, if X ∼ µ, then U := Fµ (X) is uniformly distributed on (0, 1). Therefore, Te(X) = Fνb−1 (U ), T0 (X) = Fν−1 (U ). Using the one-dimensional quantile representation of the Wasserstein distance, we obtain Z 1 Z 2 e |T (x) − T0 (x)| dµ(x) = |Fνb−1 (t) − Fν−1 (t)|2 dt = W22 (b ν , ν), 0
which proves (19). For (20), the lower bound follows from Lemma 2, since Te# µ = νb. For the matching upper bound, simply choose the valid transport map T = T0 in the infimum and use (19). This proves the claim. 16
This identity has a useful minimax consequence. Let N ⊆ P2 (R) be a class of target distributions, and recall the minimax Wasserstein distribution-estimation risk ν , ν), MW2 (N) := inf sup Eν W22 (b νb ν∈N
where the infimum is over all estimators of the target distribution based on the sample Y1 , . . . , Yn . Then Z Z 2 b |Tb(x) − T (x)|2 dµ(x) = MW2 (N). inf sup Eν |T (x) − Tν (x)| dµ(x) = inf sup Eν inf Tb ν∈N
Tb ν∈N
T# µ=ν
(21) Indeed, the lower bounds follow because every map estimator Tb induces a distribution estimator νb = Tb# µ, and both the OT loss and the valid map loss are bounded below by W22 (b ν , ν). Conversely, given any distribution estimator νb, the monotone estimator Tνb attains exactly this Wasserstein error by Lemma 7. In one dimension, estimating the OT map, estimating a valid transport map, and estimating the target distribution in squared Wasserstein distance are all the same minimax problem. In particular, there is no one-dimensional analogue of the separation phenomena we constructed in our work: any mechanism that makes the OT map hard to learn also makes the induced target distribution hard to estimate in W2 , and therefore also makes the problem of estimating a valid transport map hard.
B
Stochastic Maps
While in the main paper we focused primarily on the setting with deterministic transport maps, analogous results hold more generally when studying stochastic maps. Methods that form the basis for stochastic diffusion models inherently produce stochastic maps. We first give an analogue of Lemma 2 for stochastic maps. b be a Markov kernel from Rd to Rd , and define Lemma 8 (Stochastic projection risk). Let K Z b νb(A) = K(A | x) dµ(x), A ⊆ Rd . Then, for every ν ∈ Pp (Rd ), Z K:
R
inf K(·|x)dµ(x)=ν
b | x), K(· | x) dµ(x) = Wpp (b Wpp K(· ν , ν).
(22)
Proof. We first prove the lower bound. Fix any kernel K such that Z K(· | x) dµ(x) = ν. b | x) and K(· | x). More formally, one For each x, let γx be an optimal coupling between K(· may use measurable ε-optimal couplings and then let ε ↓ 0. Integrating these couplings over x gives a coupling γ of νb and ν. Therefore, Z Z p p b | x), K(· | x) dµ(x). Wp (b ν , ν) ≤ ∥y − yb∥2 dγ(b y , y) = Wpp K(· 17
Taking the infimum over K gives the lower bound. For the upper bound, let λ be an optimal coupling of νb and ν. Disintegrate it as dλ(b y , y) = db ν (b y ) Q(dy | yb). Now define a new kernel Z
⋆
K (dy | x) = Then
Z
b y | x). Q(dy | yb) K(db
K ⋆ (· | x) dµ(x) = ν,
so K ⋆ is a valid stochastic transport from µ to ν. Moreover, for each x, the joint law b y | x) Q(dy | yb) K(db b | x) and K ⋆ (· | x). Hence is a coupling of K(· Z Z ⋆ p b b y | x) Q(dy | yb) dµ(x) y − y∥p2 K(db Wp K(· | x), K (· | x) dµ(x) ≤ ∥b Z = ∥b y − y∥p2 dλ(b y , y) = Wpp (b ν , ν). Together with the lower bound, this proves (22). b is a Markov kernel from We can similarly derive a parallel result to that of Lemma 3. If K Rd to Rd , define its induced terminal law by Z νb(A) :=
b K(A | x) dµ(x),
A ⊆ Rd .
We can define the valid loss in the stochastic setting as: Z S b b | x), K(· | x) dµ(x). W22 K(· Lvalid (K) := R inf K:
K(·|x)dµ(x)=ν
Let MSvalid (N) denote the corresponding minimax risk. Lemma 9. For any µ ∈ P2 (Rd ) and any N ⊆ P2 (Rd ), MSvalid (N) = MW2 (N).
(23)
b and let νb be its Proof. We first prove the lower bound. Fix any stochastic estimator K, induced terminal law. For any valid kernel K from µ to ν, the collection of optimal couplings b | x) and K(· | x), integrated over x ∼ µ, gives a coupling of νb and ν. Therefore, between K(· Z b | x), K(· | x) dµ(x) ≥ W 2 (b W22 K(· 2 ν , ν). Taking the infimum over valid K gives b ≥ W22 (b LSvalid (K) ν , ν), 18
and the same minimax argument as in Lemma 3 yields MSvalid (N) ≥ MW2 (N). For the reverse inequality, fix any distribution estimator νe and define the data-dependent kernel b | x) := νe(·), K(· x ∈ Rd . This kernel ignores x and has induced terminal law νe. For any target ν, the kernel K(· | x) := ν(·) is valid from µ to ν, and hence Z S b Lvalid (K) ≤ W22 (e ν , ν) dµ(x) = W22 (e ν , ν). Taking expectation, supremum over ν, and infimum over νe proves the reverse inequality.
C
Detailed Proofs
C.1
Proof of Lemma 2
We first prove the lower bound. Fix any measurable map T such that T# µ = ν, and let X ∼ µ. Then (Tb(X), T (X)) is a coupling of νb and ν. Therefore, by the definition of the Wasserstein distance, Z ∥Tb(x) − T (x)∥p dµ(x) = E∥Tb(X) − T (X)∥p ≥ Wpp (b ν , ν). 2
2
Taking the infimum over all T satisfying T# µ = ν gives (1). Now suppose that there exists an optimal Monge map S from νb to ν. Define T ⋆ := S ◦ Tb. Then ⋆ µ = S# (Tb# µ) = S# νb = ν, T#
so T ⋆ is a valid transport map from µ to ν. Moreover, Z Z p ⋆ b ∥T (x) − T (x)∥2 dµ(x) = ∥Tb(x) − S(Tb(x))∥p2 dµ(x). Since Tb# µ = νb, the last display equals Z ∥z − S(z)∥p2 db ν (z) = Wpp (b ν , ν). Combining this upper bound with (1) proves equality.
C.2
Proof of Lemma 3
Fix any map estimator Tb, and write νb := Tb# µ. Then νb is a distribution estimator of ν. By Lemma 2, for every ν ∈ N, Z inf ∥Tb(x) − T (x)∥22 dµ(x) ≥ W22 (b ν , ν). T# µ=ν
19
Taking expectation, supremum over ν ∈ N, and then infimum over Tb gives Mvalid (N) ≥ inf sup Eν W22 (Tb# µ, ν) Tb ν∈N
≥ inf sup Eν W22 (b ν , ν), νb ν∈N
where the last infimum is over all distribution estimators, a larger class than those necessarily induced by map estimators. This proves the claim.
C.3
Proof of Proposition 1
The first inequality is Lemma 3. The second inequality follows pointwise from the fact that the OT map Tν is one valid transport map from µ to ν, so Z Z ∥Tb(x) − T (x)∥22 dµ(x) ≤ ∥Tb(x) − Tν (x)∥22 dµ(x). inf T# µ=ν
For the last inequality, take any distribution estimator νb and output the plug-in OT map Tνb. By (5), its OT-map risk is at most Cstab Eν W22 (b ν , ν). Taking the supremum over ν ∈ N and then the infimum over νb gives the desired bound.
C.4
Proof of Lemma 4
This result follows from a standard reduction from estimation to testing (see [27]). Fix an estimator Tb. It induces a test ψ(Y1 , . . . , Yn ) ∈ arg min ∥Tb − Ti ∥L2 (µ) . i∈{0,1}
On the event {ψ ̸= i}, the triangle inequality gives ∆OT = ∥T0 − T1 ∥L2 (µ) ≤ ∥Tb − Ti ∥L2 (µ) + ∥Tb − T1−i ∥L2 (µ) ≤ 2∥Tb − Ti ∥L2 (µ) . Thus
1 ∥Tb − Ti ∥2L2 (µ) ≥ ∆2OT 1{ψ ̸= i}. 4
Taking expectations, then the maximum over i, and finally the infimum over Tb, proves (7). For the valid map upper bound, fix S0 , S1 with Si# µ = νi and use the estimator Tb = S0 , which ignores the data. Under ν0 its valid map loss is zero, while under ν1 its valid map loss is at most ∥S0 − S1 ∥2L2 (µ) , since S1 is an admissible valid map. This proves (8).
C.5
Proof of Lemma 5
The identity (9) follows by direct calculation. Let s0 (x) = sgn(x · u0 ) and sθ (x) = sgn(x · uθ ). Since the linear terms cancel, Tθ (x) − T0 (x) = a{sθ (x)uθ − s0 (x)u0 }. The signs s0 and sθ disagree on two wedges whose total µ-mass is θ/π. On the complement, the squared difference is 4a2 sin2 (θ/2); on the wedges, it is 4a2 cos2 (θ/2). Therefore θ θ + cos2 (θ/2) , ∥Tθ − T0 ∥2L2 (µ) = 4a2 sin2 (θ/2) 1 − π π 20
which is comparable to θ for small θ. Next observe that νθ = (Rθ )# ν0 , where Rθ denotes rotation by angle θ. Thus the coupling Y 7→ Rθ Y , with Y ∼ ν0 , gives W22 (ν0 , νθ ) ≤ E∥Y − Rθ Y ∥22 ≲ θ2 , because ν0 is supported in a fixed bounded set. Finally, ν0 has density (π)−1 1Ω0 , where Ω0 is a finite union of half-disks, and νθ has density −1 (π) 1Rθ Ω0 . Since Ω0 has finite perimeter and is bounded, |Ω0 △Rθ Ω0 | ≲ θ. Consequently H 2 (ν0 , νθ ) ≲ θ.
C.6
Proof of Theorem 1
By Lemma 5, H 2 (ν0 , νθn ) ≲ θn . Choosing κ > 0 small enough ensures that nH 2 (ν0 , νθn ) is bounded by a sufficiently small universal constant. Hence the product measures ν0⊗n and νθ⊗n n have total variation distance bounded away from one, and the testing error en in Lemma 4 is bounded below by a universal constant. Combining Lemma 4 with (9) gives MOT (Nn ) ≳ θn ≳
1 . n
For the valid map upper bound, use the estimator Tb = T0 , which ignores the data. The loss is zero under ν0 . Under νθn , the map Rθn T0 is a valid transport from µ to νθn . Therefore inf
S# µ=νθn
∥T0 − S∥2L2 (µ) ≤ ∥T0 − Rθn T0 ∥2L2 (µ) ≲ θn2 ,
where the last inequality again uses boundedness of the support of ν0 . This proves (13).
C.7
Proof of Lemma 6
Fix an arbitrary estimator Tb. For each j, write Z ∥f ∥2j := ∥f (x)∥22 dµ(x). Gj
Fix j and fix the signs σ−j outside coordinate j. Let σ − = (σ−j , −1).
σ + = (σ−j , +1),
Define a test of the jth bit by nearest-neighbor decoding in the local L2 (Gj , µ) distance: σ bj ∈ arg min ∥Tb − T(σ−j ,τ ) ∥2j . τ ∈{±1}
Ties may be broken arbitrarily. If the true sign is +1 and σ bj = −1, then ∥Tb − Tσ− ∥j ≤ ∥Tb − Tσ+ ∥j . 21
Therefore, by the triangle inequality, ∥Tσ+ − Tσ− ∥j ≤ ∥Tσ+ − Tb∥j + ∥Tb − Tσ− ∥j ≤ 2∥Tb − Tσ+ ∥j . Thus
∆j 1 ∥Tb − Tσ+ ∥2j ≥ ∥Tσ+ − Tσ− ∥2j ≥ 4 4 on the event {b σj = −1}. The same argument with the signs reversed gives ∥Tb − Tσ− ∥2j ≥
∆j 4
on the event {b σj = +1}. Hence 1 1 E + ∥Tb − Tσ+ ∥2j + Eσ− ∥Tb − Tσ− ∥2j 2 σ 2 ∆j 1 ⊗n 1 ⊗n ≥ P + (b σj = −1) + Pσ− (b σj = +1) . 4 2 σ 2 ⊗n The term in brackets is the average error probability of a test between Pσ⊗n + and Pσ − . For any two distributions P, Q, the minimal average testing error under the uniform prior is 21 (1 − p TV(P, Q)). Moreover, TV(P, Q) ≤ 1 − ρ(P, Q)2 . Using (15), we obtain q 1 ⊗n 1 ⊗n 1 2 P + (b σj = −1) + Pσ− (b σj = +1) ≥ 1 − 1 − ρ0 . 2 σ 2 2
Therefore, for every fixed σ−j , ∆j 1 1 E + ∥Tb − Tσ+ ∥2j + Eσ− ∥Tb − Tσ− ∥2j ≥ 2 σ 2 8
q 2 1 − 1 − ρ0 .
(24)
Now average (24) over all choices of σ−j and sum over j. Since the sets G1 , . . . , GM are disjoint, 2−M
Z
X
Eσ
∥Tb(x) − Tσ (x)∥22 dµ(x) ≥
σ∈{±1}M
≥
M X
2−M
X
Eσ ∥Tb − Tσ ∥2j
j=1
σ∈{±1}M
1−
p M 1 − ρ20 X ∆j . 8 j=1
The supremum over σ is at least the average over σ, and the display holds for every estimator Tb. Taking the infimum over Tb proves the result.
C.8
Proof of Theorem 2
We first record a simple geometric fact which helps to identify the OT map in our construction. Lemma 10 (Isolated blob matching). Let Si = B(xi , r),
Ci = B(yi , r), 22
i = 1, . . . , N,
be pairwise disjoint source and target balls. Suppose that µ assigns mass pi uniformly to Si and ν assigns the same mass pi uniformly to Ci . Assume that the prescribed matching Si 7→ Ci satisfies max i
∥x − y∥2 < min
sup
inf
i̸=k x∈Si , y∈Ck
x∈Si , y∈Ci
∥x − y∥2 .
(25)
Then every optimal coupling between µ and ν is supported on N [
Si × Ci .
i=1
Consequently, if µ is absolutely continuous, the OT map sends Si to Ci for every i. Since Ci is a translate of Si , this map is the translation T (x) = x + (yi − xi ),
x ∈ Si .
Proof. Let π be an optimal coupling. Since optimal couplings for the squared Euclidean cost are cyclically monotone, the support of π is c-cyclically monotone, where c(x, y) = ∥x − y∥22 . Suppose, for contradiction, that π(Si × Ck ) > 0 for some i ̸= k. Consider the directed graph on {1, . . . , N } in which we draw an edge i → k whenever π(Si × Ck ) > 0. Because the source and target masses of each component are the same, any off-diagonal edge belongs to a directed cycle. Thus there exist distinct indices i1 , . . . , iℓ and points (xq , yq ) ∈ supp(π) ∩ (Siq × Ciq+1 ),
q = 1, . . . , ℓ,
where iℓ+1 = i1 . By (25), each xq ∈ Siq is strictly closer to every point of Ciq than to every point of Ciq+1 . Since yq−1 ∈ Ciq , we have ∥xq − yq ∥22 > ∥xq − yq−1 ∥22 , where y0 := yℓ . Summing over q gives ℓ X q=1
∥xq − yq ∥22 >
ℓ X
∥xq − yq−1 ∥22 ,
q=1
which contradicts cyclic monotonicity. Therefore π has no off-diagonal mass. It follows that the restriction of π to each Si × Ci is an optimal coupling between the uniform measure on Si and the uniform measure on Ci . Since Ci = Si + (yi − xi ), the translation x 7→ x + (yi − xi ) is an optimal map. When the source is absolutely continuous, the OT map is unique µ-a.e., and hence the OT map agrees with this translation on each Si . We now verify (25) for our construction. At the level of centers, the assigned source-target distance in each block is σ σ ∥xj,L − yj,L ∥22 = ∥xj,R − yj,R ∥22 = a2 + (ε − θn )2 .
The closest incorrectly assigned target center is the opposite target center in the same block, for which the squared distance is a2 + (ε + θn )2 . Indeed, target centers in different blocks have horizontal distance at least 3ε − θn from the source center under consideration, whereas the 23
opposite target center in the same block has horizontal distance ε + θn ; since θn ≪ ε, the latter is the closest incorrect target center. Thus the center-level distance gap is p p 4εθn p a2 + (ε + θn )2 − a2 + (ε − θn )2 = p ≳a εθn . 2 2 a + (ε + θn ) + a2 + (ε − θn )2 All centers remain in a fixed bounded set. Passing from centers to balls of radius rn perturbs distances by at most Crn , where C depends only on the diameter of this bounded set and on a. Since rn ≪ εθn , the strict separation (25) holds for all sufficiently large n. Therefore the σ and OT map Tσ from µ to νσ sends the source ball around xj,L to the target ball around yj,L σ the source ball around xj,R to the target ball around yj,R , by translation. Lemma 11. There exists a constant ca > 0, depending only on a, such that if rn ≤ ca εθn , then, for all sufficiently large n, the following statements hold: 1. For every σ ∈ {±1}n and every j = 1, . . . , n, Z ∥Tσ (x) − Tσ(j) (x)∥22 dµ(x) = 4a2 ε. Gj
Thus the local separation condition in Lemma 6 holds with ∆j = 4a2 ε. 2. If Pσ = νσ , then for every σ and every j, n ρ(Pσ⊗n , Pσ⊗n (j) ) = (1 − ε) .
In particular, since ε = 1/n, there is a universal constant ρ0 > 0 such that ρ(Pσ⊗n , Pσ⊗n (j) ) ≥ ρ0 for all sufficiently large n. Proof. Let σ (j) be obtained from σ by flipping the jth sign. On the left source ball, (j)
σ σ yj,L − yj,L = (0, 2σj a),
and on the right source ball, (j)
σ σ yj,R − yj,R = (0, −2σj a).
Thus, for every x ∈ Gj , ∥Tσ (x) − Tσ(j) (x)∥22 = 4a2 . Since µ(Gj ) = ε, it follows that Z Gj
∥Tσ (x) − Tσ(j) (x)∥22 dµ(x) = 4a2 ε.
It remains to verify the Hellinger affinity condition. The distributions νσ and νσ(j) agree on every block except block j, whose total mass is ε. Inside block j, their supports are disjoint 24
for all sufficiently large n, since rn ≪ εθn ≤ θn and a > 0 is fixed. Hence the one-sample Hellinger affinity is exactly the common mass: ρ(νσ , νσ(j) ) = 1 − ε. Hellinger affinity tensorizes under products, so n n ρ(νσ⊗n , νσ⊗n (j) ) = ρ(νσ , νσ (j) ) = (1 − ε) .
Since ε = 1/n,
1 n (1 − ε) = 1 − n n
is bounded below by a positive universal constant for all sufficiently large n. This proves the Hellinger affinity condition and completes the proof. An immediate consequence of this result is that the family we constructed satisfies the assumptions of Lemma 6 with M = n, ∆j = 4a2 ε,
j = 1, . . . , n,
and with a universal Hellinger affinity lower bound ρ0 > 0, which in turn yields the lower bound on MOT (Nn ). C.8.1
Upper Bounds on the Valid Map Risk
To conclude the proof of the theorem we need to upper bound Mvalid (Nn ). Let o = (1, . . . , 1) and use the deterministic estimator Tb := To . Fix any true sign vector σ. We construct a valid map Sσ from µ to νσ that stays close to To . On block j, if σj = 1, set Sσ = To . If σj = −1, then To sends the right source blob to the upper target blob centered at (uj + θn , a) and the left source blob to the lower target blob centered at (uj − θn , −a). Instead, define Sσ to send the right source blob to the upper target blob of νσ , centered at (uj − θn , a), and the left source blob to the lower target blob of νσ , centered at (uj + θn , −a). This changes only the horizontal coordinate, by 2θn . Thus Sσ# µ = νσ and, on every source point, ∥To (x) − Sσ (x)∥2 ≤ 2θn . Therefore ∥To − Sσ ∥2L2 (µ) ≤ 4θn2 . Since this holds for every σ, we have Mvalid (Nn ) ≤ 4θn2 = 4e−2n , which proves (18).
25