Abstract
Entropic optimal transport (EOT) offers a computationally tractable approximation to the classical optimal transport problem. In this note, we study the approximation rate of the entropic optimal transport map as it approaches the Brenier map when the regularization parameter $\varepsilon$ tends to zero. We focus on the semidiscrete setting, where the input measure is absolutely continuous while the output is finitely discrete. While previous work established an approximation rate of $O(\sqrt{\varepsilon})$ under the $L^2$-norm, this work establishes a faster $O(\varepsilon^2)$ rate (up to polylogarithmic factors) under the dual Lipschitz norm. This rate is shown to be sharp. As a corollary, we derive a central limit theorem (CLT) for the entropic estimator of the Brenier map in the dual Lipschitz space, facilitating robust statistical inference.
Introduction
Optimal Transport (OT) provides a powerful framework for comparing probability distributions and finding the "Brenier map"—the most efficient way to transform one distribution into another. However, computing the exact Brenier map is often computationally prohibitive, particularly in high-dimensional spaces. To address this, researchers frequently employ entropic regularization, which adds a small penalty term (scaled by $\varepsilon$) to the transport objective. This regularization enables the use of the fast Sinkhorn algorithm, transforming a complex optimization problem into a manageable one.
The primary drawback of this approach is the introduction of a regularization bias. While it is well-known that the entropic map $T^\varepsilon$ converges to the true Brenier map $T^0$ as $\varepsilon \to 0$, the speed of this convergence determines the utility of EOT for high-precision tasks and statistical inference. Previous studies suggested a convergence rate of $O(\sqrt{\varepsilon})$ when measured by the standard $L^2$ distance. This work demonstrates that by shifting the mathematical perspective to dual norms, the convergence is significantly faster than previously understood.
Theoretical Framework and Methodology
The Semidiscrete Setting
The authors focus on the semidiscrete optimal transport problem, a common scenario in data science where a continuous source distribution (such as a Gaussian density) is mapped to a discrete target distribution (such as a finite set of empirical data points). In this context, the Brenier map is characterized by a partition of the continuous space into Laguerre cells—Voronoi-like regions where each cell is assigned to a specific point in the discrete target.
Shifting to Dual Norms
The core innovation of this research is the move from the $L^2$ norm to the dual Lipschitz norm (and more broadly, dual Hölder norms). The $L^2$ norm is highly sensitive to local fluctuations, particularly at the boundaries of Laguerre cells where the entropic map struggles to approximate the sharp transitions of the Brenier map. By using a dual norm, the authors evaluate the map's performance when integrated against smooth test functions. This "averaging" effect reveals that the local errors introduced by regularization tend to cancel each other out globally.
Analytical Techniques
To establish the faster rates, the authors employed several advanced mathematical tools:
- Asymptotic Expansion: They performed a high-order expansion of the entropic map around the limit $\varepsilon = 0$.
- Geometric Analysis: They analyzed the geometry of Laguerre cells and used the coarea formula to manage the complex boundaries where the most significant approximation errors occur.
- Sharpness Verification: Using a synthetic one-dimensional example (mapping a uniform distribution to a two-point discrete distribution), they demonstrated that the $O(\varepsilon^2)$ rate is the best possible bound for Lipschitz test functions.
Key Insights and Results
Faster Convergence Rates
The study proves that for an $\alpha$-Hölder test function, the approximation error scales as $O(\varepsilon^{1+\alpha})$. Specifically, for the standard Lipschitz case (where $\alpha=1$), the rate is $O(\varepsilon^2 \log^3(1/\varepsilon))$. This aligns the convergence of the map with the known convergence rate of the entropic cost itself, providing a more unified theoretical understanding of EOT.
Statistical Efficiency and the CLT
One of the most significant practical outcomes of this research is the derivation of a Central Limit Theorem (CLT). In statistical applications, the total error of an estimator is a combination of sampling noise ($1/\sqrt{n}$) and regularization bias. Because the bias in the dual norm vanishes at a rate of $O(\varepsilon^2)$, it becomes negligible much faster than the sampling noise. This allows the authors to show that the entropic estimator $\hat{T}^{\varepsilon_n}_n$ converges to a Gaussian process in the dual space, provided the regularization parameter $\varepsilon_n$ is chosen to decay at an appropriate rate.
Conclusion and Future Directions
This work provides a theoretical justification for the use of entropic regularization in high-precision statistical tasks. By proving that the bias vanishes at an $O(\varepsilon^2)$ rate in the dual Lipschitz space, the authors bridge the gap between computational efficiency and statistical accuracy.
However, several avenues for future research remain. The current results are limited to the semidiscrete setting; extending these rates to the continuous-to-continuous setting is a major open challenge due to the increased geometric complexity of the transport maps. Additionally, the authors note that the logarithmic factors in their bounds might be artifacts of the proof technique, suggesting that an even cleaner $O(\varepsilon^2)$ rate might be achievable. Finally, relaxing the assumptions on the support of the input distribution (currently required to be a compact convex set) would broaden the applicability of these results to more diverse machine learning problems.
Summary updated