Overcoming the Curse of Dimensionality in Optimal Transport

280 concepts213 papers1 proposal

Optimal Transport (OT) provides a geometrically meaningful way to compare probability distributions by computing the minimum cost required to transform one distribution into another. However, when applied to high-dimensional data, standard OT encounters a severe statistical bottleneck: the curse of dimensionality.

The Geometry of the Curse

To understand why standard OT fails in high dimensions, consider estimating the Wasserstein distance between two continuous distributions using finite samples. In a one-dimensional space, computing OT is straightforward—it reduces to sorting the data points. But as the number of dimensions $d$ increases, the volume of the space grows exponentially. Finite samples become isolated points stranded in a vast, empty vacuum.

When we attempt to find an optimal transport map between these sparse empirical samples, the mathematical optimizer is forced to pair points that are far apart. As Alexander Korotin et al. demonstrate in Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark, continuous neural OT solvers frequently experience a sharp decline in accuracy as dimensionality increases, often producing transport directions that are nearly orthogonal to the true ground-truth map. In generative tasks like image-to-image translation, Beomsu Kim et al. note in Unpaired Image-to-Image Translation via Neural Schrödinger Bridge that this orthogonality completely destroys spatial structures.

Statistically, this geometric sparsity manifests as an exponential sample complexity. As Marco Cuturi explains in Computational Optimal Transport, the empirical estimation error scales at a rate of $O(n^{-1/d})$, where $n$ is the number of samples. To maintain the same level of accuracy when moving from 2 dimensions to 20 dimensions, the required number of samples explodes exponentially, rendering standard OT statistically impractical for high-dimensional machine learning tasks.

Entropic Regularization: Blurring the Map

The most prominent breakthrough in overcoming this statistical bottleneck is entropic regularization. Instead of searching for a deterministic, one-to-one Monge map that perfectly matches isolated points, entropic OT adds a Shannon entropy penalty to the optimization objective. This penalty forces the transport plan to be "blurry" or smoother, spreading the mass from a single source point across multiple target points.

Why does this blurriness fix the sample complexity? By regularizing the transport plan, we prevent the model from overfitting to the exact, noisy positions of sparse empirical samples. The entropy penalty acts as a low-pass filter, shifting the focus from high-frequency sample noise to the global geometric structure of the distributions.

As established by Aude Genevay et al. in Sample Complexity of Sinkhorn Divergences and supported by Gonzalo Mena et al. in Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem, this simple geometric blurring fundamentally alters the statistical behavior of the estimator. Entropic optimal transport (and its derivative, the Sinkhorn divergence) completely bypasses the curse of dimensionality, achieving a dimension-independent sample complexity of $O(n^{-1/2})$. This matches the rate of Maximum Mean Discrepancy (MMD) while retaining the underlying geometric awareness of optimal transport.

Dimensionality Reduction via Subspace Projections

Another intuitive strategy to escape the curse of dimensionality is to project high-dimensional distributions onto lower-dimensional spaces where optimal transport is statistically efficient.

The Sliced-Wasserstein (SW) distance takes this idea to its logical extreme by projecting multi-dimensional distributions onto random one-dimensional lines. Because 1D optimal transport can be solved exactly and instantly via sorting, SW avoids the computational and statistical pitfalls of high-dimensional spaces. As shown by Kimia Nadjahi et al. in Approximate Bayesian Computation with the Sliced-Wasserstein Distance, this projection mechanism allows transport-based distance estimation to scale gracefully to high-dimensional data without losing structural fidelity.

However, random 1D projections can discard important multivariate structures. To preserve these relationships, Projection Robust Wasserstein (PRW) distances search for the best $k$-dimensional subspace that maximizes the transport cost between two distributions. By focusing only on the orthogonal subspace where the two distributions differ the most, PRW filters out uninformative ambient noise. Tianyi Lin et al. demonstrated in On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification that PRW distances achieve a fast convergence rate that depends only on the subspace dimension $k$ rather than the ambient dimension $d$, providing robust estimation even under model misspecification.

Structural Constraints and Low-Rank Couplings

A third paradigm forces structural constraints directly onto the transport plan itself, assuming that high-dimensional data inherently lies on or moves along a low-dimensional manifold.

Instead of allowing arbitrary transport plans, Aden Forrow introduced Factored Couplings in Statistical Optimal Transport via Factored Couplings, which restrict the transport plan to a low-rank matrix factorization. This constraint implies that mass is routed through a small number of latent bottleneck variables or anchor points. By constraining the degrees of freedom in the transport plan, this approach achieves a statistical convergence rate completely independent of the ambient dimension, making it highly effective for fields like single-cell genomics where features number in the thousands but underlying biological processes are low-dimensional.

Summary

The curse of dimensionality in optimal transport stems from a fundamental geometric mismatch: standard OT tries to find exact, deterministic matchings between sparse samples in an exponentially vast space. Modern research circumvents this by either blurring the matching via entropic regularization, projecting the data onto low-dimensional subspaces, or enforcing low-rank structural constraints on the transport plan. Each of these mechanisms trades off fine-grained, high-frequency deterministic accuracy for robust, dimension-independent statistical convergence.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 225 papers
  2. Version 1 · 2026-10-04 · 271 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_in_optimal_trans_70dd94f0,
  title = {curse of dimensionality in optimal transport (curse of dimensionality)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-in-optimal-transport-curse-of-dimensionality/rdr_70dd94f094df41aaa8424c67beb886f4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_curse_of_dimensionality_in_optimal_trans_70dd94f0_v2,
  title = {curse of dimensionality in optimal transport (curse of dimensionality)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-in-optimal-transport-curse-of-dimensionality/rdr_70dd94f094df41aaa8424c67beb886f4/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake