# Minimum intrinsic dimension scaling for entropic optimal transport

Austin J. Stromme Department of EECS at the Massachusetts Institute of
Technology<EMAIL_ADDRESS>
###### Abstract

Motivated by the manifold hypothesis, which states that data with a high
extrinsic dimension may yet have a low intrinsic dimension, we develop refined
statistical bounds for entropic optimal transport that are sensitive to the
intrinsic dimension of the data. Our bounds involve a robust notion of
intrinsic dimension, measured at only a single distance scale depending on the
regularization parameter, and show that it is only the minimum of these
single-scale intrinsic dimensions which governs the rate of convergence. We
call this the Minimum Intrinsic Dimension scaling (MID scaling) phenomenon,
and establish MID scaling with no assumptions on the data distributions so
long as the cost is bounded and Lipschitz, and for various entropic optimal
transport quantities beyond just values, with stronger analogs when one
distribution is supported on a manifold. Our results significantly advance the
theoretical state of the art by showing that MID scaling is a generic
phenomenon, and provide the first rigorous interpretation of the statistical
effect of entropic regularization as a distance scale.

##  1 Introduction

Optimal transport (OT) is a powerful paradigm for comparing probability
distributions based on a minimum-energy criterion, and has recently been
employed throughout applied science, including statistics, computer science,
biology and beyond [Vil08, San15, PC18, PZ19, SST+19]. Rather than comparing
distributions pointwise, OT searches for the most efficient way to transform
one into the other, and thus gives practitioners a geometrically meaningful
method of contrasting and interpolating data that can be represented as
probability distributions. For probability measures $\mu,\nu$ on
$\mathbb{R}^{d}$ the OT problem, with respect to the squared Euclidean cost
$\|\cdot\|^{2}$, is defined as

$W_{2}^{2}(\mu,\nu):=\min_{\pi\in\Pi(\mu,\nu)}\int\|x-y\|^{2}\mathrm{d}\pi(x,y),$
(1.1)

where $\Pi(\mu,\nu)$ denotes the set of probability distributions $\pi$ on
$\mathbb{R}^{d}\times\mathbb{R}^{d}$ which couple $\mu$ to $\nu$, namely such
that their marginal on the first $d$ coordinates is $\mu$ and their marginal
on the last $d$ coordinates is $\nu$. The fundamental theorem of OT guarantees
that, so long as $\mu,\nu$ have finite second moments, there is a solution to
(1.1); moreover if $\mu$ has a density with respect to the Lebesgue measure,
there is a unique minimizer which is supported on the graph of a deterministic
map [Vil08]. For many applications, such as domain adaptation [FCTR16] or
cellular biology [SST+19], it is the coupling minimizing (1.1), rather than
the cost $W_{2}^{2}(\mu,\nu)$ itself, which is of greatest interest.

#### Entropic optimal transport.

When discretized, the OT problem (1.1) becomes a linear program (LP) with two
equality constraints. Although this problem can be feasibly solved at moderate
scale with specialized LP solvers which have computational complexity scaling
cubically in the support size [DGP+20], in practice, OT is most often
approximated with an entropic regularization term [Cut13]. This entropically
regularized problem is then solved with a simple iterative rounding algorithm
known as Sinkhorn’s algorithm [Sin64, SK67], and is preferred for its
quadratic scaling in the support size, simplicity, and parallelizability. The
entropically regularized OT (entropic OT) problem is defined, for a
regularization parameter $\varepsilon>0$, as

$S_{\varepsilon}(\mu,\nu):=\min_{\pi\in\Pi(\mu,\nu)}\int\|x-y\|^{2}\mathrm{d}\pi(x,y)+\varepsilon\operatorname{KL}(\pi\,\|\,\mu\otimes\nu),$
(1.2)

where $\mu\otimes\nu$ denotes the joint law of $(x,y)$ when $x\sim\mu$ and
$y\sim\nu$ are independent, and the Kullback–Leibler divergence is defined as

$\operatorname{KL}(P\,\|\,Q):=\begin{cases}\int\ln\big{(}\frac{\mathrm{d}P}{\mathrm{d}Q}(x)\big{)}\mathrm{d}P(x)&P\ll
Q,\\\ \infty&P\not\ll Q,\end{cases}$

and the notation $P\ll Q$ means $P$ is absolutely continuous with respect to
$Q$.

###  1.1 Statistical aspects of (entropic) OT

Unfortunately, the un-regularized OT problem (1.1) is known to suffer from a
statistical curse of dimensionality. To describe this barrier, consider the
practical situation in which one does not have access to the entire
distributions $\mu,\nu$, and instead only has access to iid samples of size
$n$ from each distribution, which we write as
$\mathcal{X}:=(x_{1},\ldots,x_{n})\sim\mu^{\otimes n}$ and
$\mathcal{Y}:=(y_{1},\ldots,y_{n})\sim\nu^{\otimes n}$. Let $\hat{\mu}$ and
$\hat{\nu}$ denote the empirical measures supported on $\mathcal{X}$ and
$\mathcal{Y}$, respectively, namely

$\hat{\mu}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}\quad\quad\textrm{ and
}\quad\quad\hat{\nu}:=\frac{1}{n}\sum_{j=1}^{n}\delta_{y_{j}}.$

Given the empirical measures $\hat{\mu},\hat{\nu}$, the most natural way to
estimate the population quantity $W_{2}^{2}(\mu,\nu)$ is with the plug-in
estimator $W_{2}^{2}(\hat{\mu},\hat{\nu})$. The discrepancy between the
empirical OT value and its population counterpart is an old and well-studied
area, and it has long been understood that rates like $n^{-2/d}$ are typical –
for instance, if $d\geqslant 5$, and $\mu,\nu$ are absolutely continuous with
respect to the Lebesgue measure on $[0,1]^{d}$ [Dud69, MNW21]. It is natural
to wonder whether these rates can be improved with other estimators, but it
was recently shown they are essentially un-improvable, both for OT value
estimation [NWR22, MBNWW21] and OT map estimation [HR19].

#### Statistical entropic OT.

Motivated by its computational benefits and corresponding prevalence in
practice, as well as the curse of dimensionality for its un-regularized
counterpart, a line of recent work has endeavored to understand the
statistical consequences of entropic regularization [LSPC19, GCB+19, MNW19,
RS22, dBGSLNW22]. This work has shown that the entropic OT problem (1.2)
offers significantly improved statistical performance, essentially
transferring the curse of dimensionality from the sample size $n$ to the
regularization parameter $\varepsilon$; the following result describes the
current state of the art when the measures are bounded and $\varepsilon$ is
small.

######  Theorem 1 ([GCB+19, MNW19]).

Suppose $\mu,\nu$ are probability measures on $\mathbb{R}^{d}$ with support
contained in the unit ball $B(0,1)$. Then for a constant $C_{d}$ depending
only on the dimension $d$,

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\leqslant
C_{d}\cdot\frac{1+\varepsilon^{-\lfloor d/2\rfloor}}{\sqrt{n}},$

where the expectation is taken over the iid samples
$\mathcal{X}\sim\mu^{\otimes n},\mathcal{Y}\sim\nu^{\otimes n}$.

By giving an explicit trade-off between regularization and statistical error,
this result offers a strong and flexible description of the performance of
entropic OT in practice. In this work, we build on Theorem 1 and develop a
refined theory of the statistical behavior of entropic OT.

###  1.2 Effective statistical dimension of entropic OT

To describe our refinements, observe that the estimate in Theorem 1 is
extrinsic in the sense that the dimension $d$ is appearing because the ambient
space is $\mathbb{R}^{d}$, rather than anything to do with the intrinsic
dimensions of $\mu$ and $\nu$. This extrinsic dimension dependence is
fundamental to the proof, and can be very pessimistic. For a toy example,
suppose $\mu$ and $\nu$ are supported on the same $k$-dimensional hyperplane
in $\mathbb{R}^{d}$: then Theorem 1 itself implies that the statistical rate
has the potentially much milder dependence $\varepsilon^{-\lfloor k/2\rfloor}$
on the regularization parameter $\varepsilon$. In such a case, we can say that
$\mu,\nu$ have extrinsic dimension $d$ yet have intrinsic dimension (at most)
$k$. Well beyond toy settings, the widely believed manifold hypothesis states
that natural data with a high extrinsic dimension is typically near to or on a
low-dimensional manifold embedded in Euclidean space, and so has low intrinsic
dimension [FMN16, BGC17]. Given the ubiquity of entropic OT in practice, it is
therefore of major interest to determine the effective statistical dimension
of entropic OT, and identify how it relates to the extrinsic dimension $d$ as
well as the intrinsic dimensions of $\mu$ and $\nu$. In this work, we thus
study the following question:

Suppose $\mu$ and $\nu$ are supported on $\mathbb{R}^{d}$, yet have
(informally speaking) intrinsic dimensions $d_{\mu}$ and $d_{\nu}$. How does
the statistical rate of convergence of entropic OT depend on $d,d_{\mu}$, and
$d_{\nu}$?

Our results will measure intrinsic dimension through the covering numbers of
the supports of $\mu$ and $\nu$. To introduce covering numbers, write the
closed ball centered at $z_{0}\in\mathbb{R}^{d}$ with radius $r>0$ as

$B^{\rm cl}(z_{0},r):=\big{\\{}z\in\mathbb{R}^{d}\colon\|z-z_{0}\|\leqslant
r\big{\\}}.$

Then the covering number of a set $A\subset\mathbb{R}^{d}$ at scale $\delta>0$
is defined as

$\mathcal{N}(A,\|\cdot\|,\delta):=\min\Big{\\{}K\in\mathbb{N}_{>0}\,\,\Big{|}\,\,\exists
z_{1},\ldots
z_{K}\in\mathbb{R}^{d}\,\,\colon\,\,A\subset\bigcup_{k=1}^{K}B^{\rm
cl}(z_{k},\delta)\Big{\\}}.$ (1.3)

It will be convenient to define

$\mathcal{N}(\mu,\delta):=\mathcal{N}(\operatorname{supp}(\mu),\|\cdot\|,\delta),\quad\quad\mathcal{N}(\nu,\delta):=\mathcal{N}(\operatorname{supp}(\nu),\|\cdot\|,\delta),\quad\quad\delta>0.$

#### Contributions.

Using this notation, we can give our answer to the above question:

MID scaling: the statistical rate of convergence of entropic OT can be upper
bounded by quantities whose dimension-dependence is purely contained within
the minimum covering number at scale $\varepsilon$, namely
$\mathcal{N}(\mu,\varepsilon)\land\mathcal{N}(\nu,\varepsilon)$.

We call this the minimum intrinsic dimension scaling (MID scaling) phenomenon.
We emphasize that the MID scaling phenomenon encapsulates two related yet
distinct phenomena:

  1. 1.

Minimum: only the minimum of the intrinsic dimensions governs the convergence

  2. 2.

Intrinsic Dimension: the dimension-dependence is intrinsic to $\mu$ and $\nu$,
and in fact is intrinsic at a single distance scale depending on the
regularization parameter.

As we elaborate on in section 3, the MID scaling phenomenon provides a strong
statistical justification for entropic OT in the context of the manifold
hypothesis. It shows that distributions with support which may not be smooth
or even locally low-dimensional can still have significantly improved
dimension-dependence in their statistical rates, and clearly describes the
statistical role of the regularization parameter $\varepsilon$ as a distance
scale. Moreover, it identifies the surprising fact that the dimension-
dependence of entropic OT is driven by the lower-dimensional (in this single-
scale sense) distribution.

The above statement of MID scaling is in the setting of Theorem 1, but our
main results establish MID scaling more generally for bounded, Lipschitz
costs, and for entropic OT quantities beyond values, including maps and
densities. As our main results in this setting, we prove MID scaling for
entropic OT values in Theorem 2, for entropic OT maps in empirical norms in
Theorem 7, and for entropic OT densities in empirical norms in Theorem 8.
Under the additional assumption that one distribution is supported on an
embedded manifold, we show that MID scaling also holds for entropic dual
potentials with fast, population norm convergence in Theorem 9, and apply this
result to prove stronger analogs of the previous results on value, map, and
density estimation.

#### Organization of the paper.

We conclude this section with a discussion of related work and a summary of
our notation. In section 2, we state our assumption on the cost function and
give background and more notation for the entropic OT problem. In section 3,
we state our main results and give examples and discussion. In section 4, we
describe some preliminary observations that form the foundation of our
approach. In section 5, we prove our main results on MID scaling with a
thorough exposition of our proof strategy in the case of value estimation. In
section 6, we prove our main results in the case where one distribution is
supported on an embedded manifold. In Appendix A, we collect some background
on embedded manifolds that we use in section 6, and in Appendix B we include
some deferred proofs.

#### Related work.

Taken as a whole, our results provide strong evidence of the MID scaling
phenomenon for entropic OT. In fact, there is additional evidence for MID
scaling and related phenomena in the literature. Recent work studied the
continuous to discrete case, and established that entropic OT maps achieve
dimension-free rates of convergence, consistent with MID scaling [PDNW23]. And
in the un-regularized setting, a similar phenomenon was recently established
for value estimation, where it was dubbed “lower complexity adaptation”
[HSM22]. The lower complexity adaptation phenomenon also states that the
minimum of the intrinsic dimensions of $\mu$ and $\nu$ dictates the rate of
convergence of un-regularized OT, but their notion of intrinsic dimension is
different from ours. Indeed, as is common in the un-regularized literature,
the intrinsic dimensions $d_{\mu}$ and $d_{\nu}$ in lower complexity
adaptation are defined using the covering numbers at many distance scales, and
so are distinct from the single-scale intrinsic dimensions in MID scaling.
Also, their results require some structural assumptions, whereas our results
show that MID scaling in the entropic setting is quite generic. In light of
these results, it is natural to expect that the minimum part of MID scaling
holds in greater generality, potentially including un-regularized maps and
plans, alternate forms of regularization, and Gromov-Wasserstein distances.

To the best of our knowledge, there is only one other work which considers the
sample complexity of regularized OT and intrinsic dimension [BEZ22]. Those
results apply to more general forms of regularization, but are only for value
estimation and incur worse $n$ dependence without identifying MID scaling. As
we discuss in detail in section 5, our technical approach is an intrinsic
dimension-sensitive refinement of [RS22] where fully dimension-free bounds
were established for entropic OT values, maps, and densities, but with
exponential factors in $1/\varepsilon$. Other works have proven convergence of
the dual potentials [LSPC19], used entropic OT quantities as computationally
efficient estimators for their un-regularized counterparts [CRL+20, PNW21],
considered the convergence of entropic OT maps [MWMA21, WMMA23], and studied
the sample complexity of entropically regularized Gromov-Wasserstein distances
[ZGMS22]. Significant recent effort has been devoted to developing central
limit theorems for entropic OT [BCP19, MNW19, KTM20, dBGSLNW22, GKRS22,
GSLNW22, GSH23].

Regarding the provenance of Theorem 1, we remark that it was originally proven
for smooth, Lipschitz costs beyond $\ell_{2}^{2}$, but with an exponential
dependence on $1/\varepsilon$ [GCB+19]. The follow-up work [MNW19] showed how
to remove this exponential factor in the compactly supported case that we
study here, but primarily concentrated on extending Theorem 1 to un-bounded
distributions.

Finally, our work can be seen as an entropic analog to the long line of work
on the convergence of the un-regularized OT problem, which dates back to
Dudley [Dud69] and encompasses precise asymptotics [DY95] as well as finer
behavior in lower dimensions [AKT84, LS86]. In fact, the analysis of un-
regularized OT is naturally sensitive to intrinsic dimension, at least when
intrinsic dimension is measured through covering numbers at many scales
[Dud69, BLG14, WB19]. The discrepancy between Theorem 1 and the natural
appearance of intrinsic dimension in the un-regularized OT problem provides
part of the motivation for this work. More discussion of the similarities and
differences between this line of work and our results is provided in section
3.

#### Notation.

Given $a,b\in\mathbb{R}$, we write the minimum $a\land b:=\min(a,b)$, and the
maximum $a\lor b:=\max(a,b)$. For a non-negative integer
$K\in\mathbb{N}_{>0}$, we write $[K]=\\{1\ldots,K\\}$. We always work with
Borel probability distributions. Given probability distributions $P,Q$ on
$\mathbb{R}^{d}$, we denote their trivial coupling $P\otimes Q$, which is
uniquely defined by taking Borel sets $A,B\subset\mathbb{R}^{d}$ to $(P\otimes
Q)(A\times B):=P(A)Q(B)$. The support of $P$ is denoted
$\operatorname{supp}(P)$, and is defined to be the set of all points
$x\in\mathbb{R}^{d}$ such that $P$ assigns positive value to all open sets
containing $x$. The $\ell_{2}$ Euclidean norm is always written $\|\cdot\|$,
without a subscript. Given a Borel measurable
$\alpha\colon\mathbb{R}^{d}\to\mathbb{R}^{k}$ and $p\in[1,\infty)$, we define
the $L^{p}(P)$ norm as

$\|\alpha\|_{L^{p}(P)}:=\Big{(}\int\|\alpha(x)\|^{p}\mathrm{d}P(x)\Big{)}^{1/p}.$

