Unbalanced Optimal Transport, from Theory to Numerics

• URL: http://arxiv.org/abs/2211.08775v1
• Date: Wed, 16 Nov 2022 09:02:52 GMT
• Title: Unbalanced Optimal Transport, from Theory to Numerics
• Authors: Thibault S\'ejourn\'e, Gabriel Peyr\'e, Fran\c{c}ois-Xavier Vialard
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal Transport (OT) has recently emerged as a central tool in data sciences to compare in a geometrically faithful way point clouds and more generally probability distributions. The wide adoption of OT into existing data analysis and machine learning pipelines is however plagued by several shortcomings. This includes its lack of robustness to outliers, its high computational costs, the need for a large number of samples in high dimension and the difficulty to handle data in distinct spaces. In this review, we detail several recently proposed approaches to mitigate these issues. We insist in particular on unbalanced OT, which compares arbitrary positive measures, not restricted to probability distributions (i.e. their total mass can vary). This generalization of OT makes it robust to outliers and missing data. The second workhorse of modern computational OT is entropic regularization, which leads to scalable algorithms while lowering the sample complexity in high dimension. The last point presented in this review is the Gromov-Wasserstein (GW) distance, which extends OT to cope with distributions belonging to different metric spaces. 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.

Related papers

• A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers [65.28989155951132]
  In this paper, we establish upper bounds on the generalization error of an approximate OT map recovered by the minimax quadratic OT solver. While our analysis focuses on the quadratic OT, we believe that similar bounds could be derived for more general OT formulations.
  arXiv  Detail & Related papers  (2025-02-03T12:37:20Z)
• 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)
• Energy-Guided Continuous Entropic Barycenter Estimation for General Costs [95.33926437521046]
  We propose a novel algorithm for approximating the continuous Entropic OT (EOT) barycenter for arbitrary OT cost functions. Our approach is built upon the dual reformulation of the EOT problem based on weak OT.
  arXiv  Detail & Related papers  (2023-10-02T11:24:36Z)
• Slicing Unbalanced Optimal Transport [13.679363125262599]
  Optimal transport is a powerful framework to compare probability measures. We formulate two different versions of sliced unbalanced OT, and study the associated topology and statistical properties. We then develop a GPU-friendly Frank-Wolfe like algorithm to compute the corresponding loss functions.
  arXiv  Detail & Related papers  (2023-06-12T15:15:00Z)
• Unbalanced Low-rank Optimal Transport Solvers [38.79369155558385]
  We propose algorithms to implement extensions for the linear OT problem and its Fused-Gromov-Wasserstein generalization. The goal of this paper is to merge these two strains, to achieve the promise of textitboth versatile/scalable unbalanced/low-rank OT solvers.
  arXiv  Detail & Related papers  (2023-05-31T10:39:51Z)
• 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)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• Efficient estimates of optimal transport via low-dimensional embeddings [0.0]
  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.
  arXiv  Detail & Related papers  (2021-11-08T21:22:51Z)
• Debiased Sinkhorn barycenters [110.79706180350507]
  Entropy regularization in optimal transport (OT) has been the driver of many recent interests for Wasserstein metrics and barycenters in machine learning. We show how this bias is tightly linked to the reference measure that defines the entropy regularizer. We propose debiased Wasserstein barycenters that preserve the best of both worlds: fast Sinkhorn-like iterations without entropy smoothing.
  arXiv  Detail & Related papers  (2020-06-03T23:06: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.