Approximation rates of entropic maps in semidiscrete optimal transport

Ritwik Sadhu, Ziv Goldfeld, Kengo Kato

TL;DR

This paper investigates how well an "entropic" approximation of the optimal transport map (the Brenier map) captures the true map as a regularization parameter $\epsilon$ goes to zero. They show that this approximation is surprisingly accurate, achieving an $O(\epsilon^2)$ rate in a weaker norm than previously known, which is sharp and has implications for statistical inference.

What Problem Does This Paper Address?

The paper tackles the problem of optimal transport, specifically the Brenier map, which is a fundamental concept in mathematics and has found applications in machine learning (e.g., domain adaptation, transfer learning). The Brenier map establishes a one-to-one correspondence between two probability distributions (measures) that minimizes the expected squared distance between matched points. While theoretically elegant, computing the exact Brenier map is computationally challenging, especially in high dimensions.

To overcome this, researchers often use entropic regularization. This involves adding an entropy term to the optimization problem, making it solvable by efficient algorithms like Sinkhorn's algorithm. The resulting "entropic map" is an approximation of the true Brenier map. A key question is: how good is this approximation? Previous work showed that the entropic map approaches the Brenier map at a rate of $O(\epsilon)$ in the $L^2$ norm. This paper aims to establish faster convergence rates and explore their implications for statistical inference. The specific setting considered is semidiscrete optimal transport, where the input distribution is continuous (absolutely continuous) and the output distribution is discrete (a finite set of points).

Methods

The core of the paper's contribution lies in establishing sharper approximation rates for the entropic map compared to the Brenier map. Instead of focusing on the $L^2$ norm of the difference between the maps, the authors analyze the linear functional $\langle \phi, T^\epsilon - T^0 \rangle_{L^2(P)}$, where $T^\epsilon$ is the entropic map, $T^0$ is the Brenier map, $\phi$ is a vector field, and $P$ is the input measure. By taking the supremum of this functional over specific classes of vector fields, they derive convergence rates in dual norms.

Specifically, they prove an $O(\epsilon^{1+\alpha})$ rate for $\alpha$-Hölder vector fields, which translates to an $O(\epsilon^2)$ rate for Lipschitz vector fields (when $\alpha=1$). This is a significant improvement over the $O(\epsilon)$ rate previously known for the $L^2$ norm. The proofs involve detailed analysis of the structure of the entropic map and its relationship to the Brenier map, particularly by examining the "facial structures" of Laguerre cells, which are geometric objects arising in the semidiscrete setting. They also leverage results from previous work on asymptotic expansions of entropic costs and employ techniques like the coarea formula.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Faster Convergence in Weaker Norms: The most striking insight is that the entropic map can approximate the Brenier map much faster ($O(\epsilon^2)$) in a weaker norm (dual Lipschitz norm) than in the stronger $L^2$ norm ($O(\epsilon)$). This suggests that for certain types of analysis (e.g., linear functionals), the entropic approximation is remarkably good even for relatively large $\epsilon$.
  • Sharpness of the $O(\epsilon^2)$ Rate: The paper demonstrates that the $O(\epsilon^2)$ rate in the dual norm is sharp, meaning it cannot be improved in general. This provides a definitive understanding of the approximation quality.
  • Implications for Statistical Inference: The improved convergence rates have direct implications for statistical inference. The authors show that this allows for a central limit theorem for the entropic estimator of the Brenier map in the dual Lipschitz space, even when the regularization parameter $\epsilon$ decays much slower than typically required for parametric rates. This is a significant theoretical result for building statistical procedures based on entropic optimal transport.
  • Geometric Structure Matters: The analysis highlights the importance of the geometric structure of the problem, particularly the Laguerre cells, in understanding the approximation rates. The behavior of these cells as $\epsilon \to 0$ dictates the convergence behavior.

Key Results

  • Main Theorem (Theorem 3.2): For an $\alpha$-Hölder vector field $\phi$, the approximation error $|\langle \phi, T^\epsilon - T^0 \rangle_{L^2(P)}|$ is bounded by $O(\epsilon^{1+\alpha})$ up to polylogarithmic factors. For Lipschitz vector fields ($\alpha=1$), this becomes $O(\epsilon^2)$ up to polylogarithmic factors.
  • Dual Norm Convergence (Corollary 3.6): This implies that the approximation error in the dual $\alpha$-Hölder norm, $\|T^\epsilon - T^0\|_{(\mathcal{C}^\alpha)^*}$ is $O(\epsilon^{1+\alpha})$ up to polylogarithmic factors. For Lipschitz vector fields, this is $O(\epsilon^2)$.
  • Central Limit Theorem (Corollary 3.7): Under certain conditions on the input domain, the paper establishes a central limit theorem for the empirical entropic map in the dual Lipschitz space, provided the regularization parameter $\epsilon_n$ decays sufficiently slowly with the sample size $n$. This is a key result for statistical inference.

Limitations and Future Work

  • Polylogarithmic Factors: While the $O(\epsilon^2)$ rate for Lipschitz functions is sharp, it comes with polylogarithmic factors. The paper poses the question of whether these factors can be dropped.
  • Specific Conditions: The results are derived under specific assumptions on the input measure $P$ (compact convex support, Lipschitz and strictly positive density) and the output measure $Q$ (finitely discrete with minimum mass $c_0$). Relaxing these conditions could be a direction for future work.
  • Statistical Inference Assumptions: The central limit theorem relies on specific conditions for the domain $X$ (e.g., being a polytope) and a condition on the decay rate of $\epsilon_n$. Exploring these conditions further and potentially extending the CLT to more general settings would be valuable.
  • Empirical Validation: While the theoretical results are strong, empirical validation on real-world problems would be beneficial to demonstrate the practical advantages of the $O(\epsilon^2)$ approximation in specific applications.

Summary updated

Abstract

Entropic optimal transport offers a computationally tractable approximation to the classical problem. We study the approximation rate of the entropic optimal transport map (in approaching the Brenier map) when the regularization parameter ε tends to zero in the semidiscrete setting, where the input measure is absolutely continuous while the output is finitely discrete. Previous work shows that the approximation rate is O(ε) under the L2-norm with respect to the input measure. In this work, we establish faster, O(ε2) rates up to polylogarithmic factors, under the dual Lipschitz norm, which is weaker than the L2-norm. For the said dual norm, the O(ε2) rate is sharp. As a corollary, we derive a central limit theorem for the entropic estimator for the Brenier map in the dual Lipschitz space when the regularization parameter tends to zero as the sample size increases.
BibTeX
@inproceedings{sadhu2025approximation,
  author = {Ritwik Sadhu and Ziv Goldfeld and Kengo Kato},
  title = {{Approximation rates of entropic maps in semidiscrete optimal transport}},
  booktitle = {Electronic},
  year = {2025},
  doi = {10.1214/25-ecp682},
}
Figure