Sparse Regularized Optimal Transport without Curse of Dimensionality

Alberto González-Sanz, Stephan Eckstein, Marcel NutzarXiv 2025 · DOI · arXiv

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:

  1. Linearize the optimality conditions: They analyze the derivative of the dual operator and prove it is invertible.
  2. 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.
  3. 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

Abstract

Entropic optimal transport -- the optimal transport problem regularized by KL diver\-gence -- is highly successful in statistical applications. Thanks to the smoothness of the entropic coupling, its sample complexity avoids the curse of dimensionality suffered by unregularized optimal transport. The flip side of smoothness is overspreading: the entropic coupling always has full support, whereas the unregularized coupling that it approximates is usually sparse, even given by a map. Regularizing optimal transport by less-smooth $f$-divergences such as Tsallis divergence (i.e., $L^p$-regularization) is known to allow for sparse approximations, but is often thought to suffer from the curse of dimensionality as the couplings have limited differentiability and the dual is not strongly concave. We refute this conventional wisdom and show, for a broad family of divergences, that the key empirical quantities converge at the parametric rate, independently of the dimension. More precisely, we provide central limit theorems for the optimal cost, the optimal coupling, and the dual potentials induced by i.i.d.\ samples from the marginals. These results are obtained by a powerful yet elementary approach that is of broader interest for Z-estimation in function classes that are not Donsker.
BibTeX
@misc{gonzalezsanz2025sparse,
  author = {Alberto González-Sanz and Stephan Eckstein and Marcel Nutz},
  title = {{Sparse Regularized Optimal Transport without Curse of Dimensionality}},
  year = {2025},
  eprint = {2505.04721},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.04721},
  howpublished = {arXiv},
}
Figure