Projection Robust Wasserstein Barycenters

Minhui Huang · Shiqian Ma · Lifeng Lai

Virtual

Keywords: [ Algorithms ] [ Optimal Transport ]

[ Abstract ]
[
[ Paper ]
Tue 20 Jul 9 a.m. PDT — 11 a.m. PDT

Spotlight presentation: Optimization 1
Tue 20 Jul 6 a.m. PDT — 7 a.m. PDT

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, and a relaxed PRWB (RPRWB) model that is computationally more tractable. By combining the iterative Bregman projection algorithm and Riemannian optimization, we propose two algorithms for computing the RPRWB, which is a max-min problem over the Stiefel manifold. 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.

Chat is not available.