The sup norm $\|\alpha\|_{L^{\infty}(P)}$ is defined to be the essential
supremum of $\|\alpha\|$ with respect to $P$. For a Borel measurable
$\beta\colon\mathbb{R}^{d}\to\mathbb{R}$, we will variously write

$\int\beta(x)\mathrm{d}P(x)=\mathbb{E}_{P}[\beta]=P(\beta).$

We will also write

$\operatorname{Var}_{P}(\beta):=\mathbb{E}_{P}[(\beta-\mathbb{E}_{P}[\beta])^{2}].$

The notation $u\lesssim v$ indicates $u\leqslant Cv$ for constant $C$; whether
the constant $C$ is numerical or problem-dependent is a matter of context. The
suppressed constants in our main results on MID scaling, described in sections
3.1 and 3.2 are numerical, while the suppressed constants for our results on
embedded manifolds, described in section 3.3, depend on the low-dimensional
distribution.

Given a metric $\operatorname{dist}_{N}$ on a set $N\subset\mathbb{R}^{d}$, we
will write the $\operatorname{dist}_{N}$-ball of radius $r$ around $z_{0}\in
N$ as

$B_{\operatorname{dist}_{N}}(z_{0},r):=\\{z\in
N\colon\operatorname{dist}_{N}(z,z_{0})<r\\}.$

If $\operatorname{dist}_{N}=\|\cdot\|$ and $N=\mathbb{R}^{d}$, we simply write
$B(z_{0},r)$. The closed ball is written

$B_{\operatorname{dist}_{N}}^{\rm cl}(z_{0},r):=\\{z\in
N\colon\operatorname{dist}_{N}(z,z_{0})\leqslant r\\},$

and again, if $\operatorname{dist}_{N}=\|\cdot\|$ and $N=\mathbb{R}^{d}$, we
simply write $B^{\rm cl}(z_{0},r)$.

Throughout, we will assume that $\mu,\nu$ are probability measures on
$\mathbb{R}^{d}$, and we have iid samples
$\mathcal{X}:=(x_{1},\ldots,x_{n})\sim\mu^{\otimes n}$ and
$\mathcal{Y}:=(y_{1},\ldots,y_{n})\sim\nu^{\otimes n}$. Expectations
$\mathbb{E}$ without a subscript will always refer to integration over both of
these samples.

##  2 Assumptions and background on entropic OT

In this section, we state our assumption on the cost function, and then
establish important notation while reviewing duality for the entropic OT
problem.

###  2.1 Assumptions on cost

Our results are most naturally stated for bounded, Lipschitz costs rather than
the squared Euclidean cost $\|\cdot\|^{2}$ and so we will work at this level
of generality throughout the remainder of the paper. We make the following
formal assumption on our cost function $c$.

######  Assumption 1 (Bounded and uniformly Lipschitz cost).

We assume the cost $c$ is Borel measurable and $c\in
L^{\infty}(\mu\otimes\nu)$. By re-scaling the problem we assume without loss
of generality that

$\|c\|_{L^{\infty}(\mu\otimes\nu)}\leqslant 1.$

Also, we assume there exists $L>0$ such that for all
$y\in\operatorname{supp}(\nu)$,

$|c(x,y)-c(x^{\prime},y)|\leqslant L\|x-x^{\prime}\|\quad\quad\forall
x,x^{\prime}\in\operatorname{supp}(\mu),$

and, similarly, for all $x\in\operatorname{supp}(\mu)$,

$|c(x,y)-c(x,y^{\prime})|\leqslant L\|y-y^{\prime}\|\quad\quad\forall
y,y^{\prime}\in\operatorname{supp}(\nu).$

We remark that in the case where $c$ is the squared Euclidean cost
$\|\cdot\|^{2}$, Assumption 1 just means the supports of $\mu$ and $\nu$ are
compact.

###  2.2 Strong duality for entropic OT

Given the cost function $c$, we define the population entropic OT problem as

$S_{\varepsilon}(\mu,\nu):=\inf_{\pi\in\Pi(\mu,\nu)}\big{\\{}\pi(c)+\varepsilon\operatorname{KL}(\pi\,\|\,\mu\otimes\nu)\big{\\}}.$
(2.1)

The empirical entropic OT problem is then defined

$S_{\varepsilon}(\hat{\mu},\hat{\nu}):=\inf_{\pi\in\Pi(\hat{\mu},\hat{\nu})}\big{\\{}\pi(c)+\varepsilon\operatorname{KL}(\pi\,\|\,\hat{\mu}\otimes\hat{\nu})\big{\\}}.$
(2.2)

There are unique optimal solutions to the primal problems (2.1) and (2.2),
which we write as $\pi_{\varepsilon}$ and $\hat{\pi}_{\varepsilon}$,
respectively. We distinguish between $c$ and $S_{\varepsilon}(\mu,\nu)$ by
referring to the former as the cost function, and the latter as the entropic
OT value.

#### Strong duality.

Under Assumption 1 on the cost $c$, a form of strong duality holds for both
the population and empirical entropic OT problems. We refer to [DMG20] for
these results as well as a thorough review of the literature on this topic.
For the population entropic OT problem, strong duality is

$S_{\varepsilon}(\mu,\nu)=\sup_{(f,g)\in L^{\infty}(\mu)\times
L^{\infty}(\nu)}\Phi_{\varepsilon}(f,g):=\mu(f)+\nu(g)-\varepsilon(\mu\otimes\nu)(e^{-\varepsilon^{-1}(c-f-g)}-1).$

The function $\Phi_{\varepsilon}\colon L^{\infty}(\mu)\times
L^{\infty}(\nu)\to\mathbb{R}$ is the population entropic OT dual function.
Similarly for the empirical entropic OT problem, strong duality is stated

$S_{\varepsilon}(\hat{\mu},\hat{\nu})=\sup_{(f,g)\in
L^{\infty}(\hat{\mu})\times
L^{\infty}(\hat{\nu})}\hat{\Phi}_{\varepsilon}(f,g):=\hat{\mu}(f)+\hat{\nu}(g)-\varepsilon(\hat{\mu}\otimes\hat{\nu})(e^{-\varepsilon^{-1}(c-f-g)}-1).$

And this $\hat{\Phi}_{\varepsilon}\colon L^{\infty}(\hat{\mu})\times
L^{\infty}(\hat{\nu})\to\mathbb{R}$ is the empirical entropic OT dual
function.

#### Population and empirical dual potentials.

The population and empirical dual problems have solutions
$(f_{\varepsilon},g_{\varepsilon})\in L^{\infty}(\mu)\times L^{\infty}(\nu)$
and $(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})\in
L^{\infty}(\hat{\mu})\times L^{\infty}(\hat{\nu})$, respectively. These
solutions are unique up to the translation $(f,g)\mapsto(f-a,g+a)$ for
$a\in\mathbb{R}$, and we thus specify the solutions we consider by assuming
$\nu(g_{\varepsilon})=0$ and $\hat{\nu}(\hat{g}_{\varepsilon})=0$.

#### Population and empirical densities.

For notational convenience, we also define the population density, for
$\mu$-almost every $x$ and $\nu$-almost every $y$, as

$p_{\varepsilon}(x,y):=\frac{\mathrm{d}\pi_{\varepsilon}}{\mathrm{d}(\mu\otimes\nu)}(x,y)=e^{-\varepsilon^{-1}(c(x,y)-f_{\varepsilon}(x)-g_{\varepsilon}(y))}.$
(2.3)

And we similarly define, for all $x\in\mathcal{X}$ and $y\in\mathcal{Y}$, the
empirical density

$\hat{p}_{\varepsilon}(x,y):=\frac{\mathrm{d}\hat{\pi}_{\varepsilon}}{\mathrm{d}(\hat{\mu}\otimes\hat{\nu})}(x,y)=e^{-\varepsilon^{-1}(c(x,y)-\hat{f}_{\varepsilon}(x)-\hat{g}_{\varepsilon}(y))}$
(2.4)

#### Marginal constraints for the dual potentials.

The marginal constraints $\pi_{\varepsilon}\in\Pi(\mu,\nu)$ and
$\hat{\pi}_{\varepsilon}\in\Pi(\hat{\mu},\hat{\nu})$ in fact define necessary
and sufficient optimality conditions for the corresponding dual potentials
through equations (2.3) and (2.4), respectively. The resulting system of
equations is sometimes known as the Schrödinger system, and is fundamental to
entropic optimal transport. For the population potentials, the marginal
constraints imply that for $\mu$-almost every $x_{0}$ and $\nu$-almost every
$y_{0}$,

$1=\int
e^{-\varepsilon^{-1}(c(x,y)-f_{\varepsilon}(x_{0})-g_{\varepsilon}(y))}\mathrm{d}\nu(y),\quad\quad
1=\int
e^{-\varepsilon^{-1}(c(x,y)-f_{\varepsilon}(x)-g_{\varepsilon}(y_{0}))}\mathrm{d}\mu(x).$
(2.5)

The empirical potentials $\hat{f}_{\varepsilon},\hat{g}_{\varepsilon}$ satisfy
the analogous marginal equations: for all $x\in\mathcal{X}$ and
$y\in\mathcal{Y}$,

$1=\frac{1}{n}\sum_{j=1}^{n}e^{-\varepsilon^{-1}(c(x,y_{j})-\hat{f}_{\varepsilon}(x)-\hat{g}_{\varepsilon}(y_{j}))},\quad\quad
1=\frac{1}{n}\sum_{i=1}^{n}e^{-\varepsilon^{-1}(c(x_{i},y)-\hat{f}_{\varepsilon}(x_{i})-\hat{g}_{\varepsilon}(y))}.$
(2.6)

#### Canonical extensions of the dual potentials.

In fact, the marginal equations (2.6) yield a canonical means of extending the
empirical entropic dual potentials to functions on all of $\mathbb{R}^{d}$
[Ber20, PNW21]. We observe that solving for $\hat{f}_{\varepsilon}$ in (2.6)
yields, for $x\in\mathcal{X}$,

$\hat{f}_{\varepsilon}(x)=-\varepsilon\ln\big{(}\frac{1}{n}\sum_{j=1}^{n}e^{-\varepsilon^{-1}(c(x,y_{j})-\hat{g}_{\varepsilon}(y_{j}))}\big{)}.$
(2.7)

Since $c$ is defined everywhere, this equation actually makes sense for all
$x\in\operatorname{supp}(\mu)$, and so we thus define $\hat{f}_{\varepsilon}$
on all of $\operatorname{supp}\mu$ with this formula. Similarly, we put,

$\hat{g}_{\varepsilon}(y):=-\varepsilon\ln\big{(}\frac{1}{n}\sum_{i=1}^{n}e^{-\varepsilon^{-1}(c(x_{i},y)-\hat{f}_{\varepsilon}(x_{i}))}\big{)}\quad\quad
y\in\operatorname{supp}(\nu).$ (2.8)

Using Equation (2.4), we extend the empirical density $\hat{p}_{\varepsilon}$
to all of $\operatorname{supp}(\mu)\times\operatorname{supp}(\nu)$ as well.

##  3 Main results

In this section we describe our main results on the effective statistical
dimension of entropic optimal transport. In section 3.1, we introduce and
discuss MID scaling in the context of entropic OT value estimation. In section
3.2, we state our results which establish MID scaling for entropic OT map and
density estimation. And in section 3.3, we show how these results can be
strengthened in the case where one of the measures is supported on an embedded
manifold. Throughout, we work under Assumption 1 on the cost function.

###  3.1 Introduction to MID scaling with value convergence

In this section, we introduce the reader to MID scaling in the context of the
convergence of entropic OT values. We state our main result on MID scaling for
values, Theorem 2, give several examples, and then conclude with discussion of
its statistical significance and tightness.

#### MID scaling for value estimation.

Recall the definition of covering numbers from (1.3), and that we define

$\mathcal{N}(\mu,\delta):=\mathcal{N}(\operatorname{supp}(\mu),\|\cdot\|,\delta),\quad\quad\mathcal{N}(\nu,\delta):=\mathcal{N}(\operatorname{supp}(\nu),\|\cdot\|,\delta),\quad\quad\delta>0.$

Our main result on entropic OT value estimation follows.

######  Theorem 2 (MID scaling for values).

For numerical constants independent of all problem parameters,

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\lesssim(1+\varepsilon)\sqrt{\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}}.$

The only dimensional quantity in this estimate is contained in the minimum
covering numbers at scale $\varepsilon$, demonstrating the MID scaling
phenomenon. We emphasize that this result only requires that the cost $c$ is
bounded and Lipschitz (Assumption 1), in contrast to the smoothness
assumptions in most of the previous literature.

#### Examples of MID scaling.

To gain a feeling for Theorem 2, let us consider some examples.

######  Example 3 (Generic distributions in $B(0,1)$).

For generic probability distributions, we can apply Theorem 2 with standard
upper bounds on covering numbers in Euclidean space [Ver18, Proposition
4.2.12]. We find that if $\mu,\nu$ are supported in
$B(0,1)\subset\mathbb{R}^{d}$, then for numerical constants independent of all
problem parameters, and for all $\varepsilon>0$,

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\lesssim(1+\varepsilon)\cdot\Big{(}1+\frac{2L}{\varepsilon}\Big{)}^{d/2}\cdot\frac{1}{\sqrt{n}}.$

Specializing to the case of the $\ell_{2}^{2}$ cost, this bound nearly
recovers Theorem 1 under weaker conditions – Lipschitzness rather than
smoothness – on the cost, being worse by a factor of $\varepsilon^{-1/2}$ in
the case where $d$ is odd.111For large $\varepsilon$, our bound diverges while
Theorem 1 becomes $O(1/\sqrt{n})$, but it is straightforward to modify our
proofs to fully recover Theorem 1 in this case.

In cases where just one of the measures is assumed to have low intrinsic
dimension, we can obtain bounds which only depend on that measure.

######  Example 4 (Semi-discrete).

Suppose $\nu$ is supported on $K$ points. Then for numerical constants
independent of all problem parameters, and for all $\varepsilon>0$,

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\lesssim(1+\varepsilon)\cdot\sqrt{\frac{K}{n}}.$

######  Example 5 (Embedded manifold).

When $\nu$ is supported on a $d_{\nu}$-dimensional compact, smooth, embedded
Riemannian manifold without boundary, we can apply Theorem 2 with the bound
$\mathcal{N}(\nu,\delta)\leqslant C_{\nu}\delta^{-d_{\nu}}$, valid for some
$C_{\nu}>0$ and $\delta$ sufficiently small (Proposition 43 in Appendix A
formally verifies this fact). In this case, Theorem 2 implies that for
$\varepsilon>0$ sufficiently small and numerical constants independent of all
problem parameters,

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\lesssim\sqrt{C_{\nu}}(1+\varepsilon)\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}/2}\cdot\frac{1}{\sqrt{n}}.$

Because MID scaling involves only a single distance scale, the above examples
can be generalized to sets which are only low dimensional at some scales.

######  Example 6 ($\delta$-fattening of sets [WB19]).

For $\delta\geqslant 0$ and $A\subset\mathbb{R}^{d}$, the $\delta$-fattening
of $A$ is

$A_{\delta}:=\bigcup_{a\in A}B^{\rm cl}(a,\delta).$

Suppose $\operatorname{supp}(\nu)\subset A_{\delta}$ for some $\delta>0$ and
$A$ such that $\mathcal{N}(A,\|\cdot\|,\tau)\leqslant C_{A}\tau^{-k}$ for all
$\tau$ sufficiently small and some constants $C_{A},k\geqslant 0$. Note that
covering numbers on $A_{\delta}$ can be compared to those on $A$ itself, since
for $\tau\geqslant\delta$ we have
$\mathcal{N}(A_{\delta},\|\cdot\|,\tau)\leqslant\mathcal{N}(A,\|\cdot\|,\tau-\delta)$.
Hence for $\varepsilon>L\delta$ sufficiently small,

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\lesssim\sqrt{C_{A}}(1+\varepsilon)\cdot\Big{(}\frac{L}{\varepsilon-L\delta}\Big{)}^{k/2}\cdot\frac{1}{\sqrt{n}}.$

The above example illustrates that, so long as the ratio $\varepsilon/L$ is
significantly larger than the fattening scale $\delta$, the rates are
essentially the same as if $\operatorname{supp}(\nu)$ were actually contained
in $A$, despite the fact that $\operatorname{supp}(\nu)$ may be full-
dimensional at scale $\delta$. In this way, the dimension-dependence of MID
scaling is oblivious to features below scale $\varepsilon/L$.

#### Discussion of MID scaling.

