Abstract
Optimal Transport (OT) is a powerful framework for comparing probability distributions, yet its practical utility is often hampered by the "curse of dimensionality." While Entropic Optimal Transport (EOT) offers a parametric sample complexity that avoids this curse, it introduces undesirable "overspreading" and numerical instability. Quadratically Regularized Optimal Transport (QOT) provides a sparse and stable alternative, but its statistical efficiency has long been questioned due to the non-smooth nature of its dual potentials. This paper establishes that QOT also achieves parametric sample complexity ($n^{-1/2}$), independent of dimension. By leveraging Vapnik–Chervonenkis (VC) theory and the geometric regularity of the optimal coupling’s support, the authors provide the first Central Limit Theorems (CLTs) for QOT potentials, costs, and couplings, positioning QOT as a statistically robust framework for high-dimensional data analysis.
Introduction
Optimal Transport (OT) has become a cornerstone of modern data science, providing a geometrically intuitive way to compare distributions in fields as diverse as image processing and single-cell genomics. However, OT faces a significant statistical hurdle: the curse of dimensionality. When approximating continuous distributions with $n$ i.i.d. samples, the error in the empirical OT cost typically scales as $n^{-1/d}$, where $d$ is the dimension. In high-dimensional settings, the amount of data required to achieve accuracy becomes prohibitively large.
To circumvent this, researchers frequently turn to Regularized Optimal Transport (ROT). The most prominent variant, Entropic Optimal Transport (EOT), utilizes a logarithmic penalty to achieve a parametric convergence rate of $n^{-1/2}$. However, EOT is not without flaws. It produces full-support couplings that map every source point to every target point, leading to "overspreading" or blurriness in applications. Furthermore, EOT becomes numerically unstable when the regularization parameter is small.
The Quadratic Alternative
Quadratically Regularized Optimal Transport (QOT) serves as a compelling alternative. By penalizing the $L^2$ norm of the coupling rather than relative entropy, QOT preserves the sparsity of the original OT problem while maintaining numerical stability. Despite these practical advantages, QOT was long suspected to suffer from the curse of dimensionality. Unlike EOT, the dual potentials of QOT are not smooth, and its dual problem lacks strong concavity—the two primary mathematical properties used to prove the efficiency of EOT.
In "Sample Complexity of Quadratically Regularized Optimal Transport," Alberto González-Sanz, Eustasio del Barrio, and Marcel Nutz prove that these fears were unfounded. They demonstrate that QOT is just as statistically efficient as EOT, achieving the gold-standard $n^{-1/2}$ convergence rate.
Methodology: Geometry Over Smoothness
The authors’ breakthrough stems from a shift in perspective: moving away from the smoothness of functions and focusing instead on the geometry of the support. Their analysis introduces several novel theoretical bridges:
- Lipschitz Regularity of Sections: The authors prove that the "sections" of the optimal QOT coupling—the sets describing where mass is moved—vary smoothly (Lipschitz) in relation to the regularization parameters.
- VC Theory Integration: In a departure from standard OT literature, the researchers employ Vapnik–Chervonenkis (VC) theory. By bounding the statistical complexity of the support sets using VC dimensions, they create a mathematical substitute for the missing smoothness in the dual potentials.
- Z-Estimation and $C^{1,1}$ Regularity: The problem is framed as a "Z-estimation" task (finding the zero of a specific operator), allowing for the derivation of limit theorems. Additionally, they establish that population potentials possess $C^{1,1}$ regularity, providing a link to classical regularity theories like those of Caffarelli.
Key Results
The paper provides a rigorous statistical foundation for QOT, yielding three primary results:
- Parametric Sample Complexity: The error in estimating QOT costs and potentials from $n$ samples scales with $1/\sqrt{n}$, regardless of the dimension $d$. This confirms that QOT is viable for high-dimensional applications without requiring exponential data growth.
- Central Limit Theorems (CLTs): The authors establish the first CLTs for the dual potentials (the "shadow prices" of mass movement), the optimal costs (the total work), and the optimal couplings (the transport plan itself).
- Gradient Estimates: The study provides new estimates for the gradients of the potentials, which are critical for the development of efficient gradient-descent-based solvers.
Discussion and Future Work
While this work proves that QOT is statistically efficient, some open questions remain. The constants in the $n^{-1/2}$ rate depend on the regularization parameter $\epsilon$. As $\epsilon$ approaches zero (recovering unregularized OT), these constants may grow, and finding "$\epsilon$-uniform" bounds is a target for future research. Additionally, the current analysis assumes compact, convex supports and bounded densities; extending these results to heavy-tailed distributions or non-convex supports would further broaden the applicability of QOT.
By proving that sparsity and statistical efficiency can coexist, this research elevates QOT from a heuristic alternative to a theoretically sound powerhouse for high-dimensional optimal transport.
Summary updated