Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

Alex Delalande
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:1619-1642, 2022.

Abstract

We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. These bounds quantify the stability of the dual solutions of the regularized problem (sometimes called Sinkhorn potentials) w.r.t. the regularization parameter, for which we ensure a better than Lipschitz dependence. Such facts may be a first step towards a mathematical justification of $\varepsilon$-scaling heuristics for the numerical resolution of regularized semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-delalande22a, title = { Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport }, author = {Delalande, Alex}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {1619--1642}, 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/delalande22a/delalande22a.pdf}, url = {https://proceedings.mlr.press/v151/delalande22a.html}, abstract = { We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. These bounds quantify the stability of the dual solutions of the regularized problem (sometimes called Sinkhorn potentials) w.r.t. the regularization parameter, for which we ensure a better than Lipschitz dependence. Such facts may be a first step towards a mathematical justification of $\varepsilon$-scaling heuristics for the numerical resolution of regularized semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs. } }
Endnote
%0 Conference Paper %T Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport %A Alex Delalande %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-delalande22a %I PMLR %P 1619--1642 %U https://proceedings.mlr.press/v151/delalande22a.html %V 151 %X We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. These bounds quantify the stability of the dual solutions of the regularized problem (sometimes called Sinkhorn potentials) w.r.t. the regularization parameter, for which we ensure a better than Lipschitz dependence. Such facts may be a first step towards a mathematical justification of $\varepsilon$-scaling heuristics for the numerical resolution of regularized semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.
APA
Delalande, A.. (2022). Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:1619-1642 Available from https://proceedings.mlr.press/v151/delalande22a.html.

Related Material