Aram-Alexandre Pooladian
email: pooladian<aram-alexandre.pooladian@nyu.edu>.

Vincent Divol

Jonathan Niles-Weed

Minimax estimation of discontinuous optimal transport maps: The semi-discrete case

We consider the problem of estimating the optimal transport map between two probability distributions, P and Q in R d , on the basis of i.i.d. samples. All existing statistical analyses of this problem require the assumption that the transport map is Lipschitz, a strong requirement that, in particular, excludes any examples where the transport map is discontinuous. As a first step towards developing estimation procedures for discontinuous maps, we consider the important special case where the data distribution Q is a discrete measure supported on a finite number of points in R d . We study a computationally efficient estimator initially proposed by Pooladian & Niles-Weed (2021), based on entropic optimal transport, and show in the semi-discrete setting that it converges at the minimax-optimal rate n -1/2 , independent of dimension. Other standard map estimation techniques both lack finite-sample guarantees in this setting and provably suffer from the curse of dimensionality. We confirm these results in numerical experiments, and provide experiments for other settings, not covered by our theory, which indicate that the entropic estimator is a promising methodology for other discontinuous transport map estimation problems.

Introduction

The theory of optimal transport (OT) defines a natural geometry on the space of probability measures [START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF][START_REF] Villani | Optimal transport: old and new[END_REF] and has become ubiquitous in modern data-driven tasks. In this area, optimal transport maps are a central object of study: suppose P and Q are two probability distributions with finite second moments, with P having a density with respect to the Lebesegue measure on R d . Then, Brenier's theorem (see Section 2.1) states that there exists a convex function φ 0 whose gradient defines a unique optimal transport map between P and Q. This map is optimal in the sense that it minimizes the following objective function:

∇φ 0 := argmin T ∈T (P,Q) 1 2 ∥x -T (x)∥ 2 dP (x) , (1)
where T (P, Q) := {T : R d → R d | X ∼ P, T (X) ∼ Q} is the set of transport maps between P and Q. The optimal value of the objective function in Equation ( 1) is called the (squared) 2-Wasserstein distance, written explicitly as

S 0 (P, Q) = 1 2 ∥x -∇φ 0 (x)∥ 2 dP (x) ,
though a more general formulation is available (see Section 2.1). Computing or approximating S 0 (P, Q) as well as ∇φ 0 has found use in several academic communities, such as economics [START_REF] Carlier | Vector quantile regression: an optimal transport approach[END_REF][START_REF] Chernozhukov | Monge-Kantorovich depth, quantiles, ranks and signs[END_REF][START_REF] Gunsilius | Matching for causal effects via multimarginal optimal transport[END_REF][START_REF] Torous | An optimal transport approach to causal inference[END_REF], computational biology [START_REF] Bunne | Learning single-cell perturbation responses using neural optimal transport[END_REF]2022;[START_REF] Demetc ¸i | Unsupervised integration of single-cell multi-omics datasets with disproportionate cell-type representation[END_REF][START_REF] Lübeck | Neural unbalanced optimal transport via cycle-consistent semi-couplings[END_REF][START_REF] Moriel | Novosparc: flexible spatial reconstruction of single-cell gene expression with optimal transport[END_REF][START_REF] Schiebinger | Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming[END_REF][START_REF] Yang | Predicting cell lineages using autoencoders and optimal transport[END_REF], and computer vision [START_REF] Feydy | Optimal transport for diffeomorphic registration[END_REF][START_REF] Solomon | Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains[END_REF]2016), among many others.

Practitioners seldom have access to P or Q, but instead have access to i.i.d. samples X 1 , . . . , X n ∼ P and Y 1 , . . . , Y n ∼ Q. On the basis of these samples, practitioners face both computational and statistical challenges when estimating ∇φ 0 . From a theoretical perspective, the statistical task of estimating optimal transport maps has attracted much interest in the last few years [START_REF] Deb | Rates of estimation of optimal transport maps using plug-in estimators via barycentric projections[END_REF][START_REF] Divol | Optimal transport map estimation in general function spaces[END_REF][START_REF] Ghosal | Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing[END_REF][START_REF] Hütter | Minimax estimation of smooth optimal transport maps[END_REF][START_REF] Manole | Plugin estimation of smooth optimal transport maps[END_REF][START_REF] Muzellec | Near-optimal estimation of smooth transport maps with kernel sums-of-squares[END_REF][START_REF] Pooladian | Entropic estimation of optimal transport maps[END_REF].

The first finite-sample analysis of this problem was performed by [START_REF] Hütter | Minimax estimation of smooth optimal transport maps[END_REF], who proposed an estimator for ∇φ 0 under the assumption that φ 0 is s + 1-times continuously differentiable, for s > 1. They showed that a wavelet-based estimator φW satisfies

E∥∇ φW -∇φ 0 ∥ 2 L 2 (P ) ≲ n -2s 2s+d-2 log 2 (n) ,
and that this rate is minimax optimal up to logarithmic factors. Their analysis requires that P and Q have bounded densities with compact support Ω ⊆ R d , and that φ 0 be both strongly convex and smooth. Implementing the estimator φW is computationally challenging even in moderate dimensions, and is practically infeasible for d > 3. Follow up work has proposed alternative estimators which improve upon φW either in computational efficiency or in the generality in which they apply. Though these subsequent works go significantly beyond the setting considered by [START_REF] Hütter | Minimax estimation of smooth optimal transport maps[END_REF], none has eliminated the crucial assumption that φ 0 is smooth, i.e., that the transport map ∇φ 0 is Lipschitz.

We highlight two estimators proposed in this line of work that are particularly practical. [START_REF] Manole | Plugin estimation of smooth optimal transport maps[END_REF] study the 1-Nearest Neighbor estimator T1NN . This estimator is obtained by solving the empirical optimal transport problem between the samples, which is then extended to a function defined on R d using a projection scheme; see Section 4 for more details. Given n samples from the source and target measures in R d , T1NN has a runtime of O(n 3 ) via the Hungarian Algorithm (see Peyré & Cuturi, 2019, Chapter 3), and, for d ≥ 5, achieves the rate

E∥ T1NN -∇φ 0 ∥ 2 L 2 (P ) ≲ n -2 d (2)
whenever the optimal Brenier potential φ 0 is smooth and strongly convex, and under mild regularity conditions on P . In another work, Pooladian & Niles-Weed (2021) conducted a statistical analysis of an estimator originally proposed by [START_REF] Seguy | Large-scale optimal transport and mapping estimation[END_REF] based on entropic optimal transport. The efficiency of Sinkhorn's algorithm for large-scale problems [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]Peyré & Cuturi, 2019) makes this estimator attractive from a computational perspective, and Pooladian & Niles-Weed (2021) also give statistical guarantees, though these fall short of being minimax-optimal.

Despite this progress, none of the aforementioned results can be applied in situations where ∇φ 0 is not Lipschitz. And in practice, even requiring the continuity of the transport map can be far too stringent. It is indeed too much to hope for that an underlying data distribution (e.g. over the space of images) has one single connected component; this is supported by recent work that stipulates that the underlying data distribution is the union of disjoint manifolds of varying intrinsic dimension [START_REF] Brown | The union of manifolds hypothesis and its implications for deep generative modelling[END_REF]. In such a setting, the transport map ∇φ 0 will not be continuous, demonstrating the need of considering the problem of the statistical estimation of discontinuous transport maps to get closer to real-world situations.

As a first step, we choose to focus on the case where the target distribution Q = J j=1 q j δ yj is discrete while the source measure P has full support, often called the semidiscrete setting in the optimal transport literature. In this setting, the optimal transport map ∇φ 0 is constant over regions known as Laguerre cells (each cell corresponding to a different atom of the discrete measure), while displaying discontinuities on their boundaries (see Section 2.1.1 for more details). Figure 1 provides such an example. Semidiscrete optimal transport therefore provides a natural class of discontinuous transport maps. We focus on this setting for two reasons. First, it has garnered a lot of attention in recent years, in both computational and theoretical circles (see, e.g., [START_REF] Altschuler | Asymptotics for semidiscrete entropic optimal transport[END_REF][START_REF] Chen | Semi-discrete normalizing flows through differentiable tessellation[END_REF]Mérigot et al., 2021), due in particular to its connection with the quantization problem [START_REF] Graf | Foundations of quantization for probability distributions[END_REF]. Second, the semi-discrete setting is intriguing from a statistical perspective: existing results show that statistical estimation problems involving semi-discrete optimal transport can escape the curse of dimensionality (del [START_REF] Del Barrio | Central limit theorems for empirical transportation cost in general dimension[END_REF]del Barrio et al., 2022a;[START_REF] Forrow | Statistical optimal transport via factored couplings[END_REF][START_REF] Hundrieser | Empirical optimal transport between different measures adapts to lower complexity[END_REF]. For example, Hundrieser et al. (2022, Theorem 3.2) show that if P n and Q n are empirical measures consisting of i.i.d. samples from P and Q, then the semi-discrete assumption implies

E|S 0 (P, Q) -S 0 (P n , Q n )| ≲ n -1/2 .
These results offer the tantalizing possibility that semidiscrete transport maps can be estimated at the rate n -1/2 , in sharp contrast to the dimension-dependent rates obtained in bounds such as (2). However, the optimal rates of estimation for semi-discrete transport maps are not known, and no estimators with finite-sample convergence guarantees exist.

MAIN CONTRIBUTIONS

We show that the computationally efficient estimator Tε based on entropically regularized optimal transport, originally studied in [START_REF] Pooladian | Entropic estimation of optimal transport maps[END_REF][START_REF] Seguy | Large-scale optimal transport and mapping estimation[END_REF], provably estimates discontinuous semi-discrete optimal transport maps at the optimal rate. More precisely, our contributions are the following:

1. For Q discrete and P with full support on a compact, convex set, we show that Tε achieves the following dimension-independent convergence rate to the optimal transport map (see Theorem 3.1)

E∥ Tε -∇φ 0 ∥ 2 L 2 (P ) ≲ n -1/2 , (3)
when the regularization parameter ε ≍ n -1/2 . We further show (Proposition 4.1) that this rate is minimax optimal.

2. As a by-product of our analysis, we give new parametric rates of convergence to the entropic Brenier map T ε , a result which improves exponentially on prior work in the dependence on ε (see Theorem 3.7 and Remark 3.8).

3. Our proof technique requires several new results, including a novel stability bound for the entropic Brenier maps (Proposition 3.9), and a new stability result for the entropic dual Brenier potentials in the semi-discrete case (Proposition 3.11).

4. We show that, unlike Tε , the 1-Nearest-Neighbor estimator is provably suboptimal in the semi-discrete setting (see Proposition 4.2) by exhibiting a discrete measure Q such that the risk suffers from the curse of dimensionality:

E∥ T1NN -∇φ 0 ∥ 2 L 2 (P ) ≳ n -1/d .

5.

In Section 4, we verify our theoretical findings on synthetic experiments. We also show by simulation that the entropic estimator appears to perform well even outside the semi-discrete setting, suggesting it as a promising choice for estimating other types of discontinuous maps.

NOTATION

The Euclidean ball centered at a with radius r > 0 is written as B(a; r).

L 2 (ρ) := E X∼ρ ∥f (X)∥ 2 . Simi- larly, we write Var ρ (f ) := E X∼ρ [(f (X) -E X∼ρ [f (X)]) 2 ]
for the variance of f with respect to ρ.

Background on optimal transport

Optimal transport

We define P(Ω) to be the space of probability measures whose support lies in a compact subset Ω ⊆ R d . If a probability measure P has a density with respect to the Lebesgue measure on R d with support Ω ⊆ R d , then we write P ∈ P ac (Ω).

For two probability measures P, Q ∈ P(Ω), we define the (squared) 2-Wasserstein distance to be [START_REF] Kantorovitch | On the translocation of masses[END_REF])