We emphasize that MID scaling is similar to, but distinct from, the intrinsic
dimension-dependence in the un-regularized OT literature [Dud69, BLG14, WB19,
HSM22]. While in both settings the minimum of the intrinsic dimensions governs
the rate of convergence, the notion of intrinsic dimension is different. In
the un-regularized setting, intrinsic dimension is characterized through
uniform covering number control at small scales, whereas in MID scaling the
covering numbers play a role, but only at a single distance scale. The
convergence of un-regularized OT is, in fact, adaptive to multi-scale
behavior, but the relevant scales are determined by the sample size $n$,
meaning that milder covering numbers at some scales only translate to improved
rates while $n$ is not too large; in fact, such rates are known to be tight
[WB19]. In contrast, MID scaling shows that entropic OT benefits from better
covering number control at some scales for all sample sizes $n$. Essentially,
entropic regularization decouples the sample size and the distance scale of
the problem, allowing for a flexible trade-off between the intrinsic dimension
of the data distribution and the amount of regularization.222Thanks to Yann
Ollivier for stimulating comments on this point.

MID scaling helps clarify the statistical role of entropic regularization,
showing that beyond its well-known computational virtues, entropy also
provides statistical regularization by specifying a distance scale, allowing
the user to balance the intrinsic curse of dimensionality of the data with the
statistical difficulty of the problem. Because of the manifold hypothesis,
which states that natural data is typically supported on or near a low-
dimensional embedded manifold, we expect data to have significantly smaller
intrinsic dimension than extrinsic dimension. And so a means to flexibly adapt
optimal transport to such intrinsic low-dimensional structure, particularly
approximate low-dimensional structure, is of major interest. MID scaling
demonstrates that entropic regularization provides this benefit for optimal
transport.

#### Remarks on tightness.

While the upper bounds in this work substantiate MID scaling and the
statistical benefits of entropic regularization, a complete statistical
account of entropic OT requires lower bounds. We leave a thorough study of
this interesting direction to future work, but do give some indications on the
tightness of Theorem 2 here. For this reason, we note that the CLT for
entropic OT states that the asymptotic variance of
$\sqrt{n}(S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu))$ is
$\operatorname{Var}_{\mu}(f_{\varepsilon})+\operatorname{Var}_{\nu}(g_{\varepsilon})$
[GSH23]. In particular, it follows that the dependence on $n$ in Theorem 2 is
optimal, and moreover that Theorem 2 is tight in the case where $\nu$ is
supported on two points (see Example 4).

However, this example doesn’t rule out the possibility that the dependence on
the covering numbers of $\mu$ and $\nu$ can be improved. To reason about such
issues, we can reduce to lower bounds for the un-regularized OT problem. For
example, it is known that the approximation error $|S_{\varepsilon}-S_{0}|$ is
$O(\varepsilon)$, up to logarithmic factors [GCB+19]. Combining this
approximation error with minimax lower bounds for estimating un-regularized OT
values then implies a firm speed limit on statistical bounds for entropic OT
values. Arguing along these lines, we show in Appendix B.1 that Theorem 2
implies that entropic estimators can estimate $W_{1}$ distances at the rate
$n^{-1/(d+2)}$, close to the minimax optimal $n^{-1/d}$ rate [NWR22], and that
moreover the covering number dependence in the bound of Theorem 2 cannot be
improved in general.

###  3.2 MID scaling for maps and densities

Theorem 2 gives a strong instance of the MID scaling phenomenon for entropic
optimal transport, yet in many applications of entropic OT, such as trajectory
reconstruction [SST+19] and domain adaptation [FCTR16, SDF+18], it is of
greater interest to estimate the solution to the entropic OT problem than the
value of the entropic OT objective alone. Motivated by this fact, we also
study the performance of empirical plug-in estimators for the problems of
entropic OT map estimation as well as density estimation, and develop results
analogous to Theorem 2, showing that natural plug-in estimators also sport MID
scaling.

We define the entropic OT map

$T_{\varepsilon}(x):=\mathbb{E}_{\pi_{\varepsilon}}[y\,|\,x].$

Note that the analogous map defined over $y$ is symmetric with this one, and
so we study only this case without loss of generality. The map
$T_{\varepsilon}$ is an entropic analog of the OT map, and has been the
subject of much recent work as it offers greater computational and statistical
efficiency than its un-regularized counterpart [PNW21, MWMA21, RS22, PDNW23].
We study the empirical analog of $T_{\varepsilon}(x)$:

$\hat{T}_{\varepsilon}(x):=\mathbb{E}_{\hat{\pi}_{\varepsilon}}[y\,|\,x]=\frac{1}{n}\sum_{j=1}^{n}y_{j}\hat{p}_{\varepsilon}(x,y_{j}).$
(3.1)

We consider $\hat{T}_{\varepsilon}$ as an estimator for its population analog
$T_{\varepsilon}$ and show it enjoys a $1/\sqrt{n}$ rate of convergence with
MID scaling.

######  Theorem 7.

Suppose the diameter of $\operatorname{supp}(\nu)$ is at most $R$. Then for
numerical constants independent of all problem parameters,

$\mathbb{E}[\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}]\lesssim
R^{2}\big{(}1+\frac{1}{\varepsilon}\big{)}\sqrt{\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}}.$

We note that this result is measured with respect to the empirical norm
$\|\cdot\|_{L^{2}(\hat{\mu})}$, rather than the population norm
$\|\cdot\|_{L^{2}(\mu)}$. In the next section we assume that one distribution
is supported on an embedded manifold and show that this result can be
strengthened to population norm convergence with fast $1/n$ rates. As before,
we may derive bounds from this result in cases where we have a priori control
on the relevant covering numbers. Previous work on the convergence of
$\hat{T}_{\varepsilon}$ to $T_{\varepsilon}$ for generic distributions
incurred an exponential dependence on $1/\varepsilon$ [MWMA21, RS22]; Theorem
2 removes this exponential dependence while only incurring MID scaling.

We finally remark that Theorem 7 only uses the boundedness of $y$, and can be
extended to bound the convergence of other conditional expectations
$\mathbb{E}_{\pi_{\varepsilon}}[\alpha(x,y)\,|\,x]$ for bounded
$\alpha\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{k}$. Such
generality is of interest, since some researchers study alternative
definitions of entropic OT maps when the cost is not $\ell_{2}^{2}$. For
example, when $c(x,y)=h(x-y)$ for strictly convex $h$, a very recent work
suggested a different definition of $T_{\varepsilon}$ based on analogy to the
un-regularized OT map in this case [CKA23]. If $h$ satisfies Assumption 1 and
is additionally strongly convex and differentiable everywhere, it is not hard
to check that Theorem 7 also holds for the maps introduced in that work.

#### MID scaling for entropic OT density estimation.

We can also consider estimating the full entropic OT density
$p_{\varepsilon}$, defined in (2.3). A natural way to estimate
$p_{\varepsilon}$ from samples is with its plug-in counterpart,
$\hat{p}_{\varepsilon}$ from (2.4). We obtain the following result.

######  Theorem 8.

For numerical constants independent of all problem parameters,

$\mathbb{E}[\|\hat{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\lesssim\big{(}1+\frac{1}{\sqrt{\varepsilon}}\big{)}\Big{(}\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}\Big{)}^{1/4}.$

This result shows that MID scaling even applies when estimating the full
density $p_{\varepsilon}$, albeit in the empirical
$L^{1}(\hat{\mu}\otimes\hat{\nu})$ norm. Previously known bounds for the
convergence of $\hat{p}_{\varepsilon}$ to $p_{\varepsilon}$ incurred an
exponential dependence on $1/\varepsilon$ [RS22], and Theorem 8 removes this
dependence while only incurring MID scaling. In the next section, we
demonstrate a stronger form of MID scaling for these problems when the low-
dimensional distribution is supported on an embedded manifold.

###  3.3 Fast rates with MID scaling on embedded manifolds

In this section, we describe how we can strengthen the results from the
previous section by assuming the low-dimensional measure is supported on an
embedded manifold.

#### Assumptions.

We work under the following assumptions, and for simplicity assume that $\nu$
is the low-dimensional measure. See Appendix A for a review of embedded
Riemannian manifolds, as well as a discussion of the tools from the theory of
random geometric graphs on embedded manifolds that we use in our proofs.

######  Assumption 2 ($\nu$ is supported on an embedded manifold).

Assume $\nu$ is supported on a compact, smooth, connected, Riemannian manifold
$(N,h)$ of dimension $d_{\nu}\geqslant 3$ without boundary, where $N$ is
endowed with the submanifold geometry from its inclusion in $\mathbb{R}^{d}$.

We also assume that $\nu$ is compatible with $N$ in the following sense.

######  Assumption 3 ($\nu$ is Lipschitz and non-vanishing).

Assume that $\nu$ has a Lipschitz, non-vanishing density with respect to the
Riemannian volume on $N$.

These assumptions represent a natural instantiation of the manifold hypothesis
while still furnishing enough analytical structure to yield stronger results
than in the previous section. In this section and associated proofs,
Assumptions 2 and 3 are made throughout, in addition to Assumption 1.

#### Suppressing constants depending on $N$ and $\nu$.

In contrast to the previous section, in this section and associated proofs we
will generally suppress constants depending on $N$ and $\nu$. The suppressed
constants are strictly a function of the intrinsic dimension $d_{\nu}$ (and
not the extrinsic dimension $d$), the geometry of $N$, and uniform bounds on
the density of $\nu$ and its Lipschitz constant. In Appendix A, where we
collect all the background and necessary results on embedded manifolds and
random geometric graphs, we describe the relevant geometric quantities from
the manifold $N$.

#### Main result on dual potential convergence.

The purpose of this section is to show that under these assumptions on $\nu$
and $N$, we can derive significantly stronger instances of MID scaling than in
the previous section. Our main result concerns the convergence of the
empirical dual potentials $\hat{f}_{\varepsilon},\hat{g}_{\varepsilon}$ to
their population counterparts $f_{\varepsilon},g_{\varepsilon}$. Such
convergence is essentially stronger than that of entropic OT values, maps, and
densities, since each of those quantities is defined in terms of the dual
potentials. Since this result measures convergence in population norms, we
remind the reader that the out of sample extensions of
$\hat{f}_{\varepsilon},\hat{g}_{\varepsilon}$ as defined in (2.7) and (2.8),
respectively, are in full effect.

######  Theorem 9.

If $\varepsilon/L$ is sufficiently small, then

$\mathbb{E}\big{[}\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\mu)}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}\big{]}\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{13d_{\nu}+8}\cdot\frac{1}{n}.$

We also have convergence in empirical norms

$\mathbb{E}\big{[}\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}\big{]}\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{9d_{\nu}+4}\cdot\frac{1}{n}.$

Some remarks on this result are in order. First, as in all the results of this
section, we require $\varepsilon/L$ to be sufficiently small; the precise size
is given in Equation (A.1). Second, the result concerns the sum of the squared
norms, but this is merely for a convenient statement, and the proofs for each
term are separate and different. Third, the empirical norm convergence is
useful for some of our applications below, while also being an important
preliminary step to the full population norm results. Fourth, we remark that,
to the best of our knowledge, all previously known bounds on entropic OT dual
potentials incurred an exponential dependence on $\varepsilon$ [LSPC19,
dBGSLNW22, RS22]. The significance of Theorem 9 is that it avoids exponential
dependence on $\varepsilon$ while only incurring minimum intrinsic dimension-
dependence, in accordance with MID scaling.

#### MID scaling in the embedded manifold setting.

As do all the results in this section, Theorem 9 evinces a slightly modified
form of MID scaling as compared to the previous sections. In our embedded
manifold setting, the minimum part of MID scaling simply means that the
intrinsic dimension of $\mu$ doesn’t appear in the bounds (remarkably, nothing
about $\mu$ appears in the bound at all); if $\mu$ were also assumed to
satisfy the above assumptions on a manifold of dimension $d_{\mu}$, we could
write bounds with an appropriate minimum. In terms of the intrinsic dimension
part of MID scaling, there is only a superficial difference, since although
the rates in this section do not explicitly involve covering numbers at scale
$\varepsilon/L$ but instead the power $(L/\varepsilon)^{d_{\nu}}$, the two
are, in fact, comparable (Proposition 43). And finally, as we mentioned above,
there are hidden constants depending on $N$ and $\nu$, and especially the
intrinsic dimension $d_{\nu}$, as opposed to the previous results which had
only numerical constants.

#### Applications of dual convergence.

We demonstrate the power of Theorem 9 with a few applications. Our first two
results improve upon the map and density estimation results from the previous
section. For each of these applications, we again require $\varepsilon/L$ to
be sufficiently small, as specified in Equation (A.1).

Recall the setting of Theorem 7: we wish to estimate
$T_{\varepsilon}(x):=\mathbb{E}_{\pi_{\varepsilon}}[y\,|\,x]$ from samples,
and we use the plug-in estimator
$\hat{T}_{\varepsilon}(x):=\mathbb{E}_{\hat{\pi}_{\varepsilon}}[y\,|\,x]$.
Using the canonical extensions of the empirical dual potentials
$\hat{f}_{\varepsilon},\hat{g}_{\varepsilon}$ and correspondingly the
empirical density $\hat{p}_{\varepsilon}$ as in equations (2.7), (2.8), and
(2.4), we can extend $\hat{T}_{\varepsilon}$ to a map in $L^{2}(\mu)$, and
consider convergence in this population norm. This extended map
$\hat{T}_{\varepsilon}$ can be evaluated in linear time once the empirical
dual potentials are known, and was originally proposed as a computationally
efficient estimator for the un-regularized OT map [PNW21]. We obtain the
following corollary of Theorem 9.

######  Corollary 10.

If $\varepsilon/L$ is sufficiently small, and the diameter of
$\operatorname{supp}(\nu)$ is at most $R$, then

$\mathbb{E}[\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|^{2}_{L^{2}(\mu)}]\lesssim
R^{2}\cdot\big{(}1+\frac{1}{\varepsilon^{4}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{11d_{\nu}+4}\cdot\frac{1}{n}$

Corollary 10 improves over Theorem 7 in that it achieves a fast $1/n$ rate of
convergence in the full population norm $L^{2}(\mu)$.

We can also strengthen our result on density estimation from the previous
section, Theorem 8. As in the case of map estimation, the canonical extensions
of the empirical density $\hat{p}_{\varepsilon}$ described in section 2, allow
us to consider $\hat{p}_{\varepsilon}$ as an out of sample estimator for
$p_{\varepsilon}$.

######  Corollary 11.

If $\varepsilon/L$ is sufficiently small, then

$\mathbb{E}[\|\hat{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}]\lesssim\big{(}1+\frac{1}{\varepsilon^{4}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{15d_{\nu}+8}\cdot\frac{1}{n}.$

This result shows that, in the embedded manifold setting, Theorem 8 can be
strengthened to full population norm convergence, $L^{2}$ rather than $L^{1}$,
and to faster rates.

Our final application concerns the _bias_ of entropic OT, namely the quantity
$\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})]-S_{\varepsilon}(\mu,\nu)$.
Recent work established that the bias converges at a fast $1/n$ rate, yet with
an exponential dependence on the regularization parameter $\varepsilon$ [RS22,
dBGSLNW22]. The following result removes this exponential dependence and
achieves MID scaling. We state this result as a Theorem since, unlike the
previous Corollaries, it doesn’t directly follow from Theorem 9.

######  Theorem 12.

If $\varepsilon/L$ is sufficiently small, then

$|\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})]-S_{\varepsilon}(\mu,\nu)|\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{9d_{\nu}+4}\cdot\frac{1}{n}.$

In sum, the results in this section demonstrate a strong form of the MID
scaling phenomenon in the relatively general setting of Assumptions 2 and 3.
These results underscore the main message of our work: MID scaling is a
generic phenomenon for entropic OT. They demonstrate that MID scaling is
certainly not limited to value estimation or map and density estimation in
empirical norms with slow $1/\sqrt{n}$ rates, but in the embedded manifold
setting even holds for dual potentials, maps, densities, and biases, all with
fast $1/n$ rates in population norms.

##  4 Preliminary results

In this section, we fix final pieces of notation and describe some simple
observations that form the foundation of our approach.

###  4.1 Concavity for the empirical dual

Given probability measures $P,Q$ on $\mathbb{R}^{d}$, we define the entropic
OT dual function $\Phi^{PQ}_{\varepsilon}\colon L^{\infty}(P)\times
L^{\infty}(Q)\to\mathbb{R}$ as

$\Phi^{PQ}_{\varepsilon}(f,g):=P(f)+Q(g)-\varepsilon(P\otimes
Q)(e^{-\varepsilon^{-1}(c-f-g)}-1).$

With this notation, we can express the population dual
$\Phi_{\varepsilon}=\Phi_{\varepsilon}^{\mu\nu}$ and the empirical dual
$\hat{\Phi}_{\varepsilon}=\Phi_{\varepsilon}^{\hat{\mu}\hat{\nu}}$. We collect
some basic facts about entropic dual functions below.

######  Proposition 13.

Let $P,Q$ be probability measures on $\mathbb{R}^{d}$. The corresponding
entropic OT dual function $\Phi^{PQ}_{\varepsilon}$ has the following
properties:

  1. 1.

(Definition of gradient.) For every pair $h_{1}=(f_{1},g_{1})\in
L^{\infty}(P)\times L^{\infty}(Q)$, there exists an element of
$L^{\infty}(P)\times L^{\infty}(Q)$ which we denote by
$\nabla\Phi_{\varepsilon}^{PQ}(f_{1},g_{1})$ such that for all
$h_{0}=(f_{0},g_{0})\in L^{\infty}(P)\times L^{\infty}(Q)$,

$\displaystyle\langle\nabla\Phi_{\varepsilon}^{PQ}(h_{1}),h_{0}\rangle_{L^{2}(P)\times
L^{2}(Q)}$ $\displaystyle=\int f_{0}(x)\Big{(}1-\int
e^{-\varepsilon^{-1}(c(x,y)-f_{1}(x)-g_{1}(y))}\mathrm{d}Q(y)\Big{)}\mathrm{d}P(x)$
$\displaystyle+\int g_{0}(y)\Big{(}1-\int
e^{-\varepsilon^{-1}(c(x,y)-f_{1}(x)-g_{1}(y))}\mathrm{d}P(x)\Big{)}\mathrm{d}Q(x).$

In other words, the gradient of $\Phi_{\varepsilon}^{PQ}$ at $(f_{1},g_{1})$
is the marginal error corresponding to $(f_{1},g_{1})$.

  2. 2.

(Concavity.) For any two pairs of dual potentials $h_{0},h_{1}\in
L^{\infty}(P)\times L^{\infty}(Q)$, we have the inequalities

$\Phi_{\varepsilon}^{PQ}(h_{0})-\Phi_{\varepsilon}^{PQ}(h_{1})\leqslant\langle\nabla\Phi_{\varepsilon}^{PQ}(h_{1}),h_{0}-h_{1}\rangle_{L^{2}(P)\times
L^{2}(Q)},$ (4.1)

and

$\langle\nabla\Phi_{\varepsilon}^{PQ}(h_{0}),h_{0}-h_{1}\rangle_{L^{2}(P)\times
L^{2}(Q)}\leqslant\Phi_{\varepsilon}^{PQ}(h_{0})-\Phi_{\varepsilon}^{PQ}(h_{1}).$
(4.2)

  3. 3.

(Marginal rounding improves the dual objective.) Let $(f,g)\in
L^{\infty}(P)\times L^{\infty}(Q)$, and set

$\tilde{f}(x):=-\varepsilon\log\Big{(}\int
e^{-\varepsilon^{-1}(c(x,y)-g(y))}\mathrm{d}Q(y)\Big{)}.$

Then

$\Phi_{\varepsilon}^{PQ}(f,g)\leqslant\Phi_{\varepsilon}^{PQ}(\tilde{f},g).$

And analogously when marginal rounding in the $g$ variable.

###### Proof of Proposition 13.

The first item is a definition. For the second item, write

$\Phi_{\varepsilon}^{PQ}(f,g)=(P\otimes Q)\big{(}f(x)+g(y)-\varepsilon
e^{-\varepsilon^{-1}(c(x,y)-f(x)-g(y))}\big{)}+\varepsilon,$

and observe that the function $t\mapsto t-\varepsilon
e^{-\varepsilon^{-1}(c-t)}$ is concave. The result follows by applying the
concavity of the integrand pointwise and collecting terms. The third item
follows from the first two. ∎

###  4.2 Pointwise control and log-Lipschitz bounds

In this section we describe some simple yet powerful implications of
Assumption 1.

The following pointwise bounds appear in a number of places [MNW19, DMG20,
RS22], and so their proof is omitted.

######  Proposition 14 (Pointwise control on dual potentials).

Under our normalization conventions that $\nu(g_{\varepsilon})=0$ and
$\hat{\nu}(\hat{g}_{\varepsilon})=0$, we have the uniform bounds

$\|\hat{f}_{\varepsilon}\|_{L^{\infty}(\mu)},\,\,\|\hat{g}_{\varepsilon}\|_{L^{\infty}(\nu)}\leqslant
2,\quad\quad\|f_{\varepsilon}\|_{L^{\infty}(\mu)},\,\,\|g_{\varepsilon}\|_{L^{\infty}(\nu)}\leqslant
1.$

The following Lipschitz bounds are also well-known [DMG20], but since they are
the foundation of our approach we include their proof.

######  Proposition 15 (Lipschitz bounds).

The population dual potentials $f_{\varepsilon}$ and $g_{\varepsilon}$ are
$L$-Lipschitz over $\operatorname{supp}(\mu)$ and $\operatorname{supp}(\nu)$,
respectively. The extended empirical dual potentials $\hat{f}_{\varepsilon}$
and $\hat{g}_{\varepsilon}$ are also $L$-Lipschitz over
$\operatorname{supp}(\mu)$ and $\operatorname{supp}(\nu)$, respectively. In
particular, the population density $p_{\varepsilon}$ and the extended
empirical density $\hat{p}_{\varepsilon}$ are each
$\frac{2L}{\varepsilon}$-log-Lipschitz in each of their variables over
$\operatorname{supp}(\mu)\times\operatorname{supp}(\nu)$.

###### Proof.

By the marginal constraints (2.5), we have that for all
$x\in\operatorname{supp}(\mu)$,

$e^{-\frac{1}{\varepsilon}f_{\varepsilon}(x)}=\int
e^{-\frac{1}{\varepsilon}(c(x,y)-g_{\varepsilon}(y)}\mathrm{d}\nu(y).$

Using Assumption 1 on the cost $c$ being Lipschitz, we see that for
$x,x^{\prime}\in\operatorname{supp}(\mu)$

$e^{-\frac{1}{\varepsilon}f_{\varepsilon}(x)}\leqslant
e^{-\frac{1}{\varepsilon}f_{\varepsilon}(x^{\prime})+\frac{L}{\varepsilon}\|x-x^{\prime}\|}$

By symmetry it follows that

$|f_{\varepsilon}(x)-f_{\varepsilon}(x^{\prime})|\leqslant L\|x-x^{\prime}\|.$

The analogous argument establishes the claim for $g_{\varepsilon}$, and also
proves the claims for the extended empirical potentials
$\hat{f}_{\varepsilon}$ and $\hat{g}_{\varepsilon}$.

For the claims about the densities, note that

$\log
p_{\varepsilon}(x,y)=-\frac{1}{\varepsilon}\big{(}c(x,y)-f_{\varepsilon}(x)-g_{\varepsilon}(y)\big{)},$

and so the claim follows from the previous ones for $f_{\varepsilon}$ and
$g_{\varepsilon}$, as well as Assumption 1. Similarly for
$\log\hat{p}_{\varepsilon}$. ∎

##  5 Proofs of MID scaling with slow rates

In this section, we give our proofs of MID scaling for values, Theorem 2, MID
scaling for maps in empirical norms, Theorem 7, and MID scaling for densities
in empirical norms, Theorem 8. The proofs are organized in the following
manner. In section 5.1, we give a detailed exposition of our approach in the
case of value estimation. In section 5.2, we give the proof of one of our main
technical lemmas, and the source of MID scaling, on sub-exponential bounds for
$\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}$. In section 5.3, we show how
to reduce map estimation to the estimates from the previous sections, and do
the same for density estimation in section 5.4.

###  5.1 Proof of value rate and overview of technical approach

In this section, we illustrate the main ideas of our technical approach by
describing our proof of Theorem 2 on the convergence of entropic OT values. To
situate our approach, note that most existing statistical work on entropic OT
studies smooth cost functions and shows that the smoothness of the cost
functions implies smoothness for the dual potentials, leading to small
function classes over which empirical processes can be well-controlled
[GCB+19, LSPC19, MNW19, dBGSLNW22, BEZ22]. The present work builds on a
different approach, developed in [RS22], which entirely avoids empirical
process theory by using strong concavity of the empirical dual objective. The
benefit of this approach is that it is simple, requires no smoothness
assumptions on the cost, leads to dimension-free bounds, and can be used to
prove fast rates for most entropic OT quantities [RS22]. However, because it
is dimension-free, it is not suited to a fine understanding of the dimension-
dependence of entropic OT, and in particular it incurs exponential factors of
$1/\varepsilon$ at many points in the arguments. The main technical goal of
this work is to refine this strong concavity of the empirical dual approach by
replacing the exponential dependence on $1/\varepsilon$ with a very fine
dependence on the dimension of the problem: MID scaling.

To this end, note that the exponential dependence of [RS22] primarily arises
from two separate sources: first, the strong concavity of the empirical dual
objective, and second, pointwise bounds on the entropic density
$p_{\varepsilon}$. For the results in this section, we avoid the exponential
factors arising from strong concavity by using more delicate arguments which
rely on only concavity, and remove the exponential factors from the pointwise
bounds on the entropic density $p_{\varepsilon}$ with a novel estimate (Lemma
16 below) which is itself the source of MID scaling.

To present the ideas as clearly as possible, we will suppress numerical
constants with the notation $u\lesssim v$; they can easily be extracted from
the proof. Recall that $\Phi_{\varepsilon}$ is the population entropic OT dual
function, and $\hat{\Phi}_{\varepsilon}$ is its empirical counterpart. Then
Theorem 2 concerns the quantity

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]=\mathbb{E}[|\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|].$

To bound this quantity, we first decompose it in the following manner:

$\displaystyle\mathbb{E}[|\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|]$
$\displaystyle\leqslant\mathbb{E}[|\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|]+\mathbb{E}[|\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|]$
$\displaystyle=\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]+\mathbb{E}[|\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|].$

For convenience, we refer to the first term as a bias term, and the second as
a variance term. Note that our usage of “bias” and “variance” in this context
is not intended to be standard, merely suggestive.

#### Variance term.

If we just examine this variance term, we can compute:

$\displaystyle\mathbb{E}[$
$\displaystyle|\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|]$
$\displaystyle=\mathbb{E}[|(\hat{\mu}-\mu)(f_{\varepsilon})+(\hat{\nu}-\nu)(g_{\varepsilon})-\varepsilon(\hat{\mu}\otimes\hat{\nu}-\mu\otimes\nu)(p_{\varepsilon})|]$
$\displaystyle\leqslant\mathbb{E}[\big{(}(\hat{\mu}-\mu)(f_{\varepsilon})+(\hat{\nu}-\nu)(g_{\varepsilon})-\varepsilon(\hat{\mu}\otimes\hat{\nu}-\mu\otimes\nu)(p_{\varepsilon})\big{)}^{2}]^{1/2}$
$\displaystyle\lesssim\big{(}\mathbb{E}[\big{(}(\hat{\mu}-\mu)(f_{\varepsilon})\big{)}^{2}]+\mathbb{E}[\big{(}(\hat{\nu}-\nu)(g_{\varepsilon})\big{)}^{2}]+\varepsilon^{2}\mathbb{E}[\big{(}(\hat{\mu}\otimes\hat{\nu}-\mu\otimes\nu)(p_{\varepsilon})\big{)}^{2}]\big{)}^{1/2}$
$\displaystyle\leqslant\mathbb{E}[\big{(}(\hat{\mu}-\mu)(f_{\varepsilon})\big{)}^{2}]^{1/2}+\mathbb{E}[\big{(}(\hat{\nu}-\nu)(g_{\varepsilon})\big{)}^{2}]^{1/2}+\varepsilon\mathbb{E}[\big{(}(\hat{\mu}\otimes\hat{\nu}-\mu\otimes\nu)(p_{\varepsilon})\big{)}^{2}]^{1/2}.$

For the first two terms, we use the pointwise boundedness of the dual
potentials from Proposition 14 to yield

$\mathbb{E}[\big{(}(\hat{\mu}-\mu)(f_{\varepsilon})\big{)}^{2}]^{1/2}+\mathbb{E}[\big{(}(\hat{\nu}-\nu)(g_{\varepsilon})\big{)}^{2}]^{1/2}=\sqrt{\frac{\operatorname{Var}_{\mu}(f_{\varepsilon})}{n}}+\sqrt{\frac{\operatorname{Var}_{\nu}(g_{\varepsilon})}{n}}\lesssim\frac{1}{\sqrt{n}}.$

For the third term, the marginal constraints for $p_{\varepsilon}$ from (2.5)
allow us to cancel cross-terms and compute

$\displaystyle\mathbb{E}[(\hat{\mu}\otimes\hat{\nu})(p_{\varepsilon}-(\mu\otimes\nu)(p_{\varepsilon}))^{2}]^{1/2}$
$\displaystyle=\mathbb{E}[(\hat{\mu}\otimes\hat{\nu})(p_{\varepsilon}-1)^{2}]^{1/2}$
$\displaystyle=\Big{(}\frac{1}{n^{4}}\sum_{i,j,k,l=1}^{n}\mathbb{E}[(p_{\varepsilon}(x_{i},y_{j})-1)(p_{\varepsilon}(x_{k},y_{l})-1)]\Big{)}^{1/2}$
$\displaystyle=\frac{1}{n}\sqrt{\operatorname{Var}_{\mu\otimes\nu}(p_{\varepsilon})}\leqslant\frac{1}{n}\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}.$

We note that this kind of calculation is used repeatedly throughout the paper.
We finally arrive at the bound

$\displaystyle\mathbb{E}[|\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|]$
$\displaystyle\lesssim\frac{1}{\sqrt{n}}+\frac{\varepsilon\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}}{n}$
$\displaystyle\lesssim(1+\varepsilon)\frac{\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}}{\sqrt{n}},$
(5.1)

where the last inequality follows because $(\mu\otimes\nu)(p_{\varepsilon})=1$
implies $1\leqslant\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}$ by Cauchy-
Schwarz.

#### Bias term.

We use concavity of the empirical dual to control the bias term
$\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]$
by a quantity involving $\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}$ again.
Indeed, by Proposition 13 on concavity of $\hat{\Phi}_{\varepsilon}$ and
Proposition 14 on pointwise control for the dual potentials, we have

$\displaystyle\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]$
$\displaystyle\leqslant\mathbb{E}[\langle\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}]$
$\displaystyle\leqslant\mathbb{E}\big{[}\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}\cdot\|(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}\big{]}$
$\displaystyle\lesssim\mathbb{E}\big{[}\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}^{2}\big{]}^{1/2}.$

Using the marginal constraints (2.5) to cancel cross terms once more, we find

$\displaystyle\mathbb{E}[\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}^{2}]$
$\displaystyle=\mathbb{E}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\Big{(}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x_{i},y_{j})-1\Big{)}^{2}$
$\displaystyle+\frac{1}{n}\sum_{j=1}^{n}\Big{(}\frac{1}{n}\sum_{i=1}^{n}p_{\varepsilon}(x_{i},y_{j})-1\Big{)}^{2}\Big{]}$
$\displaystyle=\frac{1}{n^{3}}\sum_{i,j_{0},j_{1}=1}^{n}\mathbb{E}[(p_{\varepsilon}(x_{i},y_{j_{0}})-1)(p_{\varepsilon}(x_{i},y_{j_{1}})-1)]$
$\displaystyle+\frac{1}{n^{3}}\sum_{i_{0},i_{1},j=1}^{n}\mathbb{E}[(p_{\varepsilon}(x_{i_{0}},y_{j})-1)(p_{\varepsilon}(x_{i_{1}},y_{j})-1)]$
$\displaystyle=\frac{2}{n}\operatorname{Var}_{\mu\otimes\nu}(p_{\varepsilon})\lesssim\frac{\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}}{n}.$

We arrive at an important, if elementary, bound that we will use frequently
throughout this work,

$\mathbb{E}[\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}^{2}]\lesssim\frac{\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}}{n}.$
(5.2)

In particular, the bias is bounded as

$\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]\lesssim\frac{\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}}{\sqrt{n}}.$
(5.3)

#### Controlling $\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}$.

We can combine (5.1) and (5.3) to obtain

$\mathbb{E}[|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|]\lesssim(1+\varepsilon)\frac{\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}}{\sqrt{n}}.$
(5.4)

We have thus reduced the problem to terms with a dimension-free dependence on
the sample size $n$, and with the dimension and $\varepsilon$-dependence
residing fully in the term
$(1+\varepsilon)\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}$. Up to this point,
the differences between the techniques introduced in [RS22] and our approach
are essentially contained in two steps, each taken to avoid factors of
$e^{1/\varepsilon}$. First, we control the bias term with concavity rather
than strong concavity. And second, we refrain from using the pointwise control
of Proposition 14 to bound the $p_{\varepsilon}$ terms, which would result in
the bound $\|p_{\varepsilon}\|_{L^{\infty}(\mu\otimes\nu)}\leqslant
e^{C/\varepsilon}$ for a constant $C$. Such pointwise and exponential bounds
were, to the best of our knowledge, all that was known about $p_{\varepsilon}$
until this work.

One of the core technical innovations in this work, and indeed the source of
MID scaling, is to provide the following sub-exponential bound on
$p_{\varepsilon}$.

######  Lemma 16 (MID scaling for entropic densities).

We have

$\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}\lesssim\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L}).$

This Lemma is proven by using the marginal constraints that $p_{\varepsilon}$
satisfies in Equation (2.5) to gain pointwise control on $p_{\varepsilon}$
that, when integrated, yields the covering numbers. The proof is given in the
following section. Theorem 2 follows by plugging this Lemma into Equation
(5.4).

For our subsequent results, it is convenient to record the following Lemma,
which results from combining Equation (5.3) with Lemma 16.

######  Lemma 17 (MID scaling for the bias).

We have

$\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)]\lesssim\sqrt{\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}}.$

