Sharp local sparsity of regularized optimal transport

1. Problem Statement and Context

The Core Problem:
The paper investigates the Regularized Optimal Transport (ROT) problem with $L_p$-type entropies ($p \in (1, 2]$). Unlike the classical Optimal Transport (OT) problem, which seeks a deterministic map (or plan) between two probability measures $\lambda$ and $\mu$, ROT adds a regularization term to the cost function. This makes the problem strictly convex and computationally tractable.

The Specific Challenge:
While Entropic Optimal Transport (EOT, corresponding to $p=1$) is widely used, it suffers from the "curse of dimensionality" and produces transport plans with maximal support (the density is strictly positive everywhere). In contrast, ROT plans with $p > 1$ exhibit sparsity: the support of the optimal coupling $\pi_\varepsilon$ shrinks as the regularization parameter $\varepsilon \to 0$, converging to the support of the unregularized OT plan $\pi_0$.

The Open Question:
Previous works (e.g., González-Sanz & Nutz, Wiesel & Xu) established that the support shrinks, but the sharp rate of this convergence for general multivariate data (beyond univariate or self-transport cases) remained an open problem. The authors aim to characterize the precise geometry and rate at which the sections of the transport plan's support contract.

2. Mathematical Formulation

The ROT problem is defined as:
$$\text{ROT}_{\varepsilon, p} := \inf_{\pi \in \Pi(\lambda, \mu), \pi \ll \lambda \otimes \mu} \left( \int \frac{1}{2}\|x - y\|^2 d\pi + \varepsilon \int h_p\left(\frac{d\pi}{d(\lambda \otimes \mu)}\right) d(\lambda \otimes \mu) \right)$$
where $h_p(z) = \frac{|z|^p}{p-1}$ (with $p \in (1, 2]$).

The density of the optimal plan $\pi_\varepsilon$ is given by:
$$\rho_\varepsilon(x, y) = \frac{1}{\varepsilon^{q-1} q^{q-1}} \left( f_\varepsilon(x) + g_\varepsilon(y) - \frac{1}{2}\|x - y\|^2 \right)_+^{q-1}$$
where $q = \frac{p}{p-1}$ is the Young conjugate, and $(\cdot)_+$ denotes the positive part. The term $(\cdot)_+$ allows the density to vanish, creating a sparse support.

The authors define the sections of the support for a fixed $x$:
$$S_x = \{ y : \rho_\varepsilon(x, y) > 0 \}$$
The goal is to determine the diameter and geometry of $S_x$ as $\varepsilon \to 0$.

3. Methodology and Assumptions

Assumptions:

• $\lambda$ and $\mu$ are probability measures with compact supports $\Omega_0$ and $\Omega_1$.
• They possess $C^{0, \alpha}$ densities bounded away from zero and infinity.
• The unregularized OT map $T = \nabla \phi$ is a $C^{1, \alpha}$ diffeomorphism (bi-Lipschitz).
• The analysis focuses on the interior of the support ($x \in \text{int}(\Omega_0)$) to avoid boundary effects.

Key Technical Tools:

1. Convex Potentials: The authors work with the convex potentials $\varphi_\varepsilon = \|\cdot\|^2/2 - f_\varepsilon$ and $\psi_\varepsilon = \|\cdot\|^2/2 - g_\varepsilon$.
2. Uniform Regularity: They rely on a prior result (González-Sanz & Koch, 2026) establishing that the Hessian of the potentials, $\nabla^2 \varphi_\varepsilon$, is uniformly bounded in $L^\infty_{loc}$ as $\varepsilon \to 0$.
3. Fenchel Duality & Geometry: The proof utilizes the relationship between the subdifferentials of the potentials and the geometry of the sets $S_x$. Specifically, $S_x$ is shown to be a convex set.
4. Reynolds' Transport Theorem: A non-standard version of this theorem is derived (Appendix A) to compute the second derivatives of the potentials when the domain of integration ($S_x$) depends on $x$.
5. Scaling Arguments: The proof involves careful scaling of the integrals defining the density to extract the dependence on $\varepsilon$.

4. Key Contributions and Results

A. Sharp Local Sparsity (Theorem 3.1)

The main result characterizes the geometry of the support section $S_x$. For any compact subset $K_0$ strictly inside $\Omega_0$, there exists a constant $R_0$ such that for small $\varepsilon$:
$$B\left(\nabla \varphi_\varepsilon(x), \frac{1}{R_0} \varepsilon^{\frac{1}{d(p-1)+2}}\right) \subset S_x \subset B\left(\nabla \varphi_\varepsilon(x), R_0 \varepsilon^{\frac{1}{d(p-1)+2}}\right)$$
Significance:

• The support sections behave like balls centered at the gradient of the potential.
• The radius scales as $\varepsilon^{\frac{1}{d(p-1)+2}}$.
• This rate is proven to be sharp (cannot be improved) via an explicit construction on the torus (Section 6).
• This generalizes previous univariate results and results restricted to self-transport ($\lambda = \mu$) to the general multivariate case.

B. Uniform Strong Convexity (Corollary 3.2)

The authors prove that the regularized potentials $\varphi_\varepsilon$ are uniformly strongly convex on compact subsets of the interior of the support.
$$\inf_{\|h\|=1} \langle \nabla^2 \varphi_\varepsilon(x) h, h \rangle \geq \frac{1}{C}$$
This property is crucial for ensuring the stability of the transport map and the well-posedness of the numerical schemes.

C. Convergence Rates of the Transport Map (Corollary 3.3)

The paper derives the convergence rate of the regularized transport map $\nabla \varphi_\varepsilon$ to the unregularized OT map $\nabla \phi$:
$$\|\nabla \varphi_\varepsilon - \nabla \phi\|_{L^2(K_0)} \leq C \varepsilon^{\frac{1}{d(p-1)+2}}$$
This quantifies how quickly the regularized solution approximates the true optimal transport map in the $L^2$ norm.

5. Explicit Verification (Section 6)

To demonstrate the sharpness of the derived rates, the authors solve the ROT problem explicitly for self-transport on the flat torus ($\lambda = \mu = \text{Lebesgue}$).

• Due to symmetry, the dual potentials are constant.
• The support $S_x$ is a geodesic ball with radius $R_\varepsilon$.
• Solving the marginal constraint yields $R_\varepsilon \approx \varepsilon^{\frac{1}{d(p-1)+2}}$.
• This explicit calculation confirms that the theoretical upper and lower bounds derived in Theorem 3.1 are tight.

6. Significance and Impact

1. Theoretical Advancement: This work resolves the open question regarding the precise rate of support contraction for $L_p$-regularized OT in high dimensions. It bridges the gap between the "maximal support" of EOT and the "sparse support" of ROT.
2. Algorithmic Implications: Understanding the sparsity rate is vital for designing efficient algorithms. Since the support shrinks to a ball of radius $\varepsilon^{\frac{1}{d(p-1)+2}}$, numerical methods can exploit this locality to reduce computational complexity, potentially avoiding the full $N \times N$ matrix operations required by dense methods.
3. Generalization: The results extend beyond the specific case of $p=2$ (Quadratic Regularization) and beyond self-transport, covering a broad class of regularization functions and general measure pairs.
4. Stability Analysis: The proof of uniform strong convexity provides a theoretical foundation for the stability of ROT solutions, which is essential for applications in machine learning and statistics where data is noisy.

In summary, the paper provides a rigorous geometric characterization of how regularized optimal transport plans concentrate around the true optimal map as the regularization vanishes, establishing sharp convergence rates that depend on the dimension $d$ and the regularization parameter $p$.