Progressive Entropic Optimal Transport Solvers

• URL: http://arxiv.org/abs/2406.05061v3
• Date: Wed, 30 Oct 2024 20:59:51 GMT
• Title: Progressive Entropic Optimal Transport Solvers
• Authors: Parnian Kassraie, Aram-Alexandre Pooladian, Michal Klein, James Thornton, Jonathan Niles-Weed, Marco Cuturi,
• Abstract summary: We propose a new class of EOT solvers (ProgOT) that can estimate both plans and transport maps. We provide experimental evidence demonstrating that ProgOT is a faster and more robust alternative to standard solvers. We also prove statistical consistency of our approach for estimating optimal transport maps.
• Score: 33.821924561619895
• License:
• Abstract: Optimal transport (OT) has profoundly impacted machine learning by providing theoretical and computational tools to realign datasets. In this context, given two large point clouds of sizes $n$ and $m$ in $\mathbb{R}^d$, entropic OT (EOT) solvers have emerged as the most reliable tool to either solve the Kantorovich problem and output a $n\times m$ coupling matrix, or to solve the Monge problem and learn a vector-valued push-forward map. While the robustness of EOT couplings/maps makes them a go-to choice in practical applications, EOT solvers remain difficult to tune because of a small but influential set of hyperparameters, notably the omnipresent entropic regularization strength $\varepsilon$. Setting $\varepsilon$ can be difficult, as it simultaneously impacts various performance metrics, such as compute speed, statistical performance, generalization, and bias. In this work, we propose a new class of EOT solvers (ProgOT), that can estimate both plans and transport maps. We take advantage of several opportunities to optimize the computation of EOT solutions by dividing mass displacement using a time discretization, borrowing inspiration from dynamic OT formulations, and conquering each of these steps using EOT with properly scheduled parameters. We provide experimental evidence demonstrating that ProgOT is a faster and more robust alternative to standard solvers when computing couplings at large scales, even outperforming neural network-based approaches. We also prove statistical consistency of our approach for estimating optimal transport maps.

Related papers

• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  Optimal transport theory provides a principled framework for constructing such mappings. We propose a novel optimal transport solver based on Wasserstein-1. Our experiments demonstrate that the proposed solver can mimic the $W$ OT solvers in finding a unique and monotonic" map on 2D datasets.
  arXiv  Detail & Related papers  (2024-11-01T14:23:19Z)
• Efficient Neural Network Approaches for Conditional Optimal Transport with Applications in Bayesian Inference [1.740133468405535]
  We present two neural network approaches that approximate the solutions of static and conditional optimal transport (COT) problems. We demonstrate both algorithms, comparing them with competing state-the-art approaches, using benchmark datasets and simulation-based inverse problems.
  arXiv  Detail & Related papers  (2023-10-25T20:20:09Z)
• 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)
• 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)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  We propose a novel neural algorithm for the fundamental problem of computing the entropic optimal transport (EOT) plan between continuous probability distributions. Our algorithm is based on the saddle point reformulation of the dynamic version of EOT which is known as the Schr"odinger Bridge problem. In contrast to the prior methods for large-scale EOT, our algorithm is end-to-end and consists of a single learning step.
  arXiv  Detail & Related papers  (2022-11-02T14:35:13Z)
• 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)
• On the complexity of the optimal transport problem with graph-structured cost [9.24979291231758]
  Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. The usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals.
  arXiv  Detail & Related papers  (2021-10-01T19:29:59Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• Efficient Robust Optimal Transport with Application to Multi-Label Classification [12.521494095948068]
  We model the feature-feature relationship via a symmetric positive semi-definite Mahalanobis metric in the OT cost function. We view the resulting optimization problem as a non-linear OT problem, which we solve using the Frank-Wolfe algorithm. Empirical results on the discriminative learning setting, such as tag prediction and multi-class classification, illustrate the good performance of our approach.
  arXiv  Detail & Related papers  (2020-10-22T16:43:52Z)

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.