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 annealing or $\epsilon$-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.

References in corpus (7)

• Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
• Unsupervised Hyperalignment for Multilingual Word Embeddings
• Learning Probability Measures with respect to Optimal Transport Metrics
• Asymptotics for semi-discrete entropic optimal transport
• On the difference between entropic cost and the optimal transport cost
• Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures
• Log-PCA versus Geodesic PCA of histograms in the Wasserstein space