Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem

Abstract

Computing the Wasserstein barycenter of a set of probability measures under the optimal transport metric can quickly become prohibitive for traditional second-order algorithms, such as interior-point methods, as the support size of the measures increases. In this paper, we overcome the difficulty by developing a new adapted interior-point method that fully exploits the problem's special matrix structure to reduce the iteration complexity and speed up the Newton procedure. Different from regularization approaches, our method achieves a well-balanced tradeoff between accuracy and speed. A numerical comparison on various distributions with existing algorithms exhibits the computational advantages of our approach. Moreover, we demonstrate the practicality of our algorithm on image benchmark problems including MNIST and Fashion-MNIST.

arXiv commentSupplementary Material, Appeared in Advances in Neural Information Processing Systems 32 (NeurIPS 2019)

References in corpus (14)

• Fast Computation of Wasserstein Barycenters
• Learning with a Wasserstein Loss
• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Bregman Alternating Direction Method of Multipliers
• Minimax Statistical Learning with Wasserstein Distances
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Stochastic Wasserstein Barycenters
• Generalizing Point Embeddings using the Wasserstein Space of Elliptical Distributions
• Multilevel Clustering via Wasserstein Means
• Robust Hypothesis Testing Using Wasserstein Uncertainty Sets
• Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport
• Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor
• Probabilistic Multilevel Clustering via Composite Transportation Distance
• A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters