TL;DR
This paper refutes the long-held belief that sparse regularized optimal transport (OT) necessarily suffers from the "curse of dimensionality." The authors prove that for a wide class of $f$-divergence regularizations (like Tsallis divergence), the empirical cost, coupling, and dual potentials all converge at the parametric rate ($n^{-1/2}$) regardless of the dimension, providing the first Central Limit Theorems (CLTs) for these sparse estimators.
What Problem Does This Paper Address?
Optimal Transport (OT) is a powerful tool for comparing probability distributions, but it has a major statistical weakness: the "curse of dimensionality." In its unregularized form, the sample complexity of OT scales as $n^{-2/d}$, meaning you need exponentially more data as the dimension $d$ increases to get a good estimate.
To fix this, researchers often use Entropic Regularization (KL divergence). This smooths the problem, leading to a fast, dimension-independent convergence rate of $n^{-1/2}$. However, entropic OT suffers from "overspreading"—the resulting optimal coupling has full support, even when the true underlying map is sparse or low-dimensional.
Alternative regularizations, such as Tsallis divergence ($L^p$-regularization), produce sparse couplings that better approximate the original Monge map. However, the conventional wisdom was that these sparse regularizers re-introduce the curse of dimensionality because they lack the $C^\infty$ smoothness of the KL divergence. This paper sets out to prove that this "wisdom" is wrong.
Methods
The authors employ a sophisticated version of Z-estimation, a standard statistical framework for finding parameters that solve an equation (like the first-order optimality conditions of the OT dual problem).
The technical challenge is that the function classes involved are not Donsker—a standard property required for CLTs in infinite-dimensional spaces. Because the sparse regularizers aren't perfectly smooth, the empirical potentials don't fall into the usual "nice" categories.
To overcome this, the authors:
- Linearize the optimality conditions: They analyze the derivative of the dual operator and prove it is invertible.
- Use Auxiliary Hölder Spaces: They embed the problem into Hölder spaces where the unit ball is compact, allowing them to handle the lack of smoothness.
- Decompose the Error: They break down the difference between empirical and population quantities into three terms, each handled by different compactness or tightness arguments.
Datasets
As a theoretical math/statistics paper, the primary "data" consists of mathematical proofs. However, the authors include a Simulations section (Appendix A) to validate their theory.
- Flat Torus ($\mathbb{T}^d$): They use a $d$-dimensional flat torus with volume measures as marginals. This setup allows for semi-explicit solutions to the population problem, which are necessary to accurately measure convergence rates.
- Dimensions: They test $d \in \{1, 5, 10\}$ to demonstrate that the slope of the log-log error plots remains constant (around -1 for the variance-zero regime), confirming dimension independence.
Key Insights and Ideas
- Smoothness isn't the only way: The paper shows that you don't need the infinite smoothness of the KL divergence to avoid the curse of dimensionality. As long as the convex conjugate of the regularizer is $C^2$, the parametric rate is achievable.
- Invertibility is Key: The "aha moment" lies in proving that the linearized operator $L$ is a "perturbation of the identity" (specifically, $Id + \text{compact operator}$). Using Fredholm's alternative, they show this operator is invertible even when the optimal coupling is sparse.
- Refuting Previous Bounds: Previous work suggested a rate of $n^{-k/d}$ (where $k$ is the smoothness). This paper shows those bounds were loose and that the actual influence of dimension is much more benign, similar to entropic OT.
Key Results
- Central Limit Theorems: The authors establish CLTs for the three main objects in regularized OT: the optimal cost, the optimal coupling, and the dual potentials.
- Parametric Rate: They prove that these quantities converge at a rate of $1/\sqrt{n}$, which is the gold standard in statistics and is independent of the dimension $d$.
- Uniqueness: They provide a new result showing the uniqueness of dual potentials (up to a constant) for continuous costs, provided at least one marginal has connected support.
Limitations and Future Work
- Quadratic Regularization ($L^2$): Interestingly, the popular quadratic regularization is a "boundary case" that doesn't strictly meet all the paper's $C^2$ assumptions. While simulations suggest the results still hold, a formal proof for the $L^2$ case requires separate, more specialized techniques.
- Connectedness Assumption: The proof for uniqueness and the CLT currently requires the support of one marginal to be connected. Extending this to more general, disconnected supports (like discrete-to-discrete transport) remains an open area.
- Vanishing Regularization: The study focuses on a fixed regularization parameter $\epsilon$. Analyzing the "statistical-computational-approximation" trade-off as $\epsilon \to 0$ while $n \to \infty$ is a logical next step.
Summary updated