Low-rank Optimal Transport: Approximation, Statistics and Debiasing

Meyer Scetbon, Marco Cuturi

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 Scetbon et al. (2021) 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.

Introduction

Optimal Transport (OT) has emerged as a cornerstone of modern machine learning, providing a robust framework for aligning distributions in tasks ranging from single-cell genomics to the stabilization of attention mechanisms in Transformers. Despite its utility, OT faces two significant hurdles: computational complexity and the "curse of dimensionality." Standard OT solvers typically scale quadratically or cubically with the number of data points, and statistical estimation becomes exponentially more difficult as the dimensionality of the data increases.

To address these challenges, this work investigates Low-rank Optimal Transport (LOT). By restricting the transport plan to a low-rank structure, LOT offers a path toward linear-time algorithms. This paper provides the theoretical and practical foundations necessary to establish LOT as a rigorous alternative to entropic regularization, introducing a debiased formulation and proving that LOT can effectively bypass the curse of dimensionality.

The Low-Rank Framework

The core idea of LOT is to constrain the search space for the optimal coupling—the plan that dictates how mass is moved between distributions—to those with a low nonnegative rank $r$. In high-dimensional settings, standard OT estimation error scales at a rate of $n^{-1/d}$, requiring an exponential increase in data as dimensions ($d$) grow. By contrast, the LOT framework simplifies the coupling, which intuitively should improve statistical stability. However, until now, the trade-offs between approximation error and statistical efficiency remained poorly understood.

Addressing Bias: The Debiased LOT (DLOT)

A significant limitation of the original LOT formulation is its inherent bias; the model tends to favor low-rank structures even when comparing a distribution to itself. To rectify this, we introduce Debiased LOT (DLOT). Similar to the construction of Sinkhorn Divergences, DLOT incorporates a debiasing term that ensures the distance between a distribution and itself is zero. This adjustment ensures that DLOT is a valid divergence that metrizes weak convergence, making it suitable for sensitive applications like gradient flows and generative modeling.

Theoretical Contributions

Bypassing the Curse of Dimensionality

The most significant theoretical finding of this work is that the statistical error of LOT scales at a rate of $1/\sqrt{n}$, a rate that is independent of the ambient dimension $d$. This result positions LOT as a superior choice for high-dimensional data analysis where standard OT would be statistically unreliable.

Approximation and Clustering

We provide the first clear approximation bounds for LOT, showing that for $n$ points, the error incurred by choosing a rank $r$ is approximately $O(\ln(n)/r)$. Furthermore, we reveal a fundamental link between LOT and unsupervised learning: solving the LOT problem between a distribution and itself is mathematically equivalent to the k-means clustering problem. This connection allows LOT to be viewed as a generalized form of clustering that can be adapted to any geometry by simply changing the underlying cost function.

Practical Implementation

Because the LOT optimization problem is non-convex, the choice of initialization and optimization strategy is critical. We propose several enhancements to ensure robust performance:

  1. Adaptive Step Sizes: We introduce a normalized mirror descent scheme where the step size adapts to the gradient's norm. This eliminates the need for manual hyperparameter tuning and ensures convergence across diverse datasets.
  2. Smart Initialization: Leveraging the link to clustering, we suggest using k-means or a "generalized k-means" (based on the specific cost function) to initialize the low-rank factors, significantly reducing the risk of falling into poor local minima.

Experimental Validation

Our findings are validated across several benchmarks:

  • Statistical Stability: Tests on synthetic Gaussian mixtures confirm that DLOT’s convergence rate remains stable as dimensions increase from 2 to 10, whereas standard OT performance degrades.
  • Gradient Flows: Experiments on "Moon" distributions demonstrate that while biased LOT results in distorted approximations, DLOT successfully recovers the target distribution.
  • Real-World Embeddings: On the Newsgroup20 dataset, our adaptive optimization and initialization strategies proved essential for handling high-dimensional text embeddings effectively.

Conclusion

By providing rigorous statistical guarantees and a debiased formulation, this work cements Low-rank Optimal Transport as a powerful tool for large-scale machine learning. LOT not only offers computational efficiency but also provides a statistically robust framework that overcomes the dimensionality constraints of traditional OT. Future work will explore the application of these low-rank principles to even more complex problems, such as Gromov-Wasserstein distances for matching datasets in disparate coordinate spaces.

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