# Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2018.

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

- [Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization](https://mlsanity.com/paper/2102.01752/) (2021)
- [Automatic Text Evaluation through the Lens of Wasserstein Barycenters](https://mlsanity.com/paper/2108.12463/) (2021)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Energy-Guided Continuous Entropic Barycenter Estimation for General Costs](https://mlsanity.com/paper/2310.01105/) (2023)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Nonparametric Iterative Machine Teaching](https://mlsanity.com/paper/2306.03007/) (2023)
- [Light Unbalanced Optimal Transport](https://mlsanity.com/paper/2303.07988/) (2023)
- [Variational Wasserstein Barycenters with c-Cyclical Monotonicity](https://mlsanity.com/paper/2110.11707/) (2021)
- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Categorical Schr"odinger Bridge Matching](https://mlsanity.com/paper/2502.01416/) (2025)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Fast Dual Subgradient Optimization of the Integrated Transportation Distance Between Stochastic Kernels](https://mlsanity.com/paper/2312.01432/) (2023)
- [Analysis of Kernel Mirror Prox for Measure Optimization](https://mlsanity.com/paper/2403.00147/) (2024)
- [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022)
- [FLECS-CGD: A Federated Learning Second-Order Framework via Compression and Sketching with Compressed Gradient Differences](https://mlsanity.com/paper/2210.09626/) (2022)
- [Schr"odinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres](https://mlsanity.com/paper/2506.17197/) (2025)
- [Decentralized Entropic Optimal Transport for Distributed Distribution Comparison](https://mlsanity.com/paper/2301.12065/) (2023)
- [Federated Calculation of the Free-Support Transportation Barycenter by Single-Loop Dual Decomposition](https://mlsanity.com/paper/2507.19627/) (2025)
- [When Sample Selection Bias Precipitates Model Collapse](https://mlsanity.com/paper/2606.13732/) (2026)
- [An Asynchronous Decentralized Algorithm for Wasserstein Barycenter Problem](https://mlsanity.com/paper/2304.11653/) (2023)
- [Field Codes for Distributed Coupling Samplers and Certified Empirical Transport](https://mlsanity.com/paper/2607.27078/) (2026)

## Abstract (arXiv)

We study the decentralized distributed computation of discrete approximations for the regularized Wasserstein barycenter of a finite set of continuous probability measures distributedly stored over a network. We assume there is a network of agents/machines/computers, and each agent holds a private continuous probability measure and seeks to compute the barycenter of all the measures in the network by getting samples from its local measure and exchanging information with its neighbors. Motivated by this problem, we develop, and analyze, a novel accelerated primal-dual stochastic gradient method for general stochastic convex optimization problems with linear equality constraints. Then, we apply this method to the decentralized distributed optimization setting to obtain a new algorithm for the distributed semi-discrete regularized Wasserstein barycenter problem. Moreover, we show explicit non-asymptotic complexity for the proposed algorithm.