#### Summary of the technical approach.

In summary, we decomposed the difference
$|S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)|$ into a bias
term and a variance term. For the variance term, an elementary calculation
allows us to control it by something with the dimension of the problem
residing purely in the $\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}$ term. And
for the bias term, a judicious use of concavity allows us to control it by
another expression with the dimension of the problem purely in the
$\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}$ term. We then conclude with Lemma
16. The proofs of MID scaling with slow rates for maps and densities, Theorem
7 and Theorem 8, use additional estimates that also follow the pattern of
splitting into bias and variance terms (loosely construed) to then reduce to
Lemma 16, and are included in sections 5.3 and 5.4, respectively.

###  5.2 MID scaling for entropic densities

In this section, we will prove Lemma 16, which gives sub-exponential, MID
scaling-type bounds on the entropic density $p_{\varepsilon}$. To this end,
the following fact will be useful. Recall that we write the closed ball of
size $\delta$ at $z\in\mathbb{R}^{d}$ as

$B^{\rm
cl}(z,\delta):=\big{\\{}z^{\prime}\in\mathbb{R}^{d}\colon\|z-z^{\prime}\|\leqslant\delta\big{\\}}.$

######  Proposition 18 (Average inverse mass is bounded by the covering
number).

Suppose $P$ is a compactly supported probability measure on $\mathbb{R}^{d}$.
Then for all $\delta>0$,

$\int P(B^{\rm
cl}(z,\delta))^{-1}\mathrm{d}P(z)\leqslant\mathcal{N}(P,\delta/4).$

To give the proof of this Proposition, recall that for $\tau>0$, a proper
$\tau$-covering of a set $A\subset\mathbb{R}^{d}$, is a covering of $A$ at
scale $\tau$ with centers contained within $A$. We write the minimal size of a
proper covering with respect to the Euclidean norm at scale $\tau>0$ as
$\mathcal{N}^{\rm pr}(A,\|\cdot\|,\tau)$. Note that proper covering numbers
are comparable to vanilla covering numbers since $\mathcal{N}^{\rm
pr}(A,\|\cdot\|,\tau)\leqslant\mathcal{N}(A,\|\cdot\|,\tau/2)$.

###### Proof of Proposition 18.

Let $z_{1},\ldots,z_{K}\in\operatorname{supp}(P)$ be a proper $\delta/2$
covering of $\operatorname{supp}(P)$ achieving $K=\mathcal{N}^{\rm
pr}(\operatorname{supp}(P),\|\cdot\|,\delta/2)$. Since this is a proper
covering, we know that for all $k\in[K]$, $P(B^{\rm cl}(z_{k},\delta/2))>0$.
The triangle inequality then implies

$z\in B^{\rm cl}(z_{k},\delta/2)\implies 0<P(B^{\rm
cl}(z_{k},\delta/2))\leqslant P(B^{\rm cl}(z,\delta)).$

Thus

$\displaystyle\int P(B^{\rm cl}(z,\delta))^{-1}\mathrm{d}P(z)$
$\displaystyle\leqslant\sum_{k=1}^{K}\int_{B^{\rm cl}(z_{k},\delta/2)}P(B^{\rm
cl}(z,\delta))^{-1}\mathrm{d}P(z)$
$\displaystyle\leqslant\sum_{k=1}^{K}\int_{B^{\rm cl}(z_{k},\delta/2)}P(B^{\rm
cl}(z_{k},\delta/2))^{-1}\mathrm{d}P(z)$ $\displaystyle=K=\mathcal{N}^{\rm
pr}(P,\delta/2)\leqslant\mathcal{N}(P,\delta/4).$

∎

###### Proof of Lemma 16.

We show the bound for $\mathcal{N}(\nu,\frac{\varepsilon}{L})$, the bound for
$\mathcal{N}(\mu,\frac{\varepsilon}{L})$ follows by symmetry. We proceed via
the marginal constraints on $p_{\varepsilon}$ from (2.5): for all
$x\in\operatorname{supp}(\mu)$ and $y\in\operatorname{supp}(\nu)$,

$1=p_{\varepsilon}(x,y)\int\frac{p_{\varepsilon}(x,y^{\prime})}{p_{\varepsilon}(x,y)}\mathrm{d}\nu(y^{\prime}).$
(5.5)

Applying Proposition 15 to Equation (5.5) yields,

$\displaystyle 1$ $\displaystyle\geqslant p_{\varepsilon}(x,y)\int_{B^{\rm
cl}(y,\frac{4\varepsilon}{L})}\frac{p_{\varepsilon}(x,y^{\prime})}{p_{\varepsilon}(x,y)}\mathrm{d}\nu(y^{\prime})$
$\displaystyle\geqslant p_{\varepsilon}(x,y)\int_{B^{\rm
cl}(y,\frac{4\varepsilon}{L})}e^{-\frac{2L}{\varepsilon}\|y^{\prime}-y\|}\mathrm{d}\nu(y^{\prime})$
$\displaystyle\geqslant e^{-8}\cdot p_{\varepsilon}(x,y)\cdot\nu(B^{\rm
cl}(y,\frac{4\varepsilon}{L})).$

Since $y\in\operatorname{supp}(\nu)$, $\nu(B^{\rm
cl}(y,\frac{4\varepsilon}{L}))>0$, so we can rearrange this inequality and
apply the marginal constraints (2.5) once more to yield

$\displaystyle\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}$
$\displaystyle=\int p_{\varepsilon}(x,y)^{2}\mathrm{d}(\mu\otimes\nu)(x,y)$
$\displaystyle\lesssim\int\nu(B^{\rm
cl}(y,\frac{4\varepsilon}{L}))^{-1}p_{\varepsilon}(x,y)\mathrm{d}(\mu\otimes\nu)(x,y)$
$\displaystyle=\int\nu(B^{\rm
cl}(y,\frac{4\varepsilon}{L}))^{-1}\mathrm{d}\nu(y).$

The result follows from Proposition 18. ∎

###  5.3 MID scaling for maps in empirical norm

As we discuss in the previous section, to prove Theorem 7 and Theorem 8, we
reduce to the bound on the bias from Lemma 17. We emphasize that bounds on
entropic maps and densities with exponential dependence on $1/\varepsilon$ are
known from [RS22]. To prove such bounds without incurring exponential factors
requires further work beyond the previous sections. The main idea is to
consider the following rounded dual potential, defined for all
$x\in\operatorname{supp}(\mu)$ as

$\tilde{f}_{\varepsilon}(x):=-\varepsilon\log\Big{(}\frac{1}{n}\sum_{j=1}^{n}e^{-\varepsilon^{-1}(c(x,y_{j})-g_{\varepsilon}(y_{j}))}\Big{)}.$
(5.6)

Let the corresponding density be defined for all
$x\in\operatorname{supp}(\mu)$ and $y\in\operatorname{supp}(\nu)$ as
$\tilde{p}_{\varepsilon}(x,y):=e^{-\varepsilon^{-1}(c(x,y)-\tilde{f}_{\varepsilon}(x)-g_{\varepsilon}(y))}$;
note that $\tilde{p}_{\varepsilon}$ is such that for all
$x\in\operatorname{supp}(\mu)$,

$1=\frac{1}{n}\sum_{j=1}^{n}\tilde{p}_{\varepsilon}(x,y_{j}).$

This fact allows us to compare $\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)$
with $\frac{1}{n}\tilde{p}_{\varepsilon}(x,\cdot)$ as probability
distributions on $\mathcal{Y}$. The following Lemma is then a consequence of
Pinsker’s inequality, cancellation of some terms, and a crucial use of the
monotonicity of the empirical dual under marginal rounding from Proposition 13
to replace $\tilde{f}_{\varepsilon}$ with its un-rounded counterpart
$f_{\varepsilon}$.

######  Lemma 19.

Let $\tilde{f}_{\varepsilon}$ and $\tilde{p}_{\varepsilon}$ be as above, and
suppose the diameter of $\operatorname{supp}(\nu)$ is at most $R$. Then

$\mathbb{E}\Big{[}\Big{\|}\hat{T}_{\varepsilon}-\frac{1}{n}\sum_{j=1}^{n}y_{j}\tilde{p}_{\varepsilon}(x,y_{j})\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}\lesssim\frac{R^{2}}{\varepsilon}\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)].$

However, this Lemma does not yet yield Theorem 7 as it involves the rounded
density $\tilde{p}_{\varepsilon}$. The following calculation addresses this
issue.

######  Lemma 20.

Let $\tilde{f}_{\varepsilon}$ and $\tilde{p}_{\varepsilon}$ be as above. Then

$\mathbb{E}[\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|_{L^{2}(\hat{\mu})}^{2}]\lesssim\mathbb{E}\Big{[}\Big{\|}\hat{T}_{\varepsilon}-\frac{1}{n}\sum_{j=1}^{n}y_{j}\tilde{p}_{\varepsilon}(x,y_{j})\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}+R^{2}\cdot\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}.$

We first dispatch Theorem 7, and then prove these lemmas.

###### Proof of Theorem 7.

Combining Lemma 17 with the above two lemmas yields

$\mathbb{E}[\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|_{L^{2}(\hat{\mu})}^{2}]\lesssim
R^{2}\Big{\\{}\frac{1}{\varepsilon}\cdot\sqrt{\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}}+\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}\Big{\\}}.$

Now observe that the statement of Theorem 7 is trivial when
$\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})\geqslant
n$, since we always have the bound $2R^{2}$. Hence it suffices to consider the
case
$\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})\leqslant
n$, in which case we may conclude from the above inequality. ∎

###### Proof of Lemma 19.

To prove this result, let us first assume that $0\in\operatorname{supp}(\nu)$
so that for each $y\in\operatorname{supp}(\nu)$, we have $\|y\|\leqslant R$.
Then for each $x\in\mathcal{X}$, we apply triangle inequality and Pinsker’s
inequality to see that

$\displaystyle\Big{\|}\hat{T}_{\varepsilon}(x)-\frac{1}{n}\sum_{j=1}^{n}y_{j}\tilde{p}_{\varepsilon}(x,y_{j})\Big{\|}$
$\displaystyle\leqslant\frac{R}{n}\sum_{j=1}^{n}|\tilde{p}_{\varepsilon}(x,y_{j})-\hat{p}_{\varepsilon}(x,y_{j})|$
$\displaystyle\lesssim
R\sqrt{\operatorname{KL}(\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)\,\|\,\frac{1}{n}\tilde{p}_{\varepsilon}(x,\cdot))}.$

Therefore,

$\displaystyle\Big{\|}\hat{T}_{\varepsilon}-\frac{1}{n}\sum_{j=1}^{n}y_{j}\tilde{p}_{\varepsilon}(x,y_{j})$
$\displaystyle\Big{\|}^{2}_{L^{2}(\hat{\mu})}\lesssim
R^{2}\frac{1}{n}\sum_{i=1}^{n}\operatorname{KL}(\frac{1}{n}\hat{p}_{\varepsilon}(x_{i},\cdot)\,\|\,\frac{1}{n}\tilde{p}_{\varepsilon}(x_{i},\cdot))$
$\displaystyle=\frac{R^{2}}{\varepsilon}\sum_{i,j=1}^{n}\frac{1}{n^{2}}\hat{p}_{\varepsilon}(x_{i},y_{j})(\hat{f}_{\varepsilon}(x_{i})-\tilde{f}_{\varepsilon}(x_{i})+\hat{g}_{\varepsilon}(y_{j})-g_{\varepsilon}(y_{j}))$
$\displaystyle=\frac{R^{2}}{\varepsilon}\big{(}\hat{\mu}(\hat{f}_{\varepsilon}-\tilde{f}_{\varepsilon})+\hat{\nu}(\hat{g}_{\varepsilon}-g_{\varepsilon})\big{)},$

where we used the marginal constraints of $\hat{p}_{\varepsilon}$ for the last
step. Using the notation, as in the previous section,
$\hat{\Phi}_{\varepsilon}:=\Phi_{\varepsilon}^{\hat{\mu}\hat{\nu}}$, we
recognize the result as a difference of $\hat{\Phi}_{\varepsilon}$, and apply
Proposition 13 on marginal rounding improving dual objective value, to
conclude that

$\displaystyle\Big{\|}\hat{T}_{\varepsilon}-\frac{1}{n}\sum_{j=1}^{n}y_{j}\tilde{p}_{\varepsilon}(x,y_{j})\|^{2}_{L^{2}(\hat{\mu})}$
$\displaystyle\lesssim\frac{R^{2}}{\varepsilon}\big{(}\hat{\mu}(\hat{f}_{\varepsilon}-\tilde{f}_{\varepsilon})+\hat{\nu}(\hat{g}_{\varepsilon}-g_{\varepsilon})\big{)}$
$\displaystyle=\frac{R^{2}}{\varepsilon}\big{(}\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(\tilde{f}_{\varepsilon},g_{\varepsilon})\big{)}$
$\displaystyle\leqslant\frac{R^{2}}{\varepsilon}\big{(}\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\big{)}.$

Taking expectations,
$\mathbb{E}[\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]=\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})$,
and we conclude the result. For the general case where $0$ may not be in
$\operatorname{supp}(\nu)$, we can perform the above argument with suitably
offset $y$. ∎

###### Proof of Lemma 20.

As above, let us first assume that $0\in\operatorname{supp}(\nu)$ so that for
each $y\in\operatorname{supp}(\nu)$, we have $\|y\|\leqslant R$. We apply
Young’s inequality twice, first comparing $T_{\varepsilon}(x)$ to the
empirical version $\frac{1}{n}\sum_{j=1}^{n}y_{j}p_{\varepsilon}(x,y_{j})$,
and then the empirical version to the version involving
$\tilde{p}_{\varepsilon}$:

$\displaystyle\mathbb{E}[\|\hat{T}_{\varepsilon}-T_{\varepsilon}\|_{L^{2}(\hat{\mu})}^{2}]$
$\displaystyle\lesssim\mathbb{E}\Big{[}\Big{\|}\hat{T}_{\varepsilon}-\frac{1}{n}\sum_{j=1}^{n}y_{j}\tilde{p}_{\varepsilon}(x,y_{j})\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}$
$\displaystyle+\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{j=1}^{n}y_{j}(\tilde{p}_{\varepsilon}(x,y_{j})-p_{\varepsilon}(x,y_{j}))\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}$
$\displaystyle+\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{j=1}^{n}y_{j}p_{\varepsilon}(x,y_{j})-T_{\varepsilon}(x)\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}$

The third term is controlled as

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}$
$\displaystyle\sum_{j=1}^{n}y_{j}p_{\varepsilon}(x,y_{j})-T_{\varepsilon}(x)\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\frac{1}{n^{2}}\sum_{j,k=1}^{n}\langle
y_{j}p_{\varepsilon}(x,y_{j})-T_{\varepsilon}(x),y_{k}p_{\varepsilon}(x,y_{k})-T_{\varepsilon}(x)\rangle_{L^{2}(\hat{\mu})}\Big{]}$
$\displaystyle=\frac{1}{n}\|yp_{\varepsilon}(x,y)-T_{\varepsilon}(x)\|_{L^{2}(\mu\otimes\nu)}^{2}\lesssim\frac{R^{2}}{n}\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2},$

where the second equality follows because, for $j\neq k$, $y_{j}$ and $y_{k}$
are iid draws from $\nu$, so that these terms cancel. For the second term, we
begin by observing that for each $y_{j}$,

$\tilde{p}_{\varepsilon}(x,y_{j})=\frac{p_{\varepsilon}(x,y_{j})}{\frac{1}{n}\sum_{k=1}^{n}p_{\varepsilon}(x,y_{k})}.$

We thus apply triangle inequality and this equation to see that

$\displaystyle\Big{\|}\frac{1}{n}\sum_{j=1}^{n}y_{j}(\tilde{p}_{\varepsilon}(x,y_{j})-p_{\varepsilon}(x,y_{j}))\Big{\|}$
$\displaystyle\leqslant\frac{R}{n}\sum_{j=1}^{n}|\tilde{p}_{\varepsilon}(x,y_{j})-p_{\varepsilon}(x,y_{j})|$
$\displaystyle=\frac{R}{n}\sum_{j=1}^{n}p_{\varepsilon}(x,y_{j})\Big{|}\frac{1}{\frac{1}{n}\sum_{k=1}^{n}p_{\varepsilon}(x,y_{k})}-1\Big{|}$
$\displaystyle=R\Big{|}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x,y_{j})-1\Big{|}.$

Taking the $\|\cdot\|_{L^{2}(\hat{\mu})}^{2}$ norm, we recognize this as the
squared norm of the first component of
$\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})$, and use the
bound in Equation (5.2) to conclude

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{j=1}^{n}y_{j}(\tilde{p}_{\varepsilon}(x,y_{j})-p_{\varepsilon}(x,y_{j}))\Big{\|}_{L^{2}(\hat{\mu})}^{2}\Big{]}$
$\displaystyle\leqslant
R^{2}\mathbb{E}[\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|^{2}_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}]$
$\displaystyle\lesssim\frac{R^{2}}{n}\|p_{\varepsilon}\|^{2}_{L^{2}(\mu\otimes\nu)}.$

