# Projection Robust Wasserstein Distance and Riemannian Optimization

arXiv: https://arxiv.org/abs/2006.07458 · HTML: https://mlsanity.com/paper/2006.07458/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

## Built on by (most cited first, 30 of 45)

- [Recent Advances in Optimal Transport for Machine Learning](https://mlsanity.com/paper/2306.16156/) (2023)
- [Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances](https://mlsanity.com/paper/2210.09160/) (2022)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Spherical Sliced-Wasserstein](https://mlsanity.com/paper/2206.08780/) (2022)
- [Revisiting Sliced Wasserstein on Images: From Vectorization to Convolution](https://mlsanity.com/paper/2204.01188/) (2022)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [Amortized Projection Optimization for Sliced Wasserstein Generative Models](https://mlsanity.com/paper/2203.13417/) (2022)
- [On Transportation of Mini-batches: A Hierarchical Approach](https://mlsanity.com/paper/2102.05912/) (2021)
- [Hyperbolic Sliced-Wasserstein via Geodesic and Horospherical Projections](https://mlsanity.com/paper/2211.10066/) (2022)
- [Monge, Bregman and Occam: Interpretable Optimal Transport in High-Dimensions with Feature-Sparse Maps](https://mlsanity.com/paper/2302.04065/) (2023)
- [Accelerating Inexact HyperGradient Descent for Bilevel Optimization](https://mlsanity.com/paper/2307.00126/) (2023)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [Momentum Stiefel Optimizer, with Applications to Suitably-Orthogonal Attention, and Optimal Transport](https://mlsanity.com/paper/2205.14173/) (2022)
- [Markovian Sliced Wasserstein Distances: Beyond Independent Projections](https://mlsanity.com/paper/2301.03749/) (2023)
- [Re-evaluating Word Mover's Distance](https://mlsanity.com/paper/2105.14403/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Max-Sliced Mutual Information](https://mlsanity.com/paper/2309.16200/) (2023)
- [Sharp bounds for max-sliced Wasserstein distances](https://mlsanity.com/paper/2403.00666/) (2024)
- [Hilbert Curve Projection Distance for Distribution Comparison](https://mlsanity.com/paper/2205.15059/) (2022)
- [Approximating 1-Wasserstein Distance with Trees](https://mlsanity.com/paper/2206.12116/) (2022)
- [Projection Robust Wasserstein Barycenters](https://mlsanity.com/paper/2102.03390/) (2021)
- [On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity](https://mlsanity.com/paper/2108.07992/) (2021)
- [Nonlinear Sufficient Dimension Reduction for Distribution-on-Distribution Regression](https://mlsanity.com/paper/2207.04613/) (2022)
- [Optimal Transport for Measures with Noisy Tree Metric](https://mlsanity.com/paper/2310.13653/) (2023)
- [Proximity Matters: Local Proximity Enhanced Balancing for Treatment Effect Estimation](https://mlsanity.com/paper/2407.01111/) (2024)
- [Learning Elastic Costs to Shape Monge Displacements](https://mlsanity.com/paper/2306.11895/) (2023)
- [Provably Convergent Policy Optimization via Metric-aware Trust Region Methods](https://mlsanity.com/paper/2306.14133/) (2023)
- [A Manifold Two-Sample Test Study: Integral Probability Metric with Neural Networks](https://mlsanity.com/paper/2205.02043/) (2022)
- [Robust Distribution Learning with Local and Global Adversarial Corruptions](https://mlsanity.com/paper/2406.06509/) (2024)
- [Fast Estimation of Wasserstein Distances via Regression on Sliced Wasserstein Distances](https://mlsanity.com/paper/2509.20508/) (2025)

## Abstract (arXiv)

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~citetNiles-2019-Estimation in a minimax sense, the original formulation for PRW/WPP textitcan 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.