Compressed online Sinkhorn
Fengpei Wang Clarice Poon Tony Shardlow
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 and Peyr\'e, 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.