Dimension-Free Convergence Rates for Optimal Transport

321 concepts206 papers1 proposal

To compare two probability distributions, we often turn to Optimal Transport (OT) and the Wasserstein distance. Intuitively, the Wasserstein distance measures the minimum "work" required to transport the mass of one distribution into another. This geometric awareness makes it incredibly powerful for machine learning applications like generative modeling and domain adaptation.

However, standard Optimal Transport suffers from a severe statistical bottleneck known as the curse of dimensionality. If we estimate the Wasserstein distance between two continuous distributions using $n$ samples, the empirical estimator converges to the true distance at a rate of $O(n^{-1/d})$, where $d$ is the dimension of the space. In a 10-dimensional space, you need millions of samples just to get a stable estimate; in a 100-dimensional space, it becomes statistically impossible.

The core of this problem lies in the rigidity of exact transport. In high dimensions, data points are isolated islands. An empirical distribution consisting of discrete samples looks completely different from the true, smooth underlying distribution. Exact optimal transport tries to match these isolated points perfectly, overfitting to the high-dimensional vacuum and causing the sample complexity to explode.

To make optimal transport viable for modern machine learning, we must bypass this curse. A major research direction focuses on modifying the transport problem to achieve dimension-independent convergence rates—typically the parametric rate of $O(n^{-1/2})$—allowing us to compare high-dimensional distributions with a reasonable number of samples.

Let's explore the primary mechanisms used to achieve this dimension-free convergence.


Entropic Regularization: Blurring the Target

The most popular way to break the curse of dimensionality is to add an entropic penalty to the transport plan. Instead of looking for a sharp, deterministic point-to-point matching, entropic optimal transport allows the transport plan to be "blurry."

Mathematically, we add a regularization term $\epsilon H(\gamma)$, where $H(\gamma)$ is the Shannon entropy of the transport coupling $\epsilon$. This forces the coupling to spread its mass.

Exact OT (Rigid, Overfits)         Entropic OT (Blurred, Stable)
      • ---------> •                     • ---\=====> •
      • ---------> •                     • ---/=====> •
(Highly sensitive to noise)        (Macroscopic overlap, robust)

This simple modification fundamentally changes the statistical behavior of the estimator. Mena and Weed proved that entropic optimal transport avoids the curse of dimensionality entirely, converging at a rate of $1/\sqrt{n}$ regardless of the dimension. Similarly, Genevay et al. demonstrated that Sinkhorn divergences—which use entropic regularization to interpolate between OT and Maximum Mean Discrepancy (MMD)—enjoy a sample complexity of $O(1/\sqrt{n})$ that is completely independent of the data dimension.

By blurring the transport plan, we stop caring about the exact microscopic positions of sparse high-dimensional samples. Instead, the metric evaluates the macroscopic overlap of their blurred profiles, which stabilizes rapidly even with few samples.


Projection and Slicing: Lower-Dimensional Lenses

Another intuitive way to avoid the curse of dimensionality is to change our perspective. If computing transport in a $d$-dimensional space is hard, why not project the data onto a lower-dimensional subspace where statistical convergence is fast?

Sliced Wasserstein Distances

The extreme version of this idea is to project the high-dimensional distributions onto one-dimensional lines (slices). In 1D, optimal transport is trivial to compute (it reduces to sorting the points), and its sample complexity is independent of the original ambient dimension.

Nadjahi et al. provided the theoretical foundation for this in generative modeling, proving that Sliced-Wasserstein (SW) estimators achieve a dimension-independent convergence rate of $\sqrt{n}$. By averaging the transport costs across random 1D projections, the metric captures high-dimensional differences while maintaining 1D statistical efficiency.

Subspace Robust Wasserstein Distances

Rather than averaging over random 1D lines, we can search for the specific low-dimensional subspace that captures the most significant differences between two distributions.

Paty and Cuturi introduced Subspace Robust Wasserstein distances, which find a $k$-dimensional subspace ($k \ll d$) that maximizes the transport cost between two measures. Lin et al. subsequently proved that the sample complexity of these Projection Robust Wasserstein (PRW) distances is governed entirely by the projection dimension $k$ rather than the ambient dimension $d$.