S 0 (P, Q) := min π∈Γ(P,Q) 1 2 ∥x -y∥ 2 dπ(x, y) , (4)
where π ∈ Γ(P, Q) ⊆ P(Ω × Ω) such that for any event A,

π(A × Ω) = P (A) , π(Ω × A) = Q(A) .
We call Γ(P, Q) the set of couplings between P and Q. In this work, we focus on the squared-Euclidean cost but Equation (4) is well-defined for convex, lower-semicontinuous costs; see [START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF][START_REF] Villani | Optimal transport: old and new[END_REF] for more information on optimal transport under general costs.

Equation ( 4) is a convex optimization problem on the space of joint measures, and a minimizer, denoted π 0 , always exists; we call π 0 an optimal plan from P to Q. Moreover, Equation (4) possesses the following dual formulation,

S 0 (P, Q) = 1 2 M 2 (P ) + 1 2 M 2 (Q) -inf (φ,ψ)∈Φ φ dP + ψ dQ (5)
where M 2 (P ) := ∥x∥ 2 dP (x) (similarly for M 2 (Q)) and the functions (φ, ψ)

∈ Φ ⊆ L 1 (P ) × L 1 (Q) satisfy ⟨x, y⟩ ≤ φ(x) + ψ(y) for all x, y ∈ Ω ,
As with the primal formulation, the infimum in Equation ( 5) is attained at functions (φ 0 , ψ 0 ). These minimizers are called (optimal) Brenier potentials. In particular, at optimality, we have that these Brenier potentials are convex conjugates of one another, i.e. the Legendre transform of one of the potentials gives the other:

φ * 0 (y) := sup x {⟨x, y⟩ -φ 0 (x)} = ψ 0 (y) , (6)
and vice-versa.

Apart from these two formulations of optimal transport under the squared-Euclidean cost, there exists a third, known as the Monge problem:

T 0 := argmin T ∈T (P,Q) 1 2 ∥x -T (x)∥ 2 dP (x) , (7)
where T (P, Q) is the set of admissible transport maps, i.e. for X ∼ P , T (X) ∼ Q. This optimization problem is non-convex in T , and a solution is not always guaranteed to exist for arbitrary P and Q.

The following theorem unifies these three formulations of optimal transport under the squared-Euclidean cost:

