On the Complexity of Approximating Wasserstein Barycenters

Alexey Kroshnin, Nazarii Tupitsa, Darina Dvinskikh, Pavel Dvurechensky, Alexander Gasnikov, Cesar A. UribeICML 2019 · OpenReview

TL;DR

This paper tackles the computational challenge of finding the "average" of multiple probability distributions (Wasserstein barycenter), a crucial tool in modern machine learning. The authors analyze and improve upon existing methods, offering new theoretical guarantees on their efficiency and scalability, particularly for large datasets and distributed computing environments.

What Problem Does This Paper Address?

In fields like machine learning and statistics, we often deal with collections of data represented as probability distributions (or histograms). A natural question arises: how do we find a representative "average" distribution for such a collection? The Wasserstein barycenter provides a principled way to do this, preserving the geometric structure of the data. However, computing this barycenter is computationally expensive, especially when dealing with many distributions ($m$) or high-dimensional distributions ($n$). This paper focuses on understanding and improving the computational complexity of approximating this barycenter, particularly when using entropic regularization, a common technique to make the problem more tractable. The authors aim to provide tighter theoretical bounds and more efficient algorithms, especially for scenarios involving large-scale and distributed data.

Methods

The paper contrasts two main approaches for approximating the entropic regularized Wasserstein barycenter:

  • Iterative Bregman Projections (IBP): The authors provide a novel analysis of the IBP algorithm, establishing a complexity bound proportional to $mn^2/\epsilon^2$ for approximating the non-regularized barycenter. They also introduce a proximal-IBP algorithm, which can be viewed as a proximal gradient method that uses IBP for its proximal steps. This new method aims to overcome stability issues encountered with high accuracy requirements.
  • Primal-Dual Accelerated Gradient Descent (AGD): This approach reformulates the problem into a dual form and solves it using accelerated gradient descent. The authors show this method has a complexity proportional to $mn^{2.5}/\epsilon$ and is particularly well-suited for decentralized distributed settings.

A key aspect of their work is analyzing how to choose the regularization parameter ($\gamma$) to effectively approximate the non-regularized barycenter, bridging the gap between the regularized and unregularized versions of the problem. They also explore the scalability of these algorithms in distributed settings, considering both centralized (master/slave) and general decentralized network topologies.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic complexity, with numerical experiments conducted on synthetic data (discrete and truncated Gaussian distributions).

Key Insights and Ideas

  • Bridging Regularized and Non-Regularized Barycenters: A significant contribution is showing how to select the regularization parameter to accurately approximate the true, non-regularized Wasserstein barycenter. This is crucial because entropic regularization is often used for computational tractability, but the ultimate goal is often the non-regularized version.
  • Proximal-IBP for Stability: The proposed proximal-IBP algorithm addresses a critical stability issue in IBP and AGD when high accuracy is desired (small $\epsilon$). This suggests a more robust approach for achieving precise results.
  • Scalability for Distributed Settings: The paper highlights the distinct scalability advantages of the two main approaches. IBP is amenable to centralized distributed systems, while the primal-dual AGD method is shown to work effectively in general decentralized networks, making it suitable for a wider range of real-world distributed data scenarios.
  • Complexity Trade-offs: The analysis reveals clear trade-offs between the algorithms. IBP offers a complexity of $O(mn^2/\epsilon^2)$ for the non-regularized barycenter, while primal-dual AGD achieves $O(mn^{2.5}/\epsilon)$. The choice depends on the specific problem constraints and desired level of decentralization.

Key Results

  • IBP Complexity: The paper establishes an iteration complexity bound of $O(mn^2/\epsilon^2)$ for approximating the non-regularized Wasserstein barycenter using IBP.
  • AGD Complexity: The primal-dual accelerated gradient descent method achieves a complexity of $O(mn^{2.5}/\epsilon)$ for approximating the non-regularized barycenter.
  • Proximal-IBP: A novel proximal-IBP algorithm is introduced, addressing stability issues and offering improved performance in practice, as suggested by numerical experiments.
  • Distributed Implementation: The paper demonstrates that IBP can be implemented in a centralized distributed setting, while the primal-dual AGD method is suitable for decentralized settings with arbitrary network topologies.

Limitations and Future Work

  • Theoretical vs. Practical Complexity: While theoretical bounds are provided, the paper acknowledges that practical performance can differ. The numerical experiments suggest that the proximal-IBP method, despite potentially higher per-iteration costs, can converge faster overall.
  • Specific Network Topologies: The analysis of distributed algorithms focuses on general network structures. Further research could explore the performance on more specific or dynamic network topologies.
  • Low-Rank Matrices: The paper mentions that for specific forms of cost matrices (e.g., low-rank), better complexities might be achievable for IBP iterations. Further investigation into these specialized cases could yield significant speedups.
  • Choice of Regularization Parameter: While the paper provides guidance on choosing the regularization parameter, finding the "optimal" $\gamma$ in practice might still require heuristics or adaptive strategies, as hinted at by the proximal-IBP approach.

Summary updated

Abstract

We study the complexity of approximating the Wasserstein barycenter of $m$ discrete measures, or histograms of size $n$, by contrasting two alternative approaches that use entropic regularization. ...
BibTeX
@inproceedings{kroshnin2019complexity,
  author = {Alexey Kroshnin and Nazarii Tupitsa and Darina Dvinskikh and Pavel Dvurechensky and Alexander Gasnikov and Cesar A. Uribe},
  title = {{On the Complexity of Approximating Wasserstein Barycenters}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=Hk-MO3bOWH},
}
Figure