Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport
This work provides theoretical foundations for annealing or ε-scaling heuristics in numerical optimal transport, which is incremental but important for computational applications in fields like machine learning and statistics.
The paper tackles the problem of quantifying convergence and stability for entropic semi-discrete optimal transport, deriving nearly tight and non-asymptotic bounds for dual solutions and cost differences, with improved dependence on the regularization parameter.
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 $\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.