Anchor Space Optimal Transport: Accelerating Batch Processing of Multiple OT Problems

• URL: http://arxiv.org/abs/2310.16123v1
• Date: Tue, 24 Oct 2023 18:55:12 GMT
• Title: Anchor Space Optimal Transport: Accelerating Batch Processing of Multiple OT Problems
• Authors: Jianming Huang, Xun Su, Zhongxi Fang, Hiroyuki Kasai
• Abstract summary: We propose a translated OT problem designated as the anchor space optimal transport (ASOT) problem. For the proposed ASOT problem, the distributions will be mapped into a shared anchor point space, which learns the potential common characteristics. Based on the proposed ASOT, the Wasserstein distance error to the original OT problem is proven to be bounded by ground cost errors.
• Score: 13.846014191157405
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The optimal transport (OT) theory provides an effective way to compare probability distributions on a defined metric space, but it suffers from cubic computational complexity. Although the Sinkhorn's algorithm greatly reduces the computational complexity of OT solutions, the solutions of multiple OT problems are still time-consuming and memory-comsuming in practice. However, many works on the computational acceleration of OT are usually based on the premise of a single OT problem, ignoring the potential common characteristics of the distributions in a mini-batch. Therefore, we propose a translated OT problem designated as the anchor space optimal transport (ASOT) problem, which is specially designed for batch processing of multiple OT problem solutions. For the proposed ASOT problem, the distributions will be mapped into a shared anchor point space, which learns the potential common characteristics and thus help accelerate OT batch processing. Based on the proposed ASOT, the Wasserstein distance error to the original OT problem is proven to be bounded by ground cost errors. Building upon this, we propose three methods to learn an anchor space minimizing the distance error, each of which has its application background. Numerical experiments on real-world datasets show that our proposed methods can greatly reduce computational time while maintaining reasonable approximation performance.

Related papers

• Overcoming Fake Solutions in Semi-Dual Neural Optimal Transport: A Smoothing Approach for Learning the Optimal Transport Plan [5.374547520354591]
  Semi-dual Neural OT, a widely used approach for learning OT Maps with neural networks, often generates fake solutions that fail to transfer one distribution to another accurately. We propose a novel method, OTP, which learns both the OT Map and the Optimal Transport Plan, representing the optimal coupling between two distributions. Our experiments show that the OTP model recovers the optimal transport map where existing methods fail and outperforms current OT-based models in image-to-image translation tasks.
  arXiv  Detail & Related papers  (2025-02-07T00:37:12Z)
• 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)
• 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)
• Light Unbalanced Optimal Transport [69.18220206873772]
  We propose a novel theoretically-justified, lightweight, unbalanced EOT solver. Our advancement consists of developing a novel view on the optimization of the UEOT problem yielding tractable and a non-minimax optimization objective. We show that our solver provides a universal approximation of UEOT solutions and obtains its generalization bounds.
  arXiv  Detail & Related papers  (2023-03-14T15:44:40Z)
• 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)
• 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)
• Sparsity-Constrained Optimal Transport [27.76137474217754]
  Regularized optimal transport is now increasingly used as a loss or as a matching layer in neural networks. We propose a new approach for OT with explicit cardinality constraints on the transportation plan. Our method can be thought as a middle ground between unregularized OT (recovered in the case $k$) and quadratically-regularized OT (recovered when $k$ is large enough)
  arXiv  Detail & Related papers  (2022-09-30T13:39:47Z)
• 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)
• A Survey on Optimal Transport for Machine Learning: Theory and Applications [1.1279808969568252]
  Optimal Transport (OT) theory has seen an increasing amount of attention from the computer science community. We present a brief introduction and history, a survey of previous work and propose directions of future study.
  arXiv  Detail & Related papers  (2021-06-03T16:10:42Z)
• Manifold optimization for optimal transport [34.88495814664577]
  Optimal transport (OT) has recently found widespread interest in machine learning. We discuss how to approach OT problems within the framework of the manifold optimization. We make available the Manifold optimization-based Optimal Transport, or MOT, repository with codes useful in solving OT problems in Python and Matlab.
  arXiv  Detail & Related papers  (2021-03-01T10:49:19Z)
• Joint Wasserstein Distribution Matching [89.86721884036021]
  Joint distribution matching (JDM) problem, which aims to learn bidirectional mappings to match joint distributions of two domains, occurs in many machine learning and computer vision applications. We propose to address JDM problem by minimizing the Wasserstein distance of the joint distributions in two domains. We then propose an important theorem to reduce the intractable problem into a simple optimization problem, and develop a novel method to solve it.
  arXiv  Detail & Related papers  (2020-03-01T03:39:00Z)

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.