Computational Guarantees for Doubly Entropic Wasserstein Barycenters via
  Damped Sinkhorn Iterations
Lénaïc Chizat Tomas Vaškevičius
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.