On the Complexity of Approximating Wasserstein Barycenter

Abstract

We study the complexity of approximating Wassertein barycenter of $m$ discrete measures, or histograms of size $n$ by contrasting two alternative approaches, both using entropic regularization. The first approach is based on the Iterative Bregman Projections (IBP) algorithm for which our novel analysis gives a complexity bound proportional to $\frac{m{n}^2}{{\epsilon }^2}$ to approximate the original non-regularized barycenter. Using an alternative accelerated-gradient-descent-based approach, we obtain a complexity proportional to $\frac{m{n}^{2.5}}{\epsilon }$. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to $\epsilon$, 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.

arXiv commentCorrected misprints. Added a reference to accelerated Iterative Bregman Projections introduced in arXiv:1906.03622

References in corpus (13)

• Fast Computation of Wasserstein Barycenters
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Stochastic Optimization for Large-scale Optimal Transport
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Stochastic Wasserstein Barycenters
• Multilevel Clustering via Wasserstein Means
• A Universal Primal-Dual Convex Optimization Framework
• Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
• Construction of Non-asymptotic Confidence Sets in 2-Wasserstein Space
• Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games
• Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport
• A statistical analysis of a deformation model with Wasserstein barycenters : estimation procedure and goodness of fit test

Cited by in corpus (14)

• Gradient descent algorithms for Bures-Wasserstein barycenters
• Wasserstein barycenters are NP-hard to compute
• Recent theoretical advances in decentralized distributed convex optimization
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
• On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
• Improved Complexity Bounds in Wasserstein Barycenter Problem
• Wasserstein barycenters can be computed in polynomial time in fixed dimension
• Tree-Wasserstein Barycenter for Large-Scale Multilevel Clustering and Scalable Bayes
• Sinkhorn Barycenter via Functional Gradient Descent
• Projection Robust Wasserstein Barycenters
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters
• Fixed Support Tree-Sliced Wasserstein Barycenter
• On the complexity of the optimal transport problem with graph-structured cost
• Parallel and Distributed algorithms for ML problems