Compressed online Sinkhorn

Fengpei Wang, Clarice Poon, Tony Shardlow

Abstract

Optimal Transport (OT) is a fundamental tool for comparing probability distributions, yet its computational cost remains a barrier for large-scale and streaming applications. This paper introduces Compressed Online Sinkhorn (COS), a framework that significantly enhances the efficiency of online OT computation. By integrating a refined convergence analysis with measure compression techniques such as Fourier moments and Gaussian quadrature, COS achieves up to a 4x speedup and substantial memory savings over existing methods while maintaining theoretical accuracy.

Introduction

The Sinkhorn algorithm is the standard for computing entropic Optimal Transport. However, it is traditionally a batch method, requiring the entire dataset to be available upfront. While recent "Online Sinkhorn" variants allow for processing data streams, they suffer from a "memory leak": the complexity of representing dual potentials grows linearly with the number of iterations. This makes long-term deployment on memory-constrained hardware impossible.

This work addresses this bottleneck by proposing Compressed Online Sinkhorn (COS). The authors demonstrate that because dual potentials in entropic OT are smooth, they can be represented using a fixed, small number of basis points or moments. This prevents the computational and memory explosion characteristic of previous online approaches.

Refined Convergence Analysis

A core contribution of this paper is a more rigorous mathematical foundation for online Sinkhorn methods. The authors revisited the existing analysis by Mensch and Peyré (2020), identifying a discrepancy in the original proof. They provide a new, sharper convergence rate, showing that under optimal parameter selection, the algorithm converges faster than previously thought.

Empirical error rates of the Online Sinkhorn (OS) algorithm compared against the authors' refined theoretical rate and the previous state-of-the-art theory.

As shown in the figure above, the empirical error of the algorithm (blue line) closely follows the authors' new theoretical prediction (dotted line), whereas the previous theoretical bound (dashed line) was overly pessimistic. This validation provides confidence in the algorithm's performance as it scales to millions of samples.

The Compressed Online Sinkhorn (COS) Framework

To solve the complexity explosion, COS introduces a measure compression step. Instead of storing every sample to represent the dual potentials, the algorithm approximates them using a fixed budget of $m$ points. Two primary compression strategies are explored:

  1. Gaussian Quadrature: Highly effective for 1D problems, providing optimal point placement for smooth function approximation.
  2. Fourier Moments: Designed for higher-dimensional data. This method exploits the synergy between quadratic cost functions and the Sinkhorn kernel. Since the kernel acts as a low-pass filter in the frequency domain, only a few low-frequency Fourier moments are required to capture the essential shape of the potentials.

Key Results and Efficiency

The authors evaluated COS on synthetic datasets, including high-dimensional Gaussians and complex Gaussian Mixture Models (GMMs).

  • Speed and Memory: In 5D experiments, COS achieved a 4x speedup (92 seconds vs. 386 seconds for standard Online Sinkhorn) while maintaining comparable accuracy. More importantly, the memory footprint of COS remains constant over time, whereas standard methods grow polynomially.
  • Theoretical Consistency: The compressed version of the algorithm was proven to maintain the same asymptotic convergence rate as the uncompressed version, provided the compression quality meets a specific threshold.

Limitations and Future Directions

While COS represents a significant step forward, it is currently optimized for quadratic cost functions. For costs like $L_1$ distance, where frequency decay is slower, Fourier-based compression is less efficient. Future work may explore alternative compression schemes for non-quadratic kernels. Additionally, while tested up to 5D, the "curse of dimensionality" in frequency space remains a challenge for scaling moment-based methods to very high-dimensional feature spaces. Adaptive parameter tuning for the learning rate and batch size also presents an opportunity for further performance gains.

Summary updated

Abstract

The use of optimal transport (OT) distances, and in particular entropic-regularised OT distances, is an increasingly popular evaluation metric in many areas of machine learning and data science. Their use has largely been driven by the availability of efficient algorithms such as the Sinkhorn algorithm. One of the drawbacks of the Sinkhorn algorithm for large-scale data processing is that it is a two-phase method, where one first draws a large stream of data from the probability distributions, before applying the Sinkhorn algorithm to the discrete probability measures. More recently, there have been several works developing stochastic versions of Sinkhorn that directly handle continuous streams of data. In this work, we revisit the recently introduced online Sinkhorn algorithm of Mensch & Peyré (2020). Our contributions are twofold: We improve the convergence analysis for the online Sinkhorn algorithm, the new rate that we obtain is faster than the previous rate under certain parameter choices. We also present numerical results to verify the sharpness of our result. Secondly, we propose the compressed online Sinkhorn algorithm which combines measure compression techniques with the online Sinkhorn algorithm. We provide numerical experiments to show practical numerical gains, as well as theoretical guarantees on the efficiency of our approach.
BibTeX
@misc{wang2023compressed,
  author = {Fengpei Wang and Clarice Poon and Tony Shardlow},
  title = {{Compressed online Sinkhorn}},
  year = {2023},
  eprint = {2310.05019},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.05019},
}
Figure