Kostic, Vladimir R;
Salzo, Saverio;
Pontil, Massimiliano;
(2022)
Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity.
In: Chaudhuri, K and Jegelka, S and Song, L and Szepesvari, C and Niu, G and Sabato, S, (eds.)
Proceedings of Machine Learning Research.
(pp. pp. 11529-11558).
Proceedings of Machine Learning Research (PMLR)
Preview |
PDF
kostic22a.pdf - Published Version Download (2MB) | Preview |
Abstract
In this work we propose a batch multimarginal version of the Greenkhorn algorithm for the entropic-regularized optimal transport problem. This framework is general enough to cover, as particular cases, existing Sinkhorn and Greenkhorn algorithms for the bi-marginal setting, and greedy MultiSinkhorn for the general multimarginal case. We provide a comprehensive convergence analysis based on the properties of the iterative Bregman projections method with greedy control. Linear rate of convergence as well as explicit bounds on the iteration complexity are obtained. When specialized to the above mentioned algorithms, our results give new convergence rates or provide key improvements over the state-of-the-art rates. We present numerical experiments showing that the flexibility of the batch can be exploited to improve performance of Sinkhorn algorithm both in bi-marginal and multimarginal settings.
| Type: | Proceedings paper |
|---|---|
| Title: | Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity |
| Event: | 38th International Conference on Machine Learning (ICML) |
| Location: | Baltimore, MD |
| Dates: | 17 Jul 2022 - 23 Jul 2022 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.mlr.press/v162/ |
| Language: | English |
| Additional information: | This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third-party material in this article are included in the Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/ |
| Keywords: | Science & Technology, Technology, Computer Science, Artificial Intelligence, Computer Science |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10173881 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
