Projection Robust Wasserstein Barycenter

• URL: http://arxiv.org/abs/2102.03390v1
• Date: Fri, 5 Feb 2021 19:23:35 GMT
• Title: Projection Robust Wasserstein Barycenter
• Authors: Minhui Huang, Shiqian Ma, Lifeng Lai
• Abstract summary: approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that mitigates the curse of dimensionality.
• Score: 36.97843660480747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 mitigates the curse of dimensionality. This new model 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, which is numerically challenging in practice. Combining the iterative Bregman projection algorithm and Riemannian optimization, we propose two new algorithms for computing the PRWB. The complexity of arithmetic operations of the proposed algorithms for obtaining an $\epsilon$-stationary solution is analyzed. We incorporate the PRWB into a discrete distribution clustering algorithm, and the numerical results on real text datasets confirm that our PRWB model helps improve the clustering performance significantly.

Related papers

• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
  We present an algorithm to approximate the Wasserstein-2 barycenters of continuous measures via a generative model. Based on the celebrity faces dataset, we construct Ave, celeba! dataset which can be used for quantitative evaluation of barycenter algorithms.
  arXiv  Detail & Related papers  (2022-01-28T16:59:47Z)
• Partial Wasserstein Covering [10.52782170493037]
  We consider a general task called partial Wasserstein covering with the goal of emulating a large dataset. We model this problem as a discrete optimization problem with partial Wasserstein divergence as an objective function. We show that we can efficiently make two datasets similar in terms of partial Wasserstein divergence, including driving scene datasets.
  arXiv  Detail & Related papers  (2021-06-02T01:48:41Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
  arXiv  Detail & Related papers  (2021-02-05T04:25:28Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport. We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
  arXiv  Detail & Related papers  (2021-02-02T21:01:13Z)
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance [36.97843660480747]
  The Wasserstein distance has become increasingly important in machine learning and deep learning. A recently proposed approach to alleviate the curse of dimensionality is to project the sampled data onto a lower-dimensional subspace, and then compute the Wasserstein distance between the projected data. However, this approach requires to solve a max-min problem over the Stiefel manifold, which is very challenging in practice. We propose a novel block coordinate descent (RBCD) method to solve this problem, which is based on a novel reformulation of the regularized max-min problem over the Stiefel manifold.
  arXiv  Detail & Related papers  (2020-12-09T17:47:56Z)
• Fast Epigraphical Projection-based Incremental Algorithms for Wasserstein Distributionally Robust Support Vector Machine [31.58346511479111]
  Wasserstein textbfDistributionally textbfRobust textbfOptimization (DRO) is concerned with finding decisions that perform well on data. We propose two novel epigraphical projection-based incremental algorithms to solve DRO problems.
  arXiv  Detail & Related papers  (2020-10-24T10:42:27Z)
• Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks [15.171726731041055]
  Wasserstein Barycenter is a principled approach to represent the weighted mean of a given set of probability distributions. We present a novel scalable algorithm to approximate the Wasserstein Barycenters aiming at high-dimensional applications in machine learning.
  arXiv  Detail & Related papers  (2020-07-08T22:41:18Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.