Semi-Dual Unbalanced Quadratic Optimal Transport: fast statistical rates and convergent algorithm.

Adrien Vacher, François-Xavier Vialard
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:34734-34758, 2023.

Abstract

In this paper, we derive a semi-dual formulation for the problem of unbalanced quadratic optimal transport and we study its stability properties, namely we give upper and lower bounds for the Bregman divergence of the new objective that hold globally. We observe that the new objective gains even more convexity than in the balanced case. We use this formulation to prove the first results on statistical estimation of UOT potentials and we leverage the extra convexity to recover super-parametric rates. Interestingly, unlike in the balanced case, we do not require the potentials to be smooth. Then, use variable metric descent to solve the semi-dual problem for which we prove convergence at a $1/k$ rate for strongly convex potentials and exponential convergence in the balanced case when potentials are also smooth. We emphasize that our convergence results has an interest on its own as it generalizes previous convergence results to non-equivalent metrics. Last, we instantiate a proof-of-concept tractable version of our theoretical algorithm that we benchmark on a 2D experiment in the balanced case and on a medium dimension synthetic experiment in the unbalanced case.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-vacher23a, title = {Semi-Dual Unbalanced Quadratic Optimal Transport: fast statistical rates and convergent algorithm.}, author = {Vacher, Adrien and Vialard, Fran\c{c}ois-Xavier}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {34734--34758}, 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/vacher23a/vacher23a.pdf}, url = {https://proceedings.mlr.press/v202/vacher23a.html}, abstract = {In this paper, we derive a semi-dual formulation for the problem of unbalanced quadratic optimal transport and we study its stability properties, namely we give upper and lower bounds for the Bregman divergence of the new objective that hold globally. We observe that the new objective gains even more convexity than in the balanced case. We use this formulation to prove the first results on statistical estimation of UOT potentials and we leverage the extra convexity to recover super-parametric rates. Interestingly, unlike in the balanced case, we do not require the potentials to be smooth. Then, use variable metric descent to solve the semi-dual problem for which we prove convergence at a $1/k$ rate for strongly convex potentials and exponential convergence in the balanced case when potentials are also smooth. We emphasize that our convergence results has an interest on its own as it generalizes previous convergence results to non-equivalent metrics. Last, we instantiate a proof-of-concept tractable version of our theoretical algorithm that we benchmark on a 2D experiment in the balanced case and on a medium dimension synthetic experiment in the unbalanced case.} }
Endnote
%0 Conference Paper %T Semi-Dual Unbalanced Quadratic Optimal Transport: fast statistical rates and convergent algorithm. %A Adrien Vacher %A François-Xavier Vialard %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-vacher23a %I PMLR %P 34734--34758 %U https://proceedings.mlr.press/v202/vacher23a.html %V 202 %X In this paper, we derive a semi-dual formulation for the problem of unbalanced quadratic optimal transport and we study its stability properties, namely we give upper and lower bounds for the Bregman divergence of the new objective that hold globally. We observe that the new objective gains even more convexity than in the balanced case. We use this formulation to prove the first results on statistical estimation of UOT potentials and we leverage the extra convexity to recover super-parametric rates. Interestingly, unlike in the balanced case, we do not require the potentials to be smooth. Then, use variable metric descent to solve the semi-dual problem for which we prove convergence at a $1/k$ rate for strongly convex potentials and exponential convergence in the balanced case when potentials are also smooth. We emphasize that our convergence results has an interest on its own as it generalizes previous convergence results to non-equivalent metrics. Last, we instantiate a proof-of-concept tractable version of our theoretical algorithm that we benchmark on a 2D experiment in the balanced case and on a medium dimension synthetic experiment in the unbalanced case.
APA
Vacher, A. & Vialard, F.. (2023). Semi-Dual Unbalanced Quadratic Optimal Transport: fast statistical rates and convergent algorithm.. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:34734-34758 Available from https://proceedings.mlr.press/v202/vacher23a.html.

Related Material