Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes

Marin Ballu, Quentin Berthet
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:1595-1613, 2023.

Abstract

Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a single-loop optimization algorithm for minimizing general convex objectives on these domains, utilizing the principles of Sinkhorn matrix scaling and mirror descent. The proposed algorithm is robust to noise, and can be used in an online setting. We provide theoretical guarantees for convex objectives and experimental results showcasing it effectiveness on both synthetic and real-world data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-ballu23a, title = {Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes}, author = {Ballu, Marin and Berthet, Quentin}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {1595--1613}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/ballu23a/ballu23a.pdf}, url = {https://proceedings.mlr.press/v202/ballu23a.html}, abstract = {Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a single-loop optimization algorithm for minimizing general convex objectives on these domains, utilizing the principles of Sinkhorn matrix scaling and mirror descent. The proposed algorithm is robust to noise, and can be used in an online setting. We provide theoretical guarantees for convex objectives and experimental results showcasing it effectiveness on both synthetic and real-world data.} }
Endnote
%0 Conference Paper %T Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes %A Marin Ballu %A Quentin Berthet %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-ballu23a %I PMLR %P 1595--1613 %U https://proceedings.mlr.press/v202/ballu23a.html %V 202 %X Optimal transport is an important tool in machine learning, allowing to capture geometric properties of the data through a linear program on transport polytopes. We present a single-loop optimization algorithm for minimizing general convex objectives on these domains, utilizing the principles of Sinkhorn matrix scaling and mirror descent. The proposed algorithm is robust to noise, and can be used in an online setting. We provide theoretical guarantees for convex objectives and experimental results showcasing it effectiveness on both synthetic and real-world data.
APA
Ballu, M. & Berthet, Q.. (2023). Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:1595-1613 Available from https://proceedings.mlr.press/v202/ballu23a.html.

Related Material