Efficient estimates of optimal transport via low-dimensional embeddings

• URL: http://arxiv.org/abs/2111.04838v1
• Date: Mon, 8 Nov 2021 21:22:51 GMT
• Title: Efficient estimates of optimal transport via low-dimensional embeddings
• Authors: Patric M. Fulop, Vincent Danos
• Abstract summary: Optimal transport distances (OT) have been widely used in recent work in Machine Learning as ways to compare probability distributions. Recent work by Paty et al., 2019, aims specifically at reducing this cost by computing OT using low-rank projections of the data. We extend this approach and show that one can approximate OT distances by using more general families of maps provided they are 1-Lipschitz.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal transport distances (OT) have been widely used in recent work in Machine Learning as ways to compare probability distributions. These are costly to compute when the data lives in high dimension. Recent work by Paty et al., 2019, aims specifically at reducing this cost by computing OT using low-rank projections of the data (seen as discrete measures). We extend this approach and show that one can approximate OT distances by using more general families of maps provided they are 1-Lipschitz. The best estimate is obtained by maximising OT over the given family. As OT calculations are done after mapping data to a lower dimensional space, our method scales well with the original data dimension. We demonstrate the idea with neural networks.

Related papers

• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  We prove an $mathcalO(t-1)$ lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation. To nearly achieve the desired fast rate, we design an entropic regularization scheme decreasing with the number of samples.
  arXiv  Detail & Related papers  (2024-05-23T11:46:03Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Unbalanced Optimal Transport meets Sliced-Wasserstein [11.44982599214965]
  We propose two new loss functions based on the idea of slicing unbalanced OT, and study their induced topology and statistical properties. We show that the resulting methodology is modular as it encompasses and extends prior related work.
  arXiv  Detail & Related papers  (2023-06-12T15:15:00Z)
• 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)
• Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
  Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. We propose regularizing OT with the beta-potential term associated with the so-called $beta$-divergence. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers.
  arXiv  Detail & Related papers  (2022-12-26T18:37:28Z)
• Sliced Optimal Partial Transport [13.595857406165292]
  We propose an efficient algorithm for calculating the Optimal Partial Transport problem between two non-negative measures in one dimension. We demonstrate the computational and accuracy benefits of the sliced OPT-based method in various numerical experiments.
  arXiv  Detail & Related papers  (2022-12-15T18:55:23Z)
• Unbalanced Optimal Transport, from Theory to Numerics [0.0]
  We argue that unbalanced OT, entropic regularization and Gromov-Wasserstein (GW) can work hand-in-hand to turn OT into efficient geometric loss functions for data sciences. The main motivation for this review is to explain how unbalanced OT, entropic regularization and GW can work hand-in-hand to turn OT into efficient geometric loss functions for data sciences.
  arXiv  Detail & Related papers  (2022-11-16T09:02:52Z)
• InfoOT: Information Maximizing Optimal Transport [58.72713603244467]
  InfoOT is an information-theoretic extension of optimal transport. It maximizes the mutual information between domains while minimizing geometric distances. This formulation yields a new projection method that is robust to outliers and generalizes to unseen samples.
  arXiv  Detail & Related papers  (2022-10-06T18:55:41Z)
• 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)
• Generative Modeling with Optimal Transport Maps [83.59805931374197]
  Optimal Transport (OT) has become a powerful tool for large-scale generative modeling tasks. We show that the OT map itself can be used as a generative model, providing comparable performance.
  arXiv  Detail & Related papers  (2021-10-06T18:17: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.