Applying Lemma 16 yields the result. For the general case where $0$ may not be
in $\operatorname{supp}(\nu)$, we can perform the above argument with suitably
offset $y$. ∎

###  5.4 MID scaling for densities in empirical norm

We prove Theorem 8 on empirical norm convergence of the entropic OT density
using the techniques introduced in the previous section. We prove the
following two lemmas.

######  Lemma 21.

Let $\tilde{f}_{\varepsilon},\tilde{p}_{\varepsilon}$ be as in the previous
section. Then

$\mathbb{E}[\|\hat{p}_{\varepsilon}-\tilde{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\lesssim\frac{1}{\sqrt{\varepsilon}}\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)]^{1/2}$

######  Lemma 22.

Let $\tilde{f}_{\varepsilon},\tilde{p}_{\varepsilon}$ be as in the previous
section. Then

$\mathbb{E}[\|p_{\varepsilon}-\hat{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\lesssim\mathbb{E}[\|\hat{p}_{\varepsilon}-\tilde{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]+\sqrt{\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}}.$

We first dispatch Theorem 8, and then prove these lemmas.

###### Proof of Theorem 8.

Combining the above two lemmas with Lemma 17 yields

$\mathbb{E}[\|p_{\varepsilon}-\hat{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\lesssim\frac{1}{\sqrt{\varepsilon}}\Big{(}\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}\Big{)}^{1/4}+\sqrt{\frac{\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})}{n}}.$

Now, observe that the statement of Theorem 8 is trivial when
$\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})\geqslant
n$, since we always have the bound $\lesssim 1$ by triangle inequality. Hence
it suffices to consider the case
$\mathcal{N}(\mu,\frac{\varepsilon}{L})\land\mathcal{N}(\nu,\frac{\varepsilon}{L})\leqslant
n$, in which case we may conclude from the above inequality. ∎

###### Proof of Lemma 21.

Pinsker’s and Jensen’s imply

$\displaystyle\|\tilde{p}_{\varepsilon}-\hat{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}$
$\displaystyle\lesssim\frac{1}{n}\sum_{i=1}^{n}\sqrt{\operatorname{KL}(\frac{1}{n}\hat{p}_{\varepsilon}(x_{i},\cdot)\,\|\,\frac{1}{n}\tilde{p}_{\varepsilon}(x_{i},\cdot))}$
$\displaystyle\leqslant\Big{(}\frac{1}{n}\sum_{i=1}^{n}\operatorname{KL}(\frac{1}{n}\hat{p}_{\varepsilon}(x_{i},\cdot)\,\|\,\frac{1}{n}\tilde{p}_{\varepsilon}(x_{i},\cdot))\Big{)}^{1/2}.$

Taking the expectation and applying Jensen’s once more yields

$\mathbb{E}[\|\tilde{p}_{\varepsilon}-\hat{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\lesssim\mathbb{E}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\operatorname{KL}(\frac{1}{n}\hat{p}_{\varepsilon}(x_{i},\cdot)\,\|\,\frac{1}{n}\tilde{p}_{\varepsilon}(x_{i},\cdot))\Big{]}^{1/2}.$

The statement then follows as in Lemma 19. ∎

###### Proof of Lemma 22.

Apply triangle inequality:

$\mathbb{E}[\|p_{\varepsilon}-\hat{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\leqslant\mathbb{E}[\|\hat{p}_{\varepsilon}-\tilde{p}_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]+\mathbb{E}[\|\tilde{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}].$

For the second term we use the same reasoning as in the proof of Lemma 20 to
observe that

$\|\tilde{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}=\frac{1}{n^{2}}\sum_{i,j=1}^{n}|\tilde{p}_{\varepsilon}(x_{i},y_{j})-p_{\varepsilon}(x_{i},y_{j})|=\frac{1}{n}\sum_{i=1}^{n}\Big{|}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x_{i},y_{j})-1\Big{|}.$

Applying Cauchy-Schwarz we find that

$\|\tilde{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}\leqslant\Big{(}\frac{1}{n}\sum_{i=1}^{n}\Big{(}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x_{i},y_{j})-1\Big{)}^{2}\Big{)}^{1/2}\leqslant\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}.$

Taking expectations and applying Cauchy-Schwarz once more, we can apply
Equation (5.2) to yield

$\mathbb{E}[\|\tilde{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{1}(\hat{\mu}\otimes\hat{\nu})}]\leqslant\mathbb{E}[\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}^{2}]^{1/2}\lesssim\frac{\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}}{\sqrt{n}}.$

Finally, Lemma 16 yields the result. ∎

##  6 Proofs of MID scaling with fast rates on manifolds

In this section, we give the proofs of our stronger results when $\nu$ is
supported on an embedded Riemannian manifold. To introduce our approach,
recall that fast rates of convergence for the entropic OT dual potentials,
map, density, and bias are known, but at the price of exponential factors in
$1/\varepsilon$ [RS22]. As we mention in the previous section, those estimates
are established through strong concavity of the empirical dual objective, but
because the strong concavity parameter is exponentially small, such an
approach is inadequate for establishing MID scaling. The techniques in the
previous section represent a very weak form of this approach, using only
concavity rather than strong concavity to replace exponential factors with MID
scaling. In this section, we power our arguments with a _quadratic growth_
condition [KNS16], which is a stronger condition than concavity alone, yet
still weaker than true strong concavity.

In this regard, our approach is inspired by recent work [Mar21], which has
found that a sufficient condition for a quadratic growth condition for the
entropic OT dual is a Poincaré inequality. Indeed, [Mar21] shows that given
probability measures $P,Q$ on $\mathbb{R}^{d}$, if $P$ satisfies a Poincaré
inequality with constant $C_{P}$, then for any dual potentials $f,g$,

$\|f-f_{\varepsilon}^{PQ}\|^{2}_{L^{2}(P)}\lesssim\frac{L^{2}}{\varepsilon
C_{P}}(\Phi_{\varepsilon}^{PQ}(f_{\varepsilon}^{PQ},g_{\varepsilon}^{PQ})-\Phi_{\varepsilon}^{PQ}(f,g)),$
(6.1)

where $f_{\varepsilon}^{PQ},g_{\varepsilon}^{PQ}$ are the optimal dual
potentials from $P$ to $Q$ and we are suppressing numerical constants.
However, this estimate cannot directly establish quadratic growth for the
empirical dual $\hat{\Phi}_{\varepsilon}$ since it relies on a Poincaré
inequality for the source measure $P$. We emphasize that our approach is
fundamentally about the empirical dual rather than the population dual, since
working with the empirical dual is what allows us to bypass empirical
processes by reducing to computing variances of population quantities
(consider, for example, our proof of Lemma 17).

As our first major step in this section, we develop quadratic growth
inequalities for the empirical dual. In particular, in section 6.1 we use
different techniques than [Mar21] to show that under an empirical analog of a
Poincaré inequality – a spectral gap of the random geometric graph (RGG) of
$\nu$ – an analog of (6.1) holds for the empirical dual
$\hat{\Phi}_{\varepsilon}$. Using recent advances in the theory of RGGs on
embedded manifolds [GTGHS20] which we describe in Appendix A.2, a spectral gap
for the RGG of $\nu$ then follows from a Poincaré inequality for $\nu$ itself,
which is entailed by Assumption 2 and Assumption 3. To summarize, the primary
uses of our embedded manifold assumptions are that they imply a spectral gap
for a weighted Laplacian associated to $\nu$ (Proposition 37), which then
implies a spectral gap for the RGG of $\nu$ using spectral convergence theory
[GTGHS20], which finally yields quadratic growth for the empirical dual; this
argument is encapsulated in Lemma 23.

After we prove Lemma 23 in section 6.1, in section 6.2 we next bound the $f$
dual potentials in terms of the $g$ dual potentials, both in population and
empirical norms, while only picking up MID scaling factors. These results are
combined in section 6.3 to yield convergence of the $g$ dual potentials in
empirical norm, which then implies Theorem 12 and all of Theorem 9 on dual
potential convergence except the convergence of the $g$ dual potentials in
population norm. In section 6.4, we complete the proof of Theorem 9 by
applying the previous results to establish the convergence of the $g$ dual
potentials in population norm. Finally, in section 6.5 we prove Corollary 10
and Corollary 11.

Throughout, we work under the assumption that $n$ is large enough that

$\big{(}\frac{\varepsilon}{L}\big{)}^{2d_{\nu}}\gtrsim\frac{1}{n}\Big{(}\log\Big{(}\frac{Ln}{\varepsilon}\Big{)}+\frac{1}{\varepsilon}\Big{)}.$
(6.2)

We may assume $n$ is this large without loss of generality, since otherwise it
is not hard to check that our bounds are worse than the trivial ones.

###  6.1 Quadratic growth for the empirical dual

In this section, we prove the following quadratic growth inequality for the
empirical entropic OT dual function.

######  Lemma 23 (Quadratic growth for the empirical dual).

Let $\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}\colon
L^{\infty}(\hat{\nu})\to\mathbb{R}$ denote the empirical dual objective with
$f$ rounded, namely

$\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(g):=\hat{\mu}\big{(}-\varepsilon\log\big{(}\frac{1}{n}\sum_{j=1}^{n}e^{-\varepsilon^{-1}(c(x,y_{j})-g(y_{j}))}\big{)}\big{)}+\hat{\nu}(g).$

Then, for $\varepsilon$ sufficiently small, we have

$\varepsilon\Big{(}\frac{\varepsilon}{L}\Big{)}^{d_{\nu}+2}\cdot\|g-\hat{g}_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}\lesssim\|g-\hat{g}_{\varepsilon}\|_{L^{\infty}(\hat{\nu})}^{2}(\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(\hat{g}_{\varepsilon})-\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(g)),\quad\quad\forall
g\in L^{\infty}(\hat{\nu}),\,\,\hat{\nu}(g)=0.$

This Lemma is proven by reducing the claim to a spectral gap for the random
geometric graph (RGG) of $\nu$. Using recent fundamental work on the spectral
convergence of RGGs of embedded manifolds [GTGHS20], we conclude the result.
We include this background material in Appendix A.2.

###### Proof of Lemma 23.

Fix $g\in L^{\infty}(\hat{\nu})$ with $\hat{\nu}(g)=0$, and put
$\alpha:=g-\hat{g}_{\varepsilon}$. Let

$\psi(t):=-\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(\hat{g}_{\varepsilon}+t\alpha),$

and also define

$q_{t}(x_{i},y_{j}):=\frac{e^{-\varepsilon^{-1}(c(x_{i},y_{j})-(\hat{g}_{\varepsilon}(y_{j})+t\alpha(y_{j}))}}{\frac{1}{n}\sum_{k=1}^{n}e^{-\varepsilon^{-1}(c(x_{i},y_{k})-(\hat{g}_{\varepsilon}(y_{k})+t\alpha(y_{k}))}}$

Then it is straightforward to verify that $\psi$ is a convex function with
minimum attained at $t=0$ such that

$\psi^{\prime\prime}(t)=\frac{1}{\varepsilon}\hat{\mu}\big{(}\operatorname{Var}_{\frac{1}{n}q_{t}(x,\cdot)}(\alpha)\big{)}.$

Note that,

$q_{t}(x_{i},y_{j})\geqslant
e^{-2t\varepsilon^{-1}\|\alpha\|_{L^{\infty}(\hat{\nu})}}q_{0}(x_{i},y_{j})=e^{-2t\varepsilon^{-1}\|\alpha\|_{L^{\infty}(\hat{\nu})}}\hat{p}_{\varepsilon}(x_{i},y_{j}).$

Therefore,

$\displaystyle\psi^{\prime\prime}(t)$
$\displaystyle=\frac{1}{2\varepsilon}\hat{\mu}\big{(}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}q_{t}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\big{)}$
$\displaystyle\geqslant\frac{e^{-4t\varepsilon^{-1}\|\alpha\|_{L^{\infty}(\hat{\nu})}}}{2\varepsilon}\hat{\mu}\big{(}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\big{)},$

It follows that, for $t>0$,

$\displaystyle
t^{2}\frac{e^{-4t\varepsilon^{-1}\|\alpha\|_{L^{\infty}(\hat{\nu})}}}{4\varepsilon}\hat{\mu}\big{(}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\big{)}\leqslant\psi(t)-\psi(0)\leqslant\psi(1)-\psi(0),$

where the first inequality is strong convexity for $\psi$ on the interval
$(-\infty,t]$, and the second inequality follows because $\psi$ is a convex
function with minimizer at $t=0$. If $\|\alpha\|_{L^{\infty}(\hat{\nu})}=0$,
then the inequality is trivially true. Otherwise, we may set
$t=\varepsilon/4\|\alpha\|_{L^{\infty}(\hat{\nu})}$ to yield

$\frac{\varepsilon}{\|\alpha\|^{2}_{L^{\infty}(\hat{\nu})}}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\lesssim\psi(1)-\psi(0).$

It thus suffices to show that

$\hat{\mu}\big{(}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\big{)}\gtrsim\Big{(}\frac{\varepsilon}{L}\Big{)}^{d_{\nu}+2}\hat{\nu}(\alpha^{2}),$
(6.3)

Observe that

$\hat{\mu}\big{(}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\big{)}=\frac{1}{n^{2}}\sum_{j,k=1}^{n}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\hat{p}_{\varepsilon}(x_{i},y_{j})\hat{p}_{\varepsilon}(x_{i},y_{k})\Big{)}(\alpha(y_{j})-\alpha(y_{k}))^{2}.$

By Proposition 15,

$\hat{p}_{\varepsilon}(x_{i},y_{j})\geqslant
e^{-2\frac{L}{\varepsilon}\|y_{j}-y_{k}\|}\hat{p}_{\varepsilon}(x_{i},y_{k}),\quad\quad\forall
j,k\in[n].$

Hence

$\displaystyle\frac{1}{n^{2}}\sum_{j,k=1}^{n}\Big{(}\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\hat{p}_{\varepsilon}(x_{i},y_{j})\hat{p}_{\varepsilon}(x_{i},y_{k})\Big{)}(\alpha(y_{j})-\alpha(y_{k}))^{2}\geqslant$
$\displaystyle\frac{1}{n^{2}}\sum_{j,k=1}^{n}e^{-2\frac{L}{\varepsilon}\|y_{j}-y_{k}\|}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\hat{p}_{\varepsilon}(x_{i},y_{k})^{2}\Big{)}(\alpha(y_{j})-\alpha(y_{k}))^{2}$
$\displaystyle\geqslant\frac{1}{n^{2}}\sum_{j,k=1}^{n}e^{-2\frac{L}{\varepsilon}\|y_{j}-y_{k}\|}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\hat{p}_{\varepsilon}(x_{i},y_{k})\Big{)}^{2}(\alpha(y_{j})-\alpha(y_{k}))^{2}$
$\displaystyle=\frac{1}{n^{2}}\sum_{j,k=1}^{n}e^{-2\frac{L}{\varepsilon}\|y_{j}-y_{k}\|}(\alpha(y_{j})-\alpha(y_{k}))^{2}.$

Now, form the RGG with threshold $\delta=\frac{\varepsilon}{L}$, so that
$y_{j}\sim y_{k}$ if and only if
$\|y_{j}-y_{k}\|\leqslant\frac{\varepsilon}{L}$. Then

$\hat{\mu}\big{(}\mathbb{E}_{y,y^{\prime}\sim\frac{1}{n}\hat{p}_{\varepsilon}(x,\cdot)}[(\alpha(y)-\alpha(y^{\prime}))^{2}]\big{)}\gtrsim\frac{1}{n^{2}}\sum_{j\sim
k}(\alpha(y_{j})-\alpha(y_{k}))^{2}.$

Applying Theorem 36 from Appendix A.2, we arrive at (6.3), and so the result
follows. ∎

###  6.2 Reduction from $f$ dual potentials to $g$ dual potentials

In this section, we will prove the following Lemma, which shows that although
the $f$ dual potentials are defined on the support of $\mu$ – a potentially
higher dimensional set than the support of $\nu$ – their convergence can be
controlled by the convergence of the $g$ dual potentials while only incurring
MID scaling factors.

######  Lemma 24 (Reduction from $f$ dual potentials to $g$ dual potentials).

We have

$\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|_{L^{2}(\hat{\mu})}^{2}]\lesssim\Big{(}\frac{L}{\varepsilon}\Big{)}^{3d_{\nu}}\big{(}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}]+\frac{1+\varepsilon^{2}}{n}\big{)},$

and similarly

$\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|_{L^{2}(\mu)}^{2}]\lesssim\Big{(}\frac{L}{\varepsilon}\Big{)}^{3d_{\nu}}\big{(}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}]+\frac{1+\varepsilon^{2}}{n}\big{)}.$

To prove Lemma 24, as well as for the proofs in the following sections, the
following helper lemmas are convenient (proven in Appendix B.2).

######  Lemma 25 (Mass of empirical balls).

With probability at least $1-\frac{1}{n}e^{-10/\varepsilon}$,

$\inf_{z\in
N}\hat{\nu}(B(z,\frac{\varepsilon}{L}))\gtrsim\Big{(}\frac{\varepsilon}{L}\Big{)}^{d_{\nu}}.$