Ambient Space (Dimension d) --------> Optimized Subspace (Dimension k)
  [ Sparse, isolated points ]           [ Concentrated, structured mass ]
  Sample Complexity: O(n^{-1/d})        Sample Complexity: O(n^{-1/k})

Low-Rank Constraints: Simplifying the Coupling Matrix

When we compute optimal transport between $n$ source points and $n$ target points, we are searching for an $n \times n$ coupling matrix. In high dimensions, this matrix has too many degrees of freedom, allowing it to overfit to the random noise of the samples.

To prevent this, we can constrain the structural complexity of the transport plan itself by forcing it to be low-rank. Forrow et al. introduced this concept via Factored Couplings, showing that imposing a rank constraint decouples the statistical error from the ambient dimension.

Scetbon and Cuturi expanded on this with Low-Rank Optimal Transport (LOT). By restricting the transport plan to a low-rank matrix factorization, the optimization problem scales linearly with the number of data points, and the statistical convergence rate becomes independent of the data's dimensionality. The low-rank constraint acts as a regularizer that forces the transport plan to route mass through a small number of latent "hubs," ignoring high-dimensional sample sparsity.


Smoothing the Data: Adding Isotropic Noise

Instead of regularizing the transport plan or projecting the coordinates, what if we directly smooth the underlying probability distributions?

Goldfeld analyzed the Smooth Wasserstein Distance (SWD), which is computed by convolving the empirical and target distributions with isotropic Gaussian noise before calculating the transport cost.

Empirical Samples                     Convolved with Gaussian Noise
    •      •                              ░░▒▒░░    ░░▒▒░░
        •        =====> Convolute =====>       ░░▒▒░░
    •      •                              ░░▒▒░░    ░░▒▒░░
(Discrete & Sparse)                     (Continuous & Overlapping)

The intuition here is elegant: high-dimensional sample sparsity means that empirical data points rarely line up. By convolving each data point with a Gaussian kernel, we turn discrete delta masses into overlapping continuous densities. The author proved that this simple smoothing step acts as a powerful statistical regularizer, transforming the empirical convergence rate into a dimension-free $O(n^{-1/2})$.


Geometric Regularization of Potentials

A final perspective focuses on the dual formulation of optimal transport. According to Brenier's theorem, the optimal transport map is the gradient of a convex function, known as the Brenier potential. In high dimensions, estimating this potential from empirical samples is highly unstable.

d'Aspremont and Paty proposed enforcing geometric constraints—specifically smoothness and strong convexity—directly onto the Brenier potentials. By treating regularity as a hard constraint during optimization, the estimator is forced to find a stable, smooth map that interpolates cleanly between sparse data points. This geometric prior effectively tames the high-dimensional variance, allowing the estimator to beat the curse of dimensionality.


Summary

The curse of dimensionality in optimal transport is a consequence of being too precise. When we force an estimator to find the absolute cheapest way to match isolated points in a vast high-dimensional vacuum, it overfits to the sample configuration, leading to an exponential $O(n^{-1/d})$ sample complexity.

As demonstrated across these varied subfields, the solution is always a form of strategic simplification:

  • Entropic Regularization blurs the matching plan.
  • Slicing and Projections restrict our view to low-dimensional perspectives.
  • Low-Rank Constraints limit the degrees of freedom of the coupling matrix.
  • Gaussian Smoothing fills the high-dimensional vacuum with continuous density.

By sacrificing microscopic precision, these methods capture the true macroscopic geometry of distributions, unlocking stable, dimension-free $O(n^{-1/2})$ convergence for high-dimensional machine learning.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dimension_independent_convergence_dimens_52f7c278,
  title = {dimension-independent convergence (dimension-independent sample complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dimension-independent-convergence-dimension-independent-sample-complexity/rdr_52f7c27818474290b557f176129a3faa},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_dimension_independent_convergence_dimens_52f7c278_v1,
  title = {dimension-independent convergence (dimension-independent sample complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dimension-independent-convergence-dimension-independent-sample-complexity/rdr_52f7c27818474290b557f176129a3faa/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake