Low-rank Optimal Transport: Approximation, Statistics and Debiasing

Meyer Scetbon, marco cuturi

Optimal Transport (OT) is a powerful mathematical framework for comparing probability distributions, increasingly used in machine learning applications ranging from single-cell genomics to self-supervised learning. However, to scale to modern, massive datasets, OT requires solvers that can operate on millions of points.

This paper provides a rigorous theoretical and practical foundation for Low-rank Optimal Transport (LOT), a method that scales OT by restricting the complexity of the "coupling" between datasets. The authors prove that LOT avoids the "curse of dimensionality" that plagues standard transport methods and introduce a "debiased" version that makes it a highly reliable tool for machine learning tasks.

The Challenges of Standard Optimal Transport

While highly effective, standard OT faces two major hurdles:

  1. Computational Cost: Solving the standard OT problem (the Kantorovich problem) for $n$ points typically scales as $O(n^3 \log n)$, which is prohibitive for large datasets.
  2. Statistical Fragility: In high-dimensional spaces, estimating OT from samples becomes incredibly difficult—a phenomenon known as the "curse of dimensionality."

"Low-rank" OT (restricting the transport plan to a low-rank matrix) was previously proposed to achieve linear $O(n)$ scaling. However, its theoretical properties were poorly understood. Specifically, it was unclear how fast it converges to "true" OT as rank increases, or how well it behaves statistically. Furthermore, LOT suffers from a "bias" where the distance between a distribution and itself is not zero, which can break machine learning models relying on gradient flows.

Advancing Low-Rank Optimal Transport

The authors build upon the LOT framework, which constrains the search for an optimal coupling to those with a non-negative rank at most $r$. They introduce several key improvements:

  • Debiased LOT (DLOT): Inspired by Sinkhorn divergences, the authors propose a debiasing formula: $DLOT(P, Q) = LOT(P, Q) - \frac{1}{2}[LOT(P, P) + LOT(Q, Q)]$. This ensures that the distance from a distribution to itself is zero, allowing it to behave like a proper "divergence."
  • Optimization Improvements: They introduce an adaptive step-size for the mirror descent algorithm used to solve LOT, making it more robust across different problems without manual tuning.
  • Smart Initialization: Because the LOT problem is non-convex, the authors propose using k-means clustering to initialize the algorithm. This significantly reduces the risk of getting stuck in poor local minima.

Key Insights and Results

Defeating the Curse of Dimensionality

The most significant theoretical finding is that the statistical error of LOT is $O(1/\sqrt{n})$, a rate that is independent of the dimension. This makes LOT far more robust for high-dimensional data than standard OT. Empirical tests on synthetic mixtures of Gaussians confirmed that the error rate does not degrade as the dimension $d$ increases, perfectly matching the authors' theoretical upper bounds.

Empirical statistical rates for DLOT across different dimensions and ranks. The consistent slopes indicate that the convergence rate is independent of the dimension $d$.

LOT as Generalized Clustering

The authors prove that LOT is essentially a generalization of the k-means clustering algorithm. When the rank $r$ is small, LOT acts like a soft-clustering mechanism that matches groups of points rather than individual points.

The Importance of Debiasing in Gradient Flows

Without debiasing, a model trying to learn a distribution via LOT will "shrink" the distribution toward a low-rank structure rather than matching the true target. DLOT fixes this, allowing for accurate recovery of complex shapes. This is vividly demonstrated in 2D gradient flow experiments, where a source distribution is morphed to match a target "moon" shape.

Comparison of gradient flows. DLOT (top row) successfully recovers the target moon shape, while standard biased LOT (bottom row) collapses into a low-rank skeleton.

Limitations and Future Work

While these advancements solidify LOT as a legitimate contender to entropic regularization, some challenges remain:

  • Non-Convexity: Even with k-means initialization, LOT remains a non-convex problem, meaning there is no absolute guarantee of reaching the global optimum in all cases.
  • Tightness of Bounds: The authors provided an upper bound for the statistical complexity but note they "fall short of providing a lower bound." Proving that their $1/\sqrt{n}$ rate is the absolute best possible for this class of problems remains an open theoretical challenge.
  • Hyperparameter Tuning: The choice of rank $r$ still acts as a trade-off between computational speed and approximation accuracy that practitioners must navigate carefully.

Summary updated

Abstract

The matching principles behind optimal transport (OT) play an increasingly important role in machine learning, a trend which can be observed when OT is used to disambiguate datasets in applications (e.g. single-cell genomics) or used to improve more complex methods (e.g. balanced attention in transformers or self-supervised learning). To scale to more challenging problems, there is a growing consensus that OT requires solvers that can operate on millions, not thousands, of points. The low-rank optimal transport (LOT) approach advocated in \cite{scetbon2021lowrank} holds several promises in that regard, and was shown to complement more established entropic regularization approaches, being able to insert itself in more complex pipelines, such as quadratic OT. LOT restricts the search for low-cost couplings to those that have a low-nonnegative rank, yielding linear time algorithms in cases of interest. However, these promises can only be fulfilled if the LOT approach is seen as a legitimate contender to entropic regularization when compared on properties of interest, where the scorecard typically includes theoretical properties (statistical complexity and relation to other methods) or practical aspects (debiasing, hyperparameter tuning, initialization). We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
BibTeX
@inproceedings{scetbon2022low,
  author = {Meyer Scetbon and marco cuturi},
  title = {{Low-rank Optimal Transport: Approximation, Statistics and Debiasing}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=4btNeXKFAQ},
}
Figure