# Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

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

- [Score-based Generative Neural Networks for Large-Scale Optimal Transport](https://mlsanity.com/paper/2110.03237/) (2021)
- [Automatic Text Evaluation through the Lens of Wasserstein Barycenters](https://mlsanity.com/paper/2108.12463/) (2021)
- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [Energy-guided Entropic Neural Optimal Transport](https://mlsanity.com/paper/2304.06094/) (2023)
- [Heterogeneous manifolds for curvature-aware graph embedding](https://mlsanity.com/paper/2202.01185/) (2022)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [An improved central limit theorem and fast convergence rates for entropic transportation costs](https://mlsanity.com/paper/2204.09105/) (2022)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure](https://mlsanity.com/paper/2108.08129/) (2021)
- [Minimum intrinsic dimension scaling for entropic optimal transport](https://mlsanity.com/paper/2306.03398/) (2023)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Neural Sinkhorn Gradient Flow](https://mlsanity.com/paper/2401.14069/) (2024)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Operator World Models for Reinforcement Learning](https://mlsanity.com/paper/2406.19861/) (2024)
- [Sliced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2102.07115/) (2021)
- [Sampling From the Wasserstein Barycenter](https://mlsanity.com/paper/2105.01706/) (2021)
- [Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport](https://mlsanity.com/paper/2110.12678/) (2021)
- [Optimal transport with f-divergence regularization and generalized Sinkhorn algorithm](https://mlsanity.com/paper/2105.14337/) (2021)
- [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022)
- [Schr"odinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres](https://mlsanity.com/paper/2506.17197/) (2025)
- [Conditional Gradients for the Approximate Vanishing Ideal](https://mlsanity.com/paper/2202.03349/) (2022)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)
- [Fused Gromov-Wasserstein Variance Decomposition with Linear Optimal Transport](https://mlsanity.com/paper/2411.10204/) (2024)

## Abstract (arXiv)

We present a novel algorithm to estimate the barycenter of arbitrary probability distributions with respect to the Sinkhorn divergence. Based on a Frank-Wolfe optimization strategy, our approach proceeds by populating the support of the barycenter incrementally, without requiring any pre-allocation. We consider discrete as well as continuous distributions, proving convergence rates of the proposed algorithm in both settings. Key elements of our analysis are a new result showing that the Sinkhorn divergence on compact domains has Lipschitz continuous gradient with respect to the Total Variation and a characterization of the sample complexity of Sinkhorn potentials. Experiments validate the effectiveness of our method in practice.