WIAS Preprint No. 2665, (2019)

On the complexity of approximating Wasserstein barycenter



Authors

  • Kroshnin, Alexey
  • Dvinskikh, Darina
  • Dvurechensky, Pavel
    ORCID: 0000-0003-1201-2343
  • Gasnikov, Alexander
    ORCID: 0000-0003-1201-2343
  • Tupitsa, Nazarii
  • Uribe, César A.

2010 Mathematics Subject Classification

  • 90C25 90C30 90C06

2008 Physics and Astronomy Classification Scheme

  • 90C90

Keywords

  • Optimal transport, Wasserstein barycenter, Sinkhorn's algorithma, accelerated gradient descent, distributed optimization

DOI

10.20347/WIAS.PREPRINT.2665

Abstract

We study the complexity of approximating Wassertein barycenter of discrete measures, or histograms by contrasting two alternative approaches, both using entropic regularization. We provide a novel analysis for our approach based on the Iterative Bregman Projections (IBP) algorithm to approximate the original non-regularized barycenter. We also get the complexity bound for alternative accelerated-gradient-descent-based approach and compare it with the bound obtained for IBP. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to ", which causes instability of both algorithms when the desired accuracy is high. To overcome this issue, we propose a novel proximal-IBP algorithm, which can be seen as a proximal gradient method, which uses IBP on each iteration to make a proximal step. We also consider the question of scalability of these algorithms using approaches from distributed optimization and show that the first algorithm can be implemented in a centralized distributed setting (master/slave), while the second one is amenable to a more general decentralized distributed setting with an arbitrary network topology.

Download Documents