Quantitative contraction rates for Sinkhorn algorithm: beyond bounded costs and compact marginals

Giovanni Conforti, Alain Durmus, Giacomo Greco

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademic

98 Downloads (Pure)

Samenvatting

We show non-asymptotic exponential convergence of Sinkhorn iterates to the Schrödinger potentials, solutions of the quadratic Entropic Optimal Transport problem on Rd. Our results hold under mild assumptions on the marginal inputs: in particular, we only assume that they admit an asymptotically positive log-concavity profile, covering as special cases log-concave distributions and bounded smooth perturbations of quadratic potentials. More precisely, we provide exponential L1 and pointwise convergence of the iterates (resp. their gradient and Hessian) to Schrödinger potentials (resp. their gradient and Hessian) for large enough values of the regularization parameter. As a corollary, we establish exponential convergence of Sinkhorn plans with respect to a symmetric relative entropy and in Wasserstein distance of order one. Up to the authors' knowledge, these are the first results which establish exponential convergence of Sinkhorn's algorithm in a general setting without assuming bounded cost functions or compactly supported marginals.
Originele taal-2Engels
Artikelnummer2304.04451
Aantal pagina's51
TijdschriftarXiv
Volume2023
DOI's
StatusGepubliceerd - 10 apr. 2023

Vingerafdruk

Duik in de onderzoeksthema's van 'Quantitative contraction rates for Sinkhorn algorithm: beyond bounded costs and compact marginals'. Samen vormen ze een unieke vingerafdruk.

Citeer dit