# An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 46 references that are in the map.
- First posted on arXiv 2 Mar 2022.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [On the Efficiency of Entropic Regularized Algorithms for Optimal Transport](https://mlsanity.com/paper/1906.01437/) (2019)
- [Continuous Regularized Wasserstein Barycenters](https://mlsanity.com/paper/2008.12534/) (2020)
- [Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support](https://mlsanity.com/paper/1510.00012/) (2015)
- [A Smoothed Dual Approach for Variational Wasserstein Problems](https://mlsanity.com/paper/1503.02533/) (2015)
- [Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm](https://mlsanity.com/paper/2002.04783/) (2020)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Stochastic Wasserstein Barycenters](https://mlsanity.com/paper/1802.05757/) (2018)
- [On a Combination of Alternating Minimization and Nesterov's Momentum](https://mlsanity.com/paper/1906.03622/) (2019)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [Towards Optimal Running Times for Optimal Transport](https://mlsanity.com/paper/1810.07717/) (2018)
- [Approximating optimal transport with linear programs](https://mlsanity.com/paper/1810.05957/) (2018)
- [Greedy stochastic algorithms for entropy-regularized optimal transport problems](https://mlsanity.com/paper/1803.01347/) (2018)
- [A Graph Theoretic Additive Approximation of Optimal Transport](https://mlsanity.com/paper/1905.11830/) (2019)
- [Improved Complexity Bounds in Wasserstein Barycenter Problem](https://mlsanity.com/paper/2010.04677/) (2020)
- [Distributed Computation of Wasserstein Barycenters over Networks](https://mlsanity.com/paper/1803.02933/) (2018)

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

- [Light Schr"odinger Bridge](https://mlsanity.com/paper/2310.01174/) (2023)
- [Light Unbalanced Optimal Transport](https://mlsanity.com/paper/2303.07988/) (2023)
- [Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances](https://mlsanity.com/paper/2405.15441/) (2024)
- [A Survey on Algorithmic Developments in Optimal Transport Problem with Applications](https://mlsanity.com/paper/2501.06247/) (2025)
- [Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm](https://mlsanity.com/paper/2210.16645/) (2022)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)

## Abstract (arXiv)

Fixed-support Wasserstein barycenters average probability distributions while accounting for the geometry of the support. We study the entropically regularized Wasserstein barycenter problem with a fixed regularization parameter and propose an accelerated stochastic variance-reduced primal-dual algorithm. The proposed algorithm uses a semi-dual finite-sum structure in which each stochastic gradient requires only one softmax over the barycenter support. The resulting finite-sum components have dimension-free smoothness bounds, which lead to a complexity result showing that the method improves the support-size dependence of deterministic accelerated gradient by a square-root factor while preserving accelerated dependence on the target accuracy. Experiments on synthetic data, DOTmark images, shape aggregation, and digit-averaging instances are consistent with the theoretical dependence on support size and accuracy and show lower arithmetic costs than the tested first-order baselines.