Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections

• URL: http://arxiv.org/abs/2106.15427v1
• Date: Tue, 29 Jun 2021 13:56:19 GMT
• Title: Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections
• Authors: Kimia Nadjahi, Alain Durmus, Pierre E. Jacob, Roland Badeau, Umut \c{S}im\c{s}ekli
• Abstract summary: The Sliced-Wasserstein distance (SW) is being increasingly used in machine learning applications. We propose a new perspective to approximate SW by making use of the concentration of measure phenomenon. Our method does not require sampling a number of random projections, and is therefore both accurate and easy to use compared to the usual Monte Carlo approximation.
• Score: 19.987683989865708
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Sliced-Wasserstein distance (SW) is being increasingly used in machine learning applications as an alternative to the Wasserstein distance and offers significant computational and statistical benefits. Since it is defined as an expectation over random projections, SW is commonly approximated by Monte Carlo. We adopt a new perspective to approximate SW by making use of the concentration of measure phenomenon: under mild assumptions, one-dimensional projections of a high-dimensional random vector are approximately Gaussian. Based on this observation, we develop a simple deterministic approximation for SW. Our method does not require sampling a number of random projections, and is therefore both accurate and easy to use compared to the usual Monte Carlo approximation. We derive nonasymptotical guarantees for our approach, and show that the approximation error goes to zero as the dimension increases, under a weak dependence condition on the data distribution. We validate our theoretical findings on synthetic datasets, and illustrate the proposed approximation on a generative modeling problem.

Related papers

• Sliced Wasserstein with Random-Path Projecting Directions [49.802024788196434]
  We propose an optimization-free slicing distribution that provides a fast sampling for the Monte Carlo estimation of expectation. We derive the random-path slicing distribution (RPSD) and two variants of sliced Wasserstein, i.e., the Random-Path Projection Sliced Wasserstein (RPSW) and the Importance Weighted Random-Path Projection Sliced Wasserstein (IWRPSW)
  arXiv  Detail & Related papers  (2024-01-29T04:59:30Z)
• On diffusion-based generative models and their error bounds: The log-concave case with full convergence estimates [5.13323375365494]
  We provide theoretical guarantees for the convergence behaviour of diffusion-based generative models under strongly log-concave data. Our class of functions used for score estimation is made of Lipschitz continuous functions avoiding any Lipschitzness assumption on the score function. This approach yields the best known convergence rate for our sampling algorithm.
  arXiv  Detail & Related papers  (2023-11-22T18:40:45Z)
• Fast Approximation of the Generalized Sliced-Wasserstein Distance [13.840237470871406]
  Generalized sliced Wasserstein distance is a variant of sliced Wasserstein distance. We propose to form deterministic and fast approximations of generalized sliced Wasserstein distance.
  arXiv  Detail & Related papers  (2022-10-19T03:15:50Z)
• Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures [29.26015093627193]
  We develop the Exponential Location Update (ELU) algorithm to efficiently explore the curvature of the negative log-likelihood functions. We demonstrate that the ELU algorithm converges to the final statistical radius of the models after a logarithmic number of iterations.
  arXiv  Detail & Related papers  (2022-05-23T06:49:55Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• Instance-Optimal Compressed Sensing via Posterior Sampling [101.43899352984774]
  We show for Gaussian measurements and emphany prior distribution on the signal, that the posterior sampling estimator achieves near-optimal recovery guarantees. We implement the posterior sampling estimator for deep generative priors using Langevin dynamics, and empirically find that it produces accurate estimates with more diversity than MAP.
  arXiv  Detail & Related papers  (2021-06-21T22:51:56Z)
• 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)
• Faster Wasserstein Distance Estimation with the Sinkhorn Divergence [0.0]
  The squared Wasserstein distance is a quantity to compare probability distributions in a non-parametric setting. In this work, we propose instead to estimate it with the Sinkhorn divergence. We show that, for smooth densities, this estimator has a comparable sample complexity but allows higher regularization levels.
  arXiv  Detail & Related papers  (2020-06-15T06:58:16Z)
• Distributional Sliced-Wasserstein and Applications to Generative Modeling [27.014748003733544]
  Sliced-Wasserstein distance (SW) and its variant, Max Sliced-Wasserstein distance (Max-SW) have been used widely in the recent years. We propose a novel distance, named Distributional Sliced-Wasserstein distance (DSW) We show that the DSW is a generalization of Max-SW, and it can be computed efficiently by searching for the optimal push-forward measure.
  arXiv  Detail & Related papers  (2020-02-18T04:35:16Z)
• Fast approximations in the homogeneous Ising model for use in scene analysis [61.0951285821105]
  We provide accurate approximations that make it possible to numerically calculate quantities needed in inference. We show that our approximation formulae are scalable and unfazed by the size of the Markov Random Field. The practical import of our approximation formulae is illustrated in performing Bayesian inference in a functional Magnetic Resonance Imaging activation detection experiment, and also in likelihood ratio testing for anisotropy in the spatial patterns of yearly increases in pistachio tree yields.
  arXiv  Detail & Related papers  (2017-12-06T14:24:34Z)

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.