Theorem 2.1 (Brenier's theorem;Brenier, 1991). Let P ∈ P ac (Ω) and let Q ∈ P(Ω), then 1. the solution to Equation (7) exists and is of the form T 0 = ∇φ 0 , where φ 0 solves Equation (5)

2. π 0 is also uniquely defined as

dπ 0 (x, y) = dP (x)δ {∇φ0(x)} (y) .
When we want to place emphasis on the underlying measures, we will write φ 0 = φ P →Q 0 , ψ 0 = ψ P →Q 0 and T 0 = T P →Q 0 .

OT IN THE SEMI-DISCRETE CASE

In optimal transport, the semi-discrete setting refers to the case where P has as density with respect to the Lebesgue measure on R d , and Q is a discrete measure supported on points. The following theorem characterizes the optimal transport map in this situation, which exhibits a particular structure compared to the general results in the previous section. Let [J] = {1, . . . , J}.

Proposition 2.2 [START_REF] Aurenhammer | Minkowski-type theorems and least-squares clustering[END_REF]. If P ∈ P ac (Ω) and Q is a discrete measure supported on the points y 1 , . . . , y J , then the optimal transport map ∇φ 0 is given by

∇φ 0 (x) := argmax j∈[J] {⟨x, y j ⟩ -ψ 0 (y j )} , (8)
where ψ 0 is the dual to φ 0 in the sense of Equation (6).

Here, the optimal dual Brenier potential ψ 0 can be identified with a vector in R J , defined by the number of atoms, and the optimal Brenier potential is consequently given by

φ 0 := max j∈[J]
{⟨x, y j ⟩ -ψ 0 (y j )} .

Although φ 0 is not differentiable, only subdifferentiable, we still use the gradient notation as ∇φ 0 is well-defined P -almost everywhere.

The map ∇φ 0 partitions the space into J convex polytopes L j := ∇φ -1 0 ({y j }) called Laguerre cells; recall Figure 1. From this definition, it is clear that for a given x ∈ L j , x → ∇φ 0 (x) = y j is the optimal transport mapping. The difficulty in finding this map lies in determining the cells L j , or equivalently the dual variables ψ 0 (y j ).

Entropic optimal transport

Entropic regularization was introduced to both optimal transport and machine learning communities in the seminal paper by [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF], allowing approximate optimal transport distances to be computed at unprecedented speeds. Entropic optimal transport (EOT) is defined as the following regularized version of Equation ( 4): for ε > 0 S ε (P, Q) := min

π∈Γ(P,Q) 1 2 ∥x -y∥ 2 dπ(x, y) + εKL(π∥P ⊗ Q) , (9)
where KL(µ∥ν) = log dµ dν dµ when µ ∈ P(Ω) is absolutely continuous with respect to ν ∈ P(Ω). This speedup is due to the elegant connection of (9) to Sinkhorn's algorithm; we refer the interested reader to (Peyré & Cuturi, 2019, Chapter 4) for more information. The computational tractability of S ε compared to S 0 when dealing with many samples lends itself to being a central object of study in its own right (see, e.g., [START_REF] Chizat | Faster Wasserstein distance estimation with the Sinkhorn divergence[END_REF][START_REF] Genevay | Sample complexity of Sinkhorn divergences[END_REF][START_REF] Gonzalez-Sanz | Weak limits of entropy regularized optimal transport; potentials, plans and divergences[END_REF][START_REF] Mena | Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem[END_REF][START_REF] Rigollet | On the sample complexity of entropic optimal transport[END_REF]. Equation ( 9) admits the following dual formulation, which is now an unconstrained optimization problem [START_REF] Genevay | Entropy-regularized optimal transport for machine learning[END_REF][START_REF] Marino | An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm[END_REF])

S ε (P, Q) = 1 2 M 2 (P ) + 1 2 M 2 (Q) -inf φ,ψ φ dP + ψ dQ + ε (e (⟨x,y⟩-φ(x)-ψ(y))/ε -1) dP (x) dQ(y) , (10)
where (φ, ψ) ∈ L 1 (P )×L 1 (Q). When P and Q have finite second moments, Equation ( 9) admits a unique minimizer, π ε and we have the existence of minimizers to Equation ( 10), which we denote as (φ ε , ψ ε ). We call π ε the entropic optimal plan and (φ ε , ψ ε ) are called entropic Brenier potentials.

The following optimality relation further relates these primal and dual solutions [START_REF] Csiszár | I-divergence geometry of probability distributions and minimization problems[END_REF]:

dπ ε (x, y) := e (⟨x,y⟩-φε(x)-ψε(y))/ε dP (x) dQ(y) .
As a consequence, the following relationship holds at optimality:

S ε (P, Q) = 1 2 M 2 (P ) + 1 2 M 2 (Q) -φ ε dP -ψ ε dQ ,
and, moreover, we can define versions of φ ε and ψ ε such that the following relationships hold (see [START_REF] Mena | Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem[END_REF][START_REF] Nutz | Entropic optimal transport: Convergence of potentials[END_REF]) over all x ∈ R d and y ∈ R d , respectively:

φ ε (x) = ε log e (⟨x,y⟩-ψε(y))/ε dQ(y) , (11)
ψ ε (y) = ε log e (⟨x,y⟩-φε(x))/ε dP (x) , (12)
which are smoothed version of the Legendre transform, see Appendix A for details. In what follows, we always assume that we have selected φ ε and ψ ε so that these identities hold.

ENTROPIC BRENIER MAP

If (X, Y ) ∼ π ε , we may define the conditional probability

π x ε of Y given that X = x, with density dπ x ε dQ (y) ∝ exp ((⟨x, y⟩ -ψ ε (y))/ε) . ( 13
)
The barycentric projection of the optimal entropic coupling π ε , or entropic Brenier map, is a central object of study in several works e.g. (del Barrio et al., 2022b;[START_REF] Goldfeld | Limit theorems for entropic optimal transport maps and the Sinkhorn divergence[END_REF][START_REF] Pooladian | Entropic estimation of optimal transport maps[END_REF][START_REF] Rigollet | On the sample complexity of entropic optimal transport[END_REF], defined as

T ε (x) = y dπ x ε (y) = ∇φ ε (x) , (14)
where π x ε is as in Equation ( 13). Note that this quantity is well defined for all x ∈ R d as long as the source and target measures have compact support; in particular, it applies to both discrete and continuous measures. The second equality follows from Equation ( 11) and the dominated convergence theorem. As in the unregularized case, we will write

φ ε = φ P →Q ε , ψ ε = ψ P →Q ε and T ε = T P →Q ε
when we want to emphasize on the dependency with respect to the underlying measures.

This particular barycentric projection was proposed as a tool for large-scale optimal transport by [START_REF] Seguy | Large-scale optimal transport and mapping estimation[END_REF], but analyzed statistically for the first time by [START_REF] Pooladian | Entropic estimation of optimal transport maps[END_REF] as an estimator for the optimal transport map. We mention some of their results to highlight the differences with our new results for the semi-discrete setting in Section 3. First, they prove the following approximation result for T ε . Proposition 2.3 (Pooladian & Niles-Weed, 2021, Corollary 1). Let P, Q be compactly supported absolutely continuous measures on a compact set Ω ⊆ R d with densities p and q, that are bounded away from 0 and ∞. Assume that φ 0 is smooth and strongly convex, and that φ * 0 is at least C 3 . Then,

∥T ε -∇φ 0 ∥ 2 L 2 (P ) ≲ ε 2 . ( 15
)
Their main statistical result is the following theorem: Proposition 2.4 (Pooladian & Niles-Weed, 2021, Theorem 3). Suppose the same assumptions as Proposition 2.3, and let P n and Q n denote the empirical measures of P and Q constructed from i.i.d. samples. Let Tε = T Pn→Qn ε denote the entropic Brenier map from P n to Q n and let T 0 = ∇φ 0 be the optimal transport map from

P to Q. Then, if ε ≍ n -1 d ′ +3 E∥ Tε -T 0 ∥ 2 L 2 (P ) ≲ n - 3 2(d ′ +3) log(n) , (16)
where d ′ = 2⌈d/2⌉.

Note that in particular the the rate of convergence of the entropic estimator critically depends on the ambient dimension d in the continuous-to-continuous case.

RELATED WORK

Characterizing the convergence of entropic objects (e.g. potentials, cost, plans) to their unregularized counterparts in the ε → 0 regime has been a topic of several works in recent years. Convergence of the costs S ε to S 0 with precise rates was investigated in [START_REF] Chizat | Faster Wasserstein distance estimation with the Sinkhorn divergence[END_REF][START_REF] Conforti | A formula for the time derivative of the entropic cost and applications[END_REF][START_REF] Pal | On the difference between entropic cost and the optimal transport cost[END_REF]. The works [START_REF] Bernton | Entropic optimal transport: Geometry and large deviations[END_REF][START_REF] Carlier | Convergence of entropic schemes for optimal transport and gradient flows[END_REF]Ghosal et al., 2022;[START_REF] Léonard | From the Schrödinger problem to the Monge-Kantorovich problem[END_REF] study the convergence of the minimizers π ε to π 0 under varying assumptions. Convergence of the potentials in a very general setting was established in [START_REF] Nutz | Entropic optimal transport: Convergence of potentials[END_REF], though without a rate of convergence in ε. In the semidiscrete case, this gap was closed in [START_REF] Altschuler | Asymptotics for semidiscrete entropic optimal transport[END_REF] followed closely by [START_REF] Delalande | Nearly tight convergence bounds for semidiscrete entropic optimal transport[END_REF], which gave nonasymptotic rates. The Sinkhorn Divergence, a non-negative, symmetric version of S ε , was introduced in [START_REF] Genevay | Learning generative models with Sinkhorn divergences[END_REF], was statistically analysed in [START_REF] Goldfeld | Limit theorems for entropic optimal transport maps and the Sinkhorn divergence[END_REF] and also in (del Barrio et al., 2022b;[START_REF] Gonzalez-Sanz | Weak limits of entropy regularized optimal transport; potentials, plans and divergences[END_REF], and was connected to the entropic Brenier map in [START_REF] Pooladian | Debiaser beware: Pitfalls of centering regularized transport maps[END_REF]. The recent pre-print by [START_REF] Rigollet | On the sample complexity of entropic optimal transport[END_REF] proved parametric rates of estimation between the empirical entropic Brenier map and its population counterpart, though with an exponentially poor dependence on the regularization parameter (see Remark 3.8). Using covariance inequalities, the entropic Brenier potentials were used give a new proof of Caffarelli's contraction theorem; see [START_REF] Chewi | An entropic generalization of Caffarelli's contraction theorem via covariance inequalities[END_REF]; this approach was recently generalized in [START_REF] Conforti | Weak semiconvexity estimates for Schrödinger potentials and logarithmic Sobolev inequality for Schrödinger bridges[END_REF]. Entropic optimal transport has also come into contact with the area of deep generative modelling through the following works [START_REF] De Bortoli | Diffusion Schrödinger bridge with applications to score-based generative modeling[END_REF][START_REF] Finlay | Learning normalizing flows from Entropy-Kantorovich potentials[END_REF], among others.

Statistical performance of the entropic estimator in the semi-discrete setting

Let P n and Q n be the empirical measures associated with two n-samples from P and Q. We make the following regularity assumptions on P , already introduced by Delalande (2022).

(A) The measure P has a compact convex support Ω ⊆ B(0; R), with a density p satisfying 0 < p min ≤ p ≤ p max < ∞ for positive constants p min , p max and R.

For example, P can be the uniform distribution over Ω, or a truncated Gaussian distribution. Furthermore, we will need the following assumption on Q.

(B) The discrete probability measure Q = J j=1 q j δ yj is such that q j ≥ q min > 0 and y j ∈ B(0; R) for all j ∈ [J].

The goal of this section is to prove the following theorem: Theorem 3.1. Let P satisfy (A) and let Q satisfy (B). Let Tε = T Pn→Qn ε . Then, for ε ≍ n -1/2 and n large enough,

E∥ Tε -T 0 ∥ 2 L 2 (P ) ≲ n -1/2 . ( 17
)
Remark 3.2. We remark that the hidden constants in Theorem 3.7 and related results depend on J, p min , p max , q min and R. Remark 3.3 (Fixing the support via rounding). At present, the entropic map need not necessarily map exactly to one of {y 1 , . . . , y J }. In fact, Tε :

R d → conv({Y 1 , . . . , Y n }),
where conv(A) is the convex hull for some set A. In turn, the support of the entropic map does not in general match that of Q. However, this can be readily fixed with a rounding scheme. We can replace our estimator by Tε which is obtained by mapping the output of Tε to its nearest neighbor in the support of Q -this projection step is easy to compute, given that we essentially know the support of Q via samples. By viewing this as a projection onto an appropriate set (namely, the set of transport maps with codomain equal to the support of Q), and applying the triangle inequality, it holds that

E∥ Tε -T 0 ∥ 2 L 2 (P ) ≤ 2E∥ Tε -T 0 ∥ 2 L 2 (P )
but Tε matches the support of Q.

Let T ε = T P →Q ε denote the entropic Brenier map associated to P and Q. Our proof relies on the following bias-variance decomposition:

E∥ Tε -T 0 ∥ 2 L 2 (P ) ≲ E∥ Tε -T ε ∥ 2 L 2 (P ) +∥T ε -T 0 ∥ 2 L 2 (P ) .
Following the next two results (Theorem 3.4 and Theorem 3.7) and the preceding decomposition, the proof of Theorem 3.1 is merely a balancing act in the regularization parameter ε.

Theorem 3.4. Let P satisfy (A) and let Q satisfy (B). Then, for ε small enough,

∥T ε -T 0 ∥ 2 L 2 (P ) ≲ ε . ( 18
)
The proof of Theorem 3.4 relies on the following qualitative picture: if a point x belongs to some Laguerre cell L j , and is far away from the boundary of L j , then the entropic optimal plan π ε will send almost all of its mass towards the point y j = T 0 (x), sending an exponentially small amount of mass to the other points y j . Such a picture is correct as long as x is at distance at least ε from the boundary of the Laguerre cell L j , incurring a total error of order ε. A rigorous proof of Theorem 3.4 can be found in Appendix B.

Note that this rate is slower than the rate appearing in Proposition 2.3 in the continuous-to-continuous case. The following example shows that the dependency in ε is optimal in Theorem 3.4, indicating that the presence of discontinuities necessarily affects the approximation properties of the entropic Brenier map.

Example 3.5. Let P be a probability measure on R having a symmetric bounded density p continuous at 0, and let Q = 1 2 (δ -1 + δ 1 ). Following [START_REF] Altschuler | Asymptotics for semidiscrete entropic optimal transport[END_REF] Section 3), one can check that the entropic Brenier map in this setting is the following scaled sigmoidal function

T ε (x) = tanh(2x/ε) ,
whereas the optimal transport map T 0 (x) = sign(x). Then, performing a computation

∥T ε -T 0 ∥ 2 L 2 (P ) = 2 ∞ 0 (1 -tanh(2x/ε)) 2 p(x) dx = ε ∞ 0 (1 -tanh(u)) 2 p(uε/2) du = εp(0)(log(4) -1) + o(ε) ,
where in the last step we invoked the dominated convergence theorem, and computed the limiting integral. Remark 3.6. Assumption (A) can be relaxed for Theorem 3.4 to hold. More precisely, it can be replaced by Assumptions 2.2 and 2.9 of [START_REF] Altschuler | Asymptotics for semidiscrete entropic optimal transport[END_REF], that hold for unbounded measures such as the normal distribution.

Finally, we present the sample-complexity result:

Theorem 3.7. Let P satisfy (A) and let Q satisfy (B). Then, for 0

< ε ≤ 1 such that log(1/ε) ≲ n/ log(n) E∥ Tε -T ε ∥ 2 L 2 (P ) ≲ ε -1 n -1 . ( 19
)
Remark 3.8. In [START_REF] Rigollet | On the sample complexity of entropic optimal transport[END_REF], the authors show that if P and Q are merely compactly supported with

supp(P ), supp(Q) ⊆ B(0; R), then E∥ Tε -T ε ∥ 2 L 2 (P ) ≲ e cR 2 /ε ε -1 n -1 , (20)
where c > 0 is some absolute positive constant. Thus, under the additional structural assumptions of the semi-discrete formulation, we are able to significantly improve the rate of convergence between the empirical and population entropic Brenier maps.

The proof of Theorem 3.7 relies on a novel stability result, reminiscent of (Manole et al., 2021, Theorem 6), which is of independent interest. We provide the proof in Appendix C.

Proposition 3.9. Let µ, ν, µ ′ , ν ′ be four probability measures supported in B(0; R). Then the entropic maps T µ→ν ε and

T µ ′ →ν ′ ε satisfy ε 8R 2 ∥T µ→ν ε -T µ ′ →ν ′ ε ∥ 2 L 2 (µ) ≤ (φ µ ′ →ν ′ ε -φ µ→ν ε ) dµ + (ψ µ ′ →ν ′ ε -ψ µ→ν ε ) dν + εKL(ν∥ν ′ )
Remark 3.10. The right side of the bound in Proposition 3.9 is equal to

S ε (µ, ν) -S ε (µ ′ , ν ′ ) + f µ ′ →ν ′ ε d(µ ′ -µ) + g µ ′ →ν ′ ε d(ν ′ -ν) + εKL(ν∥ν ′ ) ,
where

f µ ′ →ν ′ ε = 1 2 ∥ • ∥ 2 -φ µ ′ →ν ′ ε and g µ ′ →ν ′ ε = 1 2 ∥ • ∥ 2 - ψ µ ′ →ν ′ ε
. Proposition 3.9 is therefore the entropic analogue of the stability bounds of Manole et al. (2021, Theorem 6) and Ghosal & Sen (2022, Lemma 5.1). Unlike those results, Proposition 3.9 allows both the source and target measure to be modified, and does not require any smoothness assumptions.

Proof sketch of Theorem 3.7

To prove Theorem 3.7, we first consider the one-sample setting, where we assume that we only have access to samples Y 1 , . . . , Y n ∼ Q, but we have full access to P . We then consider the one-sample entropic estimator T P →Qn ε . We apply Proposition 3.9 with µ = µ ′ := P , ν := Q n and ν ′ := Q, yielding (see Corollary C.1 for details)

ε 8R 2 E∥T P →Qn ε -T ε ∥ 2 L 2 (µ) ≤ E (ψ ε -ψ P →Qn ε ) d(Q n -Q) + εKL(Q n ∥Q)
Let χ 2 (P ∥Q) denote the χ 2 -divergence between probability measure. Young's inequality (see Lemma H.1) and the inequality KL(Q n ∥Q) ≤ χ 2 (Q n ∥Q) yield the following bound:

E∥T P →Qn ε -T ε ∥ 2 L 2 (P ) ≤ 8R 2 ε E[Var Q (ψ P →Qn ε -ψ ε )] 2 + E[χ 2 (Q n ∥Q)] 2 + 8R 2 E[χ 2 (Q n ∥Q)] .
To complete our proof sketch, we use a new stability result on the entropic dual Brenier potentials, catered for the semidiscrete setting.

Proposition 3.11. Let µ be a measure that satisfies (A). Let ν, ν ′ be two discrete probability measures supported on {y 1 , . . . , y J }, with ν ′ ≥ λν for some λ > 0. Then, for 0

< ε ≤ 1, Var ν (ψ µ→ν ′ ε -ψ µ→ν ε ) ≤ C λ 2 χ 2 (ν ′ ∥ν), (21)
where C depends on R, p min and p max .

Moreover, a computation provided in Lemma H.2 shows that E[χ 2 (Q n ∥Q)] = J-1 n , which is enough to conclude the proof of the one-sample case, see Appendix E for details. The two-sample setting is tackled using similar reasoning, where we ultimately prove in Appendix F that the risk E∥ Tε -

T P →Qn ε ∥ 2 L 2 (P ) is upper bounded by 8R 2 ε E (φ P →Qn ε -φ Pn→Qn ε ) d(P n -P ) .
Such a quantity can again be related to the estimation of the dual potentials ψ P →Qn ε and ψ Pn→Qn ε . Using the same reasoning as before, we expect a parametric rate of convergence for this term as well. Merging the two results completes the proof of Theorem 3.7. We refer to Appendix F for full details.

Comparing against the 1NN estimator

Rate optimality of the entropic Brenier map

The upper bound of Theorem 3.7 shows that our estimator achieves the n -1/2 rate. In fact, the following simple proposition tells us that this rate is optimal in the semi-discrete case.

Proposition 4.1. Let P be the uniform distribution on [-1/2, 1/2] d and for any J ≥ 2, let Q J denote the space of of probability measures with at most J atoms, supported on [-1/2, 1/2] d . Define the minimax rate of estimation

R n (Q J ) = inf T sup Q∈Q J E Q n [∥ T -T P →Q 0 ∥ 2 L2(P ) ] .
Then, it holds that R n (Q J ) ≥ n -1/2 /64.

Proof. Let e be a vector of the canonical basis of R d , scaled by 1/2. Fix 0 < r < 1/2 and let

Q 0 = 1 2 δ -e + 1 2 δ e and Q 1 = ( 1 2 -r)δ -e + ( 1 2 + r)δ e . A computation gives ∥T P →Q0 0 -T P →Q1 0 ∥ 2 L2(P ) = r.
Therefore, by Le Cam's lemma (see, e.g., Wainwright, 2019, Chapter 15),

R n (Q J,R ) ≥ r 8 (1 -d TV (Q n 0 , Q n 1 )). ( 22
)
Let d H 2 (Q 0 , Q 1 ) denote the (squared) Hellinger distance between measures. We have

d TV (Q n 0 , Q n 1 ) 2 ≤
d H 2 (Q n 0 , Q n 1 ) ≤ nd H 2 (Q 0 , Q 1 ). Furthermore, a compu- tation gives d H 2 (Q 0 , Q 1 ) = 1 2 -r -1 2 2 + 1 2 + r -1 2 2 = 2 -( √ 1 + 2r + √ 1 -2r) ≤ 4r 2 .
We obtain the conclusion by picking r = n -1/2 /4.

The 1NN estimator is proveably suboptimal

The 1-Nearest-Neighbor estimator, henceforth denoted T1NN , was proposed by [START_REF] Manole | Plugin estimation of smooth optimal transport maps[END_REF] as a computational surrogate for estimating optimal transport maps in the low smoothness regime. Written succinctly, their estimator is

T1NN (x) = n i=1 1 Vi (x)Y π(i) , where (V i ) n i=1
are Voronoi regions i.e.

V i := {x ∈ R d : ∥x -X i ∥ ≤ ∥x -X k ∥ , ∀ k ̸ = i} ,
and π is the optimal transport plan between the empirical measures P n and Q n , which amounts to a permutation.

Computing the closest X i to a new sample x has runtime O(n log(n)), though the complexity of this estimator is determined by computing the plan π, which takes O(n 3 ) time via, e.g., the Hungarian Algorithm (see Peyré & Cuturi, 2019, Chapter 3).

When φ 0 is smooth and strongly convex, [START_REF] Manole | Plugin estimation of smooth optimal transport maps[END_REF] showed that, for d ≥ 5,

E∥ T1NN -∇φ 0 ∥ 2 L 2 (P ) ≲ n -2/d
. In contrast to the rate optimality of the entropic Brenier map, we now show that T1NN is proveably suboptimal in the semi-discrete setting. Not only does it fail to recover the minimax rate obtained by the entropic Brenier map, but its performance in fact degrades in comparison to the smooth case. A proof appears in Appendix G. Proposition 4.2. There exist a measure P satisfying (A) and a discrete measure Q satisfying (B) such that for d ≥ 3

E∥ T1NN -T P →Q 0 ∥ 2 L 2 (P ) ≳ n -1/d .

Experiments

We briefly verify our theoretical findings on synthetic experiments. To create the following plots, we draw two sets of n i.i.d. points from P , (X 1 , . . . , X n ) and (X ′ 1 , . . . , X ′ n ), and create target points

Y i = T 0 (X ′ i )
, where T 0 is known to us in advance in order to generate the data. Our estimators are computed on the data (X 1 , . . . , X n ) and (Y 1 , . . . , Y n ), and we evaluate the Mean-Squared error criterion

MSE( T ) = ∥ T -T 0 ∥ 2 L 2 (P )
of a given map estimator T using Monte Carlo integration, using 50000 newly sampled points from P . We plot the means across 10 repeated trials, accompanied by their standard deviations.

SEMI-DISCRETE EXAMPLE #1

First consider P = Unif([0, 1] d ) and create atoms {y 1 , . . . , y J } by partitioning the points along the first coordinate for all j ∈ [J]:

(y j )[1] = (j -1/2) J , (y j )[2] = • • • = (y j )[d] = 0.5 .
We choose uniform q j = 1/J for j ∈ [J]. In this case, it is easy to see that the optimal transport map T 0 (x) is uniquely defined by the first coordinate of x 1 . Figure 2 illustrates the rate-optimal performance of the entropic Brenier map, and the proveably suboptimal performance of the 1-Nearest-Neighbor estimator.

SEMI-DISCRETE EXAMPLE #2

We now consider a synthetic experiment with far less symmetry. Let P = Unif([0, 1] d ), and fix J ∈ N. We randomly generate y 1 , . . . , Y J ∈ [0, 1] d , and also randomly generate ψ 0 ∈ R J , and consider the optimal transport map T 0 (x) = argmin j∈[J] {x ⊤ y j -(ψ 0 ) j }. We define Q = (T 0 ) ♯ P , leading to the same setup as before, but with a less structured optimal transport map. We consider J = 5 and d = 50, and repeat the procedure of the preceding section to generate our data, and the resulting estimator.

DISCONTINUOUS EXAMPLE

We turn our attention to a discontinuous transport map, where for x ∈ R d , all the coordinates are fixed except for the first one

T 0 (x) = 2sign(x[1]) ⊗ x[2] ⊗ • • • ⊗ x[d] .
We choose P = Unif([-1, 1] d ) to exhibit a discontinuity in the data. Focusing on d = 10, we see in Figure 4 that the entropic map estimator avoids the curse of dimensionality and enjoys a faster convergence rate, with better constants.

Conclusion

Understanding optimal transport maps in the semi-discrete case is a natural stepping-stone to understanding the case for general discontinuous transport maps. In this work, we propose a tractable, minimax optimal estimator of the Brenier map in the semi-discrete setting, where the rate of estimation is dimension independent. To prove our result, we require several new results and techniques, and, as a by-product of our analysis, give the first parametric rates of estimation the entropic Brenier map, without exponential dependence in the regularization parameter. Our synthetic experiments indicate that the entropic Brenier map might be useful in estimating other variants of discontinuous transport maps, which constitutes an interesting direction for future research.

A. Reminders on semi-discrete entropic optimal transport

We recall in this section some known results on entropic optimal transport that will be needed later. Let µ, ν ∈ P(Ω), where Ω ⊂ B(0; R) is a compact set.

Lemma A.1 [START_REF] Genevay | Sample complexity of Sinkhorn divergences[END_REF]. The entropic potential (φ µ→ν ε , ψ µ→ν ε ) have a bounded amplitude, in the sense that

max x∈Ω φ µ→ν ε -min x∈Ω φ µ→ν ε ≤ cR (23)
for some absolute constant c, and similarly for ψ µ→ν ε .

Assume now that ν = J j=1 ν j δ yj is a discrete measure. In this situation, only the values of the dual potential ψ µ→ν ε on the points y 1 , . . . , y J are relevant. We therefore consider ψ µ→ν ε as a vector in R J . The potentials φ µ→ν ε and ψ µ→ν ε are dual of one another, in the sense of the ε-Legendre transform. Given a finite measure ρ, the ε-Legendre transform of a function h with respect to ρ is given by

Φ ρ ε (h)(x) = ε log e (⟨x,y⟩-h(x))/ε dρ(x). ( 24
)
Relations ( 11) and ( 12) express that

φ µ→ν ε = Φ ν ε (ψ µ→ν ε
) and vice-versa. In the semi-discrete setting, it is also convenient to introduce the ε-Legendre transform with respect to the counting measure σ on {y 1 , . . . , y J }. For a vector ψ ∈ R J , we have

Φ ε (ψ)(x) := Φ σ ε (ψ)(x) = ε log e (⟨x,yj ⟩-ψ(yj ))/ε . ( 25
)
The Φ ε transform and the Φ ν ε transform are linked through the relation

Φ ν ε (ψ) = Φ ε ( ψ) where ψ(y j ) = ψ(y j ) -ε log ν j , (26)
where we call ψ a shifted potential. With this notation, the optimality condition on the potentials can be rephrased. Let

F µ→ν ε : ψ ∈ R J → Φ ε (ψ) dµ + ψ dν . (27)
Then, the function F µ→ν ε is minimized at ψµ→ν ε . For ψ ∈ R J and x ∈ R d , we introduce the probability measure supported on {y 1 , . . . , y J } given by ∀i ∈

[J], π x ε [ψ](y i ) =
e (⟨x,yi⟩-ψ(yi))/ε J j=1 e (⟨x,yj ⟩-ψ(yj ))/ε = e (⟨x,yi⟩-Φε(ψ)(x)-ψ(yi))/ε . (28)

A computation gives ∇F µ→ν ε (ψ) = π x ε [ψ] dµ(x) -ν, so that at optimality, we have

π x ε [ ψµ→ν ε ] dµ(x) = ν. (29)
In this case,

π x ε = π x ε [ ψµ→ν ε ]
is the conditional distribution of the second marginal of π ε given that the first is equal to x, as in Section 2.2.1. More generally, for any potential ψ, the first order condition implies that ψ is equal to ψµ→ν ψ ε , the optimal dual potential between µ an ν ψ = π x ε [ψ] dµ(x).

B. Bound on the approximation error

Proof of Theorem 3.4. Let i, j ∈ [J]. We define the jth slack at x ∈ L i by

1 2 ∆ ij (x) = -⟨x, y j ⟩ + φ 0 (x) + ψ 0 (y j ). ( 30
)
As φ 0 is the Legendre transform of ψ 0 , we have ∆ ij (x) ≥ 0. If the cells L i and L j have a nonempty intersection, the set

H ij (t) = {x ∈ L i : ∆ ij (x)
= t} represents the trace on L i of the hyperplane spanned by the boundary between L i and L j , shifted by t. It is stated in [START_REF] Altschuler | Asymptotics for semidiscrete entropic optimal transport[END_REF] that for every nonnegative measurable function

f : R → R + , Li f (∆ ij (x))p(x) dx = 1 2∥y i -y j ∥ ∞ 0 f (t)h ij (t) dt, (31)
where

h ij (t) = Hij (t) p(x) dH d-1 (x) and H d-1 is the (d -1)-dimensional Hausdorff measure. In particular, w ij = h ij (0)
is the (weighted) surface of the boundary between the i th and j th Laguerre cells (should it exist). Given x ∈ L i , let s(x) = min j̸ =i 1 2 ∆ ij (x). When the point x is sufficiently inside its Laguerre cell, the conditional probability π x ε becomes extremely concentrated around the point y i , as the next lemma shows. Note that π x 0 = δ yi when x ∈ L i . Lemma B.1. Let x ∈ L i . For ε small enough, it holds that for every j ∈ [J], |π x ε (y j ) -π x 0 (y j )| ≤ ce -s(x)/ε , where c depends on J, the distances ∥y i -y j ∥ and on the quantities w ij .

Such a result was already stated in (Delalande, 2022, Corollary 2.2), although while requiring that the source measure P has a Hölder continuous density. Only assumption (A) is needed here.

Proof. According to (Altschuler et al., 2022, Proposition 4.6), for ε small enough,

ε -1 ∥ ψε -ψ 0 ∥ ∞ ≤ C, ( 32
)
where ψε is the shifted version of ψ ε (see ( 25)) and C depends on the distances ∥y i -y j ∥ and on the w ij s. Following [START_REF] Delalande | Nearly tight convergence bounds for semidiscrete entropic optimal transport[END_REF], Proof of Corollary 2.2) and ( 28), we have for j ̸ = i

|π x ε (y j ) -π x 0 (y j )| = π x ε (y j ) = e (⟨x,yj ⟩-ψε(yj ))/ε J j ′ =1 e (⟨x,y j ′ ⟩-ψε(yj′ ))/ε ≤ e 2C e (⟨x,yj ⟩-ψ0(yj ))/ε J j ′ =1 e (⟨x,y j ′ ⟩-ψ0(y j ′ ))/ε ≤ e 2C e -s(x)/ε . A similar computation yields that |π x ε (y i ) -π x 0 (y i )| = |π x ε (y i ) -1| ≤ Je 2C e -s(x)/ε .
We can bound for any x ∈ L i ,

∥T ε (x) -T 0 (x)∥ = ∥ J j=1 y j (π x ε (y j ) -π x 0 (y j ))∥ ≤ c J j=1 ∥y j ∥e -s(x)/ε . (33)
Therefore, letting C ′ denote a constant, which may depend on J, whose value may change from line to line, we obtain

∥T ε -T 0 ∥ 2 L2(P ) = J i=1 Li ∥T ε (x) -T 0 (x)∥ 2 dP (x) ≤ C ′ J i=1 Li J j=1 e -2s(x)/ε dP (x) (34)
≤ C ′ i̸ =j Li e -∆ij (x)/ε dP (x) ≤ C ′ i̸ =j 1 2∥y i -y j ∥ ∞ 0 e -t/ε h ij (t) dt , (35)
where in the second equality, we used the definition of s(x). Assumption (A) ensures that the functions h ij s are bounded, which implies that the right-hand side in ( 35) is of order ε.

C. Stability of entropic transport plans

Proof of Proposition 3.9. Note that we may assume without loss of generality that ν ≪ ν ′ and that KL(ν∥ν ′ ) < ∞, for otherwise the bound is vacuous. For notational convenience, we omit the dependence on ε in the subscripts.

Write π µ,ν = γ µ,ν (x, y)dµ(x)dν(y) for the entropic optimal plan between µ and ν, where γ µ,ν = exp 1 ε (⟨x, y⟩ -φ µ→ν (x) -ψ µ→ν (y)) , and analogously define

γ µ ′ ,ν ′ = exp 1 ε (⟨x, y⟩ -φ µ ′ →ν ′ (x) -ψ µ ′ →ν ′ (y)) .
Consider the measure γ µ ′ ,ν ′ (x, y) dµ(x) dν ′ (y). The first-order optimality condition for (φ µ ′ →ν ′ , ψ µ ′ →ν ′ ) implies that

γ µ ′ ,ν ′ (y) dν ′ (y) = 1 ∀x ∈ Ω , (36)
so that γ µ ′ ,ν ′ (x, y) dν ′ (y) is a probability measure. Let us write dπ x (y) = γ µ,ν (x, y) dν(y) and dρ x (y) = γ µ ′ ,ν ′ (x, y) dν ′ (y).

We make the following observations: first, T µ→ν (x) = y dπ x (y) and T µ ′ →ν ′ (x) = y dρ x (y). Second, the support of ρ x lies inside B(0; R); since any Lipschitz function f on B(0; R) satisfies sup x f (x) -inf x f (x) ≤ 2R, Hoeffding's lemma (see Boucheron et al., 2013, Lemma 2.2) implies that if f is Lipschitz and f dρ x = 0, then

e tf dρ x ≤ e 2R 2 t 2 ∀t ∈ R .
This implies (Bobkov & Götze, 1999, Theorem 3.1) that

W 1 (π x , ρ x ) 2 ≤ 8R 2 KL(π x ∥ρ x ) . (37)
Third, Jensen's inequality implies that for any coupling γ between π x and ρ x ,

∥y -y ′ ∥ dγ(y, y ′ ) ≥ (y -y ′ ) dγ(y, y ′ ) = ∥T µ→ν (x) -T µ ′ →ν ′ (x)∥ , (38)
so that in particular,

∥T µ→ν (x) -T µ ′ →ν ′ (x)∥ ≤ W 1 (π x , ρ x ).
Combining these facts, we obtain

1 8R 2 ∥T µ→ν (x) -T µ ′ →ν ′ (x)∥ 2 ≤ KL(π x ∥ρ x ) = log γ µ,ν γ µ ′ ,ν ′ (x, y) dν dν ′ (y) γ µ,ν (x, y) dν(y) . (39)
Integrating both sides of this equation with respect to µ yields

1 8R 2 ∥T µ→ν (x) -T µ ′ →ν ′ (x)∥ 2 L 2 (µ) ≤ log γ µ,ν γ µ ′ ,ν ′ (x, y) dν dν ′ (y) dπ µ,ν (x, y) . (40)
Expanding the definition of γ µ,ν and γ µ ′ ,ν ′ and using that log dν dν ′ (y) dπ µ,ν (x, y) = log dν dν ′ (y) dν(y) = KL(ν∥ν ′ ) yields the claim.

We now record two corollaries of this bound, which apply when either the source or the target measures of the entropic maps agree. Corollary C.1. For any µ, ν, ν ′ supported in B(0; R),

1 8R 2 ∥T µ→ν ε -T µ→ν ′ ε ∥ 2 L 2 (µ) ≤ ε -1 (ψ µ→ν ′ ε -ψ µ→ν ε ) d(ν -ν ′ ) + KL(ν∥ν ′ ) (41)
Proof. We apply Proposition 3.9 with µ = µ ′ , which yields (once again omitting the dependency in ε)

1 8R 2 ∥T µ→ν ε -T µ→ν ′ ε ∥ 2 L 2 (µ) ≤ ε -1 (φ µ→ν ′ -φ µ→ν ) dµ + (ψ µ→ν ′ -ψ µ→ν ) dν + KL(ν∥ν ′ ) . (42)
By definition, (φ µ→ν ′ , ψ µ→ν ′ ) minimizes the expression φ dµ + ψ dν ′ + ε e (⟨x,y⟩-φ(x)-ψ(y))/ε dµ(x) dν ′ (y) -ε, so, recalling that e (⟨x,y⟩-φ µ→ν ′ (x)-ψ µ→ν ′ (y))/ε dµ(x) dν ′ (y) = 1, we have in particular

φ µ→ν ′ dµ + ψ µ→ν ′ dν ′ ≤ φ µ→ν dµ + ψ µ→ν dν ′ + ε e (⟨x,y⟩-φ µ→ν (x)-ψ µ→ν (y))/ε dµ(x) dν ′ (y) -ε = φ µ→ν dµ + ψ µ→ν dν ′ ,
where we have used that the first-order optimality condition for (φ µ→ν , ψ µ→ν ) implies that e (⟨x,y⟩-φ µ→ν (x)-ψ µ→ν (y))/ε dµ(x) dν ′ (y) = 1 as well (see ( 11)). This implies

(φ µ→ν ′ -φ µ→ν ) dµ ≤ -(ψ µ→ν ′ -ψ µ→ν ) dν ′ . ( 43
)
Applying this inequality to (42) yields

1 8R 2 ∥T µ→ν ε -T µ→ν ′ ε ∥ 2 L 2 (µ) ≤ ε -1 (ψ µ→ν ′ -ψ µ→ν ) d(ν -ν ′ ) + KL(ν∥ν ′ ).
Corollary C.2. For any µ, µ ′ , ν supported in B(0; R),

1 8R 2 ∥T µ→ν ε -T µ ′ →ν ε ∥ 2 L 2 (µ) ≤ ε -1 (φ µ ′ →ν ε -φ µ→ν ε ) d(µ -µ ′ ) . (44)
Proof. We apply Proposition 3.9 with ν = ν ′ , yielding (dropping the dependency on ε)

1 8R 2 ∥T µ→ν -T µ ′ →ν ∥ 2 L 2 (µ) ≤ ε -1 (φ µ ′ →ν -φ µ→ν ) dµ + (ψ µ ′ →ν -ψ µ→ν ) dν . ( 45
)
An argument analogous to the one used in the proof of Corollary C.1 gives the inequality

φ µ ′ →ν dµ ′ + ψ µ ′ →ν dν ≤ φ µ→ν dµ ′ + ψ µ→ν dν , (46)
or, equivalently,

(ψ µ ′ →ν -ψ µ→ν ) dν ≤ -(φ µ ′ →ν -φ µ→ν ) dµ ′ , (47)
and combining this inequality with (45) proves the claim. ). Let ν = J j=1 ν j δ yj be a measure supported on {y 1 , . . . , y J } ⊆ B(0; R) and let µ supported on a compact convex set Ω ⊆ B(0; R) with a density p satisfying p min ≤ p ≤ p max for some p max ≥ p min > 0. For ψ ∈ R J , define ν ψ = π x ε [ψ] dµ(x) and assume that ν ψ ≥ λν for some 0 < λ ≤ 1. Then, we have for ε ∈ (0, 1)

