Convergence of batch Greenkhorn for Regularized Multimarginal Optimal Transport

• URL: http://arxiv.org/abs/2112.00838v1
• Date: Wed, 1 Dec 2021 21:31:26 GMT
• Title: Convergence of batch Greenkhorn for Regularized Multimarginal Optimal Transport
• Authors: Vladimir Kostic and Saverio Salzo and Massimilano Pontil
• Abstract summary: We provide a complete converge analysis based on the properties of the iterative Bregman projections (IBP) method with greedy control. When specialized to above mentioned algorithms, our results give new insights and/or improve existing ones.
• Score: 6.123324869194195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we propose a batch version of the Greenkhorn algorithm for multimarginal regularized optimal transport problems. Our framework is general enough to cover, as particular cases, some existing algorithms like Sinkhorn and Greenkhorn algorithm for the bi-marginal setting, and (greedy) MultiSinkhorn for multimarginal optimal transport. We provide a complete converge analysis, which is based on the properties of the iterative Bregman projections (IBP) method with greedy control. Global linear rate of convergence and explicit bound on the iteration complexity are obtained. When specialized to above mentioned algorithms, our results give new insights and/or improve existing ones.

Related papers

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm, dubbed ALEXR. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions. We present lower complexity bounds to demonstrate that the convergence rates of ALEXR are optimal among first-order block-coordinate algorithms for the considered class of cFCCO problems.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• 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)
• The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control [0.0]
  This note complements the paper "One-Way Ticket to Las Vegas and the Quantum Adversary" I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form, using the same perspective as Barnum-Saks-Szegedy.
  arXiv  Detail & Related papers  (2022-11-29T15:25:45Z)
• Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm [0.0]
  Entropic regularization provides a generalization of the original optimal transport problem. replacing the Kullback-Leibler divergence with a general $f$-divergence leads to a natural generalization. We propose a practical algorithm for computing the regularized optimal transport cost and its gradient.
  arXiv  Detail & Related papers  (2021-05-29T16:37:31Z)
• Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence [29.189409618561964]
  We develop new adaptive algorithms for variational inequalities with monotone operators. Our algorithms automatically adapt to unknown problem parameters. We show that our algorithms are universal and simultaneously achieve the optimal convergence rates.
  arXiv  Detail & Related papers  (2020-10-15T14:44:26Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS [19.252319300590653]
  A black-box function $f:mathcalX mapsto mathbbR$ is optimized under the assumption that $f$ is H"older smooth and has bounded norm in the RKHS associated with a given kernel $K$. In this paper, we propose a new algorithm (textttLP-GP-UCB) where the usual GP surrogate model is augmented with Local Polynomial (LP) estimators of the H" smooth parameter $f$.
  arXiv  Detail & Related papers  (2020-05-11T01:55:39Z)
• Inference with Aggregate Data: An Optimal Transport Approach [16.274397329511196]
  We consider inference (filtering) problems over probabilistic graphical models with aggregate data generated by a large population of individuals. We propose a new efficient belief propagation algorithm over tree-structured graphs with computational complexity as well as a global convergence guarantee.
  arXiv  Detail & Related papers  (2020-03-31T03:12:20Z)

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.