Projection Robust Wasserstein Distance and Riemannian Optimization
arXiv:2006.07458
Abstract
Projection robust Wasserstein (PRW) distance, or Wasserstein projection pursuit (WPP), is a robust variant of the Wasserstein distance. Recent work suggests that this quantity is more robust than the standard Wasserstein distance, in particular when comparing probability measures in high-dimensions. However, it is ruled out for practical application because the optimization model is essentially non-convex and non-smooth which makes the computation intractable. Our contribution in this paper is to revisit the original motivation behind WPP/PRW, but take the hard route of showing that, despite its non-convexity and lack of nonsmoothness, and even despite some hardness results proved by~\citet{Niles-2019-Estimation} in a minimax sense, the original formulation for PRW/WPP \textit{can} be efficiently computed in practice using Riemannian optimization, yielding in relevant cases better behavior than its convex relaxation. More specifically, we provide three simple algorithms with solid theoretical guarantee on their complexity bound (one in the appendix), and demonstrate their effectiveness and efficiency by conducing extensive experiments on synthetic and real data. This paper provides a first step into a computational theory of the PRW distance and provides the links between optimal transport and Riemannian optimization.
arXiv commentAccepted by NeurIPS 2020; The first two authors contributed equally; fix the confusing parts in the proof and refine the algorithms and complexity bounds
References in corpus (25)
- Fast Computation of Wasserstein Barycenters
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Global rates of convergence for nonconvex optimization on manifolds
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Riemannian Adaptive Optimization Methods
- Sample Complexity of Sinkhorn divergences
- Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
- Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
- Smooth and Sparse Optimal Transport
- On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
- Subspace Robust Wasserstein Distances
- Generalizing Point Embeddings using the Wasserstein Space of Elliptical Distributions
- High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
- Multilevel Clustering via Wasserstein Means
- Averaging Stochastic Gradient Descent on Riemannian Manifolds
- Statistical Optimal Transport via Factored Couplings
- Efficiently escaping saddle points on manifolds
- Learning Probability Measures with respect to Optimal Transport Metrics
- Langevin Monte Carlo and JKO splitting
- Riemannian adaptive stochastic gradient algorithms on matrix manifolds
- Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
- Escaping from saddle points on Riemannian manifolds
- Structured Quasi-Newton Methods for Optimization with Orthogonality Constraints
- Distributional Sliced-Wasserstein and Applications to Generative Modeling
- Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?