mlsanityData to 7 Oct 2026

Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes

arXiv 2211.10420 ↗First posted 18 Nov 2022cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a single-loop optimization algorithm for minimizing general convex objectives on these domains, utilizing the principles of Sinkhorn matrix scaling and mirror descent. The proposed algorithm is robust to noise, and can be used in an online setting. We provide theoretical guarantees for convex objectives and experimental results showcasing it effectiveness on both synthetic and real-world data.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 39 of its 69 references that are in the map. First posted on arXiv 18 Nov 2022.

Builds on

39 of 69 references.

References · 39

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2018Computational Optimal Transportcited by 765
  3. 2017Wasserstein Auto-Encoderscited by 371
  4. 2017Learning Generative Models with Sinkhorn Divergencescited by 310
  5. 2017Soft-DTW: a Differentiable Loss Function for Time-Seriescited by 265
  6. 2019Differentiation of Blackbox Combinatorial Solverscited by 224
  7. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  8. 2013Fast Computation of Wasserstein Barycenterscited by 216
  9. 2019Generalized Sliced Wasserstein Distancescited by 205
  10. 2020Fast Differentiable Sorting and Rankingcited by 196
  11. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 188
  12. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 111
27 more
  1. 2018Unsupervised Alignment of Embeddings with Wasserstein Procrustescited by 96
  2. 2017Smooth and Sparse Optimal Transportcited by 83
  3. 2021Differentiable Patch Selection for Image Recognitioncited by 68
  4. 2020Gradient Estimation with Stochastic Softmax Trickscited by 66
  5. 2021GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detectioncited by 66
  6. 2019On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithmscited by 60
  7. 2019Tree-Sliced Variants of Wasserstein Distancescited by 54
  8. 2014Multi-marginal optimal transport: theory and applicationscited by 41
  9. 2021Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projectionscited by 33
  10. 2022Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EMcited by 33
  11. 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 31
  12. 2017Structured Optimal Transportcited by 30
  13. 2019On the Complexity of Approximating Multimarginal Optimal Transportcited by 27
  14. 2019Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytopecited by 26
  15. 2020A gradient descent perspective on Sinkhorncited by 24
  16. 2018Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenterscited by 21
  17. 2018On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimizationcited by 18
  18. 2019On a Combination of Alternating Minimization and Nesterov's Momentumcited by 18
  19. 2021Self-Supervised Learning of Audio Representations from Permutations with Differentiable Rankingcited by 14
  20. 2017Reparameterizing the Birkhoff Polytope for Variational Permutation Inferencecited by 10
  21. 2020Stochastic Optimization for Regularized Wasserstein Estimatorscited by 9
  22. 2018Data-driven regularization of Wasserstein barycenters with an application to multivariate density registrationcited by 8
  23. 2021On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexitycited by 8
  24. 2019Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descentcited by 7
  25. 2021Differentiable Rendering with Perturbed Optimizerscited by 7
  26. 2017On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytopecited by 4
  27. 2022Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelizationcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 1; 2025: 1.

5 papers.

  1. 2023Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradientscited by 6
  2. 2024Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficientlycited by 6
  3. 2025A Truncated Newton Method for Optimal Transportcited by 5
  4. 2023Optimal Transport with Tempered Exponential Measurescited by 3
  5. 2023Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithmcited by 1