A Swiss Army Knife for Minimax Optimal Transport

Sofien Dhouib, Ievgen Redko, Tanguy Kerdoncuff, Rémi Emonet, Marc Sebban
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:2504-2513, 2020.

Abstract

The Optimal transport (OT) problem and its associated Wasserstein distance have recently become a topic of great interest in the machine learning community. However, the underlying optimization problem is known to have two major restrictions: (i) it largely depends on the choice of the cost function and (ii) its sample complexity scales exponentially with the dimension. In this paper, we propose a general formulation of a minimax OT problem that can tackle these restrictions by jointly optimizing the cost matrix and the transport plan, allowing us to define a robust distance between distributions. We propose to use a cutting-set method to solve this general problem and show its links and advantages compared to other existing minimax OT approaches. Additionally, we use this method to define a notion of stability allowing us to select the most robust cost matrix. Finally, we provide an experimental study highlighting the efficiency of our approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-dhouib20a, title = {A Swiss Army Knife for Minimax Optimal Transport}, author = {Dhouib, Sofien and Redko, Ievgen and Kerdoncuff, Tanguy and Emonet, R{\'e}mi and Sebban, Marc}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {2504--2513}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/dhouib20a/dhouib20a.pdf}, url = {https://proceedings.mlr.press/v119/dhouib20a.html}, abstract = {The Optimal transport (OT) problem and its associated Wasserstein distance have recently become a topic of great interest in the machine learning community. However, the underlying optimization problem is known to have two major restrictions: (i) it largely depends on the choice of the cost function and (ii) its sample complexity scales exponentially with the dimension. In this paper, we propose a general formulation of a minimax OT problem that can tackle these restrictions by jointly optimizing the cost matrix and the transport plan, allowing us to define a robust distance between distributions. We propose to use a cutting-set method to solve this general problem and show its links and advantages compared to other existing minimax OT approaches. Additionally, we use this method to define a notion of stability allowing us to select the most robust cost matrix. Finally, we provide an experimental study highlighting the efficiency of our approach.} }
Endnote
%0 Conference Paper %T A Swiss Army Knife for Minimax Optimal Transport %A Sofien Dhouib %A Ievgen Redko %A Tanguy Kerdoncuff %A Rémi Emonet %A Marc Sebban %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-dhouib20a %I PMLR %P 2504--2513 %U https://proceedings.mlr.press/v119/dhouib20a.html %V 119 %X The Optimal transport (OT) problem and its associated Wasserstein distance have recently become a topic of great interest in the machine learning community. However, the underlying optimization problem is known to have two major restrictions: (i) it largely depends on the choice of the cost function and (ii) its sample complexity scales exponentially with the dimension. In this paper, we propose a general formulation of a minimax OT problem that can tackle these restrictions by jointly optimizing the cost matrix and the transport plan, allowing us to define a robust distance between distributions. We propose to use a cutting-set method to solve this general problem and show its links and advantages compared to other existing minimax OT approaches. Additionally, we use this method to define a notion of stability allowing us to select the most robust cost matrix. Finally, we provide an experimental study highlighting the efficiency of our approach.
APA
Dhouib, S., Redko, I., Kerdoncuff, T., Emonet, R. & Sebban, M.. (2020). A Swiss Army Knife for Minimax Optimal Transport. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:2504-2513 Available from https://proceedings.mlr.press/v119/dhouib20a.html.

Related Material