mlsanityData to 14 Oct 2026

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

arXiv 2405.15441 ↗First posted 24 May 2024stat.ML cs.CC cs.LGcited by 4

Not on the map. Why?

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.

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

42 of 93 references.

References · 42

  1. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 641
  2. 2015Optimal Transport for Domain Adaptationcited by 463
  3. 2016Kernel Mean Embedding of Distributions: A Review and Beyondcited by 364
  4. 2017Learning Generative Models with Sinkhorn Divergencescited by 314
  5. 2017Joint Distribution Optimal Transportation for Domain Adaptationcited by 282
  6. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 223
  7. 2019Generalized Sliced Wasserstein Distancescited by 208
  8. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 185
  9. 2015On Wasserstein Two Sample Testing and Related Families of Nonparametric Testscited by 166
  10. 2020Learning Deep Kernels for Non-Parametric Two-Sample Testscited by 130
  11. 2019Max-Sliced Wasserstein Distance and its use for GANscited by 119
  12. 2018Generative Modeling using the Sliced Wasserstein Distancecited by 108
30 more
  1. 2016Generative Models and Model Criticism via Optimized Maximum Mean Discrepancycited by 100
  2. 2019Subspace Robust Wasserstein Distancescited by 90
  3. 2017Sliced Wasserstein Kernel for Persistence Diagramscited by 77
  4. 2021MMD Aggregated Two-Sample Testcited by 75
  5. 2018The Price of Fair PCA: One Extra Dimensioncited by 67
  6. 2017On the regularization of Wasserstein GANscited by 65
  7. 2016Interpretable Distribution Features with Maximum Testing Powercited by 63
  8. 2018Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distancecited by 56
  9. 2020Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learningcited by 47
  10. 2020Projection Robust Wasserstein Distance and Riemannian Optimizationcited by 45
  11. 2019Asymptotic Guarantees for Learning Generative Models with the Sliced-Wasserstein Distancecited by 43
  12. 2022Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distancescited by 41
  13. 2021Sinkhorn Distributionally Robust Optimizationcited by 38
  14. 2020On Projection Robust Optimal Transport: Sample Complexity and Model Misspecificationcited by 34
  15. 2018Robust Hypothesis Testing Using Wasserstein Uncertainty Setscited by 28
  16. 2019Two-sample Testing Using Deep Learningcited by 27
  17. 2020A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distancecited by 27
  18. 2022Efficient Aggregated Kernel Tests using Incomplete U-statisticscited by 27
  19. 2020Two-sample Test using Projected Wasserstein Distancecited by 17
  20. 2024Sharp bounds for max-sliced Wasserstein distancescited by 10
  21. 2022A Data-Driven Approach to Robust Hypothesis Testing Using Sinkhorn Uncertainty Setscited by 9
  22. 2021Projection Robust Wasserstein Barycenterscited by 8
  23. 2023Variable Selection for Kernel Two-Sample Testscited by 7
  24. 2022An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenterscited by 6
  25. 2019Cross-Language Aphasia Detection using Optimal Transport Domain Adaptationcited by 5
  26. 2022A Manifold Two-Sample Test Study: Integral Probability Metric with Neural Networkscited by 5
  27. 2024Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Setscited by 4
  28. 2022On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problemscited by 3
  29. 2022A Riemannian exponential augmented Lagrangian method for computing the projection robust Wasserstein distancecited by 3
  30. 2023On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithmscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Population-Aligned Persona Generation for LLM-based Social Simulationcited by 21
  2. 2025Minimax-Optimal Two-Sample Test with Sliced Wassersteincited by 1
  3. 2025Kernel Quantile Embeddings and Associated Probability Metricscited by 0
  4. 2026Selection-Aware Stress Testing for Interactive Agentscited by 0