Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

• URL: http://arxiv.org/abs/2405.15441v3
• Date: Sun, 02 Feb 2025 21:27:13 GMT
• Title: Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
• Authors: Jie Wang, March Boedihardjo, Yao Xie,
• Abstract summary: kernel max-sliced (KMS) Wasserstein distance is developed for this purpose. We show that computing the KMS $2$-Wasserstein distance is NP-hard.
• Score: 9.608373793625107
• License:
• Abstract: 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\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 obtained solution. We provide numerical examples to demonstrate the good performance of our scheme for high-dimensional two-sample testing.

Related papers

• Optimal Transport Barycenter via Nonconvex-Concave Minimax Optimization [11.344401324787974]
  Wasserstein-Descent $dotmathbbH1$-Ascent (WDHA) algorithm for computing exact barycenter. We present a nearly linear time $O(m logm)$ and linear space complexity $O(m)$ primal-dual algorithm for approximating the barycenter problem.
  arXiv  Detail & Related papers  (2025-01-24T16:55:21Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Private Geometric Median [10.359525525715421]
  We study differentially private (DP) algorithms for computing the geometric median (GM) of a dataset. Our main contribution is a pair of DP algorithms for the task of private GM with an excess error guarantee that scales with the effective diameter of the datapoints.
  arXiv  Detail & Related papers  (2024-06-11T16:13:09Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters [0.0]
  We present two algorithms to approximate the solution of multi-marginal optimal transport (MOT) with squared Euclidean costs for $N$ discrete probability measures. They are fast, memory-efficient and easy to implement and can be used with any sparse OT solver as a black box.
  arXiv  Detail & Related papers  (2022-02-02T10:59:54Z)
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization [94.18714844247766]
  Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport. We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
  arXiv  Detail & Related papers  (2021-02-02T21:01:13Z)
• Two-sample Test using Projected Wasserstein Distance [18.46110328123008]
  We develop a projected Wasserstein distance for the two-sample test, a fundamental problem in statistics and machine learning. A key contribution is to couple optimal projection to find the low dimensional linear mapping to maximize the Wasserstein distance between projected probability distributions.
  arXiv  Detail & Related papers  (2020-10-22T18:08:58Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
  arXiv  Detail & Related papers  (2020-06-22T14:35:33Z)
• Augmented Sliced Wasserstein Distances [55.028065567756066]
  We propose a new family of distance metrics, called augmented sliced Wasserstein distances (ASWDs) ASWDs are constructed by first mapping samples to higher-dimensional hypersurfaces parameterized by neural networks. Numerical results demonstrate that the ASWD significantly outperforms other Wasserstein variants for both synthetic and real-world problems.
  arXiv  Detail & Related papers  (2020-06-15T23:00:08Z)
• Projection Robust Wasserstein Distance and Riemannian Optimization [107.93250306339694]
  We show that projection robustly solidstein (PRW) is a robust variant of Wasserstein projection (WPP) This paper provides a first step into the computation of the PRW distance and provides the links between their theory and experiments on and real data.
  arXiv  Detail & Related papers  (2020-06-12T20:40:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.