Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem
This work addresses a computational bottleneck in optimal transport for researchers and practitioners, offering a faster and more accurate method for Wasserstein barycenter computation, though it is incremental as it builds on existing interior-point methods.
The paper tackles the computational challenge of solving the Wasserstein barycenter problem for large support sizes by developing an adapted interior-point method that exploits matrix structure to reduce iteration complexity and speed up Newton steps, achieving a tradeoff between accuracy and speed and demonstrating advantages on distributions and image benchmarks like MNIST and Fashion-MNIST.
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.