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:
- Flawed Convergence Rates: The original analysis claimed rates approaching $O(N^{-1})$, but relied on an inapplicable stochastic approximation result.
- 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