mlsanityData to 7 Oct 2026

On Robust Optimal Transport: Computational Complexity and Barycenter Computation

arXiv 2102.06857 ↗First posted 13 Feb 2021cs.LG cs.DS math.OCcited by 27

Not on the map. Why?

Abstract (arXiv)

We consider robust variants of the standard optimal transport, named robust optimal transport, where marginal constraints are relaxed via Kullback-Leibler divergence. We show that Sinkhorn-based algorithms can approximate the optimal cost of robust optimal transport in widetildeO(fracn2varepsilon) time, in which n is the number of supports of the probability distributions and varepsilon is the desired error. Furthermore, we investigate a fixed-support robust barycenter problem between m discrete probability distributions with at most n number of supports and develop an approximating algorithm based on iterative Bregman projections (IBP). For the specific case m = 2, we show that this algorithm can approximate the optimal barycenter value in widetildeO(fracmn2varepsilon) time, thus being better than the previous complexity widetildeO(fracmn2varepsilon2) of the IBP algorithm for approximating the Wasserstein barycenter.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 23 of its 38 references that are in the map. First posted on arXiv 13 Feb 2021.

Builds on

23 of 38 references.

References · 23

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  3. 2017Improved Training of Wasserstein GANscited by 2,223
  4. 2018Computational Optimal Transportcited by 765
  5. 2015Optimal Transport for Domain Adaptationcited by 457
  6. 2017Wasserstein Auto-Encoderscited by 371
  7. 2017Learning Generative Models with Sinkhorn Divergencescited by 310
  8. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  9. 2017A Rewriting System for Convex Optimization Problemscited by 178
  10. 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 111
  11. 2020Graph Optimal Transport for Cross-Domain Alignmentcited by 103
  12. 2019Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matchingcited by 102
11 more
  1. 2020Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptationcited by 86
  2. 2020On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithmcited by 61
  3. 2019On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithmscited by 60
  4. 2020The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxationcited by 55
  5. 2017Multilevel Clustering via Wasserstein Meanscited by 48
  6. 2020Outlier-Robust Optimal Transportcited by 45
  7. 2015Scalable Bayes via Barycenter in Wasserstein Spacecited by 44
  8. 2020CO-Optimal Transportcited by 42
  9. 2018Massively scalable Sinkhorn distances via the Nystr"om methodcited by 40
  10. 2020Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithmcited by 29
  11. 2019A Graph Theoretic Additive Approximation of Optimal Transportcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 9; 2024: 8; 2025: 3; 2026: 2.

27 papers.

Sort:

By area:

  1. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
  2. 2022Wasserstein K-means for clustering probability distributionscited by 16
  3. 2023Energy-Guided Continuous Entropic Barycenter Estimation for General Costscited by 12
  4. 2022Hilbert Curve Projection Distance for Distribution Comparisoncited by 9
  5. 2024Generalized Sobolev Transport for Probability Measures on a Graphcited by 9
  6. 2024Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transportcited by 9
  7. 2023Robust Estimation under the Wasserstein Distancecited by 8
  8. 2021Variational Wasserstein Barycenters with c-Cyclical Monotonicitycited by 7
  9. 2023Unbalanced Low-rank Optimal Transport Solverscited by 7
  10. 2023Optimal Transport for Measures with Noisy Tree Metriccited by 7
  11. 2024A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributionscited by 7
  12. 2023Outlier-Robust Gromov-Wasserstein for Graph Datacited by 6
15 more
  1. 2023Importance Sparsification for Sinkhorn Algorithmcited by 6
  2. 2023A High-Quality Robust Diffusion Framework for Corrupted Datasetcited by 6
  3. 2024Robust Distribution Learning with Local and Global Adversarial Corruptionscited by 5
  4. 2024Optimal Transport for Fairness: Archival Data Repair using Small Research Data Setscited by 3
  5. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  6. 2025A Survey on Algorithmic Developments in Optimal Transport Problem with Applicationscited by 3
  7. 2025MGPATH: Vision-Language Model with Multi-Granular Prompt Learning for Few-Shot WSI Classificationcited by 3
  8. 2024Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategiescited by 2
  9. 2022On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gapscited by 1
  10. 2023Keypoint-Guided Optimal Transport: Models, Algorithms, and Applicationscited by 1
  11. 2023On Robust Wasserstein Barycenter: The Model and Algorithmcited by 1
  12. 2024On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussianscited by 0
  13. 2025Partial Distribution Alignment via Adaptive Optimal Transportcited by 0
  14. 2026Accelerated Sinkhorn Algorithms for Partial Optimal Transportcited by 0
  15. 2026Accelerated Algorithm for Sparse Regularized Partial Optimal Transportcited by 0