Algorithms for Weak Optimal Transport with an Application to Economics

• URL: http://arxiv.org/abs/2205.09825v2
• Date: Mon, 23 May 2022 15:51:09 GMT
• Title: Algorithms for Weak Optimal Transport with an Application to Economics
• Authors: Fran\c{c}ois-Pierre Paty, Philippe Chon\'e, Francis Kramarz
• Abstract summary: Theory of weak optimal transport (WOT) allows the transport cost between one point and the points it is matched with to be nonlinear. In this paper, we propose to use mirror descent algorithms to solve the primal and dual versions of the WOT problem. We also apply our algorithms to the variant of WOT introduced by [Chon'e et al., 2022] where mass is distributed from one space to another through unnormalized kernels (WOTUK)
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The theory of weak optimal transport (WOT), introduced by [Gozlan et al., 2017], generalizes the classic Monge-Kantorovich framework by allowing the transport cost between one point and the points it is matched with to be nonlinear. In the so-called barycentric version of WOT, the cost for transporting a point $x$ only depends on $x$ and on the barycenter of the points it is matched with. This aggregation property of WOT is appealing in machine learning, economics and finance. Yet algorithms to compute WOT have only been developed for the special case of quadratic barycentric WOT, or depend on neural networks with no guarantee on the computed value and matching. The main difficulty lies in the transportation constraints which are costly to project onto. In this paper, we propose to use mirror descent algorithms to solve the primal and dual versions of the WOT problem. We also apply our algorithms to the variant of WOT introduced by [Chon\'e et al., 2022] where mass is distributed from one space to another through unnormalized kernels (WOTUK). We empirically compare the solutions of WOT and WOTUK with classical OT. We illustrate our numerical methods to the economic framework of [Chon\'e and Kramarz, 2021], namely the matching between workers and firms on labor markets.

Related papers

• Progressive Entropic Optimal Transport Solvers [33.821924561619895]
  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.
  arXiv  Detail & Related papers  (2024-06-07T16:33:08Z)
• On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
  We consider online model selection with decentralized data over $M$ clients, and study the necessity of collaboration among clients. Our results show (i) collaboration is unnecessary in the absence of computational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited to $o(K)$, where $K$ is the number of candidate hypothesis spaces.
  arXiv  Detail & Related papers  (2024-04-15T06:32:28Z)
• Quantum Theory and Application of Contextual Optimal Transport [2.160404814399144]
  We propose a first-of-its-kind quantum computing formulation for amortized optimization of contextualized transportation plans. We report a performance that cannot be matched with our classical neural OT approach.
  arXiv  Detail & Related papers  (2024-02-22T22:03:16Z)
• Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
  We propose a new scalable approach for solving the Wasserstein barycenter problem. Our methodology is based on the recent Neural OT solver. We also establish theoretical error bounds for our proposed approach.
  arXiv  Detail & Related papers  (2024-02-06T09:17:07Z)
• Double-Bounded Optimal Transport for Advanced Clustering and Classification [58.237576976486544]
  We propose Doubly Bounded Optimal Transport (DB-OT), which assumes that the target distribution is restricted within two boundaries instead of a fixed one. We show that our method can achieve good results with our improved inference scheme in the testing stage.
  arXiv  Detail & Related papers  (2024-01-21T07:43:01Z)
• 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)
• 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)
• 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)
• Kantorovich Strikes Back! Wasserstein GANs are not Optimal Transport? [138.1080446991979]
  Wasserstein Generative Adversarial Networks (WGANs) are the popular generative models built on the theory of Optimal Transport (OT) and the Kantorovich duality. Despite the success of WGANs, it is still unclear how well the underlying OT dual solvers approximate the OT cost (Wasserstein-1 distance, $mathbbW_1$) and the OT gradient needed to update the generator. We construct 1-Lipschitz functions and use them to build ray monotone transport plans. This strategy yields pairs of continuous benchmark distributions with the analytically known OT plan, OT cost and OT
  arXiv  Detail & Related papers  (2022-06-15T19:07:46Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  We introduce an explicit factorization of low rank couplings as a product of textitsub-coupling factors linked by a common marginal. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.
  arXiv  Detail & Related papers  (2021-03-08T13:18:45Z)
• Regularized Optimal Transport is Ground Cost Adversarial [34.81915836064636]
  We show that regularization of the optimal transport problem can be interpreted as ground cost adversarial. This gives access to a robust dissimilarity measure on the ground space, which can in turn be used in other applications.
  arXiv  Detail & Related papers  (2020-02-10T17:28:35Z)

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.