F µ→ν ε (ψ) -min ψ F µ→ν ε ≥ Cλ • Var ν (ψ -ψ µ→ν ε ), (48)
where C = e 2R 2 pmax pmin + ε -1 pmin pmax .

Proof. As µ and ε are fixed, we will simply write ψ ν instead of ψ µ→ν ε , and write similarly F ν = F µ→ν ε . Recall the definition (25) of the shifted potential ψν (y j ) = ψ ν (y j ) -ε log ν j . According to (Delalande, 2022, Theorem 3.2), the functional F ν is minimized at the vector ψν , with

∀v ∈ R J , Var ν (v) ≤ e 2R 2 p max p min + ε v ⊤ ∇ 2 F ν ( ψν )v. (49)
For t ∈ [0, 1], let ψ t = ψν + t(ψ -ψν ) and let ν t = π x ε [ψ t ] dµ(x). The potential ψ t is the (shifted) entropic Brenier potential between µ and ν t , so that it minimizes the functional F νt (see Appendix A). Also, note that ∇ 2 F ν does not depend on ν, so that

v ⊤ ∇ 2 F ν (ψ t )v = v ⊤ ∇ 2 F νt (ψ t )v ≥ e 2R 2 p max p min + ε -1 Var νt (v). ( 50
) Let v = ψ -ψ µ→ν ε . A Taylor expansion of F ν gives F ν (ψ) -F ν ( ψν ) = 1 0 v ⊤ ∇ 2 F ν (ψ t )v dt ≥ e 2R 2 p max p min + ε -1 1 0 Var νt (v) dt. ( 51
)
Lemma D.2. Write ν t = J j=1 ν t,j δ yj . Then, for all t ∈ [0, 1] and j ∈ [J], we have ν t,j ≥ pmin pmax ν 1-t 0,j ν t 1,j .

