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.
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:
- Gaussian Quadrature: Highly effective for 1D problems, providing optimal point placement for smooth function approximation.
- 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