Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach

Giacomo Greco, Maxence Noble, Giovanni Conforti, Alain Oliviero-Durmus

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

Computational optimal transport (OT) has recently emerged as a powerful framework with applications in various fields. In this paper we focus on a relaxation of the original OT problem, the entropic OT problem, which allows to implement efficient and practical algorithmic solutions, even in high dimensional settings. This formulation, also known as the Schrödinger Bridge problem, notably connects with Stochastic Optimal Control (SOC) and can be solved with the popular Sinkhorn algorithm. In the case of discrete-state spaces, this algorithm is known to have exponential convergence; however, achieving a similar rate of convergence in a more general setting is still an active area of research. In this work, we analyze the convergence of the Sinkhorn algorithm for probability measures defined on the d-dimensional torus TdL, that admit densities with respect to the Haar measure of TdL. In particular, we prove pointwise exponential convergence of Sinkhorn iterates and their gradient. Our proof relies on the connection between these iterates and the evolution along the Hamilton-Jacobi-Bellman equations of value functions obtained from SOC -problems. Our approach is novel in that it is purely probabilistic and relies on coupling by reflection techniques for controlled diffusions on the torus.

Originele taal-2Engels
Titel6th Annual Conference on Learning Theory, COLT 2023
UitgeverijPMLR
Pagina's716-746
Aantal pagina's31
StatusGepubliceerd - 2023
Evenement36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India
Duur: 12 jul. 202315 jul. 2023

Publicatie series

NaamProceedings of Machine Learning Research (PMLR)
Volume195

Congres

Congres36th Annual Conference on Learning Theory, COLT 2023
Land/RegioIndia
StadBangalore
Periode12/07/2315/07/23

Bibliografische nota

Publisher Copyright:
© 2023 G. Greco, M. Noble, G. Conforti & A. Oliviero–Durmus.

Financiering

GG thanks École Polytechnique for its hospitality, where this research has been carried out, and NDNS+ for funding his visit there (NDNS/2023.004 PhD Travel Grant). GG is supported from the NWO Research Project 613.009.111 ”Analysis meets Stochastics: Scaling limits in complex systems”. GC acknowledges funding from the grant SPOT (ANR-20-CE40-0014). AD acknowledges support from the Lagrange Mathematics and Computing Research Center. AD would like to thank the Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programm The mathematical and statistical foundation of future data-driven engineering when work on this paper was undertaken. This work was supported by: EPSRC grant number EP/R014604/1.

FinanciersFinanciernummer
SPOTANR-20-CE40-0014
Engineering and Physical Sciences Research CouncilEP/R014604/1
Nederlandse Organisatie voor Wetenschappelijk Onderzoek613.009.111

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit