Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
<|reference_start|>Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances: 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$ dimensions 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\in[1,\infty)$. 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 SDP solution. We provide numerical examples to demonstrate the good performance of our scheme for high-dimensional two-sample testing.<|reference_end|>
@article{wang2024statistical,
    title={Statistical and Computational Guarantees of Kernel Max-Sliced
  Wasserstein Distances},
    author={Jie Wang and March Boedihardjo and Yao Xie},
    journal={arXiv preprint arXiv:2405.15441},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15441},
    primaryClass={stat.ML cs.CC cs.LG}
}