######  Lemma 26 (Uniform control on entropic densities).

We have the uniform bound,

$\|p_{\varepsilon}\|_{L^{\infty}(\mu\otimes\nu)}\lesssim\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}.$

And, with probability at least $1-\frac{1}{n}e^{-10/\varepsilon}$,

$\|\hat{p}_{\varepsilon}\|_{L^{\infty}(\mu\otimes\nu)}\lesssim\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}.$

###### Proof of Lemma 24.

Let

$\tilde{f}_{\varepsilon}(x):=-\varepsilon\log\Big{(}\frac{1}{n}\sum_{j=1}^{n}e^{-\frac{1}{\varepsilon}(c(x,y_{j})-g_{\varepsilon}(y_{j}))}\Big{)}.$

Note that, for all $x\in\operatorname{supp}\mu$,

$(\hat{f}_{\varepsilon}(x)-f_{\varepsilon}(x))^{2}\lesssim(\hat{f}_{\varepsilon}(x)-\tilde{f}_{\varepsilon}(x))^{2}+(\tilde{f}_{\varepsilon}(x)-f_{\varepsilon}(x))^{2},$

and we’ll begin by studying each of these terms separately.

For the first term, put $\alpha:=g_{\varepsilon}-\hat{g}_{\varepsilon}$, and
let $\varphi\colon[0,1]\to\mathbb{R}$ be defined as

$\varphi(t):=-\varepsilon\log\Big{(}\frac{1}{n}\sum_{j=1}^{n}e^{-\varepsilon^{-1}(c(x,y_{j})-\hat{g}_{\varepsilon}(y_{j})-t\alpha(y_{j})}\Big{)},$

and notice $\varphi(0)=\hat{f}_{\varepsilon}(x)$ while
$\varphi(1)=\tilde{f}_{\varepsilon}(x)$. For $y\in\operatorname{supp}(\nu)$,
put

$q_{t}(x,y):=\frac{e^{-\varepsilon^{-1}(c(x,y)-\hat{g}_{\varepsilon}(y)-t\alpha(y))}}{\frac{1}{n}\sum_{k=1}^{n}e^{-\varepsilon^{-1}(c(x,y_{k})-\hat{g}_{\varepsilon}(y_{k})-t\alpha(y_{k}))}}$

Then

$\displaystyle|\varphi^{\prime}(t)|$
$\displaystyle=\Big{|}\frac{1}{n}\sum_{j=1}^{n}\alpha(y_{j})q_{t}(x,y_{j})\Big{|}\leqslant\|\alpha\|_{L^{2}(\hat{\nu})}\Big{(}\frac{1}{n}\sum_{j=1}^{n}q_{t}(x,y_{j})^{2}\Big{)}^{1/2}.$

Using Proposition 15, we find that for any
$y,y^{\prime}\in\operatorname{supp}(\nu)$ and $t\in[0,1]$,

$\displaystyle|\log q_{t}(x,y)-\log q_{t}(x,y^{\prime})|$
$\displaystyle=\frac{1}{\varepsilon}|c(x,y)-\hat{g}_{\varepsilon}(y)-t\alpha(y)-(c(x,y^{\prime})-\hat{g}_{\varepsilon}(y^{\prime})-t\alpha(y^{\prime}))|$
$\displaystyle\leqslant\frac{2L}{\varepsilon}\|y-y^{\prime}\|.$

Therefore, for any $j\in[n]$,

$1=\frac{1}{n}\sum_{k=1}^{n}q_{t}(x,y_{k})\gtrsim
q_{t}(x,y_{j})\hat{\nu}(B(y_{j},\frac{\varepsilon}{L}))\geqslant
q_{t}(x,y_{j})\inf_{z\in N}\hat{\nu}(B(z,\frac{\varepsilon}{L})).$

So that

$\displaystyle|\hat{f}_{\varepsilon}(x)-\tilde{f}_{\varepsilon}(x)|\leqslant\int_{0}^{1}|\varphi^{\prime}(t)|\mathrm{d}t$
$\displaystyle\leqslant\|\alpha\|_{L^{2}(\hat{\nu})}\int_{0}^{1}\Big{(}\frac{1}{n}\sum_{j=1}^{n}q_{t}(x,y_{j})^{2}\Big{)}^{1/2}\mathrm{d}t$
$\displaystyle\lesssim\|\alpha\|_{L^{2}(\hat{\nu})}\sup_{z\in
N}\hat{\nu}(B(z,\frac{\varepsilon}{L}))^{-1/2}\int_{0}^{1}\Big{(}\frac{1}{n}\sum_{j=1}^{n}q_{t}(x,y_{j})\Big{)}^{1/2}\mathrm{d}t$
$\displaystyle=\|\alpha\|_{L^{2}(\hat{\nu})}\sup_{z\in
N}\hat{\nu}(B(z,\frac{\varepsilon}{L}))^{-1/2}.$ (6.4)

Now consider the $(\tilde{f}_{\varepsilon}(x)-f_{\varepsilon}(x))^{2}$ term.
Note that

$|\tilde{f}_{\varepsilon}(x)-f_{\varepsilon}(x)|=\Big{|}\varepsilon\log\Big{(}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x,y_{j})\Big{)}\Big{|}.$

Since

$1=\int p_{\varepsilon}(x,y)\mathrm{d}\nu(y),$

there must exist some $y^{\prime}\in\operatorname{supp}(\nu)$ such that
$p_{\varepsilon}(x,y^{\prime})\geqslant 1$. By Proposition 15, this implies

$\displaystyle\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x,y_{j})\geqslant\frac{1}{n}\sum_{j=1}^{n}\frac{p_{\varepsilon}(x,y_{j})}{p_{\varepsilon}(x,y^{\prime})}\geqslant\frac{1}{n}\sum_{j=1}^{n}e^{-\frac{2L}{\varepsilon}\|y_{j}-y^{\prime}\|}\gtrsim\hat{\nu}(B(y^{\prime},\frac{\varepsilon}{L})).$

Using Lipschitz-ness of $\log$,

$|\tilde{f}_{\varepsilon}(x)-f_{\varepsilon}(x)|\lesssim\varepsilon\hat{\nu}(B(y^{\prime},\frac{\varepsilon}{L}))^{-1}\Big{|}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x,y_{j})-1\Big{|}.$
(6.5)

Now, let $\mathcal{E}$ denote the event of Lemma 25. Observe that by the
pointwise control in Proposition 14 and since
$\mathbb{P}[\mathcal{E}^{c}]\leqslant\frac{1}{n}$,

$\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}]\lesssim\mathbb{E}[\mathbbold{1}[\mathcal{E}]\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}]+\frac{1}{n}.$

Combining Equations (6.4) and (6.5) yields

$\displaystyle\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}]$
$\displaystyle\lesssim\mathbb{E}[\mathbbold{1}[\mathcal{E}]\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}]+\frac{1}{n}$
$\displaystyle\lesssim\mathbb{E}[\mathbbold{1}[\mathcal{E}](\|\hat{f}_{\varepsilon}-\tilde{f}_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\tilde{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})})]+\frac{1}{n}$
$\displaystyle\lesssim\Big{(}\frac{L}{\varepsilon}\Big{)}^{2d_{\nu}}\mathbb{E}\Big{[}\mathbbold{1}[\mathcal{E}]\Big{\\{}\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}+\frac{\varepsilon^{2}}{n}\sum_{i=1}^{n}\Big{(}\frac{1}{n}\sum_{j=1}^{n}p_{\varepsilon}(x_{i},y_{j})-1\Big{)}^{2}\Big{\\}}\Big{]}+\frac{1}{n}$
$\displaystyle\leqslant\Big{(}\frac{L}{\varepsilon}\Big{)}^{2d_{\nu}}\mathbb{E}\Big{[}\mathbbold{1}[\mathcal{E}]\Big{\\{}\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}+\frac{\varepsilon^{2}}{n}\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|^{2}_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}\Big{\\}}\Big{]}+\frac{1}{n}$
$\displaystyle\lesssim\Big{(}\frac{L}{\varepsilon}\Big{)}^{2d_{\nu}}\Big{\\{}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]+\frac{\varepsilon^{2}}{n}\|p_{\varepsilon}\|_{L^{2}(\mu\otimes\nu)}^{2}\Big{\\}}+\frac{1}{n},$

where the final inequality follows from $\mathbbold{1}[\mathcal{E}]\leqslant
1$ and Equation (5.2). By Lemma 16 and Proposition 43 on the covering numbers
of $N$ (proved in Appendix A.3), we conclude the first inequality. The second
follows in the same manner. ∎

###  6.3 MID scaling for the bias and $g$ dual potentials in empirical norm

In this section, we use our quadratic growth inequality from section 6.1 and
our bound on the $f$ dual potentials in terms of the $g$ dual potentials from
section 6.2 to prove the following result, on convergence of the $g$ dual
potentials in empirical norm.

######  Lemma 27 (Convergence of $g$ dual potentials in empirical norm).

We have

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{6d_{\nu}+4}\cdot\frac{1}{n}.$

By the previous section, this implies convergence of the $f$ dual potentials
in both empirical and population norms, and therefore yields all parts of
Theorem 9 other than the population norm convergence of the $g$ dual
potentials, which is proved in the next section. As a byproduct of our proof,
we will also obtain Theorem 12, on MID scaling with fast rates for the bias.

Notice that a $1/\sqrt{n}$ rate follows by combining our result on quadratic
growth for the empirical dual, Lemma 23, with our prior result on the bias,
Lemma 17. To obtain a faster rate, we proceed by a self-bounding argument.

We first bound the bias
$\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]$
in terms of $\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}$
and $\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}$ plus a
$1/n$ term arising from the squared norm of
$\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})$.

######  Lemma 28.

For all $a>0$,

$\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{\mu},\hat{\nu})-\hat{\Phi}_{\varepsilon}(\mu,\nu)]\lesssim\frac{1}{an}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}+a\mathbb{E}\big{[}\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}\big{]}.$

Using our result on the quadratic growth of $\hat{\Phi}_{\varepsilon}$, Lemma
23, the previous step then implies a bound for
$\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}$ in terms of
itself, $1/n$, and
$\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}$.

######  Lemma 29.

For all $a>0$,

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]\lesssim\frac{1}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+2}\Big{\\{}\frac{1}{an}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}+a\mathbb{E}\big{[}\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}\big{]}\Big{\\}}+\frac{1}{n}.$

Combining this inequality with Lemma 24 from section 6.2 and taking the free
parameter $a$ sufficiently small, we can re-arrange and arrive at Lemma 27.
Plugging our bounds on the dual potentials into Lemma 28 then yields Theorem
12. Let’s give these proofs first, before we turn to the proofs of Lemma 28
and Lemma 29.

###### Proof of Lemma 27.

By Lemma 29 and Lemma 24, for all $a>0$,

$\displaystyle\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]\lesssim\frac{1}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+2}\Big{\\{}\frac{1}{an}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}+a\Big{(}\frac{L}{\varepsilon}\Big{)}^{3d_{\nu}}\big{(}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}]+\frac{1+\varepsilon^{2}}{n}\big{)}\Big{\\}}+\frac{1}{n}.$

If we take $a=C\varepsilon\big{(}\frac{\varepsilon}{L}\big{)}^{4d_{\nu}+2}$
for a sufficiently small constant $C$, we can re-arrange to yield

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]\lesssim\big{(}1+\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{6d_{\nu}+4}\cdot\frac{1}{n}\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{6d_{\nu}+4}\cdot\frac{1}{n}.$

∎

###### Proof of Theorem 12.

First notice that
$\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})]-S_{\varepsilon}(\mu,\nu)=\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]\geqslant
0$, so that

$|\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})]-S_{\varepsilon}(\mu,\nu)|=\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})].$

Invoking Lemma 28 with $a=1$, and applying Lemma 24 plus Lemma 27, we obtain

$\displaystyle\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)]\lesssim\big{(}1+\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{9d_{\nu}+4}\cdot\frac{1}{n}\leqslant\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{9d_{\nu}+4}\cdot\frac{1}{n}.$

and whence the result. ∎

The proofs of Lemma 28 and Lemma 29 follow.

###### Proof of Lemma 28.

By Proposition 13, for all $a>0$,

$\displaystyle\mathbb{E}[S_{\varepsilon}(\hat{\mu},$
$\displaystyle\hat{\nu})-S_{\varepsilon}(\mu,\nu)]=\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]$
$\displaystyle=\mathbb{E}[\hat{\Phi}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]$
$\displaystyle\leqslant\mathbb{E}[\langle\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}]$
$\displaystyle\leqslant\frac{1}{a}\mathbb{E}[\|\nabla\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\hat{\nu})}^{2}]+a\mathbb{E}\big{[}\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}\big{]}.$

By Equation (5.2) and Lemma 16, we have

$\mathbb{E}[S_{\varepsilon}(\hat{\mu},\hat{\nu})-S_{\varepsilon}(\mu,\nu)]\lesssim\frac{1}{an}\mathcal{N}(N,\frac{\varepsilon}{L})+a\mathbb{E}\big{[}\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}\big{]}.$

Applying Proposition 43 on the covering covering numbers of $N$ (proved in
Appendix A.3), we may conclude. ∎

###### Proof of Lemma 29.

We begin by re-centering $g_{\varepsilon}$ so that we can apply Lemma 23:

$\displaystyle\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\hat{\nu})}^{2}]$
$\displaystyle\leqslant\mathbb{E}[\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]+\mathbb{E}[(\hat{\nu}(g_{\varepsilon}))^{2}]$
$\displaystyle\lesssim\mathbb{E}[\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]+\frac{1}{n},$
(6.6)

where the last step follows by our convention that $\nu(g_{\varepsilon})=0$
and the pointwise control on $g_{\varepsilon}$ from Proposition 14. Let
$\mathcal{E}$ denote the event described in Lemma 23. Applying Proposition 14
once more we see that

$\displaystyle\mathbb{E}[\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]$
$\displaystyle=\mathbb{E}[\mathbbold{1}[\mathcal{E}]\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]+\mathbb{E}[\mathbbold{1}[\mathcal{E}^{c}]]$
$\displaystyle\lesssim\mathbb{E}[\mathbbold{1}[\mathcal{E}]\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]+\frac{1}{n}$
$\displaystyle\lesssim\mathbb{E}\Big{[}\mathbbold{1}[\mathcal{E}]\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|^{2}_{L^{\infty}(\hat{\nu})}$
$\displaystyle\times\frac{1}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+2}\big{(}\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(\hat{g}_{\varepsilon})-\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(g_{\varepsilon})\big{)}\Big{]}+\frac{1}{n}.$

Using $\mathbbold{1}[\mathcal{E}]\leqslant 1$ and Proposition 14 once more, we
find

$\mathbb{E}[\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]\lesssim\frac{1}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+2}\mathbb{E}\big{[}\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(\hat{g}_{\varepsilon})-\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(g_{\varepsilon})\big{]}.$

By Proposition 13 on marginal rounding

$\Psi_{\varepsilon}^{\hat{\mu}\hat{\nu}}(g_{\varepsilon})\geqslant\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}).$

Hence

$\mathbb{E}[\|\hat{g}_{\varepsilon}-(g_{\varepsilon}-\hat{\nu}(g_{\varepsilon}))\|_{L^{2}(\hat{\nu})}^{2}]\lesssim\frac{1}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+2}\mathbb{E}\big{[}\hat{\Phi}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})\big{]}.$

Since
$\mathbb{E}[\hat{\Phi}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]=\Phi_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})$,
the result follows from Lemma 28. ∎

###  6.4 Fast rates for $g$-dual potentials in population norms

In this section, we establish the remaining part of Theorem 9 by proving the
following Lemma.

######  Lemma 30 (Fast population norm convergence of $g$-dual potentials).

We have

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\nu)}^{2}]\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{13d_{\nu}+8}\cdot\frac{1}{n}.$

Lemma 30 is proved with another self-bounding argument that we outline here,
ignoring $\varepsilon/L$ dependence for clarity. Note that we will frequently
use the canonical extension of $\hat{g}_{\varepsilon}$ to consider
$(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})$ as a dual variable pair for
the semi-empirical problem between $\hat{\mu}$ and $\nu$. In particular,
notation such as $\nu(\hat{g}_{\varepsilon})$ is not referring to integration
over any part of the sample $y_{1},\ldots,y_{n}\sim\nu^{\otimes n}$, but
rather over an _independent_ draw from $\nu$.

  1. 1.

Lemma 31: Use a Poincaré inequality on $\nu$ (which follows from our
assumptions and is described in Proposition 40 in Appendix A.3) to control
$\|\hat{g}_{\varepsilon}-g_{\varepsilon}-\nu(\hat{g}_{\varepsilon})\|_{L^{2}(\nu)}^{2}$
in terms of entropic OT maps defined on $N$

  2. 2.

Lemma 32: Use the same analysis as in the proof of the empirical norm
convergence of the entropic OT maps (section 5.3) to control the previous term
in terms of $1/n$, the semi-empirical dual objective
$\Phi^{\hat{\mu}\nu}_{\varepsilon}$, and
$\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\nu)}^{2}$, with a free
parameter from Young’s inequality.

  3. 3.

