Sample Complexity of Quadratically Regularized Optimal Transport

Alberto González-Sanz, Eustasio del Barrio, Marcel NutzarXiv 2025 · DOI · arXiv

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:

  1. 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.
  2. 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).
  3. 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

Abstract

It is well known that optimal transport suffers from the curse of dimensionality: when the prescribed marginals are approximated by i.i.d. samples, the convergence of the empirical optimal transport problem to the population counterpart slows exponentially with increasing dimension. Entropically regularized optimal transport (EOT) has become the standard bearer in many statistical applications as it avoids this curse. Indeed, EOT has parametric sample complexity, as has been shown in a series of works based on the smoothness of the EOT potentials or the strong concavity of the dual EOT problem. However, EOT produces full-support approximations to the (sparse) OT problem, leading to overspreading in applications, and is computationally unstable for small regularization parameters. The most popular alternative is quadratically regularized optimal transport (QOT), which penalizes couplings by $L^2$ norm instead of relative entropy. QOT produces sparse approximations of OT and is computationally stable. However, its potentials are not smooth (do not belong to a Donsker class) and its dual problem is not strongly concave, hence QOT is often assumed to suffer from the curse of dimensionality. In this paper, we show that QOT nevertheless has parametric sample complexity. More precisely, we establish central limit theorems for its dual potentials, optimal couplings, and optimal costs. Our analysis is based on novel arguments that focus on the regularity of the support of the optimal QOT coupling. Specifically, we establish a Lipschitz property of its sections and leverage VC theory to bound its statistical complexity. Our analysis also leads to gradient estimates of independent interest, including $C^{1,1}$ regularity of the population potentials.
BibTeX
@misc{gonzalezsanz2025sample,
  author = {Alberto González-Sanz and Eustasio del Barrio and Marcel Nutz},
  title = {{Sample Complexity of Quadratically Regularized Optimal Transport}},
  year = {2025},
  eprint = {2511.09807},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.09807},
  howpublished = {arXiv},
}
Figure