Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations

• URL: http://arxiv.org/abs/2008.09165v3
• Date: Wed, 26 May 2021 03:48:35 GMT
• Title: Linear Optimal Transport Embedding: Provable Wasserstein classification for certain rigid transformations and perturbations
• Authors: Caroline Moosm\"uller and Alexander Cloninger
• Abstract summary: Discriminating between distributions is an important problem in a number of scientific fields. The Linear Optimal Transportation (LOT) embeds the space of distributions into an $L2$-space. We demonstrate the benefits of LOT on a number of distribution classification problems.
• Score: 79.23797234241471
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Discriminating between distributions is an important problem in a number of scientific fields. This motivated the introduction of Linear Optimal Transportation (LOT), which embeds the space of distributions into an $L^2$-space. The transform is defined by computing the optimal transport of each distribution to a fixed reference distribution, and has a number of benefits when it comes to speed of computation and to determining classification boundaries. In this paper, we characterize a number of settings in which LOT embeds families of distributions into a space in which they are linearly separable. This is true in arbitrary dimension, and for families of distributions generated through perturbations of shifts and scalings of a fixed distribution.We also prove conditions under which the $L^2$ distance of the LOT embedding between two distributions in arbitrary dimension is nearly isometric to Wasserstein-2 distance between those distributions. This is of significant computational benefit, as one must only compute $N$ optimal transport maps to define the $N^2$ pairwise distances between $N$ distributions. We demonstrate the benefits of LOT on a number of distribution classification problems.

Related papers

• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  This paper addresses the challenge of gradual domain adaptation within a class of manifold-constrained data distributions. We propose a methodology rooted in Distributionally Robust Optimization (DRO) with an adaptive Wasserstein radius. Our bounds rely on a newly introduced it compatibility measure, which fully characterizes the error propagation dynamics along the sequence.
  arXiv  Detail & Related papers  (2024-10-17T22:07:25Z)
• Instance-Optimal Private Density Estimation in the Wasserstein Distance [37.58527481568219]
  Estimating the density of a distribution from samples is a fundamental problem in statistics. We study differentially private density estimation in the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-06-27T22:51:06Z)
• Energy-Based Sliced Wasserstein Distance [47.18652387199418]
  A key component of the sliced Wasserstein (SW) distance is the slicing distribution. We propose to design the slicing distribution as an energy-based distribution that is parameter-free. We then derive a novel sliced Wasserstein metric, energy-based sliced Waserstein (EBSW) distance.
  arXiv  Detail & Related papers  (2023-04-26T14:28:45Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  We study simple binary hypothesis testing under both local differential privacy (LDP) and communication constraints. We qualify our results as either minimax optimal or instance optimal.
  arXiv  Detail & Related papers  (2023-01-09T18:36:49Z)
• Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
  We show that efficiency of Metropolis-Hastings (M-H) algorithms in discrete spaces can be characterized by an acceptance rate that is independent of the target distribution. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.
  arXiv  Detail & Related papers  (2022-09-16T22:09:53Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• On the capacity of deep generative networks for approximating distributions [8.798333793391544]
  We prove that neural networks can transform a one-dimensional source distribution to a distribution arbitrarily close to a high-dimensional target distribution in Wasserstein distances. It is shown that the approximation error grows at most linearly on the ambient dimension. $f$-divergences are less adequate than Waserstein distances as metrics of distributions for generating samples.
  arXiv  Detail & Related papers  (2021-01-29T01:45:02Z)

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.