mlsanityData to 14 Oct 2026

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

arXiv 1705.09634 ↗First posted 26 May 2017cs.DS stat.MLcited by 223

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 223 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 42; 2022: 47; 2023: 37; 2024: 31; 2025: 32; 2026: 34.

223 papers.

Sort:

By area:

  1. 2023Multisample Flow Matching: Straightening Flows with Minibatch Couplingscited by 278
  2. 2021Entropic estimation of optimal transport mapscited by 90
  3. 2023Simulation-free Schr"odinger bridges via score and flow matchingcited by 83
  4. 2021Low-Rank Sinkhorn Factorizationcited by 67
  5. 2021Minibatch optimal transport distances; analysis and applicationscited by 65
  6. 2021Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costscited by 61
  7. 2021Differentiable Particle Filtering via Entropy-Regularized Optimal Transportcited by 59
  8. 2022Understanding DDPM Latent Codes Through Optimal Transportcited by 45
  9. 2021Improving Mini-batch Optimal Transport via Partial Transportationcited by 41
  10. 2022Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networkscited by 41
  11. 2021Neural Monge Map estimation and its applicationscited by 40
  12. 2021Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutionscited by 39
38 more
  1. 2021Sinkhorn Distributionally Robust Optimizationcited by 38
  2. 2023Debias Coarsely, Sample Conditionally: Statistical Downscaling through Optimal Transport and Probabilistic Diffusion Modelscited by 33
  3. 2021Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Trainingcited by 32
  4. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  5. 2023Optimal Transport for Treatment Effect Estimationcited by 32
  6. 2023Transformed Distribution Matching for Missing Value Imputationcited by 31
  7. 2022Trajectory Inference via Mean-field Langevin in Path Spacecited by 30
  8. 2022Meta Optimal Transportcited by 28
  9. 2024PTaRL: Prototype-based Tabular Representation Learning via Space Calibrationcited by 28
  10. 2024Wasserstein Flow Matching: Generative modeling over families of distributionscited by 28
  11. 2021On Robust Optimal Transport: Computational Complexity and Barycenter Computationcited by 27
  12. 2023Scalable Optimal Transport Methods in Machine Learning: A Contemporary Surveycited by 27
  13. 2022Towards Compositional Adversarial Robustness: Generalizing Adversarial Training to Composite Semantic Perturbationscited by 26
  14. 2022Revisiting Sliced Wasserstein on Images: From Vectorization to Convolutioncited by 25
  15. 2022Wasserstein Task Embedding for Measuring Task Similaritiescited by 25
  16. 2022Domain Adaptation for Time-Series Classification to Mitigate Covariate Shiftcited by 24
  17. 2022Hierarchical Sliced Wasserstein Distancecited by 23
  18. 2022Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenterscited by 22
  19. 2025Multivariate Conformal Prediction using Optimal Transportcited by 22
  20. 2023Self-supervised Learning for Pre-Training 3D Point Clouds: A Surveycited by 21
  21. 2022Fine-Tuning Graph Neural Networks via Graph Topology induced Optimal Transportcited by 19
  22. 2024Wasserstein Distance Rivals Kullback-Leibler Divergence for Knowledge Distillationcited by 19
  23. 2022Amortized Projection Optimization for Sliced Wasserstein Generative Modelscited by 17
  24. 2021On Transportation of Mini-batches: A Hierarchical Approachcited by 16
  25. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
  26. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  27. 2021Smooth p-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applicationscited by 15
  28. 2023Unbalanced Optimal Transport: A Unified Framework for Object Detectioncited by 15
  29. 2021On the complexity of the optimal transport problem with graph-structured costcited by 14
  30. 2022Adaptive Distribution Calibration for Few-Shot Learning with Hierarchical Optimal Transportcited by 14
  31. 2021Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solutioncited by 13
  32. 2024Partially Observed Trajectory Inference using Optimal Transport and a Dynamics Priorcited by 13
  33. 2024Identifying Drift, Diffusion, and Causal Structure from Temporal Snapshotscited by 13
  34. 2025DistDF: Time-Series Forecasting Needs Joint-Distribution Wasserstein Alignmentcited by 13
  35. 2021Entropic Gromov-Wasserstein between Gaussian Distributionscited by 12
  36. 2022Approximate Policy Iteration with Bisimulation Metricscited by 12
  37. 2022Discovering Conservation Laws using Optimal Transport and Manifold Learningcited by 12
  38. 2023Linearized Wasserstein dimensionality reduction with approximation guaranteescited by 12

50 most cited of 223 All 223 (JSON)