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

Aram-Alexandre Pooladian1,∗, Vincent Divol2,∗, Jonathan Niles-Weed1,3
---
1Center for Data Science, New York University
---
2Ceremade, Université Paris Dauphine-PSL
3Courant Institute of Mathematical Sciences, New York University
aram-alexandre.pooladian<EMAIL_ADDRESS><EMAIL_ADDRESS>

August 28, 2024

###### Abstract

We consider the problem of estimating the optimal transport map between two
probability distributions, $P$ and $Q$ in $\mathbb{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 $\mathbb{R}^{d}$.
We study a computationally efficient estimator initially proposed by [55],
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.

††footnotetext: *Pooladian and Divol contributed equally to this work.

##  1 Introduction

The theory of optimal transport (OT) defines a natural geometry on the space
of probability measures [57, 64] 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 $\mathbb{R}^{d}$. Then, Brenier’s theorem (see Section 2.1) states
that there exists a convex function $\varphi_{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:

$\displaystyle\nabla\varphi_{0}\coloneqq\operatorname*{argmin}_{T\in\mathcal{T}(P,Q)}\int\tfrac{1}{2}\|x-T(x)\|^{2}\,\mathrm{d}P(x)\,,$
(1)

where $\mathcal{T}(P,Q)\coloneqq\\{T:\mathbb{R}^{d}\to\mathbb{R}^{d}\ |\ X\sim
P,\ T(X)\sim 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

$\displaystyle\operatorname{S_{0}}(P,Q)=\int\tfrac{1}{2}\|x-\nabla\varphi_{0}(x)\|^{2}\,\mathrm{d}P(x)\,,$

though a more general formulation is available (see Section 2.1). Computing or
approximating $\operatorname{S_{0}}(P,Q)$ as well as $\nabla\varphi_{0}$ has
found use in several academic communities, such as economics [11, 13, 62, 39],
computational biology [9, 6, 43, 61, 48, 27, 67], and computer vision [60, 59,
28], among many others.

Practitioners seldom have access to $P$ or $Q$, but instead have access to
i.i.d. samples $X_{1},\ldots,X_{n}\sim P$ and $Y_{1},\ldots,Y_{n}\sim Q$. On
the basis of these samples, practitioners face both computational and
statistical challenges when estimating $\nabla\varphi_{0}$. From a theoretical
perspective, the statistical task of estimating optimal transport maps has
attracted much interest in the last few years [40, 50, 45, 25, 55, 26, 37].

The first finite-sample analysis of this problem was performed by [40], who
proposed an estimator for $\nabla\varphi_{0}$ under the assumption that
$\varphi_{0}$ is $s+1$-times continuously differentiable, for $s>1$. They
showed that a wavelet-based estimator $\hat{\varphi}_{\text{W}}$ satisfies

$\displaystyle\mathbb{E}\|\nabla\hat{\varphi}_{\text{W}}-\nabla\varphi_{0}\|_{L^{2}(P)}^{2}\lesssim
n^{-\frac{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
$\Omega\subseteq\mathbb{R}^{d}$, and that $\varphi_{0}$ be both strongly
convex and smooth. Implementing the estimator $\hat{\varphi}_{\text{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 $\hat{\varphi}_{\text{W}}$ either in computational efficiency or
in the generality in which they apply. Though these subsequent works go
significantly beyond the setting considered by [40], none has eliminated the
crucial assumption that $\varphi_{0}$ is smooth, i.e., that the transport map
$\nabla\varphi_{0}$ is Lipschitz.

We highlight two estimators proposed in this line of work that are
particularly practical. [45] study the $1$-Nearest Neighbor estimator
$\hat{T}_{\text{1NN}}$. This estimator is obtained by solving the empirical
optimal transport problem between the samples, which is then extended to a
function defined on $\mathbb{R}^{d}$ using a projection scheme; see Section 4
for more details. Given $n$ samples from the source and target measures in
$\mathbb{R}^{d}$, $\hat{T}_{\text{1NN}}$ has a runtime of $\mathcal{O}(n^{3})$
via the Hungarian Algorithm [see 53, Chapter 3], and, for $d\geq 5$, achieves
the rate

$\mathbb{E}\|\hat{T}_{\text{1NN}}-\nabla\varphi_{0}\|_{L^{2}(P)}^{2}\lesssim
n^{-\frac{2}{d}}\,$ (2)

whenever the optimal Brenier potential $\varphi_{0}$ is smooth and strongly
convex, and under mild regularity conditions on $P$. In another work, [55]
conducted a statistical analysis of an estimator originally proposed by [58]
based on entropic optimal transport. The efficiency of Sinkhorn’s algorithm
for large-scale problems [19, 53] makes this estimator attractive from a
computational perspective, and [55] 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 $\nabla\varphi_{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 [3]. In such a setting,
the transport map $\nabla\varphi_{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=\sum_{j=1}^{J}q_{j}\delta_{y_{j}}$ is discrete while the source measure $P$
has full support, often called the _semi-discrete_ setting in the optimal
transport literature. In this setting, the optimal transport map
$\nabla\varphi_{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. Semi-discrete optimal transport
therefore provides a natural class of discontinuous transport maps.

Figure 1: 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.

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., 49, 2, 10], due in particular to its connection with the quantization
problem [34]. 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 [30, 22, 20, 41]. For example, [41, 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

$\mathbb{E}|S_{0}(P,Q)-S_{0}(P_{n},Q_{n})|\lesssim n^{-1/2}\,.$

These results offer the tantalizing possibility that semi-discrete 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 $\hat{T}_{\varepsilon}$
based on entropically regularized optimal transport, originally studied in
[58, 55], provably estimates discontinuous semi-discrete optimal transport
maps at the optimal rate. More precisely, our contributions are the following:

  1. 1.

For $Q$ discrete and $P$ with full support on a compact, convex set, we show
that $\hat{T}_{\varepsilon}$ achieves the following dimension-independent
convergence rate to the optimal transport map (see Theorem 3.1)

$\mathbb{E}\|\hat{T}_{\varepsilon}-\nabla\varphi_{0}\|^{2}_{L^{2}(P)}\lesssim
n^{-1/2}\,,$ (3)

when the regularization parameter $\varepsilon\asymp n^{-1/2}$. We further
show (Proposition 4.1) that this rate is minimax optimal.

  2. 2.

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

  3. 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. 4.

We show that, unlike $\hat{T}_{\varepsilon}$, 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:

$\displaystyle\mathbb{E}\|\hat{T}_{\text{1NN}}-\nabla\varphi_{0}\|^{2}_{L^{2}(P)}\gtrsim
n^{-1/d}\,.$

  5. 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)$.
The symbols $C$ and $c$ denote positive constants whose value may change from
line to line. Write $a\lesssim b$ and $a\asymp b$ if there exist constants
$c,C>0$ such that $a\leq Cb$ and $cb\leq a\leq Cb$, respectively. For an
integer $N\in\mathbb{N}$, we let $[N]\coloneqq\\{1,\ldots,N\\}$. For a
function $f$ and a probability measure $\rho$, we write
$\|f\|_{L^{2}(\rho)}^{2}\coloneqq\mathbb{E}_{X\sim\rho}\|f(X)\|^{2}\,.$
Similarly, we write
$\text{Var}_{\rho}(f)\coloneqq\mathbb{E}_{X\sim\rho}[(f(X)-\mathbb{E}_{X\sim\rho}[f(X)])^{2}]$
for the variance of $f$ with respect to $\rho$.

##  2 Background on optimal transport

###  2.1 Optimal transport

We define $\mathcal{P}(\Omega)$ to be the space of probability measures whose
support lies in a compact subset $\Omega\subseteq\mathbb{R}^{d}$. If a
probability measure $P$ has a density with respect to the Lebesgue measure on
$\mathbb{R}^{d}$ with support $\Omega\subseteq\mathbb{R}^{d}$, then we write
$P\in\mathcal{P}_{\text{ac}}(\Omega)$.

For two probability measures $P,Q\in\mathcal{P}(\Omega)$, we define the
(squared) $2$-Wasserstein distance to be [42]

$\displaystyle\operatorname{S_{0}}(P,Q):=\min_{\pi\in\Gamma(P,Q)}\iint\tfrac{1}{2}\|x-y\|^{2}\,\mathrm{d}\pi(x,y)\,,$
(4)

where $\pi\in\Gamma(P,Q)\subseteq\mathcal{P}(\Omega\times\Omega)$ such that
for any event $A$,

$\displaystyle\pi(A\times\Omega)=P(A)\,,\quad\pi(\Omega\times A)=Q(A)\,.$

We call $\Gamma(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 [64, 57] 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 $\pi_{0}$, always exists; we call $\pi_{0}$ an
optimal plan from $P$ to $Q$. Moreover, Equation 4 possesses the following
dual formulation,

$\displaystyle\begin{split}\operatorname{S_{0}}(P,Q)&=\tfrac{1}{2}M_{2}(P)+\tfrac{1}{2}M_{2}(Q)-\inf_{(\varphi,\psi)\in\Phi}\int\varphi\,\mathrm{d}P+\int\psi\,\mathrm{d}Q\end{split}$
(5)

where $M_{2}(P):=\int\|x\|^{2}\,\mathrm{d}P(x)$ (similarly for $M_{2}(Q)$) and
the functions $(\varphi,\psi)\in\Phi\subseteq L_{1}(P)\times L_{1}(Q)$ satisfy

$\displaystyle\langle x,y\rangle\leq\varphi(x)+\psi(y)\ \text{for all
}x,y\in\Omega\,,$

As with the primal formulation, the infimum in Equation 5 is attained at
functions $(\varphi_{0},\psi_{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:

$\displaystyle\varphi_{0}^{*}(y):=\sup_{x}\\{\langle
x,y\rangle-\varphi_{0}(x)\\}=\psi_{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:

$\displaystyle
T_{0}:=\operatorname*{argmin}_{T\in\mathcal{T}(P,Q)}\int\tfrac{1}{2}\|x-T(x)\|^{2}\,\mathrm{d}P(x)\,,$
(7)

where $\mathcal{T}(P,Q)$ is the set of admissible transport maps, i.e. for
$X\sim P$, $T(X)\sim 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; 8).

Let $P\in\mathcal{P}_{\text{ac}}(\Omega)$ and let $Q\in\mathcal{P}(\Omega)$,
then

  1. 1.

the solution to Equation 7 exists and is of the form
$T_{0}=\nabla\varphi_{0}$, where $\varphi_{0}$ solves Equation 5

  2. 2.

$\pi_{0}$ is also uniquely defined as

$\,\mathrm{d}\pi_{0}(x,y)=\,\mathrm{d}P(x)\delta_{\\{\nabla\varphi_{0}(x)\\}}(y)\,.$

When we want to place emphasis on the underlying measures, we will write
$\varphi_{0}=\varphi_{0}^{P\to Q}$, $\psi_{0}=\psi_{0}^{P\to Q}$ and
$T_{0}=T_{0}^{P\to Q}$.

####  2.1.1 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 $\mathbb{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,\dots,J\\}$.

######  Proposition 2.2 (1).

If $P\in\mathcal{P}_{\text{ac}}(\Omega)$ and $Q$ is a discrete measure
supported on the points $y_{1},\dots,y_{J}$, then the optimal transport map
$\nabla\varphi_{0}$ is given by

$\displaystyle\nabla\varphi_{0}(x)\coloneqq\operatorname*{argmax}_{j\in[J]}\\{\langle
x,y_{j}\rangle-\psi_{0}(y_{j})\\}\,,$ (8)

where $\psi_{0}$ is the dual to $\varphi_{0}$ in the sense of Equation 6.

Here, the optimal dual Brenier potential $\psi_{0}$ can be identified with a
vector in $\mathbb{R}^{J}$, defined by the number of atoms, and the optimal
Brenier potential is consequently given by

$\varphi_{0}\coloneqq\max_{j\in[J]}\\{\langle
x,y_{j}\rangle-\psi_{0}(y_{j})\\}\,.$

Although $\varphi_{0}$ is not differentiable, only subdifferentiable, we still
use the gradient notation as $\nabla\varphi_{0}$ is well-defined $P$-almost
everywhere.

The map $\nabla\varphi_{0}$ partitions the space into $J$ convex polytopes
$L_{j}\coloneqq\nabla\varphi_{0}^{-1}(\\{y_{j}\\})$ called _Laguerre cells_ ;
recall Figure 1. From this definition, it is clear that for a given $x\in
L_{j}$, $x\mapsto\nabla\varphi_{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 $\psi_{0}(y_{j})$.

###  2.2 Entropic optimal transport

Entropic regularization was introduced to both optimal transport and machine
learning communities in the seminal paper by [19], 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 $\varepsilon>0$

$\displaystyle\begin{split}\operatorname{S_{\varepsilon}}(P,Q):=\min_{\pi\in\Gamma(P,Q)}&\iint\tfrac{1}{2}\|x-y\|^{2}\,\mathrm{d}\pi(x,y)+\varepsilon\text{KL}(\pi\|P\otimes
Q)\,,\end{split}$ (9)

where
$\text{KL}(\mu\|\nu)=\int\log\frac{\,\mathrm{d}\mu}{\,\mathrm{d}\nu}\,\mathrm{d}\mu$
when $\mu\in\mathcal{P}(\Omega)$ is absolutely continuous with respect to
$\nu\in\mathcal{P}(\Omega)$. This speedup is due to the elegant connection of
(9) to Sinkhorn’s algorithm; we refer the interested reader to [53, Chapter 4]
for more information. The computational tractability of
$\operatorname{S_{\varepsilon}}$ compared to $\operatorname{S_{0}}$ when
dealing with many samples lends itself to being a central object of study in
its own right [see, e.g., 31, 47, 16, 56, 38].

Equation 9 admits the following dual formulation, which is now an
unconstrained optimization problem [32, 46]

$\begin{split}\operatorname{S_{\varepsilon}}(P,Q)=\tfrac{1}{2}M_{2}(P)+\tfrac{1}{2}M_{2}(Q)-&\inf_{\varphi,\psi}\bigg{(}\int\varphi\,\mathrm{d}P+\int\psi\,\mathrm{d}Q\\\
&\quad+\varepsilon\iint(e^{(\langle
x,y\rangle-\varphi(x)-\psi(y))/\varepsilon}-1)\,\mathrm{d}P(x)\,\mathrm{d}Q(y)\bigg{)},\end{split}$
(10)

where $(\varphi,\psi)\in L_{1}(P)\times L_{1}(Q)$. When $P$ and $Q$ have
finite second moments, Equation 9 admits a unique minimizer,
$\pi_{\varepsilon}$ and we have the existence of minimizers to Equation 10,
which we denote as $(\varphi_{\varepsilon},\psi_{\varepsilon})$. We call
$\pi_{\varepsilon}$ the entropic optimal plan and
$(\varphi_{\varepsilon},\psi_{\varepsilon})$ are called entropic Brenier
potentials. The following optimality relation further relates these primal and
dual solutions [17]:

$\displaystyle\,\mathrm{d}\pi_{\varepsilon}(x,y):=e^{(\langle
x,y\rangle-\varphi_{\varepsilon}(x)-\psi_{\varepsilon}(y))/\varepsilon}\,\mathrm{d}P(x)\,\mathrm{d}Q(y)\,.$

As a consequence, the following relationship holds at optimality:

$\displaystyle\operatorname{S_{\varepsilon}}(P,Q)=\tfrac{1}{2}M_{2}(P)+\tfrac{1}{2}M_{2}(Q)-\int\varphi_{\varepsilon}\,\mathrm{d}P-\int\psi_{\varepsilon}\,\mathrm{d}Q\,,$

and, moreover, we can define versions of $\varphi_{\varepsilon}$ and
$\psi_{\varepsilon}$ such that the following relationships hold [see 47, 51]
over all $x\in\mathbb{R}^{d}$ and $y\in\mathbb{R}^{d}$, respectively:

$\displaystyle\varphi_{\varepsilon}(x)=\varepsilon\log\int e^{(\langle
x,y\rangle-\psi_{\varepsilon}(y))/\varepsilon}\,\mathrm{d}Q(y)\,,$ (11)
$\displaystyle\psi_{\varepsilon}(y)=\varepsilon\log\int e^{(\langle
x,y\rangle-\varphi_{\varepsilon}(x))/\varepsilon}\,\mathrm{d}P(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
$\varphi_{\varepsilon}$ and $\psi_{\varepsilon}$ so that these identities
hold.

####  2.2.1 Entropic Brenier Map

If $(X,Y)\sim\pi_{\varepsilon}$, we may define the conditional probability
$\pi^{x}_{\varepsilon}$ of $Y$ given that $X=x$, with density

$\frac{\,\mathrm{d}\pi^{x}_{\varepsilon}}{\,\mathrm{d}Q}(y)\propto\exp\left((\langle
x,y\rangle-\psi_{\varepsilon}(y))/\varepsilon\right)\,.$ (13)

The barycentric projection of the optimal entropic coupling
$\pi_{\varepsilon}$, or entropic Brenier map, is a central object of study in
several works e.g. [33, 55, 21, 56], defined as

$\displaystyle T_{\varepsilon}(x)=\int y\,\mathrm{d}\pi^{x}_{\varepsilon}(y)$
$\displaystyle=\nabla\varphi_{\varepsilon}(x)\,,$ (14)

where $\pi_{\varepsilon}^{x}$ is as in Equation 13. Note that this quantity is
well defined for all $x\in\mathbb{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
$\varphi_{\varepsilon}=\varphi_{\varepsilon}^{P\to Q}$,
$\psi_{\varepsilon}=\psi_{\varepsilon}^{P\to Q}$ and
$T_{\varepsilon}=T_{\varepsilon}^{P\to 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 [58], but analyzed statistically for the first time by
[55] 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_{\varepsilon}$.

######  Proposition 2.3 (55, Corollary 1).

Let $P,Q$ be compactly supported absolutely continuous measures on a compact
set $\Omega\subseteq\mathbb{R}^{d}$ with densities $p$ and $q$, that are
bounded away from $0$ and $\infty$. Assume that $\varphi_{0}$ is smooth and
strongly convex, and that $\varphi_{0}^{*}$ is at least $\mathcal{C}^{3}$.
Then,

$\displaystyle\|T_{\varepsilon}-\nabla\varphi_{0}\|^{2}_{L^{2}(P)}\lesssim\varepsilon^{2}\,.$
(15)

Their main statistical result is the following theorem:

######  Proposition 2.4 (55, 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 $\hat{T}_{\varepsilon}=T_{\varepsilon}^{P_{n}\to Q_{n}}$ denote the
entropic Brenier map from $P_{n}$ to $Q_{n}$ and let $T_{0}=\nabla\varphi_{0}$
be the optimal transport map from $P$ to $Q$. Then, if $\varepsilon\asymp
n^{-\frac{1}{d^{\prime}+3}}$

$\displaystyle\mathbb{E}\|\hat{T}_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}\lesssim
n^{-\frac{3}{2(d^{\prime}+3)}}\log(n)\,,$ (16)

where $d^{\prime}=2\lceil d/2\rceil$.

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.

####  2.2.2 Related work

Characterizing the convergence of entropic objects (e.g. potentials, cost,
plans) to their unregularized counterparts in the $\varepsilon\to 0$ regime
has been a topic of several works in recent years. Convergence of the costs
$\operatorname{S_{\varepsilon}}$ to $\operatorname{S_{0}}$ with precise rates
was investigated in [52, 16, 18]. The works [12, 44, 5, 35] study the
convergence of the minimizers $\pi_{\varepsilon}$ to $\pi_{0}$ under varying
assumptions. Convergence of the potentials in a very general setting was
established in [51], though without a rate of convergence in $\varepsilon$. In
the semi-discrete case, this gap was closed in [2] followed closely by [24],
which gave non-asymptotic rates. The Sinkhorn Divergence, a non-negative,
symmetric version of $\operatorname{S_{\varepsilon}}$, was introduced in [36],
was statistically analysed in [33] and also in [38, 21], and was connected to
the entropic Brenier map in [54]. The recent pre-print by [56] 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 [15]; this approach was recently generalized in [14].
Entropic optimal transport has also come into contact with the area of deep
generative modelling through the following works [29, 23], among others.

##  3 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 [24].

  * (A)

The measure $P$ has a compact convex support $\Omega\subseteq B(0;R)$, with a
density $p$ satisfying $0<p_{\min}\leq p\leq p_{\max}<\infty$ for positive
constants $p_{\min}$, $p_{\max}$ and $R$.

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

  * (B)

The discrete probability measure $Q=\sum_{j=1}^{J}q_{j}\delta_{y_{j}}$ is such
that $q_{j}\geq q_{\min}>0$ and $y_{j}\in B(0;R)$ for all $j\in[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
$\hat{T}_{\varepsilon}=T_{\varepsilon}^{P_{n}\to Q_{n}}$. Then, for
$\varepsilon\asymp n^{-1/2}$ and $n$ large enough,

$\displaystyle\mathbb{E}\|\hat{T}_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}\lesssim
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},\ldots,y_{J}\\}$. In fact,
$\hat{T}_{\varepsilon}:\mathbb{R}^{d}\to\text{conv}(\\{Y_{1},\ldots,Y_{n}\\})$,
where $\text{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 $\bar{T}_{\varepsilon}$ which is obtained by mapping the output of
$\hat{T}_{\varepsilon}$ 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

$\displaystyle\mathbb{E}\|\bar{T}_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}\leq
2\mathbb{E}\|\hat{T}_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}$

but $\bar{T}_{\varepsilon}$ matches the support of $Q$.

Let $T_{\varepsilon}=T_{\varepsilon}^{P\to Q}$ denote the entropic Brenier map
associated to $P$ and $Q$. Our proof relies on the following bias-variance
decomposition:

$\displaystyle\mathbb{E}\|\hat{T}_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}$
$\displaystyle\lesssim\mathbb{E}\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|^{2}_{L^{2}(P)}+\|T_{\varepsilon}-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 $\varepsilon$.

######  Theorem 3.4.

Let $P$ satisfy (A) and let $Q$ satisfy (B). Then, for $\varepsilon$ small
enough,

$\displaystyle\|T_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}\lesssim\varepsilon\,.$
(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 $\pi_{\varepsilon}$ 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 $\varepsilon$ from the
boundary of the Laguerre cell $L_{j}$, incurring a total error of order
$\varepsilon$. 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 $\varepsilon$ 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 $\mathbb{R}$ having a symmetric bounded
density $p$ continuous at $0$, and let
$Q=\frac{1}{2}(\delta_{-1}+\delta_{1})$. Following [2, Section 3], one can
check that the entropic Brenier map in this setting is the following scaled
sigmoidal function

$T_{\varepsilon}(x)=\tanh(2x/\varepsilon)\,,$

whereas the optimal transport map $T_{0}(x)=\text{sign}(x)$. Then, performing
a computation

$\displaystyle\|T_{\varepsilon}-T_{0}\|^{2}_{L^{2}(P)}$
$\displaystyle=2\int_{0}^{\infty}(1-\tanh(2x/\varepsilon))^{2}p(x)\,\mathrm{d}x$
$\displaystyle=\varepsilon\int_{0}^{\infty}(1-\tanh(u))^{2}p(u\varepsilon/2)\,\mathrm{d}u$
$\displaystyle=\varepsilon p(0)(\log(4)-1)+o(\varepsilon)\,,$

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 [2], 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<\varepsilon\leq 1$
such that $\log(1/\varepsilon)\lesssim n/\log(n)$

$\displaystyle\mathbb{E}\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|^{2}_{L^{2}(P)}\lesssim\varepsilon^{-1}n^{-1}\,.$
(19)

######  Remark 3.8.

In [56], the authors show that if $P$ and $Q$ are merely compactly supported
with $\operatorname{supp}(P),\operatorname{supp}(Q)\subseteq B(0;R)$, then

$\displaystyle\mathbb{E}\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|^{2}_{L^{2}(P)}\lesssim
e^{cR^{2}/\varepsilon}\varepsilon^{-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
[45, Theorem 6], which is of independent interest. We provide the proof in
Appendix C.

######  Proposition 3.9.

Let $\mu,\nu,\mu^{\prime},\nu^{\prime}$ be four probability measures supported
in $B(0;R)$. Then the entropic maps $T_{\varepsilon}^{\mu\to\nu}$ and
$T_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}$ satisfy

$\displaystyle\frac{\varepsilon}{8R^{2}}\|T_{\varepsilon}^{\mu\to\nu}-T_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}\|_{L^{2}(\mu)}^{2}\leq\int(\varphi_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}-\varphi_{\varepsilon}^{\mu\to\nu})\,\mathrm{d}\mu+\int(\psi_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}-\psi_{\varepsilon}^{\mu\to\nu})\,\mathrm{d}\nu+\varepsilon\text{KL}(\nu\|\nu^{\prime})$

######  Remark 3.10.

The right side of the bound in Proposition 3.9 is equal to

$\displaystyle
S_{\varepsilon}(\mu,\nu)-S_{\varepsilon}(\mu^{\prime},\nu^{\prime})+\int
f_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}\,\mathrm{d}(\mu^{\prime}-\mu)+\int
g_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}\,\mathrm{d}(\nu^{\prime}-\nu)+\varepsilon\text{KL}(\nu\|\nu^{\prime})\,,$

where
$f_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}=\frac{1}{2}\|\cdot\|^{2}-\varphi_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}$
and
$g_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}=\frac{1}{2}\|\cdot\|^{2}-\psi_{\varepsilon}^{\mu^{\prime}\to\nu^{\prime}}$.
Proposition 3.9 is therefore the entropic analogue of the stability bounds of
[45, Theorem 6] and [37, 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},\dots,Y_{n}\sim Q$, but we
have full access to $P$. We then consider the one-sample entropic estimator
$T_{\varepsilon}^{P\to Q_{n}}$. We apply Proposition 3.9 with
$\mu=\mu^{\prime}\coloneqq P$, $\nu\coloneqq Q_{n}$ and $\nu^{\prime}\coloneqq
Q$, yielding (see Corollary C.1 for details)

$\displaystyle\begin{split}\frac{\varepsilon}{8R^{2}}\mathbb{E}\|T^{P\to
Q_{n}}_{\varepsilon}-T_{\varepsilon}\|_{L^{2}(\mu)}^{2}\leq\mathbb{E}\Big{(}\int(\psi_{\varepsilon}-\psi_{\varepsilon}^{P\to
Q_{n}})\,\mathrm{d}(Q_{n}-Q)+\varepsilon\text{KL}(Q_{n}\|Q)\Big{)}\,.\end{split}$

Let $\chi^{2}(P\|Q)$ denote the $\chi^{2}$-divergence between probability
measure. Young’s inequality (see Lemma H.1) and the inequality
$\text{KL}(Q_{n}\|Q)\leq\chi^{2}(Q_{n}\|Q)$ yield the following bound:

$\displaystyle\mathbb{E}\|T_{\varepsilon}^{P\to
Q_{n}}-T_{\varepsilon}\|^{2}_{L^{2}(P)}\leq\frac{8R^{2}}{\varepsilon}\Big{(}\frac{\mathbb{E}[\mathrm{Var}_{Q}(\psi_{\varepsilon}^{P\to
Q_{n}}-\psi_{\varepsilon})]}{2}+\frac{\mathbb{E}[\chi^{2}(Q_{n}\|Q)]}{2}\Big{)}+8R^{2}\mathbb{E}[\chi^{2}(Q_{n}\|Q)]\,.$

To complete our proof sketch, we use a new stability result on the entropic
dual Brenier potentials, catered for the semi-discrete setting.

######  Proposition 3.11.

Let $\mu$ be a measure that satisfies (A). Let $\nu$, $\nu^{\prime}$ be two
discrete probability measures supported on $\\{y_{1},\dots,y_{J}\\}$, with
$\nu^{\prime}\geq\lambda\nu$ for some $\lambda>0$. Then, for
$0<\varepsilon\leq 1$,

$\mathrm{Var}_{\nu}(\psi_{\varepsilon}^{\mu\to\nu^{\prime}}-\psi_{\varepsilon}^{\mu\to\nu})\leq\frac{C}{\lambda^{2}}\chi^{2}(\nu^{\prime}\|\nu),$
(21)

where $C$ depends on $R$, $p_{\min}$ and $p_{\max}$.

Moreover, a computation provided in Lemma H.2 shows that
$\mathbb{E}[\chi^{2}(Q_{n}\|Q)]=\frac{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
$\mathbb{E}\|\hat{T}_{\varepsilon}-T_{\varepsilon}^{P\to
Q_{n}}\|^{2}_{L^{2}(P)}$ is upper bounded by

$\displaystyle\frac{8R^{2}}{\varepsilon}\mathbb{E}\int(\varphi_{\varepsilon}^{P\to
Q_{n}}-\varphi_{\varepsilon}^{P_{n}\to Q_{n}})\,\mathrm{d}(P_{n}-P)\,.$

Such a quantity can again be related to the estimation of the dual potentials
$\psi_{\varepsilon}^{P\to Q_{n}}$ and $\psi_{\varepsilon}^{P_{n}\to Q_{n}}$.
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.

##  4 Comparing against the 1NN estimator

###  4.1 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\geq 2$,
let $\mathcal{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

$\mathcal{R}_{n}(\mathcal{Q}_{J})=\inf_{\hat{T}}\sup_{Q\in\mathcal{Q}_{J}}{\mathbb{E}_{Q^{n}}}[\|\hat{T}-T_{0}^{P\to
Q}\|^{2}_{L_{2}(P)}]\,.$

Then, it holds that $\mathcal{R}_{n}(\mathcal{Q}_{J})\geq n^{-1/2}/64$.

###### Proof.

Let $e$ be a vector of the canonical basis of $\mathbb{R}^{d}$, scaled by
$1/2$. Fix $0<r<1/2$ and let
$Q_{0}=\frac{1}{2}\delta_{-e}+\frac{1}{2}\delta_{e}$ and
$Q_{1}=(\frac{1}{2}-r)\delta_{-e}+(\frac{1}{2}+r)\delta_{e}$. A computation
gives $\|T_{0}^{P\to Q_{0}}-T_{0}^{P\to Q_{1}}\|^{2}_{L_{2}(P)}=r$. Therefore,
by Le Cam’s lemma [see, e.g., 66, Chapter 15],

$\mathcal{R}_{n}(\mathcal{Q}_{J,R})\geq\frac{r}{8}(1-{\mathrm{d_{TV}}(Q_{0}^{n},Q_{1}^{n}))}.$
(22)

Let $\mathrm{d_{H^{2}}}(Q_{0},Q_{1})$ denote the (squared) Hellinger distance
between measures. We have

$\mathrm{d_{TV}}(Q_{0}^{n},Q_{1}^{n})^{2}\leq\mathrm{d_{H^{2}}}(Q_{0}^{n},Q_{1}^{n})\leq
n\mathrm{d_{H^{2}}}(Q_{0},Q_{1})\,.$

Furthermore, a computation gives

$\displaystyle\mathrm{d_{H^{2}}}(Q_{0},Q_{1})$
$\displaystyle=\bigg{(}\sqrt{\tfrac{1}{2}-r}-\sqrt{\tfrac{1}{2}}\bigg{)}^{2}+\bigg{(}\sqrt{\tfrac{1}{2}+r}-\sqrt{\tfrac{1}{2}}\bigg{)}^{2}$
$\displaystyle=2-(\sqrt{1+2r}+\sqrt{1-2r})$ $\displaystyle\leq 4r^{2}.$

We obtain the conclusion by picking $r=n^{-1/2}/4$. ∎

###  4.2 The 1NN estimator is proveably suboptimal

The 1-Nearest-Neighbor estimator, henceforth denoted $\hat{T}_{\text{1NN}}$,
was proposed by [45] as a computational surrogate for estimating optimal
transport maps in the low smoothness regime. Written succinctly, their
estimator is
$\hat{T}_{\text{1NN}}(x)=\sum_{i=1}^{n}\bm{1}_{V_{i}}(x)Y_{\hat{\pi}(i)}$,
where $(V_{i})_{i=1}^{n}$ are Voronoi regions i.e.

$\displaystyle V_{i}\coloneqq\\{x\in\mathbb{R}^{d}\ :\
\|x-X_{i}\|\leq\|x-X_{k}\|\,,\forall\ k\neq i\\}\,,$

and $\hat{\pi}$ 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 $\mathcal{O}(n\log(n))$, though the
complexity of this estimator is determined by computing the plan $\hat{\pi}$,
which takes $\mathcal{O}(n^{3})$ time via, e.g., the Hungarian Algorithm [see
53, Chapter 3].

When $\varphi_{0}$ is smooth and strongly convex, [45] showed that, for $d\geq
5$,

$\displaystyle\mathbb{E}\|\hat{T}_{\text{1NN}}-\nabla\varphi_{0}\|^{2}_{L^{2}(P)}\lesssim
n^{-2/d}\,.$

In contrast to the rate optimality of the entropic Brenier map, we now show
that $\hat{T}_{\text{1NN}}$ 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\geq 3$

$\displaystyle\mathbb{E}\|\hat{T}_{\text{1NN}}-T_{0}^{P\to
Q}\|^{2}_{L^{2}(P)}\gtrsim n^{-1/d}\,.$

###  4.3 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},\ldots,X_{n})$ and $(X_{1}^{\prime},\ldots,X_{n}^{\prime})$, and
create target points $Y_{i}=T_{0}(X_{i}^{\prime})$, where $T_{0}$ is known to
us in advance in order to generate the data. Our estimators are computed on
the data $(X_{1},\ldots,X_{n})$ and $(Y_{1},\ldots,Y_{n})$, and we evaluate
the Mean-Squared error criterion

$\text{MSE}(\hat{T})=\|\hat{T}-T_{0}\|_{L^{2}(P)}^{2}$

of a given map estimator $\hat{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.

####  4.3.1 Semi-discrete example #1

First consider $P=\text{Unif}([0,1]^{d})$ and create atoms
$\\{y_{1},\ldots,y_{J}\\}$ by partitioning the points along the first
coordinate for all $j\in[J]$:

$\displaystyle(y_{j})[1]=\frac{(j-1/2)}{J}\,,\quad(y_{j})[2]=\cdots=(y_{j})[d]=0.5\,.$

We choose uniform $q_{j}=1/J$ for $j\in[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.

Figure 2: Left: $\hat{T}_{\varepsilon}$ versus $\hat{T}_{\text{1NN}}$ for
$J=2$ and $d=10$. Right: $\hat{T}_{\varepsilon}$ versus $\hat{T}_{\text{1NN}}$
for $J=10$ and $d=50$.

####  4.3.2 Semi-discrete example #2

We now consider a synthetic experiment with far less symmetry. Let
$P=\text{Unif}([0,1]^{d})$, and fix $J\in\mathbb{N}$. We randomly generate
$y_{1},\ldots,Y_{J}\in[0,1]^{d}$, and also randomly generate
$\psi_{0}\in\mathbb{R}^{J}$, and consider the optimal transport map
$T_{0}(x)=\operatorname*{argmin}_{j\in[J]}\\{x^{\top}y_{j}-(\psi_{0})_{j}\\}$.
We define $Q=(T_{0})_{\sharp}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. Figure 3 contains plots the MSE as a function of $n$,
where again we see a log-linear slope of around $-0.5$, which agrees with our
theory.

Figure 3: $\hat{T}_{\varepsilon}$ versus $\hat{T}_{\text{1NN}}$ for with
$\psi_{0}$ random in $d=50$

####  4.3.3 Discontinuous example

We turn our attention to a discontinuous transport map, where for
$x\in\mathbb{R}^{d}$, all the coordinates are fixed except for the first one

$\displaystyle T_{0}(x)=2\text{sign}(x[1])\otimes x[2]\otimes\cdots\otimes
x[d]\,.$

We choose $P=\text{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.

Figure 4: $\hat{T}_{\varepsilon}$ versus $\hat{T}_{\text{1NN}}$ for $d=10$

##  5 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.

## 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.

##  Appendix 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 $\mu,\nu\in\mathcal{P}(\Omega)$, where
$\Omega\subset B(0;R)$ is a compact set.

######  Lemma A.1 (31).

The entropic potential
$(\varphi_{\varepsilon}^{\mu\to\nu},\psi_{\varepsilon}^{\mu\to\nu})$ have a
bounded amplitude, in the sense that

$\max_{x\in\Omega}\varphi_{\varepsilon}^{\mu\to\nu}-\min_{x\in\Omega}\varphi_{\varepsilon}^{\mu\to\nu}\leq
cR$ (23)

for some absolute constant $c$, and similarly for
$\psi_{\varepsilon}^{\mu\to\nu}$.

Assume now that $\nu=\sum_{j=1}^{J}\nu_{j}\delta_{y_{j}}$ is a discrete
measure. In this situation, only the values of the dual potential
$\psi_{\varepsilon}^{\mu\to\nu}$ on the points $y_{1},\dots,y_{J}$ are
relevant. We therefore consider $\psi_{\varepsilon}^{\mu\to\nu}$ as a vector
in $\mathbb{R}^{J}$. The potentials $\varphi_{\varepsilon}^{\mu\to\nu}$ and
$\psi_{\varepsilon}^{\mu\to\nu}$ are dual of one another, in the sense of the
$\varepsilon$-Legendre transform. Given a finite measure $\rho$, the
$\varepsilon$-Legendre transform of a function $h$ with respect to $\rho$ is
given by

$\Phi_{\varepsilon}^{\rho}(h)(x)=\varepsilon\log\int e^{(\langle
x,y\rangle-h(x))/\varepsilon}\,\mathrm{d}\rho(x).$ (24)

Relations (11) and (12) express that
$\varphi_{\varepsilon}^{\mu\to\nu}=\Phi_{\varepsilon}^{\nu}(\psi_{\varepsilon}^{\mu\to\nu})$
and vice-versa. In the semi-discrete setting, it is also convenient to
introduce the $\varepsilon$-Legendre transform with respect to the counting
measure $\sigma$ on $\\{y_{1},\dots,y_{J}\\}$. For a vector
$\psi\in\mathbb{R}^{J}$, we have

$\Phi_{\varepsilon}(\psi)(x)\coloneqq\Phi_{\varepsilon}^{\sigma}(\psi)(x)=\varepsilon\log\sum
e^{(\langle x,y_{j}\rangle-\psi(y_{j}))/\varepsilon}.$ (25)

The $\Phi_{\varepsilon}$ transform and the $\Phi_{\varepsilon}^{\nu}$
transform are linked through the relation

$\Phi_{\varepsilon}^{\nu}(\psi)=\Phi_{\varepsilon}(\tilde{\psi})\qquad\text{
where }\qquad\tilde{\psi}(y_{j})=\psi(y_{j})-\varepsilon\log\nu_{j}\,,$ (26)

where we call $\tilde{\psi}$ a _shifted_ potential. With this notation, the
optimality condition on the potentials can be rephrased. Let

$F_{\varepsilon}^{\mu\to\nu}:\psi\in\mathbb{R}^{J}\to\int\Phi_{\varepsilon}(\psi)\,\mathrm{d}\mu+\int\psi\,\mathrm{d}\nu\,.$
(27)

Then, the function $F_{\varepsilon}^{\mu\to\nu}$ is minimized at
$\tilde{\psi}_{\varepsilon}^{\mu\to\nu}$. For $\psi\in\mathbb{R}^{J}$ and
$x\in\mathbb{R}^{d}$, we introduce the probability measure supported on
$\\{y_{1},\dots,y_{J}\\}$ given by

$\forall i\in[J],\quad\pi_{\varepsilon}^{x}[\psi](y_{i})=\frac{e^{(\langle
x,y_{i}\rangle-\psi(y_{i}))/\varepsilon}}{\sum_{j=1}^{J}e^{(\langle
x,y_{j}\rangle-\psi(y_{j}))/\varepsilon}}=e^{(\langle
x,y_{i}\rangle-\Phi_{\varepsilon}(\psi)(x)-\psi(y_{i}))/\varepsilon}.$ (28)

A computation gives $\nabla
F_{\varepsilon}^{\mu\to\nu}(\psi)=\int\pi^{x}_{\varepsilon}[\psi]\,\mathrm{d}\mu(x)-\nu$,
so that at optimality, we have

$\int\pi^{x}_{\varepsilon}[\tilde{\psi}_{\varepsilon}^{\mu\to\nu}]\,\mathrm{d}\mu(x)=\nu.$
(29)

In this case,
$\pi^{x}_{\varepsilon}=\pi^{x}_{\varepsilon}[\tilde{\psi}_{\varepsilon}^{\mu\to\nu}]$
is the conditional distribution of the second marginal of $\pi_{\varepsilon}$
given that the first is equal to $x$, as in Section 2.2.1. More generally, for
any potential $\psi$, the first order condition implies that $\psi$ is equal
to $\tilde{\psi}_{\varepsilon}^{\mu\to\nu_{\psi}}$, the optimal dual potential
between $\mu$ an
$\nu_{\psi}=\int\pi^{x}_{\varepsilon}[\psi]\,\mathrm{d}\mu(x)$.

##  Appendix B Bound on the approximation error

###### Proof of Theorem 3.4.

Let $i,j\in[J]$. We define the $j$th slack at $x\in L_{i}$ by

$\frac{1}{2}\Delta_{ij}(x)=-\langle
x,y_{j}\rangle+\varphi_{0}(x)+\psi_{0}(y_{j}).$ (30)

As $\varphi_{0}$ is the Legendre transform of $\psi_{0}$, we have
$\Delta_{ij}(x)\geq 0$. If the cells $L_{i}$ and $L_{j}$ have a nonempty
intersection, the set $H_{ij}(t)=\\{x\in L_{i}:\ \Delta_{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 [2] that for
every nonnegative measurable function $f:\mathbb{R}\to{\mathbb{R}_{+}}$,

$\int_{L_{i}}f(\Delta_{ij}(x))p(x)\,\mathrm{d}x=\frac{1}{2\|y_{i}-y_{j}\|}\int_{0}^{\infty}f(t)h_{ij}(t)\,\mathrm{d}t,$
(31)

where $h_{ij}(t)=\int_{H_{ij}(t)}p(x)\,\mathrm{d}\mathcal{H}_{d-1}(x)$ and
$\mathcal{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^{\text{th}}$ and $j^{\text{th}}$ Laguerre cells (should it
exist). Given $x\in L_{i}$, let $s(x)=\min_{j\neq
i}\frac{1}{2}\Delta_{ij}(x)$. When the point $x$ is sufficiently inside its
Laguerre cell, the conditional probability $\pi_{\varepsilon}^{x}$ becomes
extremely concentrated around the point $y_{i}$, as the next lemma shows. Note
that $\pi_{0}^{x}=\delta_{y_{i}}$ when $x\in L_{i}$.

######  Lemma B.1.

Let $x\in L_{i}$. For $\varepsilon$ small enough, it holds that for every
$j\in[J]$, $|\pi_{\varepsilon}^{x}(y_{j})-\pi_{0}^{x}(y_{j})|\leq
ce^{-s(x)/\varepsilon}$, where $c$ depends on $J$, the distances
$\|y_{i}-y_{j}\|$ and on the quantities $w_{ij}$.

Such a result was already stated in [24, 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 [2, Proposition 4.6], for $\varepsilon$ small enough,

$\varepsilon^{-1}\|\tilde{\psi}_{\varepsilon}-\psi_{0}\|_{\infty}\leq C,$ (32)

where $\tilde{\psi}_{\varepsilon}$ is the shifted version of
$\psi_{\varepsilon}$ (see (25)) and $C$ depends on the distances
$\|y_{i}-y_{j}\|$ and on the $w_{ij}$s. Following [24, Proof of Corollary 2.2]
and (28), we have for $j\neq i$

$\displaystyle|\pi_{\varepsilon}^{x}(y_{j})-\pi_{0}^{x}(y_{j})|$
$\displaystyle=\pi_{\varepsilon}^{x}(y_{j})=\frac{e^{(\langle
x,y_{j}\rangle-\tilde{\psi}_{\varepsilon}(y_{j}))/\varepsilon}}{\sum_{j^{\prime}=1}^{J}e^{(\langle
x,y_{j^{\prime}}\rangle-\tilde{\psi}_{\varepsilon}(y_{j^{\prime}}))/\varepsilon}}\leq
e^{2C}\frac{e^{(\langle
x,y_{j}\rangle-\psi_{0}(y_{j}))/\varepsilon}}{\sum_{j^{\prime}=1}^{J}e^{(\langle
x,y_{j^{\prime}}\rangle-\psi_{0}(y_{j^{\prime}}))/\varepsilon}}\leq
e^{2C}e^{-s(x)/\varepsilon}.$

A similar computation yields that
$|\pi_{\varepsilon}^{x}(y_{i})-\pi_{0}^{x}(y_{i})|=|\pi_{\varepsilon}^{x}(y_{i})-1|\leq
Je^{2C}e^{-s(x)/\varepsilon}$. ∎

We can bound for any $x\in L_{i}$,

$\|T_{\varepsilon}(x)-T_{0}(x)\|=\|\sum_{j=1}^{J}y_{j}(\pi_{\varepsilon}^{x}(y_{j})-\pi_{0}^{x}(y_{j}))\|\leq
c\sum_{j=1}^{J}\|y_{j}\|e^{-s(x)/\varepsilon}.$ (33)

Therefore, letting $C^{\prime}$ denote a constant, which may depend on $J$,
whose value may change from line to line, we obtain

$\displaystyle\|T_{\varepsilon}-T_{0}\|^{2}_{L_{2}(P)}$
$\displaystyle=\sum_{i=1}^{J}\int_{L_{i}}\|T_{\varepsilon}(x)-T_{0}(x)\|^{2}\,\mathrm{d}P(x)\leq
C^{\prime}\sum_{i=1}^{J}\int_{L_{i}}\sum_{j=1}^{J}e^{-2s(x)/\varepsilon}\,\mathrm{d}P(x)$
(34) $\displaystyle\leq C^{\prime}\sum_{i\neq
j}\int_{L_{i}}e^{-\Delta_{ij}(x)/\varepsilon}\,\mathrm{d}P(x)\leq
C^{\prime}\sum_{i\neq
j}\frac{1}{2\|y_{i}-y_{j}\|}\int_{0}^{\infty}e^{-t/\varepsilon}h_{ij}(t)\,\mathrm{d}t\,,$
(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 $\varepsilon$. ∎

##  Appendix C Stability of entropic transport plans

###### Proof of Proposition 3.9.

Note that we may assume without loss of generality that $\nu\ll\nu^{\prime}$
and that $\text{KL}(\nu\|\nu^{\prime})<\infty$, for otherwise the bound is
vacuous. For notational convenience, we omit the dependence on $\varepsilon$
in the subscripts. Write
$\pi^{\mu,\nu}=\gamma^{\mu,\nu}(x,y)\mathrm{d}\mu(x)\mathrm{d}\nu(y)$ for the
entropic optimal plan between $\mu$ and $\nu$, where
$\gamma^{\mu,\nu}=\exp\left(\frac{1}{\varepsilon}(\langle
x,y\rangle-\varphi^{\mu\to\nu}(x)-\psi^{\mu\to\nu}(y))\right)$, and
analogously define
$\gamma^{\mu^{\prime},\nu^{\prime}}=\exp\left(\frac{1}{\varepsilon}(\langle
x,y\rangle-\varphi^{\mu^{\prime}\to\nu^{\prime}}(x)-\psi^{\mu^{\prime}\to\nu^{\prime}}(y))\right)$.

Consider the measure
$\gamma^{\mu^{\prime},\nu^{\prime}}(x,y)\,\mathrm{d}\mu(x)\,\mathrm{d}\nu^{\prime}(y)$.
The first-order optimality condition for
$(\varphi^{\mu^{\prime}\to\nu^{\prime}},\psi^{\mu^{\prime}\to\nu^{\prime}})$
implies that

$\int\gamma^{\mu^{\prime},\nu^{\prime}}(y)\,\mathrm{d}\nu^{\prime}(y)=1\quad\forall
x\in\Omega\,,$ (36)

so that $\gamma^{\mu^{\prime},\nu^{\prime}}(x,y)\,\mathrm{d}\nu^{\prime}(y)$
is a probability measure. Let us write
$\mathrm{d}\pi^{x}(y)=\gamma^{\mu,\nu}(x,y)\,\mathrm{d}\nu(y)$ and
$\mathrm{d}\rho^{x}(y)=\gamma^{\mu^{\prime},\nu^{\prime}}(x,y)\,\mathrm{d}\nu^{\prime}(y)$.

We make the following observations: first, $T^{\mu\to\nu}(x)=\int
y\,\mathrm{d}\pi^{x}(y)$ and $T^{\mu^{\prime}\to\nu^{\prime}}(x)=\int
y\,\mathrm{d}\rho^{x}(y)$. Second, the support of $\rho^{x}$ lies inside
$B(0;R)$; since any Lipschitz function $f$ on $B(0;R)$ satisfies
$\sup_{x}f(x)-\inf_{x}f(x)\leq 2R$, Hoeffding’s lemma [see 7, Lemma 2.2]
implies that if $f$ is Lipschitz and $\int f\,\mathrm{d}\rho^{x}=0$, then

$\int e^{tf}\,\mathrm{d}\rho^{x}\leq e^{2R^{2}t^{2}}\quad\forall
t\in\mathbb{R}\,.$

This implies [4, Theorem 3.1] that

$W_{1}(\pi^{x},\rho^{x})^{2}\leq 8R^{2}\text{KL}(\pi^{x}\|\rho^{x})\,.$ (37)

Third, Jensen’s inequality implies that for any coupling $\gamma$ between
$\pi^{x}$ and $\rho^{x}$,

$\int\|y-y^{\prime}\|\,\mathrm{d}\gamma(y,y^{\prime})\geq\left\|\int(y-y^{\prime})\,\mathrm{d}\gamma(y,y^{\prime})\right\|=\|T^{\mu\to\nu}(x)-T^{\mu^{\prime}\to\nu^{\prime}}(x)\|\,,$
(38)

so that in particular,
$\|T^{\mu\to\nu}(x)-T^{\mu^{\prime}\to\nu^{\prime}}(x)\|\leq
W_{1}(\pi^{x},\rho^{x})$. Combining these facts, we obtain

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}(x)-T^{\mu^{\prime}\to\nu^{\prime}}(x)\|^{2}\leq\text{KL}(\pi^{x}\|\rho^{x})=\int\log\left(\frac{\gamma^{\mu,\nu}}{\gamma^{\mu^{\prime},\nu^{\prime}}}(x,y)\frac{\mathrm{d}\nu}{\mathrm{d}\nu^{\prime}}(y)\right)\gamma^{\mu,\nu}(x,y)\,\mathrm{d}\nu(y)\,.$
(39)

Integrating both sides of this equation with respect to $\mu$ yields

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}(x)-T^{\mu^{\prime}\to\nu^{\prime}}(x)\|^{2}_{L^{2}(\mu)}\leq\int\log\left(\frac{\gamma^{\mu,\nu}}{\gamma^{\mu^{\prime},\nu^{\prime}}}(x,y)\frac{\mathrm{d}\nu}{\mathrm{d}\nu^{\prime}}(y)\right)\,\mathrm{d}\pi^{\mu,\nu}(x,y)\,.$
(40)

Expanding the definition of $\gamma^{\mu,\nu}$ and
$\gamma^{\mu^{\prime},\nu^{\prime}}$ and using that

$\int\log\frac{\mathrm{d}\nu}{\mathrm{d}\nu^{\prime}}(y)\,\mathrm{d}\pi^{\mu,\nu}(x,y)=\int\log\frac{\mathrm{d}\nu}{\mathrm{d}\nu^{\prime}}(y)\,\mathrm{d}\nu(y)=\text{KL}(\nu\|\nu^{\prime})$

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 $\mu,\nu,\nu^{\prime}$ supported in $B(0;R)$,

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}_{\varepsilon}-T^{\mu\to\nu^{\prime}}_{\varepsilon}\|_{L^{2}(\mu)}^{2}\leq\varepsilon^{-1}\int(\psi_{\varepsilon}^{\mu\to\nu^{\prime}}-\psi_{\varepsilon}^{\mu\to\nu})\,\mathrm{d}(\nu-\nu^{\prime})+\text{KL}(\nu\|\nu^{\prime})$
(41)

###### Proof.

We apply Proposition 3.9 with $\mu=\mu^{\prime}$, which yields (once again
omitting the dependency in $\varepsilon$)

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}_{\varepsilon}-T^{\mu\to\nu^{\prime}}_{\varepsilon}\|_{L^{2}(\mu)}^{2}\leq\varepsilon^{-1}\left(\int(\varphi^{\mu\to\nu^{\prime}}-\varphi^{\mu\to\nu})\,\mathrm{d}\mu+\int(\psi^{\mu\to\nu^{\prime}}-\psi^{\mu\to\nu})\,\mathrm{d}\nu\right)+\text{KL}(\nu\|\nu^{\prime})\,.$
(42)

By definition, $(\varphi^{\mu\to\nu^{\prime}},\psi^{\mu\to\nu^{\prime}})$
minimizes the expression

$\int\varphi\,\mathrm{d}\mu+\int\psi\,\mathrm{d}\nu^{\prime}+\varepsilon\iint
e^{(\langle
x,y\rangle-\varphi(x)-\psi(y))/\varepsilon}\,\mathrm{d}\mu(x)\,\mathrm{d}\nu^{\prime}(y)-\varepsilon$

, so, recalling that $\iint e^{(\langle
x,y\rangle-\varphi^{\mu\to\nu^{\prime}}(x)-\psi^{\mu\to\nu^{\prime}}(y))/\varepsilon}\,\mathrm{d}\mu(x)\,\mathrm{d}\nu^{\prime}(y)=1$,
we have in particular

$\displaystyle\int\varphi^{\mu\to\nu^{\prime}}\,\mathrm{d}\mu+\int\psi^{\mu\to\nu^{\prime}}\,\mathrm{d}\nu^{\prime}$
$\displaystyle\leq\int\varphi^{\mu\to\nu}\,\mathrm{d}\mu+\int\psi^{\mu\to\nu}\,\mathrm{d}\nu^{\prime}+\varepsilon\iint
e^{(\langle
x,y\rangle-\varphi^{\mu\to\nu}(x)-\psi^{\mu\to\nu}(y))/\varepsilon}\,\mathrm{d}\mu(x)\,\mathrm{d}\nu^{\prime}(y)-\varepsilon$
$\displaystyle=\int\varphi^{\mu\to\nu}\,\mathrm{d}\mu+\int\psi^{\mu\to\nu}\,\mathrm{d}\nu^{\prime}\,,$

where we have used that the first-order optimality condition for
$(\varphi^{\mu\to\nu},\psi^{\mu\to\nu})$ implies that $\iint e^{(\langle
x,y\rangle-\varphi^{\mu\to\nu}(x)-\psi^{\mu\to\nu}(y))/\varepsilon}\,\mathrm{d}\mu(x)\,\mathrm{d}\nu^{\prime}(y)=1$
as well (see (11)). This implies

$\int(\varphi^{\mu\to\nu^{\prime}}-\varphi^{\mu\to\nu})\,\mathrm{d}\mu\leq-\int(\psi^{\mu\to\nu^{\prime}}-\psi^{\mu\to\nu})\,\mathrm{d}\nu^{\prime}\,.$
(43)

Applying this inequality to (42) yields

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}_{\varepsilon}-T^{\mu\to\nu^{\prime}}_{\varepsilon}\|_{L^{2}(\mu)}^{2}\leq\varepsilon^{-1}\int(\psi^{\mu\to\nu^{\prime}}-\psi^{\mu\to\nu})\,\mathrm{d}(\nu-\nu^{\prime})+\text{KL}(\nu\|\nu^{\prime}).\qed$

######  Corollary C.2.

For any $\mu,\mu^{\prime},\nu$ supported in $B(0;R)$,

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}_{\varepsilon}-T^{\mu^{\prime}\to\nu}_{\varepsilon}\|_{L^{2}(\mu)}^{2}\leq\varepsilon^{-1}\int(\varphi_{\varepsilon}^{\mu^{\prime}\to\nu}-\varphi_{\varepsilon}^{\mu\to\nu})\,\mathrm{d}(\mu-\mu^{\prime})\,.$
(44)

###### Proof.

We apply Proposition 3.9 with $\nu=\nu^{\prime}$, yielding (dropping the
dependency on $\varepsilon$)

$\frac{1}{8R^{2}}\|T^{\mu\to\nu}-T^{\mu^{\prime}\to\nu}\|_{L^{2}(\mu)}^{2}\leq\varepsilon^{-1}\left(\int(\varphi^{\mu^{\prime}\to\nu}-\varphi^{\mu\to\nu})\,\mathrm{d}\mu+\int(\psi^{\mu^{\prime}\to\nu}-\psi^{\mu\to\nu})\,\mathrm{d}\nu\right)\,.$
(45)

An argument analogous to the one used in the proof of Corollary C.1 gives the
inequality

$\int\varphi^{\mu^{\prime}\to\nu}\,\mathrm{d}\mu^{\prime}+\int\psi^{\mu^{\prime}\to\nu}\,\mathrm{d}\nu\leq\int\varphi^{\mu\to\nu}\,\mathrm{d}\mu^{\prime}+\int\psi^{\mu\to\nu}\,\mathrm{d}\nu\,,$
(46)

or, equivalently,

$\int(\psi^{\mu^{\prime}\to\nu}-\psi^{\mu\to\nu})\,\mathrm{d}\nu\leq-\int(\varphi^{\mu^{\prime}\to\nu}-\varphi^{\mu\to\nu})\,\mathrm{d}\mu^{\prime}\,,$
(47)

and combining this inequality with (45) proves the claim. ∎

##  Appendix D Strong convexity of the entropic semi-dual problem

######  Proposition D.1 (Strong convexity of $F^{\mu\to\nu}_{\varepsilon}$).

Let $\nu=\sum_{j=1}^{J}\nu_{j}\delta_{y_{j}}$ be a measure supported on
$\\{y_{1},\dots,y_{J}\\}\subseteq B(0;R)$ and let $\mu$ supported on a compact
convex set $\Omega\subseteq B(0;R)$ with a density $p$ satisfying
$p_{\min}\leq p\leq p_{\max}$ for some $p_{\max}\geq p_{\min}>0$. For
$\psi\in\mathbb{R}^{J}$, define
$\nu_{\psi}=\int\pi_{\varepsilon}^{x}[\psi]\,\mathrm{d}\mu(x)$ and assume that
$\nu_{\psi}\geq\lambda\nu$ for some $0<\lambda\leq 1$. Then, we have for
$\varepsilon\in(0,1)$

$F^{\mu\to\nu}_{\varepsilon}(\psi)-\min_{\psi}F^{\mu\to\nu}_{\varepsilon}\geq
C\lambda\cdot\mathrm{Var}_{\nu}(\psi-\psi^{\mu\to\nu}_{\varepsilon}),$ (48)

where
$C=\left(e^{2R^{2}}\frac{p_{\max}}{p_{\min}}+\varepsilon\right)^{-1}\frac{p_{\min}}{p_{\max}}$.

###### Proof.

As $\mu$ and $\varepsilon$ are fixed, we will simply write $\psi_{\nu}$
instead of $\psi_{\varepsilon}^{\mu\to\nu}$, and write similarly
$F_{\nu}=F_{\varepsilon}^{\mu\to\nu}$. Recall the definition (25) of the
shifted potential
$\tilde{\psi}_{\nu}(y_{j})=\psi_{\nu}(y_{j})-\varepsilon\log\nu_{j}$.
According to [24, Theorem 3.2], the functional $F_{\nu}$ is minimized at the
vector $\tilde{\psi}_{\nu}$, with

$\forall
v\in\mathbb{R}^{J},\quad\mathrm{Var}_{\nu}(v)\leq\left(e^{2R^{2}}\frac{p_{\max}}{p_{\min}}+\varepsilon\right)v^{\top}\nabla^{2}F_{\nu}(\tilde{\psi}_{\nu})v.$
(49)

For $t\in[0,1]$, let $\psi_{t}=\tilde{\psi}_{\nu}+t(\psi-\tilde{\psi}_{\nu})$
and let $\nu_{t}=\int\pi_{\varepsilon}^{x}[\psi_{t}]\,\mathrm{d}\mu(x)$. The
potential $\psi_{t}$ is the (shifted) entropic Brenier potential between $\mu$
and $\nu_{t}$, so that it minimizes the functional $F_{\nu_{t}}$ (see Appendix
A). Also, note that $\nabla^{2}F_{\nu}$ does not depend on $\nu$, so that

$v^{\top}\nabla^{2}F_{\nu}(\psi_{t})v=v^{\top}\nabla^{2}F_{\nu_{t}}(\psi_{t})v\geq\left(e^{2R^{2}}\frac{p_{\max}}{p_{\min}}+\varepsilon\right)^{-1}\mathrm{Var}_{\nu_{t}}(v).$
(50)

Let $v=\psi-\psi^{\mu\to\nu}_{\varepsilon}$. A Taylor expansion of $F_{\nu}$
gives

$F_{\nu}(\psi)-F_{\nu}(\tilde{\psi}_{\nu})=\int_{0}^{1}v^{\top}\nabla^{2}F_{\nu}(\psi_{t})v\,\mathrm{d}t\geq\left(e^{2R^{2}}\frac{p_{\max}}{p_{\min}}+\varepsilon\right)^{-1}\int_{0}^{1}\mathrm{Var}_{\nu_{t}}(v)\,\mathrm{d}t.$
(51)

######  Lemma D.2.

Write $\nu_{t}=\sum_{j=1}^{J}\nu_{t,j}\delta_{y_{j}}$. Then, for all
$t\in[0,1]$ and $j\in[J]$, we have
$\nu_{t,j}\geq\frac{p_{\min}}{p_{\max}}\nu_{0,j}^{1-t}\nu_{1,j}^{t}$.

This lemma is enough to conclude the proof. Indeed,
$\nu_{1}=\nu_{\psi}\geq\lambda\nu$, so that it implies that
$\mathrm{Var}_{\nu_{t}}(v)\geq\frac{p_{\min}}{p_{\max}}\lambda\mathrm{Var}_{\nu}(v)$.
∎

###### Proof of Lemma D.2.

According to [24, Proof of Proposition 4.1],

$\Phi_{\varepsilon}(\psi_{t})(tx+(1-t)y)\leq
t\Phi_{\varepsilon}(\tilde{\psi}^{\mu\to\nu}_{\varepsilon})(x)+(1-t)\Phi_{\varepsilon}(\psi)(y).$
(52)

Therefore, if we let $h_{t}(x)=e^{(\langle
x,y_{j}\rangle-\psi_{t}(y_{j})-\Phi_{\varepsilon}(\psi_{t})(x))/\varepsilon}$,
then we have $h_{t}(tx+(1-t)y)\geq h_{0}(x)^{t}h_{1}(y)^{1-t}$. By the
Prékopa-Leindler inequality,

$\displaystyle\nu_{t,j}=\int h_{t}(x)\,\mathrm{d}\mu(x)\geq
p_{\min}\int_{\mathcal{X}}h_{t}(x)\,\mathrm{d}x\geq
p_{\min}\left(\int_{\mathcal{X}}h_{0}(x)\,\mathrm{d}x\right)^{t}\left(\int_{\mathcal{X}}h_{1}(x)\,\mathrm{d}x\right)^{1-t}\geq\frac{p_{\min}}{p_{\max}}\nu_{0,j}^{t}\nu_{1,j}^{1-t}.$

∎

###### Proof of Proposition 3.11.

As in the previous proof, we drop the $\varepsilon$ and $\mu$ dependency in
our notation. Write $\nu_{k}=\sum_{j=1}^{J}\nu_{k,j}\delta_{y_{j}}$ for
$k=0,1$, and define as before the shifted potentials
$\tilde{\psi}_{\nu_{k}}(y_{j})=\psi_{\nu_{1}}(y_{j})-\varepsilon\log\nu_{k,j}$.
Let $\theta>0$ be a parameter to fix. According to Proposition D.1, Lemma H.1,
and using the inequality $F_{\nu_{1}}(\tilde{\psi}_{\nu_{1}})\leq
F_{\nu_{1}}(\tilde{\psi}_{\nu_{0}})$, we have

$\displaystyle
C\lambda\mathrm{Var}_{\nu_{0}}(\tilde{\psi}_{\nu_{1}}-\tilde{\psi}_{\nu_{0}})\leq
F_{\nu_{0}}(\tilde{\psi}_{\nu_{1}})-F_{\nu_{0}}(\tilde{\psi}_{\nu_{0}})$
$\displaystyle\leq
F_{\nu_{0}}(\tilde{\psi}_{\nu_{1}})-F_{\nu_{1}}(\tilde{\psi}_{\nu_{1}})+F_{\nu_{1}}(\tilde{\psi}_{\nu_{0}})-F_{\nu_{0}}(\tilde{\psi}_{\nu_{0}})$
$\displaystyle=\int(\tilde{\psi}_{\nu_{1}}-\tilde{\psi}_{\nu_{0}})(\,\mathrm{d}\nu_{0}-\,\mathrm{d}\nu_{1})$
$\displaystyle\leq\frac{\theta}{2}\mathrm{Var}_{\nu_{0}}(\tilde{\psi}_{\nu_{1}}-\tilde{\psi}_{\nu_{0}})+\frac{1}{2\theta}\chi^{2}(\nu_{1}\|\nu_{0}).$

We pick $\theta=C\lambda$ to conclude that

$\mathrm{Var}_{\nu_{0}}(\tilde{\psi}_{\nu_{1}}-\tilde{\psi}_{\nu_{0}})\leq\frac{1}{(C\lambda)^{2}}\chi^{2}(\nu_{1}\|\nu_{0}).$
(53)

Therefore, using the inequality $|\log(a/b)|\leq|a-b|/\min\\{a,b\\}$ for
$a,b>0$,

$\displaystyle\mathrm{Var}_{\nu_{0}}(\psi_{1}-\psi_{0})$ $\displaystyle\leq
2\mathrm{Var}_{\nu_{0}}(\tilde{\psi}_{1}-\tilde{\psi}_{0})+2\sum_{j=1}^{J}\nu_{0,j}\left(\log\left(\frac{\nu_{1,j}}{\nu_{0,j}}\right)\right)^{2}$
$\displaystyle\leq\frac{2}{(C\lambda)^{2}}\chi^{2}(\nu_{1}\|\nu_{0})+2\sum_{j=1}^{J}\nu_{0,j}\left(\frac{\nu_{1,j}-\nu_{0,j}}{\min\\{\nu_{0,j},\nu_{1,j}\\}}\right)^{2}$
$\displaystyle\leq\frac{2}{(C\lambda)^{2}}\chi^{2}(\nu_{1}\|\nu_{0})+\frac{2}{\lambda^{2}}\sum_{j=1}^{J}\frac{1}{\nu_{0,j}}(\nu_{1,j}-\nu_{0,j})^{2}\leq\left(\frac{2}{(C\lambda)^{2}}+\frac{2}{\lambda^{2}}\right)\chi^{2}(\nu_{1}\|\nu_{0}).\qed$

##  Appendix 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
$\mathbb{E}\|T_{\varepsilon}^{P\to
Q_{n}}-T_{\varepsilon}\|^{2}_{L^{2}(P)}\lesssim\varepsilon^{-1}n^{-1}$.

###### Proof.

To ease notation, we write $T_{\varepsilon,n}=T_{\varepsilon}^{P\to Q_{n}}$
and $\psi_{\varepsilon,n}=\psi_{\varepsilon}^{P\to Q_{n}}$. As explained in
Section 3, the stability result Proposition 3.9 implies that

$\mathbb{E}\|T_{\varepsilon,n}-T_{\varepsilon}\|^{2}_{L^{2}(P)}\leq\frac{8R^{2}}{\varepsilon}\Big{(}\frac{\mathbb{E}[\mathrm{Var}_{Q}(\psi_{\varepsilon,n}-\psi_{\varepsilon})]}{2}+\frac{\mathbb{E}[\chi^{2}(Q_{n}\|Q)]}{2}\Big{)}+8R^{2}\mathbb{E}[\chi^{2}(Q_{n}\|Q)]\,.$
(54)

Write $Q=\sum_{j=1}^{J}q_{j}\delta_{y_{j}}$ and
$Q_{n}=\sum_{j=1}^{J}\hat{q}_{j}\delta_{y_{j}}$, and introduce the event
$E=\\{\forall j\in[J],\ \hat{q}_{j}\geq q_{j}/2\\}$. If $E$ is satisfied, we
have $Q_{n}\geq Q/2$, so that Proposition 3.11 yields

$\mathrm{Var}_{Q}(\psi_{\varepsilon,n}-\psi_{\varepsilon})\leq
C\chi^{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

$\mathrm{Var}_{Q}(\psi_{\varepsilon,n}-\psi_{\varepsilon})\leq C^{\prime}.$
(56)

######  Lemma E.2.

Let $E$ be the event that $Q_{n}\geq Q/2$. Then $\mathbb{P}(E^{c})\leq
Je^{-cq_{\min}n}$ for some $c>0$.

###### Proof.

By [63, Exercise 2.3.2], we have
$\mathbb{P}(E^{c})\leq\sum_{j=1}^{J}\mathbb{P}(\hat{q}_{j}<q_{j}/2)\leq
Je^{-cq_{\min}n}$ for some $c>0$. ∎

We obtain

$\mathbb{E}\|\hat{T}_{\varepsilon,n}-T_{\varepsilon}\|^{2}_{L^{2}(P)}\lesssim\frac{R^{2}}{\varepsilon}\mathbb{E}[\chi^{2}(Q_{n}\|Q)]+\frac{R^{2}}{\varepsilon}Je^{-cq_{\min}n}\lesssim\varepsilon^{-1}n^{-1}$
(57)

by Lemma H.2. ∎

##  Appendix 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
$\nu=\sum_{j=1}^{J}\nu_{j}\delta_{y_{j}}$_ supported on
$\\{y_{1},\dots,y_{J}\\}$ with $\nu_{j}\geq\nu_{\min}>0$ for all $j\in[J]$, we
have for $\log(1/\varepsilon)\lesssim n/\log(n)$,

$\mathbb{E}\|T_{\varepsilon}^{P_{n}\to\nu}-T_{\varepsilon}^{P\to\nu}\|_{L_{2}(P)}^{2}\lesssim\varepsilon^{-1}n^{-1}.$
(58)

Theorem 3.7 follows from (58) by conditioning on $Q_{n}$. Let $E$ be the event
that $Q_{n}\geq Q/2$. Then, by Lemma E.2,

$\displaystyle\mathbb{E}\|\hat{T}_{\varepsilon}-T_{\varepsilon}^{P\to
Q_{n}}\|_{L_{2}(P)}^{2}$
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}[\|\hat{T}_{\varepsilon}-T_{\varepsilon}^{P\to
Q_{n}}\|_{L_{2}(P)}^{2}|Q_{n}]\mathds{1}\\{E\\}\right]+R^{2}\mathbb{P}(E^{c})$
$\displaystyle\leq
C\varepsilon^{-1}n^{-1}+R^{2}Je^{-cq_{\min}n}\lesssim\varepsilon^{-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

$\begin{split}\mathbb{E}\|T_{\varepsilon}^{P_{n}\to\nu}-T_{\varepsilon}^{P\to\nu}\|_{L_{2}(P)}^{2}&\leq
8R^{2}\varepsilon^{-1}\mathbb{E}\int(\varphi_{\varepsilon}^{P_{n}\to\nu}-\varphi_{\varepsilon}^{P\to\nu})\,\mathrm{d}(P_{n}-P)\\\
&=8R^{2}\varepsilon^{-1}\mathbb{E}\int(\Phi_{\varepsilon}(\tilde{\psi}_{\varepsilon}^{P_{n}\to\nu})-\Phi_{\varepsilon}(\tilde{\psi}_{\varepsilon}^{P\to\nu}))\,\mathrm{d}(P_{n}-P),\end{split}$
(59)

where we recall that for a potential $\psi$, the shifted potential
$\tilde{\psi}$ is given by $\tilde{\psi}_{j}=\psi_{j}-\varepsilon\log\nu_{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
$\psi_{\varepsilon}^{P_{n}\to\nu}$ is close to to the potential
$\psi_{\varepsilon}^{P\to\nu}$ for the $\infty$-norm. It will be convenient to
work with the “$L_{\infty}$-variance”

$\mathrm{Var}_{\infty}(\psi)=\inf_{c\in\mathbb{R}}\max_{j\in[J]}|\psi(y_{j})-c|^{2}=\left(\frac{\max\psi-\min\psi}{2}\right)^{2}.$
(60)

As the measure $\nu$ is lower bounded, it holds that

$\mathrm{Var}_{\nu}(\psi)\geq\nu_{\min}\mathrm{Var}_{\infty}(\psi).$ (61)

######  Lemma F.1 (Supremum of $\varepsilon$-Legendre transforms).

Let $\psi_{0}$ be a fixed potential and let $\tau>0$. Then, for all $j\in[J]$,

$\displaystyle\mathbb{E}\left[\sup_{\mathrm{Var}_{\infty}(\psi-\psi_{0})\leq\tau^{2}}\left|\int(\pi_{\varepsilon}^{x}(\psi)_{j}-\pi_{\varepsilon}^{x}(\psi_{0})_{j})\,\mathrm{d}(P-P_{n})(x)\right|\right]\leq
C\sqrt{\frac{J\max\\{\log(\tau/\varepsilon),1\\}}{n}}$ (62)
$\displaystyle\mathbb{E}\left[\sup_{\mathrm{Var}_{\infty}(\psi-\psi_{0})\leq\tau^{2}}\left|\int(\Phi_{\varepsilon}(\psi)(x)-\Phi_{\varepsilon}(\psi_{0}))(x)\,\mathrm{d}(P-P_{n})(x)\right|\right]\leq
C\tau\sqrt{\frac{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_{\infty}$-ball of radius $\tau$ in
$\mathbb{R}^{J}$, centered at $\psi_{0}$, and let $\|\cdot\|_{\infty}$ denote
the $\infty$-norm. For $0<u\leq\tau$, we have $\log
N(u,B,\|\cdot\|_{\infty})\leq J\log(\tau/u)$.

We start with the second inequality. Note that
$\psi\mapsto\Phi_{\varepsilon}(\psi)$ is $1$-Lipschitz continuous, and that
the functional $\Phi_{\varepsilon}$ satisfies
$\Phi_{\varepsilon}(\psi+c)=\Phi_{\varepsilon}(\psi)+c$ for all
$c\in\mathbb{R}$. Then the set $\\{\psi:\
\mathrm{Var}_{\infty}(\psi-\psi_{0})\leq\tau^{2}\\}$ is equal to the set
$\\{\psi+c:\ \psi\in B,\ c\in\mathbb{R}\\}$. As $\int
c\,\mathrm{d}(P-P_{n})=0$, we can therefore restrict the supremum to vectors
$\psi\in B$. Furthermore, an envelope function of the class
$\\{\Phi_{\varepsilon}(\psi)-\Phi_{\varepsilon}(\psi_{0}):\ \psi\in B\\}$ is
the constant function equal to $\tau$. Therefore, by Lemma H.3, we obtain

$\begin{split}\mathbb{E}\left[\sup_{\|\psi-\psi_{0}\|_{\infty}\leq\tau}\left|\int(\Phi_{\varepsilon}(\psi)-\Phi_{\varepsilon}(\psi_{0}))(\,\mathrm{d}P-\,\mathrm{d}P_{n})\right|\right]&\leq\frac{c_{0}}{\sqrt{n}}\int_{0}^{c_{1}\tau}\sqrt{J\log
2N(u,\\{\Phi_{\varepsilon}(\psi):\ \psi\in
B\\},\|\cdot\|_{\infty})}\,\mathrm{d}u\\\
&\leq\sqrt{\frac{c_{3}J\tau}{n}}.\qed\end{split}$ (64)

We repeat the same argument for the first inequality. The functional
$\pi_{\varepsilon}^{x}$ is invariant by translation:
$\pi_{\varepsilon}^{x}(\psi+c)=\pi_{\varepsilon}^{x}(\psi)$ for all
$c\in\mathbb{R}$. This implies that

$\displaystyle\sup_{\mathrm{Var}_{\infty}(\psi-\psi_{0})\leq\tau^{2}}\left|\int(\Phi_{\varepsilon}(\psi)(x)-\Phi_{\varepsilon}(\psi_{0}))(x)\,\mathrm{d}(P-P_{n})(x)\right|=$
$\displaystyle\sup_{\|\psi-\psi_{0}\|_{\infty}\leq\tau}\left|\int(\Phi_{\varepsilon}(\psi)(x)-\Phi_{\varepsilon}(\psi_{0}))(x)\,\mathrm{d}(P-P_{n})(x)\right|.$

As the function $\psi\mapsto\pi_{\varepsilon}^{x}(\psi)_{j}$ is
$\varepsilon^{-1}$-Lipschitz continuous for every $x\in\mathbb{R}^{d}$, we
have for $0<u\leq\tau/\varepsilon$,

$\log N(u,\\{x\mapsto\pi_{\varepsilon}^{x}(\psi)_{j}:\ \psi\in
B\\},\|\cdot\|_{\infty})\leq J\log(\tau/(u\varepsilon))\,.$

Remarking furthermore that $0\leq\pi_{\varepsilon}^{x}(\psi)_{j}\leq 1$ (so
that the class of functions $\\{x\mapsto\pi_{\varepsilon}^{x}(\psi)_{j}:\
\psi\in B\\}$ admits the constant function $1$ as an envelope function), we
obtain the following control using Lemma H.3:

$\displaystyle\mathbb{E}\left[\sup_{\|\psi-\psi_{0}\|_{\infty}\leq\tau}\left|\int(\pi_{\varepsilon}^{x}(\psi)_{j}-\pi_{\varepsilon}^{x}(\psi_{0})_{j})(\,\mathrm{d}P-\,\mathrm{d}P_{n})(x)\right|\right]$
$\displaystyle\qquad\leq\frac{c_{0}}{\sqrt{n}}\int_{0}^{c_{1}}\sqrt{J\log
2N(u,\\{x\mapsto\pi_{\varepsilon}^{x}(\psi)_{j}:\ \psi\in
B\\},\|\cdot\|_{\infty})}\,\mathrm{d}u$
$\displaystyle\qquad\leq\sqrt{\frac{c_{2}J\max\\{\log(\tau/\varepsilon),1\\}}{n}},$

where $c_{0}$, $c_{1}$ and $c_{2}$ are absolute constants, and the last line
follows from arguing whether $c_{1}<\tau/\varepsilon$ or not.

######  Proposition F.2.

Assume that $P$ satisfies (A) and let
$\nu=\sum_{j=1}^{J}\nu_{j}\delta_{y_{j}}$ be a measure supported on
$\\{y_{1},\dots,y_{J}\\}\subset B(0;R)$, with $\nu_{j}\geq q_{\min}$ for all
$j\in[J]$. Then, for all $0<\varepsilon\leq 1$ with
$\log(1/\varepsilon)\lesssim n/\log(n)$, it holds that

$\mathbb{E}\mathrm{Var}_{\infty}(\tilde{\psi}_{\varepsilon}^{P_{n}\to\nu}-\tilde{\psi}_{\varepsilon}^{P\to\nu})\lesssim
n^{-1}.$ (65)

###### Proof.

To alleviate notation, we will write
$\psi_{n}=\psi_{\varepsilon}^{P_{n}\to\nu}$ and
$\psi_{0}=\psi_{\varepsilon}^{P\to\nu}$. Similarly, we write
$F_{n}=F^{P_{n}\to\nu}_{\varepsilon}$ and $F_{0}=F^{P\to\nu}_{\varepsilon}$.
Let
$\nu_{n}=\int\pi_{\varepsilon}^{x}(\psi_{\varepsilon}^{P_{n}\to\nu})\,\mathrm{d}P(x)$.
Under the event $E=\\{\nu_{n}\geq\nu/2\\}$, we have according to Proposition
D.1 and the fact that $\tilde{\psi}_{n}$ minimizes $F_{n}$,

$\begin{split}C\nu_{\min}\mathrm{Var}_{\infty}(\tilde{\psi}_{n}-\tilde{\psi}_{0})&\leq
C\mathrm{Var}_{\nu}(\tilde{\psi}_{n}-\tilde{\psi}_{0})\\\ &\leq
F_{0}(\tilde{\psi}_{n})-F_{0}(\tilde{\psi}_{0})\\\ &\leq
F_{0}(\tilde{\psi}_{n})-F_{n}(\tilde{\psi}_{n})+F_{n}(\tilde{\psi}_{0})-F_{0}(\tilde{\psi}_{0})\\\
&=\int(\Phi_{\varepsilon}(\tilde{\psi}_{n})-\Phi_{\varepsilon}(\tilde{\psi}_{0}))\,\mathrm{d}(P-P_{n})\end{split}$
(66)

Let us bound $\mathbb{P}(E^{c})$. As $\tilde{\psi}_{n}$ is the minimum of
$F_{n}$, we have
$\nu=\int\pi_{\varepsilon}^{x}(\tilde{\psi}_{n})_{j}\,\mathrm{d}P_{n}(x)$ (see
Appendix A). Therefore, we may write
$\nu_{n,j}=\int\pi_{\varepsilon}^{x}(\tilde{\psi}_{n})_{j}\,\mathrm{d}P_{n}(x)+\int\pi_{\varepsilon}^{x}(\tilde{\psi}_{n})_{j}\,\mathrm{d}(P-P_{n})(x)=\nu_{j}+Z_{j}$,
where

$Z_{j}=\int\pi_{\varepsilon}^{x}(\tilde{\psi}_{n})_{j}\,\mathrm{d}(P-P_{n})(x)=\int(\pi_{\varepsilon}^{x}(\tilde{\psi}_{n})_{j}-\pi_{\varepsilon}^{x}(\tilde{\psi}_{0})_{j})\,\mathrm{d}(P-P_{n})(x).$

Note that $\mathrm{Var}_{\infty}(\tilde{\psi}_{n}-\tilde{\psi}_{0})\lesssim
R^{2}$ (see Lemma A.1), so that by Lemma F.1 and Lemma H.3,

$\mathbb{P}(E^{c})\leq\sum_{j=1}^{J}\mathbb{P}(|Z_{j}|>\nu_{j}/2)\leq
J\exp\left(-c\frac{\sqrt{n}q_{\min}}{(\sqrt{J\log(1/\varepsilon)}+\log
n}\right)\lesssim n^{-1},$ (67)

under the condition $\log(1/\varepsilon)\lesssim n/\log(n)$.

For $k\geq 0$, let $a_{k}=2^{k}/\sqrt{n}$ and fix some $p>2$. Let

$B_{a}=\sup_{\mathrm{Var}_{\infty}(\psi-\tilde{\psi}_{0})\leq
a^{2}}\left|\int(\Phi_{\varepsilon}(\psi)-\Phi_{\varepsilon}(\tilde{\psi}_{0}))\,\mathrm{d}(P-P_{n})\right|$

. Assume that $E$ is satisfied and that
$\mathrm{Var}_{\infty}(\tilde{\psi}_{0}-\tilde{\psi}_{n})\in[a^{2},b^{2}]$.
Then, according to (66), it holds that $B_{b}\geq ca^{2}$. Using Markov’s
inequality, Lemma F.1 and Lemma H.3, we bound

$\displaystyle\mathbb{E}\mathrm{Var}_{\infty}(\tilde{\psi}_{n}-\tilde{\psi}_{0})$
$\displaystyle\leq a_{0}^{2}+\sum_{k\geq
0}\mathbb{P}(\mathrm{Var}_{\infty}(\tilde{\psi}_{n}-\tilde{\psi}_{0})\in[a_{k}^{2},a_{k+1}^{2}]\text{
and }E)a_{k+1}^{2}+C\mathbb{P}(E^{c})$ $\displaystyle\lesssim
n^{-1}+\sum_{k\geq 0}\mathbb{P}\left(B_{a_{k+1}}\geq
ca_{k}^{2}\right)a_{k+1}^{2}\lesssim n^{-1}+\sum_{k\geq
0}\frac{\mathbb{E}[B_{a_{k+1}}^{p}]}{a_{k}^{2p}}a_{k+1}^{2}$
$\displaystyle\lesssim n^{-1}+\sum_{k\geq
0}\frac{(2^{k}/n)^{p}}{(4^{k}/n)^{p}}\frac{4^{k+1}}{n}\lesssim
n^{-1}+\sum_{k\geq 0}\frac{2^{2k-pk}}{n}\lesssim n^{-1}.\qed$

######  Proposition F.3.

Under the same assumptions than Proposition F.2, it holds that

$\mathbb{E}\|T_{\varepsilon}^{P_{n}\to\nu}-T_{\varepsilon}^{P\to\nu}\|^{2}_{\infty}\lesssim\varepsilon^{-1}n^{-1}.$
(68)

###### Proof.

Let $Z=\mathrm{Var}_{\infty}(\tilde{\psi}_{n}-\tilde{\psi}_{0})$. Let once
again $a_{k}=2^{k}/\sqrt{n}$ for $k\geq 1$, with $a_{0}=0$. Fix some $p>2$,
with $q=\frac{p}{p-1}$. For $a>0$, let
$D_{a}=\sup_{\mathrm{Var}_{\infty}(\psi-\tilde{\psi}_{0})\leq
a^{2}}\left|\int(\Phi_{\varepsilon}(\psi)-\Phi_{\varepsilon}(\tilde{\psi}_{0}))\,\mathrm{d}(P-P_{n})\right|$.
By Hölder inequality and Markov inequality, we obtain,

$\displaystyle\mathbb{E}\int(\Phi_{\varepsilon}(\tilde{\psi}_{n})-\Phi_{\varepsilon}(\tilde{\psi}_{0}))\,\mathrm{d}(P-P_{n})$
$\displaystyle\qquad\leq\sum_{k\geq
0}\mathbb{E}\left[\mathds{1}\\{Z\in[a_{k}^{2},a_{k+1}^{2}]\\}\sup_{\mathrm{Var}_{\infty}(\psi-\tilde{\psi}_{0})\leq
a_{k+1}^{2}}\int(\Phi_{\varepsilon}(\psi)-\Phi_{\varepsilon}(\tilde{\psi}_{0}))\,\mathrm{d}(P-P_{n})\right]$
$\displaystyle\qquad\leq\mathbb{E}[D_{a_{1}}]+\sum_{k\geq
1}\left(\mathbb{P}(Z\geq
a_{k}^{2})\right)^{1/q}\mathbb{E}\left[D_{a_{k+1}}^{p}\right]^{1/p}$
$\displaystyle\qquad\lesssim n^{-1}+\sum_{k\geq
0}\left(\frac{\mathbb{E}[Z]}{a_{k}^{2}}\right)^{1/q}\frac{2^{k}}{n}\lesssim\sum_{k\geq
0}\frac{2^{k(1-2/q)}}{n}\lesssim 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. ∎

##  Appendix 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 $\Omega=[0,1]^{d}$, and let $y_{0}=(0,1/2,\dots,1/2)$ and
$y_{1}=(1,1/2,\dots,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 $\nu$, which may either be fixed
or may be a random measure independent of $P_{n}$. We let
$\nu=\sum_{j=0,1}\nu_{j}\delta_{y_{j}}$ for $\nu_{0},\nu_{1}\geq\frac{1}{4}$;
this latter condition will hold with overwhelming probability if $\nu$ is an
empirical measure $Q_{n}$ corresponding to $n$ i.i.d. samples from
$Q=\frac{1}{2}\delta_{y_{0}}+\frac{1}{2}\delta_{y_{1}}$. Following [45], we
define the one-nearest neighbor estimator $\hat{T}_{\text{1NN}}$ in this
general context by

$\hat{T}_{\text{1NN}}(x)=\sum_{i=1}^{n}\sum_{j={0,1}}\bm{1}_{V_{i}}(x)(n\hat{\pi}(X_{i},y_{j}))\,,$

where $\hat{\pi}$ is the empirical optimal coupling between $P_{n}$ and $\nu$.

We first examine the structure of the Brenier map $T_{0}=\nabla\varphi_{0}$.
The considerations in Section 2.1.1 imply that

$T_{0}(x)=\begin{cases}y_{0}&\langle e_{1},x\rangle\leq\nu_{0}\\\
y_{1}&\langle e_{1},x\rangle>\nu_{0}\,,\end{cases}$

where $e_{1}$ is the first elementary basis vector. The potential
$\varphi_{0}$ is not differentiable on the separating hyperplane $\langle
e_{1},x\rangle=\nu_{0}$, which has measure $0$ under $P$, but we may
arbitrarily assign points on this hyperplane to $y_{0}$.

Similar arguments imply that the empirical transport plan $\hat{\pi}$ between
$P_{n}$ and $\nu$ has the following property: there exists a (random)
threshold $\tau\in(0,1)$ such that

$\hat{\pi}(x,y_{0})=\begin{cases}1&\langle e_{1},x\rangle<\tau\\\ 0&\langle
e_{1},x\rangle>\tau\,.\end{cases}$

The set $\langle e_{1},x\rangle=\tau$ may not have measure $0$ under $P_{n}$,
and $\hat{\pi}(x,y_{0})$ may take values strictly between $0$ and $1$ on this
set.

The following lemma shows that $\tau$ is close to $\nu_{0}$ with high
probability.

######  Lemma G.1.

For any $t\geq 0$,

$\mathbb{P}\left\\{\tau\geq\nu_{0}+t\right\\}\leq e^{-2nt^{2}}\,.$

###### Proof.

If $\tau\geq\nu_{0}+t$, this implies that $P_{n}(\\{x:\langle
e_{1},x\rangle<\nu_{0}+t\\})\leq\nu_{0}$. On the other hand,
$nP_{n}(\\{x:\langle e_{1},x\rangle<\nu_{0}+t\\}$ is a
$\mathrm{Bin}(n,\nu_{0}+t)$ random variable. The result then follows from
Hoeffding’s inequality [7, Theorem 2.8]. ∎

Let us write $H$ for the halfspace $\\{x:\langle
e_{1},x\rangle\leq\nu_{0}\\}$, and $\hat{H}$ for the halfspace $\\{x:\langle
e_{1},x\rangle\leq\tau\\}$. Let $x$ be any point in $\Omega$ such that $x\in
H$. We are interested in the event that there exists an element
$X_{i}\in\\{X_{1},\dots,X_{n}\\}$ such that a) $x\in V_{i}$ and b)
$X_{i}\in\hat{H}^{c}$. Call this event $\mathcal{E}(x)$. On this event,
$\hat{T}_{\text{1NN}}(x)=y_{1}$ and $T_{0}(x)=y_{0}$, so
$\|\hat{T}_{\text{1NN}}(x)-T_{0}(x)\|^{2}=1$.

We therefore obtain

$\displaystyle\mathbb{E}\|\hat{T}_{\text{1NN}}-T_{0}\|_{L^{2}(P)}^{2}$
$\displaystyle=\mathbb{E}\int\|\hat{T}_{\text{1NN}}(x)-T_{0}(x)\|^{2}\,\mathrm{d}P(x)$
$\displaystyle\geq\mathbb{E}\int_{H}\|\hat{T}_{\text{1NN}}(x)-T_{0}(x)\|^{2}\mathds{1}\\{\mathcal{E}({x})\\}\,\mathrm{d}P(x)$
$\displaystyle\gtrsim\mathbb{E}\int_{H}\mathds{1}\\{\mathcal{E}({x})\\}\,\mathrm{d}P(x)$
$\displaystyle=\int_{H}\mathbb{P}\left\\{\mathcal{E}({x})\right\\}\,\mathrm{d}P(x)\,,$

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

We now lower bound the probability of $\mathcal{E}(x)$. Let us write
$\mathcal{A}_{t}$ for the event that $\tau<\nu_{0}+t$, for $t>0$ to be
specified, and write $H_{t}$ for the halfspace $\\{x:\langle
e_{1},x\rangle\leq\nu_{0}+t\\}$. Given any $x\in H$, write
$\Delta=d(x,H_{t}^{c})$, and let $B$ be a ball of radius $2\Delta$ around $x$,
intersected with $\Omega$.

Denote by $\mathcal{F}(x)$ the event that there are no samples in $V=B\cap
H_{t}$ but there is at least one point in $B\cap H_{t}^{c}$. Then
$\mathcal{F}(x)\cap\mathcal{A}_{t}\subseteq\mathcal{E}(x)$, since on
$\mathcal{F}(x)$ the nearest neighbor to $x$ must be a sample in $H_{t}^{c}$,
and on $\mathcal{A}_{t}$ we have $H_{t}^{c}\subseteq\hat{H}^{c}$.

######  Lemma G.2.

$\mathbb{P}\left\\{\mathcal{F}(x)\cap\mathcal{A}_{t}\right\\}\geq(1-\operatorname{vol}(V))^{n}-(1-\operatorname{vol}(B))^{n}-e^{-2nt^{2}}\,.$

###### Proof.

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

$(1-\operatorname{vol}(V))^{n}=\mathbb{P}\left\\{\mathcal{F}(x)\right\\}+(1-\operatorname{vol}(B))^{n}\,.$

Since $\mathbb{P}\left\\{\mathcal{A}_{t}^{c}\right\\}\leq e^{-2nt^{2}}$, the
claim follows. ∎

We need the following lemma.

######  Lemma G.3.

Assume that $\Delta>0$ and that $d(x,\partial\Omega)\geq 2\Delta$. There exist
positive constants $c_{d,0}<1$ and $c_{d,1}$ such that

$\operatorname{vol}(V)\leq c_{d,0}\operatorname{vol}(B)$ (69)

and

$\operatorname{vol}(B)\geq c_{d,1}\Delta^{d}$ (70)

###### Proof.

This is immediate from a scaling argument: since $d(x,\partial\Omega)\geq
2\Delta$, the set $B$ is a Euclidean ball of radius $2\Delta$, and the set $V$
is a Euclidean ball of radius $2\Delta$ minus a spherical dome cut off by a
hyperplane at distance $\Delta$ from the center. When $\Delta=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,\partial\Omega)\geq 2\Delta$. The
inequalities $(1+x)^{n}\geq 1+nx$ and $e^{x}\leq 1+x+x^{2}$, valid for all
$x\in[-1,0]$ and $n\geq 1$, imply that for any $\delta>0$ there exists a
constant $c_{d,\delta}>0$ such that if $\Delta\leq c_{d,\delta}n^{-1/d}$, then
we will have

$\displaystyle(1-\operatorname{vol}(V))^{n}$ $\displaystyle\geq
1-nc_{d,0}\operatorname{vol}(B)$ (71)
$\displaystyle(1-\operatorname{vol}(B))^{n}$ $\displaystyle\leq
e^{-n\operatorname{vol}(B)}\leq 1-(1-\delta)n\operatorname{vol}(B)$ (72)

Choosing $\delta$ sufficiently small, we obtain the existence of a small
$c_{d,3}>0$ such that if $\Delta\leq c_{d,3}n^{-1/d}$, then

$(1-\operatorname{vol}(V))^{n}-(1-\operatorname{vol}(B))^{n}\geq
C_{d}n\Delta^{d}\,.$

Define $\Delta_{n}=c_{d,4}n^{-1/d}$. Putting it all together, consider the set

$S=\\{x\in H\cap\Omega:\Delta_{n}/2\leq
d(x,H_{t}^{c})\leq\Delta_{n},d(x,\partial\Omega)\geq 2\Delta_{n}\\}\,.$

The above considerations imply that
$\mathbb{P}\left\\{\mathcal{E}(x)\right\\}\geq
C_{d}n(\Delta_{n}/2)^{d}-e^{-2nt^{2}}\geq C_{d}^{\prime}-e^{-2nt^{2}}$ for all
$x\in S$. Choosing $t$ to be a sufficiently large constant multiple of
$n^{-1/2}$, we obtain

$\int_{H}\mathbb{P}\left\\{\mathcal{E}({x})\right\\}\,\mathrm{d}P(x)\geq\int_{S}\mathbb{P}\left\\{\mathcal{E}({x})\right\\}\,\mathrm{d}P(x)\gtrsim_{d}\operatorname{vol}(S)\,.$

Since $t\asymp n^{-1/2}$, we will have that $t\ll\Delta_{n}$ for $n$
sufficiently large (as $d\geq 3$). Therefore, for $n$ large enough, the set
$S$ contains the set

$S^{\prime}=\\{x\in\Omega:\nu_{0}-\Delta_{n}+t\leq\langle
e_{1},x\rangle\leq\nu_{0}-\Delta_{n}/2+t,2\Delta_{n}\leq\langle
e_{j},x\rangle\leq 1-2\Delta_{n}\quad\forall j=2,\dots,d\\}\,.$

Since $\operatorname{vol}(S^{\prime})\gtrsim_{d}\Delta_{n}\gtrsim n^{-1/d}$,
the claim follows.

##  Appendix H Auxiliary lemmas

######  Lemma H.1 (Young’s inequality).

Let $Q_{0},Q_{1}$ be probability measures with $Q_{1}\ll Q_{0}$ and let $f$ be
a function. Then, for $\theta>0$,

$\int
f(\,\mathrm{d}Q_{0}-\,\mathrm{d}Q_{1})\leq\frac{\theta\mathrm{Var}_{Q_{0}}(f)}{2}+\frac{\chi^{2}(Q_{1}\|Q_{0})}{2\theta}.$
(73)

###### Proof.

Recall Young’s inequality: for $a,b\in\mathbb{R}$,
$ab\leq\frac{a^{2}}{2}+\frac{b^{2}}{2}$. As the left-hand side is invariant by
translation, we may assume without loss of generality that $\int
f\,\mathrm{d}Q_{0}=0$, so that $\mathrm{Var}_{Q_{0}}(f)=\int
f^{2}\,\mathrm{d}Q_{0}$. We write

$\displaystyle\int f(\,\mathrm{d}Q_{0}-\,\mathrm{d}Q_{1})$
$\displaystyle=\int(\sqrt{\theta}f)\frac{\left(1-\frac{\,\mathrm{d}Q_{1}}{\,\mathrm{d}Q_{0}}\right)}{\sqrt{\theta}}\,\mathrm{d}Q_{0}\leq\frac{\theta}{2}\int
f^{2}\,\mathrm{d}Q_{0}+\frac{1}{2\theta}\int\left(1-\frac{\,\mathrm{d}Q_{1}}{\,\mathrm{d}Q_{0}}\right)^{2}\,\mathrm{d}Q_{0}$
$\displaystyle=\frac{\theta\mathrm{Var}_{Q_{0}}(f)}{2}+\frac{\chi^{2}(Q_{1}\|Q_{0})}{2\theta}.\qed$

######  Lemma H.2 (Expectation of empirical $\chi^{2}$-divergence).

Let $Q=\sum_{j=1}^{J}q_{j}\delta_{y_{j}}$ be a discrete measure supported on
$J$ atoms, and let $Q_{n}$ denote its empirical measure, consisting of $n$
i.i.d. samples. Then,

$\displaystyle\mathbb{E}[\chi^{2}(Q_{n}\|Q)]=\frac{J-1}{n}\,.$ (74)

###### Proof.

We can write $Q_{n}=\sum_{j=1}^{J}\hat{q}_{j}\delta_{y_{j}}$, where
$\hat{q}_{j}$ is a binomial random variable with parameters $n$ and $q_{j}$.
We obtain

$\displaystyle\chi^{2}(Q_{n}\|Q)=\sum_{j=1}^{J}\frac{(\hat{q}_{j}-q_{j})^{2}}{q_{j}}\,.$

Taking expectations, our bound reads

$\displaystyle\mathbb{E}[\chi^{2}(Q_{n}\|Q)]=\sum_{j=1}^{J}\frac{\text{Var}(\hat{q}_{j})}{q_{j}}=\sum_{j=1}^{J}\frac{q_{j}(1-q_{j})}{nq_{j}}=\frac{J-1}{n}.$

∎

######  Lemma H.3 (Control of suprema of empirical processes).

Let $X_{1},\dots,X_{n}$ be an i.i.d. sample from some probability measure $P$
on $\mathbb{R}^{d}$, with $P_{n}$ the associated empirical measure. Consider
$\mathcal{F}$ a class of functions $\mathbb{R}^{d}\to\mathbb{R}$ with
$\|f\|_{\infty}\leq A$ for all $f\in\mathcal{F}$. For $u>0$, let $N(u)$ be the
$u$-covering numbers of $\mathcal{F}$, that is the minimal number of balls of
radius $u$ for the $\|\cdot\|_{\infty}$-metric required to cover
$\mathcal{F}$. Then,

$\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left|\int
f\,\mathrm{d}(P_{n}-P)\right|\right]\leq\frac{C_{0}}{\sqrt{n}}\int_{0}^{C_{1}A}\sqrt{\log
2N(u)}\,\mathrm{d}u=:\frac{I}{\sqrt{n}}$ (75)

for two positive absolute constants $C_{0}$ and $C_{1}$. Furthermore, for all
$t>0$,

$\mathbb{P}\left(\sup_{f\in\mathcal{F}}\left|\int
f\,\mathrm{d}(P_{n}-P)\right|>t\right)\leq\exp\left(-\frac{C_{2}\sqrt{n}t}{I+A\log
n}\right),$ (76)

for some positive absolute constant $C_{2}$. Eventually, for all $p\geq 2$,

$\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left|\int
f\,\mathrm{d}(P_{n}-P)\right|^{p}\right]^{1/p}\leq C_{p}\frac{I+A}{\sqrt{n}}.$
(77)

###### Proof.

See [65, Theorem 2.14.2 and Theorem 2.14.5]. ∎

## References

  * AHA [98] Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov.  Minkowski-type theorems and least-squares clustering.  Algorithmica, 20(1):61–76, 1998.
  * ANWS [22] Jason M Altschuler, Jonathan Niles-Weed, and Austin J Stromme.  Asymptotics for semidiscrete entropic optimal transport.  SIAM Journal on Mathematical Analysis, 54(2):1718–1741, 2022.
  * BCR+ [22] Bradley CA Brown, Anthony L Caterini, Brendan Leigh Ross, Jesse C Cresswell, and Gabriel Loaiza-Ganem.  The union of manifolds hypothesis and its implications for deep generative modelling.  arXiv preprint arXiv:2207.02862, 2022.
  * BG [99] S. G. Bobkov and F. Götze.  Exponential integrability and transportation cost related to logarithmic Sobolev inequalities.  J. Funct. Anal., 163(1):1–28, 1999.
  * BGN [22] Espen Bernton, Promit Ghosal, and Marcel Nutz.  Entropic optimal transport: Geometry and large deviations.  Duke Mathematical Journal, 171(16):3363–3400, 2022.
  * BKC [22] Charlotte Bunne, Andreas Krause, and Marco Cuturi.  Supervised training of conditional Monge maps.  arXiv preprint arXiv:2206.14262, 2022.
  * BLM [13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration inequalities.  Oxford University Press, Oxford, 2013.  A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
  * Bre [91] Yann Brenier.  Polar factorization and monotone rearrangement of vector-valued functions.  Communications on pure and applied mathematics, 44(4):375–417, 1991\.
  * BSG+ [21] Charlotte Bunne, Stefan G Stark, Gabriele Gut, Jacobo Sarabia del Castillo, Kjong-Van Lehmann, Lucas Pelkmans, Andreas Krause, and Gunnar Rätsch.  Learning single-cell perturbation responses using neural optimal transport.  bioRxiv, 2021.
  * CAN [22] Ricky T. Q. Chen, Brandon Amos, and Maximilian Nickel.  Semi-discrete normalizing flows through differentiable tessellation.  In Advances in Neural Information Processing Systems, 2022.
  * CCG [16] Guillaume Carlier, Victor Chernozhukov, and Alfred Galichon.  Vector quantile regression: an optimal transport approach.  The Annals of Statistics, 44(3):1165–1192, 2016.
  * CDPS [17] Guillaume Carlier, Vincent Duval, Gabriel Peyré, and Bernhard Schmitzer.  Convergence of entropic schemes for optimal transport and gradient flows.  SIAM Journal on Mathematical Analysis, 49(2):1385–1418, 2017.
  * CGHH [17] Victor Chernozhukov, Alfred Galichon, Marc Hallin, and Marc Henry.  Monge–Kantorovich depth, quantiles, ranks and signs.  The Annals of Statistics, 45(1):223–256, 2017.
  * Con [22] Giovanni Conforti.  Weak semiconvexity estimates for Schrödinger potentials and logarithmic Sobolev inequality for Schrödinger bridges.  arXiv preprint arXiv:2301.00083, 2022.
  * CP [22] Sinho Chewi and Aram-Alexandre Pooladian.  An entropic generalization of Caffarelli’s contraction theorem via covariance inequalities.  arXiv preprint arXiv:2203.04954, 2022.
  * CRL+ [20] Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré.  Faster Wasserstein distance estimation with the Sinkhorn divergence.  Advances in Neural Information Processing Systems, 33, 2020.
  * Csi [75] I. Csiszár.  $I$-divergence geometry of probability distributions and minimization problems.  Ann. Probability, 3:146–158, 1975.
  * CT [21] Giovanni Conforti and Luca Tamanini.  A formula for the time derivative of the entropic cost and applications.  Journal of Functional Analysis, 280(11):108964, 2021.
  * Cut [13] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * dBGSL [22] Eustasio del Barrio, Alberto González-Sanz, and Jean-Michel Loubes.  Central limit theorems for semidiscrete Wasserstein distances.  arXiv preprint arXiv:2202.06380, 2022.
  * dBGSLNW [22] Eustasio del Barrio, Alberto Gonzalez-Sanz, Jean-Michel Loubes, and Jonathan Niles-Weed.  An improved central limit theorem and fast convergence rates for entropic transportation costs.  arXiv preprint arXiv:2204.09105, 2022.
  * dBL [19] Eustasio del Barrio and Jean-Michel Loubes.  Central limit theorems for empirical transportation cost in general dimension.  Ann. Probab., 47(2):926–951, 2019.
  * DBTHD [21] Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet.  Diffusion Schrödinger bridge with applications to score-based generative modeling.  Advances in Neural Information Processing Systems, 34:17695–17709, 2021.
  * Del [22] Alex Delalande.  Nearly tight convergence bounds for semi-discrete entropic optimal transport.  In International Conference on Artificial Intelligence and Statistics, pages 1619–1642. PMLR, 2022.
  * DGS [21] Nabarun Deb, Promit Ghosal, and Bodhisattva Sen.  Rates of estimation of optimal transport maps using plug-in estimators via barycentric projections.  Advances in Neural Information Processing Systems, 34:29736–29753, 2021.
  * DNWP [22] Vincent Divol, Jonathan Niles-Weed, and Aram-Alexandre Pooladian.  Optimal transport map estimation in general function spaces.  arXiv preprint arXiv:2212.03722, 2022.
  * DSSS [22] Pınar Demetçi, Rebecca Santorella, Björn Sandstede, and Ritambhara Singh.  Unsupervised integration of single-cell multi-omics datasets with disproportionate cell-type representation.  In International Conference on Research in Computational Molecular Biology, pages 3–19. Springer, 2022.
  * FCVP [17] Jean Feydy, Benjamin Charlier, François-Xavier Vialard, and Gabriel Peyré.  Optimal transport for diffeomorphic registration.  In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 291–299. Springer, 2017.
  * FGOP [20] Chris Finlay, Augusto Gerolin, Adam M Oberman, and Aram-Alexandre Pooladian.  Learning normalizing flows from Entropy-Kantorovich potentials.  arXiv preprint arXiv:2006.06033, 2020.
  * FHN+ [19] Aden Forrow, Jan-Christian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed.  Statistical optimal transport via factored couplings.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2454–2465. PMLR, 2019.
  * GCB+ [19] Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré.  Sample complexity of Sinkhorn divergences.  In The 22nd international conference on artificial intelligence and statistics, pages 1574–1583. PMLR, 2019.
  * Gen [19] Aude Genevay.  Entropy-regularized optimal transport for machine learning.  PhD thesis, Paris Sciences et Lettres (ComUE), 2019.
  * GKRS [22] Ziv Goldfeld, Kengo Kato, Gabriel Rioux, and Ritwik Sadhu.  Limit theorems for entropic optimal transport maps and the Sinkhorn divergence.  arXiv preprint arXiv:2207.08683, 2022.
  * GL [07] Siegfried Graf and Harald Luschgy.  Foundations of quantization for probability distributions.  Springer, 2007.
  * GNB [22] Promit Ghosal, Marcel Nutz, and Espen Bernton.  Stability of entropic optimal transport and Schrödinger bridges.  Journal of Functional Analysis, 283(9):109622, 2022.
  * GPC [18] Aude Genevay, Gabriel Peyré, and Marco Cuturi.  Learning generative models with Sinkhorn divergences.  In International Conference on Artificial Intelligence and Statistics, pages 1608–1617. PMLR, 2018.
  * GS [22] Promit Ghosal and Bodhisattva Sen.  Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing.  Ann. Statist., 50(2):1012–1037, 2022.
  * GSLNW [22] Alberto Gonzalez-Sanz, Jean-Michel Loubes, and Jonathan Niles-Weed.  Weak limits of entropy regularized optimal transport; potentials, plans and divergences.  arXiv preprint arXiv:2207.07427, 2022.
  * GX [21] Florian Gunsilius and Yuliang Xu.  Matching for causal effects via multimarginal optimal transport.  arXiv preprint arXiv:2112.04398, 2021.
  * HR [21] Jan-Christian Hütter and Philippe Rigollet.  Minimax estimation of smooth optimal transport maps.  The Annals of Statistics, 49(2):1166–1194, 2021.
  * HSM [22] Shayan Hundrieser, Thomas Staudt, and Axel Munk.  Empirical optimal transport between different measures adapts to lower complexity.  arXiv preprint arXiv:2202.10434, 2022.
  * Kan [42] L. Kantorovitch.  On the translocation of masses.  C. R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942.
  * LBG+ [22] Frederike Lübeck, Charlotte Bunne, Gabriele Gut, Jacobo Sarabia del Castillo, Lucas Pelkmans, and David Alvarez-Melis.  Neural unbalanced optimal transport via cycle-consistent semi-couplings.  arXiv preprint arXiv:2209.15621, 2022.
  * Léo [12] Christian Léonard.  From the Schrödinger problem to the Monge–Kantorovich problem.  Journal of Functional Analysis, 262(4):1879–1920, 2012.
  * MBNWW [21] Tudor Manole, Sivaraman Balakrishnan, Jonathan Niles-Weed, and Larry Wasserman.  Plugin estimation of smooth optimal transport maps.  arXiv preprint arXiv:2107.12364, 2021.
  * MG [20] Simone Di Marino and Augusto Gerolin.  An optimal transport approach for the Schrödinger bridge problem and convergence of Sinkhorn algorithm.  Journal of Scientific Computing, 85(2):1–28, 2020.
  * MNW [19] Gonzalo Mena and Jonathan Niles-Weed.  Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem.  Advances in Neural Information Processing Systems, 32, 2019.
  * MSF+ [21] Noa Moriel, Enes Senel, Nir Friedman, Nikolaus Rajewsky, Nikos Karaiskos, and Mor Nitzan.  Novosparc: flexible spatial reconstruction of single-cell gene expression with optimal transport.  Nature Protocols, 16(9):4177–4200, 2021.
  * MSS [21] Quentin Mérigot, Filippo Santambrogio, and Clément Sarrazin.  Non-asymptotic convergence bounds for Wasserstein approximation using point clouds.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12810–12821. Curran Associates, Inc., 2021.
  * MVB+ [21] Boris Muzellec, Adrien Vacher, Francis Bach, François-Xavier Vialard, and Alessandro Rudi.  Near-optimal estimation of smooth transport maps with kernel sums-of-squares.  arXiv preprint arXiv:2112.01907, 2021.
  * NW [22] Marcel Nutz and Johannes Wiesel.  Entropic optimal transport: Convergence of potentials.  Probability Theory and Related Fields, 184(1-2):401–424, 2022.
  * Pal [19] Soumik Pal.  On the difference between entropic cost and the optimal transport cost.  arXiv preprint arXiv:1905.12206, 2019.
  * PC [19] Gabriel Peyré and Marco Cuturi.  Computational optimal transport.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * PCNW [22] Aram-Alexandre Pooladian, Marco Cuturi, and Jonathan Niles-Weed.  Debiaser beware: Pitfalls of centering regularized transport maps.  arXiv preprint arXiv:2202.08919, 2022.
  * PNW [21] Aram-Alexandre Pooladian and Jonathan Niles-Weed.  Entropic estimation of optimal transport maps.  arXiv preprint arXiv:2109.12004, 2021.
  * RS [22] Philippe Rigollet and Austin J Stromme.  On the sample complexity of entropic optimal transport.  arXiv preprint arXiv:2206.13472, 2022.
  * San [15] Filippo Santambrogio.  Optimal transport for applied mathematicians.  Birkäuser, NY, 55(58-63):94, 2015.
  * SDF+ [18] Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel.  Large-scale optimal transport and mapping estimation.  In International Conference on Learning Representations, 2018.
  * SDGP+ [15] Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas.  Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains.  ACM Transactions on Graphics (TOG), 34(4):66, 2015.
  * SPKS [16] Justin Solomon, Gabriel Peyré, Vladimir G. Kim, and Suvrit Sra.  Entropic metric alignment for correspondence problems.  ACM Trans. Graph., 35(4):72:1–72:13, 2016.
  * SST+ [19] Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, et al.  Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming.  Cell, 176(4):928–943, 2019.
  * TGR [21] William Torous, Florian Gunsilius, and Philippe Rigollet.  An optimal transport approach to causal inference.  arXiv preprint arXiv:2108.05858, 2021.
  * Ver [18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge University Press, 2018.
  * Vil [09] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer, 2009.
  * VW [96] Aad W Vaart and Jon A Wellner.  Weak convergence and empirical processes with applications to statistics.  In Weak convergence and empirical processes, pages 16–28. Springer, 1996.
  * Wai [19] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.
  * YDV+ [20] Karren Dai Yang, Karthik Damodaran, Saradha Venkatachalapathy, Ali C Soylemezoglu, GV Shivashankar, and Caroline Uhler.  Predicting cell lineages using autoencoders and optimal transport.  PLoS computational biology, 16(4):e1007828, 2020.