An Efficient HPR Algorithm for the Wasserstein Barycenter Problem with $O({Dim(P)}/\varepsilon)$ Computational Complexity

Guojun Zhang, Yancheng Yuan, Defeng SunarXiv 2022 · DOI · arXiv

Abstract

Finding the geometric mean of probability distributions, known as the Wasserstein Barycenter Problem (WBP), is a fundamental task in data science but remains computationally expensive. We introduce the Halpern-Peaceman-Rachford (HPR) algorithm, which achieves a non-ergodic iteration complexity of $O(1/\varepsilon)$. By leveraging a novel linear-time subproblem solver, the HPR algorithm attains a total computational complexity of $O(Dim(P)/\varepsilon)$, where $Dim(P)$ is the problem dimension. Empirical results on synthetic and real-world datasets like MNIST and Yale Face B demonstrate that HPR significantly outperforms existing state-of-the-art solvers in both speed and accuracy.

Introduction

The Wasserstein Barycenter Problem (WBP) seeks a distribution that minimizes the sum of Wasserstein distances to a set of given distributions. Unlike Euclidean averages, Wasserstein barycenters preserve structural features, making them ideal for applications in image processing and machine learning. However, solving large-scale WBP instances is challenging. Existing methods generally fall into two categories: entropic regularization methods (e.g., Sinkhorn/IBP), which are fast but introduce blurring and numerical instability, and exact solvers (e.g., ADMM), which provide high precision but suffer from high per-iteration costs due to large linear system solves.

The HPR Algorithm

We propose the Halpern-Peaceman-Rachford (HPR) algorithm to bridge the gap between speed and precision. The algorithm integrates two key innovations:

  1. Halpern-Peaceman-Rachford Splitting: While standard Peaceman-Rachford (PR) methods may not converge for WBP, we employ Halpern iteration to ensure a non-ergodic convergence rate of $O(1/\varepsilon)$ for the Karush-Kuhn-Tucker (KKT) residual.
  2. Linear-Time Subproblem Solver: The bottleneck in primal-dual methods is typically solving linear systems of the form $AA^*y = R$. We derive a specialized procedure that exploits the block-diagonal structure of WBP constraints, reducing the complexity of these subproblems to linear time relative to the number of variables.

Complexity and Comparison

The HPR algorithm's theoretical efficiency is summarized in the context of existing literature. As shown in Figure 1, most existing algorithms either provide ergodic convergence or have higher complexity dependencies on the number of distributions $T$ and support points $m$.

Comparison of state-of-the-art algorithms for the Wasserstein Barycenter Problem.

Specifically, Figure 2 highlights how HPR improves upon the sGS-ADMM method. While sGS-ADMM achieves $O(1/\varepsilon)$ complexity in an ergodic sense or requires higher-order dependencies, HPR provides a non-ergodic $O(1/\varepsilon)$ iteration complexity with a total flop count scaling as $O(Dim(P)/\varepsilon)$, where $Dim(P) \approx Tm^2$.

Complexity comparison between sGS-ADMM and the proposed HPR algorithm.

Experimental Results

We evaluated HPR on synthetic Gaussian mixtures and real-world datasets including MNIST, Coil20, and Yale Face B.

  • Efficiency: On large synthetic problems, a hybrid HPR approach was found to be 4 times faster than the commercial Gurobi solver.
  • Stability: Unlike IBP, which often fails at high precision (e.g., KKT residual $< 10^{-5}$), HPR remains stable and converges reliably.
  • Visual Quality: HPR produces sharp barycenters, avoiding the blurring artifacts common in entropic methods.

Conclusion

The HPR algorithm provides a robust and efficient solution for the large-scale Wasserstein Barycenter Problem. By achieving $O(Dim(P)/\varepsilon)$ non-ergodic complexity, it offers a significant advancement over previous methods. Future work includes GPU acceleration to further leverage the parallelizable nature of the subproblem solver.

Summary updated

Abstract

In this paper, we propose and analyze an efficient Halpern-Peaceman-Rachford (HPR) algorithm for solving the Wasserstein barycenter problem (WBP) with fixed supports. While the Peaceman-Rachford (PR) splitting method itself may not be convergent for solving the WBP, the HPR algorithm can achieve an $O(1/\varepsilon)$ non-ergodic iteration complexity with respect to the Karush-Kuhn-Tucker (KKT) residual. More interestingly, we propose an efficient procedure with linear time computational complexity to solve the linear systems involved in the subproblems of the HPR algorithm. As a consequence, the HPR algorithm enjoys an $O({\rm Dim(P)}/\varepsilon)$ non-ergodic computational complexity in terms of flops for obtaining an $\varepsilon$-optimal solution measured by the KKT residual for the WBP, where ${\rm Dim(P)}$ is the dimension of the variable of the WBP. This is better than the best-known complexity bound for the WBP. Moreover, the extensive numerical results on both the synthetic and real data sets demonstrate the superior performance of the HPR algorithm for solving the large-scale WBP.
BibTeX
@misc{zhang2022efficient,
  author = {Guojun Zhang and Yancheng Yuan and Defeng Sun},
  title = {{An Efficient HPR Algorithm for the Wasserstein Barycenter Problem with $O(\{Dim(P)\}/\textbackslash\{\}varepsilon)$ Computational Complexity}},
  year = {2022},
  eprint = {2211.14881},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.14881},
}
Figure