This lemma is enough to conclude the proof. Indeed, ν 1 = ν ψ ≥ λν, so that it implies that Var νt (v) ≥ pmin pmax λVar ν (v).

Proof of Lemma D.2. According to (Delalande, 2022, Proof of Proposition 4.1),

Φ ε (ψ t )(tx + (1 -t)y) ≤ tΦ ε ( ψµ→ν ε )(x) + (1 -t)Φ ε (ψ)(y). (52)
Therefore, if we let h t (x) = e (⟨x,yj ⟩-ψt(yj )-Φε(ψt)(x))/ε , then we have h t (tx + (1 -t)y) ≥ h 0 (x) t h 1 (y) 1-t . By the Prékopa-Leindler inequality,

ν t,j = h t (x) dµ(x) ≥ p min X h t (x) dx ≥ p min X h 0 (x) dx t X h 1 (x) dx 1-t ≥ p min p max ν t 0,j ν 1-t 1,j .
Proof of Proposition 3.11. As in the previous proof, we drop the ε and µ dependency in our notation. Write ν k = J j=1 ν k,j δ yj for k = 0, 1, and define as before the shifted potentials ψν k (y j ) = ψ ν1 (y j ) -ε log ν k,j . Let θ > 0 be a parameter to fix. According to Proposition D.1, Lemma H.1, and using the inequality F ν1 ( ψν1 ) ≤ F ν1 ( ψν0 ), we have

