Abstract
Collecting and aggregating information from several probability measures or histograms is a fundamental task in machine learning. One of the popular solution methods for this task is to compute the barycenter of the probability measures under the Wasserstein metric. However, approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that has the potential to mitigate the curse of dimensionality. Since PRWB is numerically very challenging to solve, we further propose a relaxed PRWB (RPRWB) model, which is more tractable. The RPRWB projects the probability measures onto a lower-dimensional subspace that maximizes the Wasserstein barycenter objective. The resulting problem is a max-min problem over the Stiefel manifold. By combining the iterative Bregman projection algorithm and Riemannian optimization, we propose two new algorithms for computing the RPRWB. The complexity of arithmetic operations of the proposed algorithms for obtaining an $\epsilon$-stationary solution is analyzed. We incorporate the RPRWB into a discrete distribution clustering algorithm, and the numerical results on real text datasets confirm that our RPRWB model helps improve the clustering performance significantly.
Introduction
In modern machine learning, aggregating high-dimensional data distributions into a single representative "average" is a critical challenge. The Wasserstein Barycenter (WB) has emerged as a powerful tool for this purpose, finding applications in fields ranging from image processing to natural language processing. By minimizing the sum of Wasserstein distances to a set of input distributions, the WB captures the underlying geometric structure of the data more effectively than simple Euclidean averages.
However, standard WB methods suffer from the "curse of dimensionality." As the number of dimensions ($d$) grows, the number of samples required to accurately estimate the barycenter increases exponentially. In high-dimensional spaces, the geometric signal is often buried under significant noise, and the computational cost of solving the resulting optimization problems becomes prohibitive. This paper introduces Projection Robust Wasserstein Barycenters (PRWB) to address these limitations by focusing on the most informative lower-dimensional subspaces.
The Projection Robust Framework
The core insight of this research is that high-dimensional data often resides on or near lower-dimensional manifolds. Standard WB methods are sensitive to noise in all $d$ dimensions, but a projection-robust approach can filter out irrelevant dimensions.
The authors initially propose the PRWB, which seeks a $k$-dimensional subspace that maximizes the Wasserstein distances between distributions. By maximizing this distance, the model identifies the projection that preserves the most significant geometric differences between the input measures. However, the original PRWB formulation involves a complex "inf-sup-inf" (minimize-maximize-minimize) structure that is computationally intractable.
Relaxed PRWB (RPRWB)
To make the approach practical, the authors introduce the Relaxed PRWB (RPRWB). This model simplifies the problem by utilizing a single, common projection matrix for all distributions. This transformation results in a max-min problem over the Stiefel manifold—the space of all possible orthonormal projection matrices. This relaxation maintains the robustness of the original concept while allowing for more efficient optimization.
Algorithmic Innovations
Solving the RPRWB requires navigating the non-convex geometry of the Stiefel manifold. The authors develop two primary algorithms to find $\epsilon$-stationary solutions:
- RGA-IBP (Riemannian Gradient Ascent with Iterative Bregman Projection): This algorithm extends the popular Sinkhorn-style methods used in optimal transport to the Riemannian setting. It alternates between updating the projection matrix and computing the barycenter.
- RBCD (Riemannian Block Coordinate Descent): A more efficient alternative, RBCD updates variables in blocks. The authors demonstrate that RBCD generally offers better theoretical complexity and faster wall-clock performance by avoiding the expensive inner loops required by RGA-IBP.
Experimental Results
The effectiveness of the RPRWB was tested across synthetic and real-world datasets, focusing on robustness and clustering accuracy.
Synthetic Robustness
Using synthetic Gaussian distributions, the authors demonstrated that RPRWB correctly identifies the "ground truth" subspace even when significant Gaussian noise is added. While the error of standard WB methods spikes rapidly as noise levels ($\sigma$) increase, RPRWB remains stable, confirming its utility as a high-dimensional filter.
Text Clustering Performance
The RPRWB was integrated into a Projected D2 Clustering (PD2) algorithm and tested on news datasets (Reuters, BBCnews, and BBCsport) using 300-dimensional GloVe word embeddings. The results showed significant improvements over traditional methods:
- BBCsport Dataset: PD2 achieved an Adjusted Mutual Information (AMI) score of 0.6892, outperforming standard D2 clustering (0.6510) and k-means (0.4276).
- Efficiency: The RBCD algorithm consistently proved to be the most practical choice, scaling better with sample size than RGA-IBP.
Conclusion and Future Directions
Projection Robust Wasserstein Barycenters provide a promising path forward for high-dimensional data aggregation. By focusing on informative subspaces, the RPRWB model mitigates the curse of dimensionality and provides inherent noise tolerance.
Future work remains in several areas. While numerical evidence for improved sample complexity is strong, a rigorous theoretical proof for the barycenter problem is still needed. Additionally, while the current work focuses on "fixed-support" barycenters (where point locations are pre-determined), extending these robust projections to "free-support" problems—where point locations are also optimized—could further expand the utility of this framework in generative modeling and complex data synthesis.
Summary updated