# On Robust Optimal Transport: Computational Complexity and Barycenter Computation

arXiv: https://arxiv.org/abs/2102.06857 · HTML: https://mlsanity.com/paper/2102.06857/

## Key facts

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

## Builds on (most cited first, 23 of 23)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Wasserstein Auto-Encoders](https://mlsanity.com/paper/1711.01558/) (2017)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Graph Optimal Transport for Cross-Domain Alignment](https://mlsanity.com/paper/2006.14744/) (2020)
- [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm](https://mlsanity.com/paper/2002.03293/) (2020)
- [The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation](https://mlsanity.com/paper/2009.04266/) (2020)
- [Multilevel Clustering via Wasserstein Means](https://mlsanity.com/paper/1706.03883/) (2017)
- [Outlier-Robust Optimal Transport](https://mlsanity.com/paper/2012.07363/) (2020)
- [Scalable Bayes via Barycenter in Wasserstein Space](https://mlsanity.com/paper/1508.05880/) (2015)
- [CO-Optimal Transport](https://mlsanity.com/paper/2002.03731/) (2020)
- [Massively scalable Sinkhorn distances via the Nystr"om method](https://mlsanity.com/paper/1812.05189/) (2018)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [A Graph Theoretic Additive Approximation of Optimal Transport](https://mlsanity.com/paper/1905.11830/) (2019)

## Built on by (most cited first, 27 of 27)

- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Energy-Guided Continuous Entropic Barycenter Estimation for General Costs](https://mlsanity.com/paper/2310.01105/) (2023)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Generalized Sobolev Transport for Probability Measures on a Graph](https://mlsanity.com/paper/2402.04516/) (2024)
- [Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transport](https://mlsanity.com/paper/2410.03974/) (2024)
- [Robust Estimation under the Wasserstein Distance](https://mlsanity.com/paper/2302.01237/) (2023)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [Unbalanced Low-rank Optimal Transport Solvers](https://mlsanity.com/paper/2305.19727/) (2023)
- [Optimal Transport for Measures with Noisy Tree Metric](https://mlsanity.com/paper/2310.13653/) (2023)
- [A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions](https://mlsanity.com/paper/2405.03664/) (2024)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [A High-Quality Robust Diffusion Framework for Corrupted Dataset](https://mlsanity.com/paper/2311.17101/) (2023)
- [Robust Distribution Learning with Local and Global Adversarial Corruptions](https://mlsanity.com/paper/2406.06509/) (2024)
- [A Survey on Algorithmic Developments in Optimal Transport Problem with Applications](https://mlsanity.com/paper/2501.06247/) (2025)
- [Optimal Transport for Fairness: Archival Data Repair using Small Research Data Sets](https://mlsanity.com/paper/2403.13864/) (2024)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [MGPATH: Vision-Language Model with Multi-Granular Prompt Learning for Few-Shot WSI Classification](https://mlsanity.com/paper/2502.07409/) (2025)
- [Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies](https://mlsanity.com/paper/2407.10000/) (2024)
- [On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and OT Distance Gaps](https://mlsanity.com/paper/2205.13846/) (2022)
- [Keypoint-Guided Optimal Transport: Models, Algorithms, and Applications](https://mlsanity.com/paper/2303.13102/) (2023)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [On Barycenter Computation: Semi-Unbalanced Optimal Transport-based Method on Gaussians](https://mlsanity.com/paper/2410.08117/) (2024)
- [Partial Distribution Alignment via Adaptive Optimal Transport](https://mlsanity.com/paper/2503.05087/) (2025)
- [Accelerated Sinkhorn Algorithms for Partial Optimal Transport](https://mlsanity.com/paper/2601.17196/) (2026)
- [Accelerated Algorithm for Sparse Regularized Partial Optimal Transport](https://mlsanity.com/paper/2609.40075/) (2026)

## 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.