Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration

By Jason M. Altschuler, Jonathan Weed, Philippe Rigollet. 2017

689 citations recorded by the source corpus.

Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iteration, which also directly suggests a new greedy coordinate descent algorithm, Greenkhorn, with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice.

Subfields: Artificial Intelligence, Management Science and Operations Research, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Eric Wong
2. J. Kolter
3. Lawrence Carin
4. Frank R. Schmidt
5. G. Peyr'e
6. Marco Cuturi
7. Ray Jiang
8. Hongyuan Zha

In Management Science and Operations Research

1. Frank R. Schmidt
2. Lawrence Carin
3. J. Kolter
4. Hongyuan Zha
5. G. Peyr'e
6. Marco Cuturi
7. Michael M. Bronstein
8. Ruijia Wang

In Numerical Analysis

1. Frank R. Schmidt
2. Lawrence Carin
3. J. Kolter
4. Hongyuan Zha
5. G. Peyr'e
6. Marco Cuturi
7. Ruijia Wang
8. Xiangfeng Wang

Citations in the corpus

• Wasserstein Adversarial Examples via Projected Sinkhorn Iterations (2019, methodology): “However, it was shown that by subtracting an entropy regularization term, one can compute approximate Wasserstein distances extremely quickly using the Sinkhorn iteration (Cuturi, 2013), later shown to run in near-linear time (Altschuler et al., 2017).”
• Computational Optimal Transport (2018, methodology): “By doing a careful convergence analysis (assuming n = m for the sake of simplicity), Altschuler et al. [2017] showed that by setting ε = 4 log(n) τ ,O(‖C‖ 3 ∞ log(n)τ−3) Sinkhorn iterations (with an additional rounding step to com-”
• Gromov-Wasserstein Learning for Graph Matching and Node Embedding (2019, background): “The work in (Altschuler et al., 2017) proves that solving the regularized optimal transport based on Sinkhorn projections is with linear convergence.”
• Fast geometric learning with symbolic matrices (2020, positive): “This implementation is straightforward to generalize to stochastic settings [2, 3, 47] and non-Euclidean cost functions [9, 28, 30]: we believe that it will open new ranges of applications to the OT community [37, 39].”
• A General Approach to Fairness with Optimal Transport (2020, methodology): “Solving this regularized objective can be done efficiently via the Sinkhorn algorithm (Cuturi and Doucet 2014), which achieves a linear convergence rate (Altschuler, Weed, and Rigollet 2017).”
• A Fast Proximal Point Method for Computing Exact Wasserstein Distance (2018, methodology): “The iteration is also referred as Sinkhorn iteration, and the method is referred as Sinkhorn algorithm which, recently, is proven to achieve a near-O(n2) complexity (Altschuler et al., 2017).”
• Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics (2018, background): “…of these algorithmic successes and the behavior of some statistical procedures in general (we refer to Bhattacharya and Patrangenaru, 2003; Kendall and Le, 2011; Le Gouic and Loubes, 2017; Altschuler et al., 2017; Dvurechensky et al., 2018; Bigot et al., 2018, for works in this direction).”
• A Fast Proximal Point Method for Computing Wasserstein Distance (2018, methodology): “Following the same strategy, many variants of the Sinkhorn algorithm have been proposed [2, 9, 35].”