Compressed Online Sinkhorn

Fengpei Wang, Clarice Poon, Tony ShardlowSubmission to ICLR 2024 · Rejected

TL;DR

This paper revisits the online Sinkhorn algorithm for computing entropic optimal transport on streaming continuous distributions. The authors correct and sharpen its theoretical convergence rate and introduce Compressed Online Sinkhorn (COS), which dramatically cuts computational complexity by compressing the growing discrete support of the dual potential functions using quadrature and Fourier moment matching.

What Problem Does This Paper Address?

Computing optimal transport (OT) distances between continuous distributions is central to machine learning tasks spanning generative modeling, imaging, and single-cell genomics. While standard discrete Sinkhorn algorithms require first drawing a large batch of samples and building an $O(N^2)$ pairwise distance matrix, online Sinkhorn (introduced by Mensch & Peyré, 2020) handles continuous streaming data directly.

However, online Sinkhorn suffers from two major pain points:

  1. Flawed Convergence Rates: The original analysis claimed rates approaching $O(N^{-1})$, but relied on an inapplicable stochastic approximation result.
  2. Computational Bloat: To represent continuous dual potentials (Kantorovich potentials) in an online fashion, the algorithm accumulates Diracs over time. Evaluating potentials against these expanding sums makes per-iteration costs grow polynomially ($O(n_t b_t)$), negating its practical benefits over classic Sinkhorn as sample counts scale up.

Methods

The paper develops two key advances:

  • Corrected Convergence Rate for Online Sinkhorn: Using a discrete Gronwall lemma, the authors prove that with decaying stepsizes $\eta_t = t^b$ ($-1 < b < -1/2$) and growing batch sizes $b_t = t^{2a}$ ($a - b > 1$), the variational error decays as $O(N^{-\frac{a}{2a+1}})$ (at best $O(N^{-1/2})$), correcting the previous rate while showing that convergence is faster than previously proven when $a \ge -b$.
  • Compressed Online Sinkhorn (COS): Rather than letting the number of Dirac atoms representing the continuous potentials $u_t$ and $v_t$ grow indefinitely, COS compresses the measure to $m \ll n_t$ atoms at each step while preserving integral accuracy:
  • 1D Gaussian Quadrature (GQ): Approximates integrals against polynomial test spaces up to degree $2m-1$.
  • Fourier Moments Compression (Multi-dimensional): Matches Fourier moments over a set of frequencies sampled via Gaussian Quasi-Monte Carlo (QMC). Solving a non-negative least squares (NNLS) problem compresses the support while bounding functional approximation error.
Streaming Data (α, β) ──> Online Sinkhorn Update ──> Potential (Size nt + bt)
                                                            │
                                                     [ Compression ]
                                                            ▼
                                                   Sparse Potential (Size m)

Datasets

The authors evaluate their methods on synthetic continuous probability distributions across 1D, 2D, and 5D:

  • 1D Distributions: Unidimensional Gaussians $\mathcal{N}(3, 4)$ and $\mathcal{N}(1, 2)$.
  • 2D & 5D Distributions: Randomly generated Gaussians and two-component Gaussian Mixture Models (GMMs) with randomized means and covariance matrices.

No new real-world benchmark datasets were introduced.

Key Insights and Ideas

  • Theoretical Correction: The asymptotic rate of online Sinkhorn cannot be $O(N^{-1})$; it is bottlenecked at $O(N^{-1/2})$, matching the statistical sample complexity of entropic optimal transport.
  • Why Fourier Compression Works for OT: Under a quadratic cost $C(x, y) = \|x - y\|_2^2$, the kernel $\exp(-C/\varepsilon)$ is Gaussian. Its Fourier transform decays exponentially fast, allowing low-order Fourier moments to capture the dual potentials with minimal distortion.
  • Asymptotic Complexity Win: When the compression rate $\zeta$ exceeds $\frac{3(a-b)}{4a+1}$, COS achieves an asymptotically superior complexity-to-accuracy ratio over standard online Sinkhorn.

Key Results

  • Empirical Validation of the New Bound: Experiments in 1D, 2D, and 5D verify that the empirical variational convergence slope matches the theoretical exponent $-a / (2a+1)$ rather than the older literature bound.
  • Wall-Clock Speedups:
  • 2D GMM: COS with Fourier compression reached target objective error in 100s, compared to 449s for vanilla Online Sinkhorn (~4.5× speedup).
  • 5D GMM: COS finished in 92s, versus 153s for Online Sinkhorn (~1.6× speedup).
  • 1D Gaussian: OS and COS-Fourier tied at 130s, while COS-GQ took 151s due to quadrature setup overhead.

Limitations and Future Work

  • Cost Function Sensitivity: Fourier compression shines with quadratic costs due to rapid Gaussian frequency decay. For costs like $\ell_1$ ($C(x, y) = \|x - y\|_1$), frequency decay is much slower, worsening compression quality.
  • Curse of Dimensionality in QMC: In dimensions $d \ge 5$, the QMC error bound contains a logarithmic term $O((\log m)^d / m)$, which attenuates practical speedups.
  • Adaptive Step Sizes: In early iterations, a linear contraction term dominates before the polynomial asymptotic rate takes over; designing adaptive schemes for parameters $(a, b)$ remains open.

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