# Computational Guarantees for Doubly Entropic Wasserstein Barycenters via Damped Sinkhorn Iterations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 67 references that are in the map.
- First posted on arXiv 25 Jul 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [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)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests](https://mlsanity.com/paper/1509.02237/) (2015)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Entropic estimation of optimal transport maps](https://mlsanity.com/paper/2109.12004/) (2021)
- [Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem](https://mlsanity.com/paper/1905.11882/) (2019)
- [Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization](https://mlsanity.com/paper/2102.01752/) (2021)
- [Debiased Sinkhorn barycenters](https://mlsanity.com/paper/2006.02575/) (2020)
- [Entropy-Regularized 2-Wasserstein Distance between Gaussian Measures](https://mlsanity.com/paper/2006.03416/) (2020)
- [Wasserstein barycenters are NP-hard to compute](https://mlsanity.com/paper/2101.01100/) (2021)
- [Semi-dual Regularized Optimal Transport](https://mlsanity.com/paper/1811.05527/) (2018)
- [The Langevin Monte Carlo algorithm in the non-smooth log-concave case](https://mlsanity.com/paper/2101.10695/) (2021)
- [Wasserstein barycenters can be computed in polynomial time in fixed dimension](https://mlsanity.com/paper/2006.08012/) (2020)
- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [Estimating Barycenters of Measures in High Dimensions](https://mlsanity.com/paper/2007.07105/) (2020)
- [The statistical effect of entropic regularization in optimal transportation](https://mlsanity.com/paper/2006.05199/) (2020)
- [Doubly Regularized Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2303.11844/) (2023)
- [Stochastic Optimization for Regularized Wasserstein Estimators](https://mlsanity.com/paper/2002.08695/) (2020)
- [Data-driven regularization of Wasserstein barycenters with an application to multivariate density registration](https://mlsanity.com/paper/1804.08962/) (2018)
- [A proof of the Caffarelli contraction theorem via entropic regularization](https://mlsanity.com/paper/1904.06053/) (2019)
- [Sampling From the Wasserstein Barycenter](https://mlsanity.com/paper/2105.01706/) (2021)

## Abstract (arXiv)

We study the computation of doubly regularized Wasserstein barycenters, a recently introduced family of entropic barycenters governed by inner and outer regularization strengths. Previous research has demonstrated that various regularization parameter choices unify several notions of entropy-penalized barycenters while also revealing new ones, including a special case of debiased barycenters. In this paper, we propose and analyze an algorithm for computing doubly regularized Wasserstein barycenters. Our procedure builds on damped Sinkhorn iterations followed by exact maximization/minimization steps and guarantees convergence for any choice of regularization parameters. An inexact variant of our algorithm, implementable using approximate Monte Carlo sampling, offers the first non-asymptotic convergence guarantees for approximating Wasserstein barycenters between discrete point clouds in the free-support/grid-free setting.