AISTATS 2022poster22 citations
Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport
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.
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. }
}