Lemma 33: Control the semi-empirical objective term with concavity to yield a
bound in terms of $1/n$ and
$\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|_{L^{2}(\nu)}^{2}$, with a free
parameter from Young’s inequality.

  4. 4.

Lemma 34: Bound the shift $\mathbb{E}[\nu(\hat{g}_{\varepsilon})^{2}]$ by
$1/n$ using the semi-discrete objective once more

  5. 5.

Use the free parameters from Young’s inequality to conclude a $1/n$ bound on
$\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}$.

The formal statements of the lemmas outlined above are given below.

######  Lemma 31.

We have

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}-\nu(\hat{g}_{\varepsilon})\|_{L^{2}(\nu)}^{2}]\lesssim\mathbb{E}\Big{[}\Big{\|}\mathbb{E}_{\pi_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y]-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}_{L^{2}(\nu)}^{2}\Big{]}.$

######  Lemma 32.

For all $a>0$, we have

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\mathbb{E}_{\pi_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y]-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)$
$\displaystyle\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}_{L^{2}(\nu)}^{2}\Big{]}\lesssim\frac{L^{2}}{\varepsilon}\mathbb{E}[\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]$
$\displaystyle+a\frac{1}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{2d_{\nu}+2}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]$
$\displaystyle+L\big{(}\frac{a}{\varepsilon^{2}}+\frac{1}{a}\big{)}\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\Big{(}\frac{L}{\varepsilon}\Big{)}^{11d_{\nu}+5}\cdot\frac{1}{n}.$

######  Lemma 33.

For all $a>0$, we have

$\mathbb{E}[\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]\lesssim\frac{1}{a}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}\cdot\frac{1}{n}+a\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}].$

######  Lemma 34.

We have

$\mathbb{E}[\nu(\hat{g}_{\varepsilon})^{2}]\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\Big{(}\frac{L}{\varepsilon}\Big{)}^{11d_{\nu}+4}\cdot\frac{1}{n}$

###### Proof of Lemma 30.

Note that

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]\lesssim\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}-\nu(\hat{g}_{\varepsilon})\|^{2}_{L^{2}(\nu)}]+\mathbb{E}[\nu(\hat{g}_{\varepsilon})^{2}].$

We can thus apply each of the above lemmas to yield, for $a,a^{\prime}>0$,

$\displaystyle\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]$
$\displaystyle\lesssim\frac{L}{a}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+1}+a\frac{L^{2}}{\varepsilon}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]$
$\displaystyle+\frac{a^{\prime}}{\varepsilon}\Big{(}\frac{L}{\varepsilon}\Big{)}^{2d_{\nu}+2}\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]+L\big{(}\frac{a^{\prime}}{\varepsilon^{2}}+\frac{1}{a^{\prime}}\big{)}\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\Big{(}\frac{L}{\varepsilon}\Big{)}^{11d_{\nu}+5}\cdot\frac{1}{n}$
$\displaystyle+\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\Big{(}\frac{L}{\varepsilon}\Big{)}^{11d_{\nu}+4}\cdot\frac{1}{n}.$

Taking $a=C\varepsilon/L^{2}$ and
$a^{\prime}=C\varepsilon(\varepsilon/L)^{2d_{\nu}+2}$ for $C$ a sufficiently
small constant and re-arranging yields

$\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]\lesssim\Big{\\{}L^{2}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}+2}+\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\Big{(}\frac{L}{\varepsilon}\Big{)}^{13d_{\nu}+8}+\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\Big{(}\frac{L}{\varepsilon}\Big{)}^{11d_{\nu}+4}\Big{\\}}\cdot\frac{1}{n}.$

Using $\varepsilon/L\lesssim 1$ yields the result. ∎

###### Proof of Lemma 31.

Note that the term on the LHS is precisely
$\operatorname{Var}_{\nu}(\hat{g}_{\varepsilon}-g_{\varepsilon})$ since we
have specified $g_{\varepsilon}$ to be such that $\nu(g_{\varepsilon})=0$. We
will thus apply the Poincaré inequality on $\nu$ from Proposition 40 to bound
this term; this is legitimate because $\hat{g}_{\varepsilon}$ and
$g_{\varepsilon}$ are each Lipschitz with respect to the ambient Euclidean
norm and so are Lipschitz with respect to $(N,h)$, since embedded manifold
distances are always at least as large as extrinsic distances. We obtain

$\|\hat{g}_{\varepsilon}-g_{\varepsilon}-\nu(\hat{g}_{\varepsilon})\|^{2}_{L^{2}(\nu)}\lesssim\int\|\nabla_{N}(\hat{g}_{\varepsilon}-g_{\varepsilon})\|_{h}^{2}\mathrm{d}\nu(y).$

Since $N$ is an embedded manifold, the manifold norm of the manifold gradient
is always upper bounded by the Euclidean norm of the Euclidean gradient (for
the reader’s convenience, this fact is formally stated and proved as
Proposition 41 in Appendix A.3) so that

$\|\hat{g}_{\varepsilon}-g_{\varepsilon}-\nu(\hat{g}_{\varepsilon})\|^{2}_{L^{2}(\nu)}\lesssim\|\nabla\hat{g}_{\varepsilon}-\nabla
g_{\varepsilon}\|^{2}_{L^{2}(\nu)}.$

To calculate $\nabla g_{\varepsilon}$, consider the marginal constraint

$e^{-\frac{1}{\varepsilon}g_{\varepsilon}(y)}=\int
e^{-\frac{1}{\varepsilon}(c(x,y)-f_{\varepsilon}(x))}\mathrm{d}\mu(x).$

Differentiating and re-arranging, we find that

$\nabla
g_{\varepsilon}(y)=\mathbb{E}_{\pi_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y].$

Calculating in a similar fashion with the extended dual potential
$\hat{g}_{\varepsilon}$ we find

$\nabla\hat{g}_{\varepsilon}(y)=\mathbb{E}_{\hat{\pi}_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y]=\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y).$

The result follows. ∎

###### Proof of Lemma 32.

For all $y$ in $\operatorname{supp}(\nu)$, put

$\tilde{g}_{\varepsilon}(y):=-\varepsilon\log\Big{(}\frac{1}{n}\sum_{i=1}^{n}e^{-\varepsilon^{-1}(c(x_{i},y)-f_{\varepsilon}(x_{i}))}\Big{)},$

and let

$\tilde{p}_{\varepsilon}(x,y):=e^{-\varepsilon^{-1}(c(x,y)-f_{\varepsilon}(x)-\tilde{g}_{\varepsilon}(y)}.$

Then by Young’s inequality,

$\displaystyle\mathbb{E}\Big{[}\Big{\|}$
$\displaystyle\mathbb{E}_{\pi_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y]-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}_{L^{2}(\nu)}^{2}\Big{]}\lesssim$
$\displaystyle\mathbb{E}\Big{[}\Big{\|}\mathbb{E}_{\pi_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y]-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)p_{\varepsilon}(x_{i},y)\Big{\|}^{2}_{L^{2}(\nu)}\Big{]}$
$\displaystyle+\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)p_{\varepsilon}(x_{i},y)-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\tilde{p}_{\varepsilon}(x_{i},y)\Big{\|}^{2}_{L^{2}(\nu)}\Big{]}$
$\displaystyle+\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\tilde{p}_{\varepsilon}(x_{i},y)-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}^{2}_{L^{2}(\nu)}\Big{]}.$

Using the same argument as in the proof of Lemma 20 just with the role of
$\mu$ and $\nu$ swapped, the first two terms can each be bounded as $\lesssim
L^{2}\|p_{\varepsilon}\|^{2}_{L^{2}(\mu\otimes\nu)}/n$. By Lemma 16 and
Proposition 43, we can bound
$\|p_{\varepsilon}\|^{2}_{L^{2}(\mu\otimes\nu)}\lesssim(L/\varepsilon)^{d_{\nu}}$
and so arrive at

$\displaystyle\mathbb{E}\Big{[}\Big{\|}$
$\displaystyle\mathbb{E}_{\pi_{\varepsilon}}[\nabla_{y}c(x,y)\,|\,y]-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}_{L^{2}(\nu)}^{2}\Big{]}\lesssim$
$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\tilde{p}_{\varepsilon}(x_{i},y)-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}^{2}_{L^{2}(\nu)}\Big{]}+L^{2}\Big{(}\frac{L}{\varepsilon}\Big{)}^{d_{\nu}}\cdot\frac{1}{n}.$

We proceed as in the proof of Lemma 19, by first applying triangle inequality
and then Pinsker’s. This yields

$\displaystyle\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}$
$\displaystyle\nabla_{y}c(x_{i},y)\tilde{p}_{\varepsilon}(x_{i},y)-\frac{1}{n}\sum_{i=1}^{n}\nabla_{y}c(x_{i},y)\hat{p}_{\varepsilon}(x_{i},y)\Big{\|}^{2}_{L^{2}(\nu)}\Big{]}$
$\displaystyle\leqslant
L^{2}\mathbb{E}\Big{[}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}|\tilde{p}_{\varepsilon}(x_{i},y)-\hat{p}_{\varepsilon}(x_{i},y)|\Big{\|}^{2}_{L^{2}(\nu)}\Big{]}$
$\displaystyle\lesssim
L^{2}\mathbb{E}\Big{[}\int\operatorname{KL}(\frac{1}{n}\hat{p}_{\varepsilon}(\cdot,y)\,\|\,\frac{1}{n}\tilde{p}_{\varepsilon}(\cdot,y))\mathrm{d}\nu(y)\Big{]}$
$\displaystyle=\frac{L^{2}}{\varepsilon}\mathbb{E}\Big{[}\int\Big{(}\frac{1}{n}\sum_{i=1}^{n}\hat{p}_{\varepsilon}(x_{i},y)(\hat{f}_{\varepsilon}(x_{i})-f_{\varepsilon}(x_{i})+\hat{g}_{\varepsilon}(y)-\tilde{g}_{\varepsilon}(y))\Big{)}\mathrm{d}\nu(y)\Big{]}$
$\displaystyle=\frac{L^{2}}{\varepsilon}\mathbb{E}\Big{[}\Phi_{\varepsilon}^{\hat{\mu}\nu}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi_{\varepsilon}^{\hat{\mu}\nu}(f_{\varepsilon},\tilde{g}_{\varepsilon})+\Big{\langle}\int\hat{p}_{\varepsilon}(\cdot,y)\mathrm{d}\nu(y)-1,f_{\varepsilon}-f_{\varepsilon}\Big{\rangle}_{L^{2}(\hat{\mu})}\Big{]}$
$\displaystyle\leqslant\frac{L^{2}}{\varepsilon}\mathbb{E}\Big{[}\Phi_{\varepsilon}^{\hat{\mu}\nu}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi_{\varepsilon}^{\hat{\mu}\nu}(f_{\varepsilon},g_{\varepsilon})+\Big{\langle}\int\hat{p}_{\varepsilon}(\cdot,y)\mathrm{d}\nu(y)-1,\hat{f}_{\varepsilon}-f_{\varepsilon}\Big{\rangle}_{L^{2}(\hat{\mu})}\Big{]},$

where the second equality follows because
$(\hat{\mu}\otimes\nu)(\hat{p}_{\varepsilon})=(\hat{\mu}\otimes\nu)(\tilde{p}_{\varepsilon})=1$,
and the final inequality is via Proposition 13. To conclude the argument, we
apply Young’s inequality to the inner product term to obtain, for all $a>0$,

$\displaystyle\mathbb{E}\Big{[}\Big{\langle}\int\hat{p}_{\varepsilon}(\cdot,y)\mathrm{d}\nu(y)-1,\hat{f}_{\varepsilon}-f_{\varepsilon}\Big{\rangle}_{L^{2}(\hat{\mu})}\Big{]}$
$\displaystyle\leqslant
a\mathbb{E}\Big{[}\Big{\|}\int(\hat{p}_{\varepsilon}(\cdot,y)-1)\mathrm{d}\nu(y)\Big{\|}^{2}_{L^{2}(\hat{\mu})}\Big{]}$
$\displaystyle+\frac{1}{a}\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]$
$\displaystyle=a\mathbb{E}\Big{[}\Big{\|}\int(\hat{p}_{\varepsilon}(\cdot,y)-p_{\varepsilon}(\cdot,y))\mathrm{d}\nu(y)\Big{\|}^{2}_{L^{2}(\hat{\mu})}\Big{]}$
$\displaystyle+\frac{1}{a}\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}]$
$\displaystyle\leqslant
a\mathbb{E}[\|\hat{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{2}(\hat{\mu}\otimes\nu)}^{2}]+\frac{1}{a}\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\nu})}].$

By Lemma 35, which is stated and proved in the following section,

$\mathbb{E}[\|\hat{p}_{\varepsilon}-p_{\varepsilon}\|_{L^{2}(\hat{\mu}\otimes\nu)}^{2}]\lesssim\frac{1}{\varepsilon^{2}}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{2d_{\nu}}\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}+\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}]+\frac{1}{n}.$

Applying Lemma 24 and Lemma 27 we have

$\mathbb{E}[\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|^{2}_{L^{2}(\hat{\mu})}]\lesssim\big{(}\varepsilon^{2}+\frac{1}{\varepsilon^{2}}\big{)}\cdot\Big{(}\frac{L}{\varepsilon}\Big{)}^{9d_{\nu}+4}\cdot\frac{1}{n}.$

The result follows by collecting terms. ∎

###### Proof of Lemma 33.

Proposition 13 on concavity of the dual implies that

$\mathbb{E}[\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]\leqslant\mathbb{E}[\langle\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}].$

Observe that because $(f_{\varepsilon},g_{\varepsilon})$ attain the
$\nu$-marginal, the first component of
$\nabla\Phi_{\varepsilon}^{\hat{\mu}\nu}$ vanishes, implying

$\displaystyle\langle\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}=\big{\langle}1-\frac{1}{n}\sum_{i=1}^{n}p_{\varepsilon}(x_{i},y)),\hat{g}_{\varepsilon}-g_{\varepsilon}\big{\rangle}_{L^{2}(\nu)}.$

Young’s inequality yields, for all $a>0$,

$\mathbb{E}[\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})]\lesssim\frac{1}{a}\mathbb{E}\big{[}\big{\|}1-\frac{1}{n}\sum_{i=1}^{n}p_{\varepsilon}(x_{i},y)\big{\|}_{L^{2}(\nu)}^{2}\big{]}+a\mathbb{E}[\|\hat{g}_{\varepsilon}-g_{\varepsilon}\|^{2}_{L^{2}(\nu)}].$

The first term can be calculated as in (5.2) to yield

$\mathbb{E}\big{[}\big{\|}1-\frac{1}{n}\sum_{i=1}^{n}p_{\varepsilon}(x_{i},y)\big{\|}_{L^{2}(\nu)}^{2}\big{]}\lesssim\frac{\|p_{\varepsilon}\|^{2}_{L^{2}(\mu\otimes\nu)}}{n}.$

Finally, applying Lemma 16 and Proposition 43, we obtain the result. ∎

###### Proof of Lemma 34.

Note that, since
$(\hat{\mu}\otimes\nu)(\hat{p}_{\varepsilon})=(\hat{\mu}\otimes\nu)(p_{\varepsilon})=1$
and we make the normalization assumption $\nu(g_{\varepsilon})=0$, we have

$\nu(\hat{g}_{\varepsilon})=\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})+\hat{\mu}(f_{\varepsilon}-\hat{f}_{\varepsilon}).$

By Jensen’s inequality, we have that

$|\nu(\hat{g}_{\varepsilon})|\leqslant|\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|+\|\hat{f}_{\varepsilon}-f_{\varepsilon}\|_{L^{2}(\hat{\mu})}.$

Observe that the two-sided concavity statements from Proposition 13 imply that

$\displaystyle|\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})-\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon})|$
$\displaystyle\leqslant|\langle\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}|$
$\displaystyle+|\langle\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}|.$

For the first term, Cauchy-Schwarz and Proposition 14 on uniform bounds for
the dual potentials imply that

$|\langle\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(f_{\varepsilon},g_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}|\lesssim\|\nabla\Phi_{\varepsilon}^{\hat{\mu}\nu}(f_{\varepsilon},g_{\varepsilon})\|_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}.$

For the second term, since $(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})$
attain the $\hat{\mu}$ marginal, the second component of
$\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon})$
vanishes, so that

$\displaystyle|\langle\nabla\Phi^{\hat{\mu}\nu}_{\varepsilon}(\hat{f}_{\varepsilon},\hat{g}_{\varepsilon}),(\hat{f}_{\varepsilon}-f_{\varepsilon},\hat{g}_{\varepsilon}-g_{\varepsilon})\rangle_{L^{2}(\hat{\mu})\times
L^{2}(\nu)}|$
$\displaystyle=\big{|}\big{\langle}1-\int\hat{p}_{\varepsilon}(x,y)\mathrm{d}\nu(y),\hat{f}_{\varepsilon}-f_{\varepsilon}\big{\rangle}_{L^{2}(\hat{\mu})}\big{|}$