Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe

Thibault Sejourne, Francois-Xavier Vialard, Gabriel Peyré
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:4995-5021, 2022.

Abstract

Unbalanced optimal transport (UOT) extends optimal transport (OT) to take into account mass variations when comparing distributions. This is crucial for successful ML applications of OT, as it makes it robust to data normalization and outliers. The baseline algorithm is Sinkhorn, but its convergence speed might be significantly slower for UOT than for OT. In this work, we identify the cause for this deficiency, namely the lack of a global normalization of the iterates, which equivalently corresponds to a translation of the dual OT potentials. Our first contribution leverages this idea to develop an accelerated Sinkhorn algorithm (coined "translation invariant Sinkhorn") for UOT, bridging the computational gap with OT. Our second contribution focuses on 1-D UOT and proposes a Frank-Wolfe solver applied to this translation invariant formulation. The linear oracle of each step amounts to solving a 1-D OT problem, resulting in a linear time complexity per iteration. Our last contribution extends this method to the computation of UOT barycenter of 1-D measures. Numerical simulations showcase the convergence speed improvement brought by these three approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-sejourne22a, title = { Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe }, author = {Sejourne, Thibault and Vialard, Francois-Xavier and Peyr\'e, Gabriel}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {4995--5021}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/sejourne22a/sejourne22a.pdf}, url = {https://proceedings.mlr.press/v151/sejourne22a.html}, abstract = { Unbalanced optimal transport (UOT) extends optimal transport (OT) to take into account mass variations when comparing distributions. This is crucial for successful ML applications of OT, as it makes it robust to data normalization and outliers. The baseline algorithm is Sinkhorn, but its convergence speed might be significantly slower for UOT than for OT. In this work, we identify the cause for this deficiency, namely the lack of a global normalization of the iterates, which equivalently corresponds to a translation of the dual OT potentials. Our first contribution leverages this idea to develop an accelerated Sinkhorn algorithm (coined "translation invariant Sinkhorn") for UOT, bridging the computational gap with OT. Our second contribution focuses on 1-D UOT and proposes a Frank-Wolfe solver applied to this translation invariant formulation. The linear oracle of each step amounts to solving a 1-D OT problem, resulting in a linear time complexity per iteration. Our last contribution extends this method to the computation of UOT barycenter of 1-D measures. Numerical simulations showcase the convergence speed improvement brought by these three approaches. } }
Endnote
%0 Conference Paper %T Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe %A Thibault Sejourne %A Francois-Xavier Vialard %A Gabriel Peyré %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-sejourne22a %I PMLR %P 4995--5021 %U https://proceedings.mlr.press/v151/sejourne22a.html %V 151 %X Unbalanced optimal transport (UOT) extends optimal transport (OT) to take into account mass variations when comparing distributions. This is crucial for successful ML applications of OT, as it makes it robust to data normalization and outliers. The baseline algorithm is Sinkhorn, but its convergence speed might be significantly slower for UOT than for OT. In this work, we identify the cause for this deficiency, namely the lack of a global normalization of the iterates, which equivalently corresponds to a translation of the dual OT potentials. Our first contribution leverages this idea to develop an accelerated Sinkhorn algorithm (coined "translation invariant Sinkhorn") for UOT, bridging the computational gap with OT. Our second contribution focuses on 1-D UOT and proposes a Frank-Wolfe solver applied to this translation invariant formulation. The linear oracle of each step amounts to solving a 1-D OT problem, resulting in a linear time complexity per iteration. Our last contribution extends this method to the computation of UOT barycenter of 1-D measures. Numerical simulations showcase the convergence speed improvement brought by these three approaches.
APA
Sejourne, T., Vialard, F. & Peyré, G.. (2022). Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:4995-5021 Available from https://proceedings.mlr.press/v151/sejourne22a.html.

Related Material