Research map / Learning theory and algorithms / Optimal transport
Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives dimension-free finite-sample rates for the kernel max-sliced Wasserstein distance, proves NP-hardness of exact 2-KMS computation, and proposes a semidefinite relaxation solved by inexact mirror ascent with a rank bound and relaxation gap.
Problem
Kernel max-sliced (KMS) Wasserstein distance lacks sharp statistical guarantees and provable computational guarantees; exact computation is non-convex and existing gradient methods give only local optima.
Approach
Derives dimension-free n^{-1/(2p)} finite-sample bounds for KMS p-Wasserstein via reduction to MS Wasserstein on Hilbert space, shows NP-hardness of exact 2-KMS, and relaxes the rank-1 constraint to an SDP solved by inexact mirror ascent with Katyusha-based OT oracle, with a rank bound k and a relaxation gap.
Key results
- Finite-sample bound: KMS p-Wasserstein between empirical distributions decays as n^{-1/(2p)}, dimension-free, under a bounded-kernel assumption.
- Complexity of the first-order SDR solver is O~(n^2 delta^-2 max(n, delta^-1)), versus O~(n^6.5) for interior point methods.
- Detection delay on MSRC-12 with alpha=0.05: KMS mean 11.4 vs. 16.5 for Sinkhorn divergence and 17.8 for MS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KMS instead of Sinkhorn Div | Two-sample change-point detection · MSRC-12 | mean detection delay: 11.4 vs 16.5 | Helped |
| Use KMS instead of GSW | Two-sample change-point detection · MSRC-12 | mean detection delay: 11.4 vs 12.9 | Helped |
| Use KMS instead of MS | Two-sample change-point detection · MSRC-12 | mean detection delay: 11.4 vs 17.8 | Helped |
| Use KMS instead of Sinkhorn divergence | Generative modeling · Generative modeling | FID: 105.98 vs 114.36 | Helped |
| Use KMS instead of MMD | Generative modeling · Generative modeling | FID: 105.98 vs 113.08 | Helped |
| Use KMS instead of Sliced Wasserstein | Generative modeling · Generative modeling | FID: 105.98 vs 113.92 | Helped |
| Use KMS instead of Generalized Sliced Wasserstein | Generative modeling · Generative modeling | FID: 105.98 vs 128.07 | Helped |
| Use KMS instead of Max-Sliced Wasserstein | Generative modeling · Generative modeling | FID: 105.98 vs 115.21 | Helped |
| Use KMS instead of MS | Two-sample testing · Gaussian covariance shift | testing power | Hurt |
| Use KMS instead of the baselines | Two-sample testing · Gaussian mixture distribution shift | testing power | Helped |
| Use KMS instead of the baselines | Two-sample testing · MNIST distribution abundance changes | testing power | Helped |
| Use KMS instead of the baselines | Two-sample testing · CIFAR-10 distribution abundance changes | testing power | Helped |
Surprising findings
- The max-sliced Wasserstein distance outperforms KMS on the Gaussian covariance shift scenario, attributed to linear projections being optimal for that setting.
- Exact 2-KMS computation is NP-hard for worst-case instances, with hardness arising from sample size n alone.
Limitations
- Exact KMS 2-Wasserstein computation is NP-hard, so the SDR yields only an approximation with a relaxation gap bound of order n^-4.
- Rank reduction worst-case complexity is O(n^5), and the theoretical complexity is considerably larger than observed numerically.
- Two-sample test power still depends on dimension through the discrepancy term; the Gaussian kernel bounded assumption is needed.
Experimental setup
Datasets: MNIST CIFAR-10 MSRC-12 Kinect gesture dataset synthetic Gaussian covariance shift synthetic Gaussian mixture
Benchmarks: MNIST CIFAR-10 MSRC-12 Kinect gesture dataset
Metrics: testing power running time estimated KMS 2-Wasserstein distance detection delay FID
Baselines: SDR-IPM BCD Sinkhorn divergence MMD sliced Wasserstein generalized sliced Wasserstein max-sliced Wasserstein optimized mean embedding test
Builds on: max-sliced Wasserstein distance kernel max-sliced Wasserstein distance Katyusha momentum Danskin's theorem
Closest papers by meaning
- Sliced Wasserstein Kernels for Probability Distributions (CVPR 2016 · similarity 0.92)
- Sliced Gromov-Wasserstein (NeurIPS 2019 · similarity 0.91)
- A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.89)
- Towards Understanding Gradient Dynamics of the Sliced-Wasserstein Distance via Critical Point Analysis (ICML 2025 · similarity 0.89)
- Tree-Sliced Wasserstein Distance with Nonlinear Projection (ICML 2025 · similarity 0.88)
- Sliced Wasserstein Estimation with Control Variates (ICLR 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.