Learning Cost Functions for Optimal Transport
- URL: http://arxiv.org/abs/2002.09650v2
- Date: Mon, 5 Jul 2021 15:36:53 GMT
- Title: Learning Cost Functions for Optimal Transport
- Authors: Shaojun Ma, Haodong Sun, Xiaojing Ye, Hongyuan Zha, Haomin Zhou
- Abstract summary: Inverse optimal transport (OT) refers to the problem of learning the cost function for OT from observed transport plan or its samples.
We derive an unconstrained convex optimization formulation of the inverse OT problem, which can be further augmented by any customizable regularization.
- Score: 44.64193016158591
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inverse optimal transport (OT) refers to the problem of learning the cost
function for OT from observed transport plan or its samples. In this paper, we
derive an unconstrained convex optimization formulation of the inverse OT
problem, which can be further augmented by any customizable regularization. We
provide a comprehensive characterization of the properties of inverse OT,
including uniqueness of solutions. We also develop two numerical algorithms,
one is a fast matrix scaling method based on the Sinkhorn-Knopp algorithm for
discrete OT, and the other one is a learning based algorithm that parameterizes
the cost function as a deep neural network for continuous OT. The novel
framework proposed in the work avoids repeatedly solving a forward OT in each
iteration which has been a thorny computational bottleneck for the bi-level
optimization in existing inverse OT approaches. Numerical results demonstrate
promising efficiency and accuracy advantages of the proposed algorithms over
existing state-of-the-art methods.
Related papers
- Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment.
We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
arXiv Detail & Related papers (2024-10-28T04:47:39Z) - Operator SVD with Neural Networks via Nested Low-Rank Approximation [19.562492156734653]
This paper proposes a new optimization framework based on the low-rank approximation characterization of a truncated singular value decomposition.
New techniques called emphnesting for learning the top-$L$ singular values and singular functions in the correct order.
We demonstrate the effectiveness of the proposed framework for use cases in computational physics and machine learning.
arXiv Detail & Related papers (2024-02-06T03:06:06Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms.
An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
arXiv Detail & Related papers (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - 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) - Improved Algorithms for Neural Active Learning [74.89097665112621]
We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting.
We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
arXiv Detail & Related papers (2022-10-02T05:03:38Z) - Enhanced Teaching-Learning-based Optimization for 3D Path Planning of
Multicopter UAVs [2.0305676256390934]
This paper introduces a new path planning algorithm for unmanned aerial vehicles (UAVs) based on the teaching-learning-based optimization technique.
We first define an objective function that incorporates requirements on the path length and constraints on the movement and safe operation of UAVs.
The algorithm named Multi-subject TLBO is then proposed to minimize the formulated objective function.
arXiv Detail & Related papers (2022-05-31T16:00:32Z) - Unbalanced Optimal Transport through Non-negative Penalized Linear
Regression [9.668391961887027]
We show that the corresponding optimization problem can be reformulated as a non-negative penalized linear regression problem.
We propose novel algorithms inspired from inverse problems and nonnegative matrix factorization.
We derive for the first time an efficient algorithm to compute the regularization path of UOT with quadratic penalties.
arXiv Detail & Related papers (2021-06-08T07:16:37Z) - Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
We propose a novel algorithm to further improve the efficiency and accuracy based on Nesterov's smoothing technique.
The proposed method achieves faster convergence and better accuracy with the same parameter.
arXiv Detail & Related papers (2021-04-12T20:23:29Z)
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.