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:
- 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.
- 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$.
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$.
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