# Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 93 references that are in the map.
- First posted on arXiv 24 May 2024.

## Builds on (most cited first, 30 of 42)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Joint Distribution Optimal Transportation for Domain Adaptation](https://mlsanity.com/paper/1705.08848/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Generalized Sliced Wasserstein Distances](https://mlsanity.com/paper/1902.00434/) (2019)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests](https://mlsanity.com/paper/1509.02237/) (2015)
- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Max-Sliced Wasserstein Distance and its use for GANs](https://mlsanity.com/paper/1904.05877/) (2019)
- [Generative Modeling using the Sliced Wasserstein Distance](https://mlsanity.com/paper/1803.11188/) (2018)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [Subspace Robust Wasserstein Distances](https://mlsanity.com/paper/1901.08949/) (2019)
- [Sliced Wasserstein Kernel for Persistence Diagrams](https://mlsanity.com/paper/1706.03358/) (2017)
- [MMD Aggregated Two-Sample Test](https://mlsanity.com/paper/2110.15073/) (2021)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [On the regularization of Wasserstein GANs](https://mlsanity.com/paper/1709.08894/) (2017)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Projection Robust Wasserstein Distance and Riemannian Optimization](https://mlsanity.com/paper/2006.07458/) (2020)
- [Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distance](https://mlsanity.com/paper/1906.04516/) (2019)
- [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)
- [On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification](https://mlsanity.com/paper/2006.12301/) (2020)
- [Robust Hypothesis Testing Using Wasserstein Uncertainty Sets](https://mlsanity.com/paper/1805.10611/) (2018)
- [Two-sample Testing Using Deep Learning](https://mlsanity.com/paper/1910.06239/) (2019)
- [A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance](https://mlsanity.com/paper/2012.05199/) (2020)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)

## Built on by (most cited first, 4 of 4)

- [Population-Aligned Persona Generation for LLM-based Social Simulation](https://mlsanity.com/paper/2509.10127/) (2025)
- [Minimax-Optimal Two-Sample Test with Sliced Wasserstein](https://mlsanity.com/paper/2510.27498/) (2025)
- [Kernel Quantile Embeddings and Associated Probability Metrics](https://mlsanity.com/paper/2505.20433/) (2025)
- [Selection-Aware Stress Testing for Interactive Agents](https://mlsanity.com/paper/2608.30916/) (2026)

## Abstract (arXiv)

Optimal transport has been very successful for various machine learning tasks; however, it is known to suffer from the curse of dimensionality. Hence, dimensionality reduction is desirable when applied to high-dimensional data with low-dimensional structures. The kernel max-sliced (KMS) Wasserstein distance is developed for this purpose by finding an optimal nonlinear mapping that reduces data into 1 dimension before computing the Wasserstein distance. However, its theoretical properties have not yet been fully developed. In this paper, we provide sharp finite-sample guarantees under milder technical assumptions compared with state-of-the-art for the KMS p-Wasserstein distance between two empirical distributions with n samples for general p∈[1,∞). Algorithm-wise, we show that computing the KMS 2-Wasserstein distance is NP-hard, and then we further propose a semidefinite relaxation (SDR) formulation (which can be solved efficiently in polynomial time) and provide a relaxation gap for the obtained solution. We provide numerical examples to demonstrate the good performance of our scheme for high-dimensional two-sample testing.