Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

Alex Delalande (1, 2)

1 LMO - Laboratoire de Mathématiques d'Orsay
2 DATASHAPE - Understanding the Shape of Data

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.

Domaines: Analyse numérique [math.NA]; Intelligence artificielle [cs.AI]; Statistiques [math.ST]

Alex Delalande. Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport. AISTATS 2022 - 25th International Conference on Artificial Intelligence and Statistics, Mar 2022, Valencia / Virtual, Spain. pp.1619-1642. ⟨hal-03396206v2⟩