Markovian Sliced Wasserstein Distances: Beyond Independent Projections
This addresses computational inefficiencies in optimal transport metrics for machine learning practitioners, though it is an incremental improvement over existing Sliced Wasserstein variants.
The paper tackles the problem of redundant projections in Sliced Wasserstein distances by introducing Markovian Sliced Wasserstein (MSW) distances, which impose a first-order Markov structure on projecting directions to improve efficiency and maintain metricity, demonstrating favorable performance in applications like gradient flows and deep generative modeling.
Sliced Wasserstein (SW) distance suffers from redundant projections due to independent uniform random projecting directions. To partially overcome the issue, max K sliced Wasserstein (Max-K-SW) distance ($K\geq 1$), seeks the best discriminative orthogonal projecting directions. Despite being able to reduce the number of projections, the metricity of Max-K-SW cannot be guaranteed in practice due to the non-optimality of the optimization. Moreover, the orthogonality constraint is also computationally expensive and might not be effective. To address the problem, we introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes a first-order Markov structure on projecting directions. We discuss various members of MSW by specifying the Markov structure including the prior distribution, the transition distribution, and the burning and thinning technique. Moreover, we investigate the theoretical properties of MSW including topological properties (metricity, weak convergence, and connection to other distances), statistical properties (sample complexity, and Monte Carlo estimation error), and computational properties (computational complexity and memory complexity). Finally, we compare MSW distances with previous SW variants in various applications such as gradient flows, color transfer, and deep generative modeling to demonstrate the favorable performance of MSW.