Statistical Convergence Rates for Empirical Optimal Transport

14 concepts6 papers1 proposal

Optimal Transport (OT) has become a cornerstone of modern machine learning, offering a geometrically meaningful way to compare probability distributions. However, in practical applications, we rarely have access to the true, continuous population distributions. Instead, we work with finite samples—empirical measures.

This reality raises a fundamental statistical question: How well do optimal transport quantities estimated from finite samples approximate their true population counterparts?

A growing body of research establishes the statistical foundations of empirical optimal transport. By analyzing the convergence rates, asymptotic distributions, and stability of these estimators, this line of work explains not just that empirical OT works, but precisely why and how fast it converges across various settings.


The Geometric Intuition: Empirical Measures as Epsilon-Nets

To understand why empirical optimal transport converges, we must first understand how a discrete point cloud approximates a continuous distribution. If we sample $n$ points from a continuous manifold, how well do those points represent the underlying space?

A powerful way to quantify this is through the lens of $\infty$-optimal transportation distance. While standard Wasserstein distances ($W_1$ or $W_2$) measure the average cost of moving mass, the $W_\infty$ distance measures the maximum distance that any single unit of mass must travel.

Continuous Distribution (True Manifold)
───────────────────────────────────────────────────────
   •       •        •        •        •        •      <- Empirical Samples
   └───┬───┘└───┬────┘└───┬───┘└───┬───┘└───┬───┘
     Max Displacement (W_infinity) acts as the radius of an Epsilon-Net

As shown by Nicolás García Trillos et al., the $W_\infty$ distance between an empirical measure and the true volume form on a submanifold functions as a probabilistic equivalent to an $\epsilon$-net. By establishing tight bounds on this maximum displacement, the authors provide a reliable mechanism to guarantee that a random point cloud structurally approximates the continuous manifold. This geometric control is what allows discrete graph-based operators (like the graph Laplacian) to consistently converge to their continuous counterparts (the Laplace-Beltrami operator).


Overcoming the Curse of Dimensionality via Regularization

While vanilla OT provides beautiful geometry, it suffers from a severe statistical drawback: the curse of dimensionality. For unregularized Wasserstein distances, the sample complexity scales exponentially with the dimension $d$ (roughly $n^{-1/d}$), making it statistically impractical in high dimensions.

To bypass this limitation, practitioners use regularized variants of OT, such as sliced, smoothed, or entropic optimal transport. But how do these regularizations affect statistical inference?

Standard OT Dual Potentials:       Regularized OT Dual Potentials:
      Rough, highly sensitive            Smooth, stable under perturbation
             /\    /\                                ───────
            /  \  /  \                              /       \
  ─────────/    \/    \─────────          ─────────/         \─────────
  (High variance, slow convergence)       (Low variance, fast convergence)

Ziv Goldfeld et al. developed a unified statistical framework to answer this. They demonstrated that regularizing OT smooths the underlying dual potentials, making the empirical objective far less sensitive to individual sample fluctuations. By leveraging empirical process theory, the authors proved that regularized OT distances satisfy asymptotic normality, semiparametric efficiency, and bootstrap consistency. This smoothing effectively breaks the curse of dimensionality, providing the theoretical guarantees necessary for robust hypothesis testing and confidence intervals.

This regularizing effect is also vital in Bayesian nonparametrics. When shifting from traditional metrics (like Total Variation) to Wasserstein metrics, Minwoo Chae et al. analyzed how posterior distributions shrink around a target distribution. They showed that if the prior distribution is sufficiently regular, the posterior distribution converges at near-optimal speeds, demonstrating that regularized geometric structures naturally accelerate learning.


Stability in Averaging: Empirical Barycenters

Often, we don't just want to compare two distributions; we want to average multiple distributions. In Wasserstein space, this geometric average is known as a Wasserstein barycenter. Because we compute empirical barycenters from sample data, we need to know if a small error in our sample drastically alters the resulting average.

Input Measures (with sample noise)          Wasserstein Barycenter
     μ₁* ───┐
     μ₂* ───┼─► [ Hölder-Continuous Mapping ] ─►    Barycenter(μ*)
     μ₃* ───┘                                           │
                                                        ▼
                                            Guaranteed close to the 
                                            true population barycenter

Alex Delalande et al. addressed this by proving the quantitative stability of Wasserstein barycenters. They established that the map taking input measures to their barycenter is Hölder-continuous. This stability means that small, predictable changes in the input measures yield small, predictable changes in the barycenter. Statistically, this continuity serves as the exact bridge needed to prove that empirical barycenters converge reliably to the true population barycenter as sample sizes grow.


Extending Guarantees to Relational Spaces: Gromov-Wasserstein

The ultimate frontier for this statistical theory is the Gromov-Wasserstein (GW) distance. Unlike standard OT, which requires distributions to lie in the same metric space, GW compares distributions across different metric spaces (e.g., aligning a text embedding space with an image embedding space) by comparing the internal distances between pairs of points.

Because GW solves a quadratic assignment problem rather than a linear one, its statistical properties were long unmapped. Two recent papers cracked this open by connecting GW back to classical OT principles:

  • Duality and Sample Complexity: Zhengxin Zhang et al. introduced a novel duality framework for the GW distance. By performing a regularity analysis on the dual potentials and applying empirical process theory, the authors derived the first theoretical upper bounds on the convergence rates of empirical GW distances. Remarkably, they proved that despite GW's significantly higher algebraic complexity, its empirical convergence rates match those of standard OT.
  • Semi-Discrete Alignment Maps: In many real-world tasks, we compare a continuous space to a discrete sample (a semi-discrete setting). Gabriel Rioux et al. established a condition for the existence of optimal "Gromov-Monge maps" that align these spaces. They leveraged this geometric structure to provide finite-sample convergence rates and asymptotic distributions for the empirical semi-discrete GW distance, enabling dimension-independent statistical inference for cross-domain alignment.

Summary

The statistical viability of empirical optimal transport relies on a beautiful interplay between geometry and probability:

  1. $W_\infty$ bounds ensure that discrete samples fill out continuous spaces evenly, acting as probabilistic nets.
  2. Regularization smooths out dual potentials, suppressing sample variance and breaking the curse of dimensionality.
  3. Hölder stability ensures that errors in empirical inputs do not explode when computing geometric averages like barycenters.
  4. Duality frameworks allow even highly complex, quadratic metrics like Gromov-Wasserstein to inherit the clean, well-behaved sample complexity of classical linear optimal transport.

Key Foundational Work

Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace-Beltrami Operator (2020) — contributed 2 concept elements to this direction.
Posterior asymptotics in Wasserstein metrics on the real line (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_infinity_optimal_transportation_bounding_a0459637,
  title = {infinity-optimal transportation bounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinity-optimal-transportation-bounding/rdr_a045963724bf4d5d9668070ec0049811},
  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_infinity_optimal_transportation_bounding_a0459637_v1,
  title = {infinity-optimal transportation bounding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinity-optimal-transportation-bounding/rdr_a045963724bf4d5d9668070ec0049811/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