CλVar ν0 ( ψν1 -ψν0 ) ≤ F ν0 ( ψν1 ) -F ν0 ( ψν0 ) ≤ F ν0 ( ψν1 ) -F ν1 ( ψν1 ) + F ν1 ( ψν0 ) -F ν0 ( ψν0 ) = ( ψν1 -ψν0 )( dν 0 -dν 1 ) ≤ θ 2 Var ν0 ( ψν1 -ψν0 ) + 1 2θ χ 2 (ν 1 ∥ν 0 ).
We pick θ = Cλ to conclude that

Var ν0 ( ψν1 -ψν0 ) ≤ 1 (Cλ) 2 χ 2 (ν 1 ∥ν 0 ). (53)
Therefore, using the inequality | log(a/b)| ≤ |a -b|/ min{a, b} for a, b > 0,

Var ν0 (ψ 1 -ψ 0 ) ≤ 2Var ν0 ( ψ1 -ψ0 ) + 2 J j=1 ν 0,j log ν 1,j ν 0,j 2 ≤ 2 (Cλ) 2 χ 2 (ν 1 ∥ν 0 ) + 2 J j=1 ν 0,j ν 1,j -ν 0,j min{ν 0,j , ν 1,j } 2 ≤ 2 (Cλ) 2 χ 2 (ν 1 ∥ν 0 ) + 2 λ 2 J j=1 1 ν 0,j (ν 1,j -ν 0,j ) 2 ≤ 2 (Cλ) 2 + 2 λ 2 χ 2 (ν 1 ∥ν 0 ).

E. Control of the fluctuations in the one-sample case

Lemma E.1 (Sample complexity in the one-sample case). Assume that P satisfy (A) and that Q satisfy (B). Then, it holds that

E∥T P →Qn ε -T ε ∥ 2 L 2 (P ) ≲ ε -1 n -1 .
Proof. To ease notation, we write T ε,n = T P →Qn ε and ψ ε,n = ψ P →Qn ε . As explained in Section 3, the stability result Proposition 3.9 implies that

E∥T ε,n -T ε ∥ 2 L 2 (P ) ≤ 8R 2 ε E[Var Q (ψ ε,n -ψ ε )] 2 + E[χ 2 (Q n ∥Q)] 2 + 8R 2 E[χ 2 (Q n ∥Q)] . (54)
Write Q = J j=1 q j δ yj and Q n = J j=1 qj δ yj , and introduce the event

E = {∀j ∈ [J], qj ≥ q j /2}. If E is satisfied, we have Q n ≥ Q/2, so that Proposition 3.11 yields Var Q (ψ ε,n -ψ ε ) ≤ Cχ 2 (Q n ∥Q). ( 55
)
If E is not satisfied, we use the fact that the entropic potentials have a bounded amplitude (see Lemma A.1), to obtain that

Var Q (ψ ε,n -ψ ε ) ≤ C ′ . ( 56
)
Lemma E.2. Let E be the event that Q n ≥ Q/2. Then P(E c ) ≤ Je -cqminn for some c > 0.

Proof. By (Vershynin, 2018, Exercise 2.3.2), we have P(E c ) ≤ J j=1 P(q j < q j /2) ≤ Je -cqminn for some c > 0.

We obtain

E∥ Tε,n -T ε ∥ 2 L 2 (P ) ≲ R 2 ε E[χ 2 (Q n ∥Q)] + R 2 ε Je -cqminn ≲ ε -1 n -1 (57)
by Lemma H.2.

F. Control of the fluctuations in the two-sample case

The goal of this section is to prove Theorem 3.7. We will actually prove a more general result, and show that for any discrete measure ν = J j=1 ν j δ yj supported on {y 1 , . . . , y J } with ν j ≥ ν min > 0 for all j ∈ [J], we have for log(1/ε) ≲ n/ log(n),

E∥T Pn→ν ε -T P →ν ε ∥ 2 L2(P ) ≲ ε -1 n -1 . (58)
Theorem 3.7 follows from (58) by conditioning on Q n . Let E be the event that

Q n ≥ Q/2. Then, by Lemma E.2, E∥ Tε -T P →Qn ε ∥ 2 L2(P ) ≤ E E[∥ Tε -T P →Qn ε ∥ 2 L2(P ) |Q n ]1{E} + R 2 P(E c ) ≤ Cε -1 n -1 + R 2 Je -cqminn ≲ ε -1 n -1 .
We obtain Theorem 3.7 by combining this bound with Lemma E.1.

To prove (58), we first use Corollary C.2 which yields

E∥T Pn→ν ε -T P →ν ε ∥ 2 L2(P ) ≤ 8R 2 ε -1 E (φ Pn→ν ε -φ P →ν ε ) d(P n -P ) = 8R 2 ε -1 E (Φ ε ( ψPn→ν ε ) -Φ ε ( ψP →ν ε )) d(P n -P ), (59)
where we recall that for a potential ψ, the shifted potential ψ is given by ψj = ψ j -ε log ν j . The remainder of the proof consists in bounding this integral by using localization arguments and standard bounds on suprema of empirical processes. Our first goal is to show that the potential ψ Pn→ν ε is close to to the potential ψ P →ν ε for the ∞-norm. It will be convenient to work with the "L ∞ -variance"

Var ∞ (ψ) = inf c∈R max j∈[J] |ψ(y j ) -c| 2 = max ψ -min ψ 2 2 . ( 60
)
As the measure ν is lower bounded, it holds that

Var ν (ψ) ≥ ν min Var ∞ (ψ). (61)
Lemma F.1 (Supremum of ε-Legendre transforms). Let ψ 0 be a fixed potential and let τ > 0. Then, for all j ∈ [J],

E sup Var∞(ψ-ψ0)≤τ 2 (π x ε (ψ) j -π x ε (ψ 0 ) j ) d(P -P n )(x) ≤ C J max{log(τ /ε), 1} n (62) E sup Var∞(ψ-ψ0)≤τ 2 (Φ ε (ψ)(x) -Φ ε (ψ 0 ))(x) d(P -P n )(x) ≤ Cτ J n (63)
for some absolute constant C.

Proof. For a metric space (A, d) and u > 0, we let N (u, A, d) be the covering number of A at scale u, that is the smallest number of balls of radius u needed to cover A. Let B be the L ∞ -ball of radius τ in R J , centered at ψ 0 , and let ∥

• ∥ ∞ denote the ∞-norm. For 0 < u ≤ τ , we have log N (u, B, ∥ • ∥ ∞ ) ≤ J log(τ /u).
We start with the second inequality. Note that ψ → Φ ε (ψ) is 1-Lipschitz continuous, and that the functional

Φ ε satisfies Φ ε (ψ + c) = Φ ε (ψ) + c for all c ∈ R. Then the set {ψ : Var ∞ (ψ -ψ 0 ) ≤ τ 2 } is equal to the set {ψ + c : ψ ∈ B, c ∈ R}.
As c d(P -P n ) = 0, we can therefore restrict the supremum to vectors ψ ∈ B. Furthermore, an envelope function of the class {Φ ε (ψ) -Φ ε (ψ 0 ) : ψ ∈ B} is the constant function equal to τ . Therefore, by Lemma H.3, we obtain

E sup ∥ψ-ψ0∥∞≤τ (Φ ε (ψ) -Φ ε (ψ 0 ))( dP -dP n ) ≤ c 0 √ n c1τ 0 J log 2N (u, {Φ ε (ψ) : ψ ∈ B}, ∥ • ∥ ∞ ) du ≤ c 3 Jτ n .
We repeat the same argument for the first inequality. The functional π x ε is invariant by translation:

π x ε (ψ + c) = π x ε (ψ) for all c ∈ R. This implies that sup Var∞(ψ-ψ0)≤τ 2 (Φ ε (ψ)(x) -Φ ε (ψ 0 ))(x) d(P -P n )(x) = sup ∥ψ-ψ0∥∞≤τ (Φ ε (ψ)(x) -Φ ε (ψ 0 ))(x) d(P -P n )(x) . As the function ψ → π x ε (ψ) j is ε -1 -Lipschitz continuous for every x ∈ R d , we have for 0 < u ≤ τ /ε, log N (u, {x → π x ε (ψ) j : ψ ∈ B}, ∥ • ∥ ∞ ) ≤ J log(τ /(uε)) .
Remarking furthermore that 0 ≤ π x ε (ψ) j ≤ 1 (so that the class of functions {x → π x ε (ψ) j : ψ ∈ B} admits the constant function 1 as an envelope function), we obtain the following control using Lemma H.3:

E sup ∥ψ-ψ0∥∞≤τ (π x ε (ψ) j -π x ε (ψ 0 ) j )( dP -dP n )(x) ≤ c 0 √ n c1 0 J log 2N (u, {x → π x ε (ψ) j : ψ ∈ B}, ∥ • ∥ ∞ ) du ≤ c 2 J max{log(τ /ε), 1} n ,
where c 0 , c 1 and c 2 are absolute constants, and the last line follows from arguing whether c 1 < τ /ε or not.

Proposition F.2. Assume that P satisfies (A) and let ν = J j=1 ν j δ yj be a measure supported on {y 1 , . . . , y J } ⊂ B(0; R), with ν j ≥ q min for all j ∈ [J]. Then, for all 0 < ε ≤ 1 with log(1/ε) ≲ n/ log(n), it holds that

EVar ∞ ( ψPn→ν ε -ψP →ν ε ) ≲ n -1 . ( 64
)
Proof. To alleviate notation, we will write ψ n = ψ Pn→ν

Let us bound P(E c ). As ψn is the minimum of F n , we have ν = π x ε ( ψn ) j dP n (x) (see Appendix A). Therefore, we may write ν n,j = π x ε ( ψn ) j dP n (x) + π x ε ( ψn ) j d(P -P n )(x) = ν j + Z j , where Z j = π x ε ( ψn ) j d(P -P n )(x) = (π x ε ( ψn ) j -π x ε ( ψ0 ) j ) d(P -P n )(x).

Note that Var ∞ ( ψn -ψ0 ) ≲ R 2 (see Lemma A.1), so that by Lemma F.1 and Lemma H.

E∥T Pn→ν ε -T P →ν ε ∥ 2 ∞ ≲ ε -1 n -1 . ( 67
)
Proof. Let Z = Var ∞ ( ψn -ψ0 ). Let once again a k = 2 k / √ n for k ≥ 1, with a 0 = 0. Fix some p > 2, with q = p p-1 . For a > 0, let D a = sup Var∞(ψ-ψ0)≤a 2 (Φ ε (ψ) -Φ ε ( ψ0 )) d(P -P n ) . By Hölder inequality and Markov inequality, we obtain,

E (Φ ε ( ψn ) -Φ ε ( ψ0 )) d(P -P n ) ≤ k≥0 E   1{Z ∈ [a 2 k , a 2 k+1 ]} sup Var∞(ψ-ψ0)≤a 2 k+1 (Φ ε (ψ) -Φ ε ( ψ0 )) d(P -P n )   ≤ E[D a1 ] + k≥1 P(Z ≥ a 2 k ) 1/q E D p a k+1 1/p ≲ n -1 + k≥0 E[Z] a 2 k 1/q 2 k n ≲ k≥0 2 k(1-2/q) n ≲ n -1 ,
where we use Proposition F.2, Lemma F.1 and Lemma H.3 at the last line. Equation (59) then gives the conclusion.

G. A lower bound for the performance of the 1NN estimator

In this section, we prove Proposition 4.2. We let P be the Lebesgue measure on Ω = [0, 1] d , and let y 0 = (0, 1/2, . . . , 1/2) and y 1 = (1, 1/2, . . . , 1/2). We denote by P n an empirical measure consisting of i.i.d. samples from P . As in Appendix F, we work in a general setting of a generic discrete target measure ν, which may either be fixed or may be a random measure independent of P n . We let ν = j=0,1 ν j δ yj for ν 0 , ν 1 ≥ 1 4 ; this latter condition will hold with overwhelming probability if ν is an empirical measure Q n corresponding to n i.i.d. samples from Q = 1 2 δ y0 + 1 2 δ y1 . Following [START_REF] Manole | Plugin estimation of smooth optimal transport maps[END_REF], we define the one-nearest neighbor estimator T1NN in this general context by

T1NN (x) = n i=1 j=0,1 1 Vi (x)(nπ(X i , y j )) ,
where π is the empirical optimal coupling between P n and ν.

We first examine the structure of the Brenier map T 0 = ∇φ 0 . The considerations in Section 2.1.1 imply that T 0 (x) = y 0 ⟨e 1 , x⟩ ≤ ν 0 y 1 ⟨e 1 , x⟩ > ν 0 ,

where e 1 is the first elementary basis vector. The potential φ 0 is not differentiable on the separating hyperplane ⟨e 1 , x⟩ = ν 0 , which has measure 0 under P , but we may arbitrarily assign points on this hyperplane to y 0 .

Proof. We can write Q n = J j=1 qj δ yj , where qj is a binomial random variable with parameters n and q j . We obtain

χ 2 (Q n ∥Q) = J j=1
(q j -q j ) 2 q j .

Taking expectations, our bound reads

E[χ 2 (Q n ∥Q)] = J j=1
Var(q j ) q j = J j=1 q j (1 -q j ) nq j = J -1 n .

Lemma H.3 (Control of suprema of empirical processes). Let X 1 , . . . , X n be an i.i.d. sample from some probability measure P on R d , with P n the associated empirical measure. Consider F a class of functions R d → R with ∥f ∥ ∞ ≤ A for all f ∈ F. For u > 0, let N (u) be the u-covering numbers of F, that is the minimal number of balls of radius u for the ∥ • ∥ ∞ -metric required to cover F. Then,

E sup f ∈F f d(P n -P ) ≤ C 0 √ n C1A 0 log 2N (u) du =: I √ n ( 74
)
for two positive absolute constants C 0 and C 1 . Furthermore, for all t > 0,

P sup f ∈F f d(P n -P ) > t ≤ exp - C 2 √ nt I + A log n , (75)
for some positive absolute constant C 2 . Eventually, for all p ≥ 2,

E sup f ∈F f d(P n -P ) p 1/p ≤ C p I + A √ n . ( 76
)
Proof. See (Vaart & Wellner, 1996, Theorem 2.14.2 and Theorem 2.14.5).

Figure 1 .

 1 Figure1. An illustration of a semi-discrete optimal transport map. The support of P , the whole rectangle, is partitioned into regions, each of which is transported to one of the atoms of the discrete target measure Q. The resulting map is discontinuous at the boundaries of each cell.

  The symbols C and c denote positive constants whose value may change from line to line. Write a ≲ b and a ≍ b if there exist constants c, C > 0 such that a ≤ Cb and cb ≤ a ≤ Cb, respectively. For an integer N ∈ N, we let [N ] := {1, . . . , N }. For a function f and a probability measure ρ, we write ∥f ∥ 2

Figure 2 .

 2 Figure 2. Left: Tε versus T1NN for J = 2 and d = 10. Right: Tε versus T1NN for J = 10 and d = 50.

Figure 3 .

 3 Figure 3. Tε versus T1NN for with ψ0 random in d = 50

Figure 4 .

 4 Figure 4. Tε versus T1NN for d = 10

D

  . Strong convexity of the entropic semi-dual problem Proposition D.1 (Strong convexity of F µ→ν ε

ε

  and ψ 0 = ψ P →ν ε . Similarly, we writeF n = F Pn→ν ε and F 0 = F P →ν ε . Let ν n = π x ε (ψ Pn→ν ε ) dP (x).Under the event E = {ν n ≥ ν/2}, we have according to Proposition D.1 and the fact that ψn minimizes F n ,Cν min Var ∞ ( ψn -ψ0 ) ≤ CVar ν ( ψn -ψ0 ) ≤ F 0 ( ψn ) -F 0 ( ψ0 ) ≤ F 0 ( ψn ) -F n ( ψn ) + F n ( ψ0 ) -F 0 ( ψ0 ) = (Φ ε ( ψn ) -Φ ε ( ψ0 )) d(P -P n )

  For k ≥ 0, let a k = 2 k / √ n and fix some p > 2.Let B a = sup Var∞(ψ-ψ0)≤a 2 (Φ ε (ψ) -Φ ε ( ψ0 )) d(P -P n ) . Assume that E is satisfied and that Var ∞ ( ψ0 -ψn ) ∈ [a 2 , b 2 ].Then, according to (65), it holds that B b ≥ ca 2 . Using Markov's inequality, Lemma F.1 and Lemma H.3, we bound EVar ∞ ( ψn -ψ0 ) ≤ a 2 0 + k≥0 P(Var ∞ ( ψn -ψ0 ) ∈ [a 2 k , a 2 k+1 ] and E)a 2 k+1 + CP(E c ) Proposition F.3. Under the same assumptions than Proposition F.2, it holds that

	≲ n -1 +	k≥0	P B a k+1 ≥ ca 2 k a 2 k+1 ≲ n -1 +	k≥0	E[B p a k+1 ] k a 2p	a 2 k+1
	≲ n -1 +	k≥0	(2 k /n) p (4 k /n) p	4 k+1 n	≲ n -1 +	k≥0	2 2k-pk n	≲ n -1 .

3,

P(E c ) ≤ J j=1 P(|Z j | > ν j /2) ≤ J exp -c √ nq min ( J log(1/ε) + log n

Acknowledgements

AAP would like to thank Tudor Manole for fruitful discussions, and gratefully thanks funding sources NSF Award 1922658, and Meta AI Research. JNW is supported by the Sloan Research Fellowship and NSF grant DMS-2210583. We thank the anonymous reviewer for suggesting the addition of a rounding scheme.

Similar arguments imply that the empirical transport plan π between P n and ν has the following property: there exists a (random) threshold τ ∈ (0, 1) such that π(x, y 0 ) = 1 ⟨e 1 , x⟩ < τ 0 ⟨e 1 , x⟩ > τ .

The set ⟨e 1 , x⟩ = τ may not have measure 0 under P n , and π(x, y 0 ) may take values strictly between 0 and 1 on this set.

The following lemma shows that τ is close to ν 0 with high probability.

Lemma G.1. For any t ≥ 0,

Proof. If τ ≥ ν 0 + t, this implies that P n ({x : ⟨e 1 , x⟩ < ν 0 + t}) ≤ ν 0 . On the other hand, nP n ({x : ⟨e 1 , x⟩ < ν 0 + t} is a Bin(n, ν 0 + t) random variable. The result then follows from Hoeffding's inequality (Boucheron et al., 2013, Theorem 2.8).

Let us write H for the halfspace {x : ⟨e 1 , x⟩ ≤ ν 0 }, and Ĥ for the halfspace {x : ⟨e 1 , x⟩ ≤ τ }. Let x be any point in Ω such that x ∈ H. We are interested in the event that there exists an element X i ∈ {X 1 , . . . , X n } such that a) x ∈ V i and b) X i ∈ Ĥc . Call this event E(x). On this event, T1NN (x) = y 1 and T 0 (x) = y 0 , so ∥ T1NN (x) -T 0 (x)∥ 2 = 1.

We therefore obtain

where the final equality follows from the Fubini-Tonelli theorem.

We now lower bound the probability of E(x). Let us write A t for the event that τ < ν 0 + t, for t > 0 to be specified, and write H t for the halfspace {x : ⟨e 1 , x⟩ ≤ ν 0 + t}. Given any x ∈ H, write ∆ = d(x, H c t ), and let B be a ball of radius 2∆ around x, intersected with Ω.

Denote by F(x) the event that there are no samples in V = B ∩ H t but there is at least one point in B ∩ H c t . Then F(x) ∩ A t ⊆ E(x), since on F(x) the nearest neighbor to x must be a sample in H c t , and on A t we have

Proof. We first compute P {F(x)}. The probability that there are no samples in V is (1 -vol(V )) n , and this event may be written as the disjoint union of F(x) and the event that all of B is empty. The latter event has probability

, the claim follows.

We need the following lemma.

Lemma G.3. Assume that ∆ > 0 and that d(x, ∂Ω) ≥ 2∆. There exist positive constants c d,0 < 1 and c d,1 such that

Proof. This is immediate from a scaling argument: since d(x, ∂Ω) ≥ 2∆, the set B is a Euclidean ball of radius 2∆, and the set V is a Euclidean ball of radius 2∆ minus a spherical dome cut off by a hyperlane at distance ∆ from the center. When ∆ = 1, it is clear that the claimed inequalities hold, and the general case is obtained by dilation.

We assume in what follows that d(x, ∂Ω) ≥ 2∆. The inequalities (1 + x) n ≥ 1 + nx and e x ≤ 1 + x + x 2 , valid for all x ∈ [-1, 0] and n ≥ 1, imply that for any δ > 0 there exists a constant c d,δ > 0 such that if ∆ ≤ c d,δ n -1/d , then we will have

Choosing δ sufficiently small, we obtain the existence of a small

. Putting it all together, consider the set

The above considerations imply that

for all x ∈ S. Choosing t to be a sufficiently large constant multiple of n -1/2 , we obtain

Since t ≍ n -1/2 , we will have that t ≪ ∆ n for n sufficiently large (as d ≥ 3). Therefore, for n large enough, the set S contains the set

Since vol(S ′ ) ≳ d ∆ n ≳ n -1/d , the claim follows.

H. Auxiliary lemmas

Lemma H.1 (Young's inequality). Let Q 0 , Q 1 be probability measures with Q 1 ≪ Q 0 and let f be a function. Then, for θ > 0,

Proof. Recall Young's inequality: for a, b ∈ R, ab ≤ a 2 2 + b 2 2 . As the left-hand side is invariant by translation, we may assume without loss of generality that f dQ 0 = 0, so that Var Q0 (f ) = f 2 dQ 0 . We write

Lemma H.2 (Expectation of empirical χ 2 -divergence). Let Q = J j=1 q j δ yj be a discrete measure supported on J atoms, and let Q n denote its empirical measure, consisting of n i.i.d. samples. Then,