Unbalanced Optimal Transport meets Sliced-Wasserstein

Thibault Séjourné, Clément Bonet, Kilian Fatras, Kimia Nadjahi, Nicolas Courty

Introduction

Optimal Transport (OT) has emerged as a fundamental tool for comparing probability distributions. However, its practical application is often hindered by two significant challenges: high computational complexity and the requirement for mass conservation. Standard OT scales cubically ($O(n^3)$) with the number of samples, and it necessitates that the total mass of the compared distributions be equal. In real-world scenarios, such as comparing document word counts or biological cell populations, these constraints are rarely met.

To address these issues, researchers have developed Sliced Optimal Transport (SOT) for speed and Unbalanced Optimal Transport (UOT) for robustness to mass mismatches and outliers. This paper introduces a novel framework that bridges these two paradigms, proposing Sliced Unbalanced Optimal Transport (SUOT) and Unbalanced Sliced Optimal Transport (USOT).

Methodology: Slicing the Unbalanced Problem

The core idea is to leverage the efficiency of 1D projections (slicing) while incorporating the flexibility of unbalanced transport. The authors propose two distinct strategies:

  1. Sliced Unbalanced OT (SUOT): This method projects the high-dimensional data onto 1D lines first and then solves an independent unbalanced OT problem for each projection. This approach provides "local" robustness, effectively ignoring outliers within specific 1D views.
  2. Unbalanced Sliced OT (USOT): This variant performs a global reweighting of the original high-dimensional measures before applying standard slicing. By identifying outliers in the original space, USOT offers a more comprehensive "global" robustness.
Comparison of original distributions and the 1D projections used in SUOT and USOT.

To solve these problems efficiently, the authors developed a GPU-friendly algorithm based on the Frank-Wolfe method. This approach decomposes the complex unbalanced optimization into a sequence of simpler, balanced sliced problems, which can be solved rapidly using 1D sorting.

Theoretical Contributions

The paper provides a rigorous mathematical foundation for these new metrics. Key theoretical results include:

  • Metrizability: Proving that SUOT and USOT define valid distances on the space of positive measures.
  • Sample Complexity: Demonstrating that these methods enjoy "dimension-free" sample complexity, meaning the amount of data required to estimate the distance does not grow exponentially with the dimensionality of the space.

Empirical Results and Applications

The proposed methods were evaluated across several challenging tasks:

  • Computational Efficiency: On the large-scale Goodreads dataset, USOT achieved a 40x speedup compared to traditional UOT solvers.
  • Document Classification: In tasks involving word embeddings (BBCSport, Movies, Goodreads), USOT consistently outperformed standard SOT by effectively ignoring "noise" words that do not contribute to the document's primary topic.
  • Geophysical Modeling: The authors successfully computed unbalanced barycenters for the ClimateNet dataset on a $200 \times 200$ grid—a task previously considered computationally intractable.
  • Image Processing: In color transfer experiments, USOT demonstrated superior robustness, preventing "color bleeding" by ignoring artifacts and logos in the source images.

Conclusion and Future Directions

The SUOT and USOT frameworks offer a powerful combination of speed, scalability, and robustness. While highly effective, the methods currently require manual tuning of the "reach" parameter $\rho$, which controls mass destruction. Future work includes automating this parameter selection and extending the theoretical sample complexity proofs to the USOT variant.

This paper was reviewed on OpenReview: https://openreview.net/forum?id=AjJTg5M0r8

Summary updated

BibTeX
@inproceedings{sejourne2023unbalanced,
  author = {Thibault Séjourné and Clément Bonet and Kilian Fatras and Kimia Nadjahi and Nicolas Courty},
  title = {{Unbalanced Optimal Transport meets Sliced-Wasserstein}},
  booktitle = {Frontiers4LCD @ ICML},
  year = {2023},
  url = {https://openreview.net/forum?id=gpGn3uG2yu},
}
Figure