  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.
