Exponential convergence of Sinkhorn’s algorithm: a coupling approach
Sinkhorn's algorithm is an iterative fitting procedure that allows to quickly compute the unique solution of the Entropic Optimal Transport problem, i.e. the entropic regularization of the Kantorovich-OT problem. Despite its wide use in applications, the study of its convergence rate is still a very active area of research, particularly in the unbounded setting where the exponential convergence of the algorithm is not yet completely understood. In this talk, after a small introduction on the quadratic EOT problem and its equivalence stochastic formulation, namely the Schrödinger problem, we are going to prove that Sinkhorn's algorithm converges exponentially fast for a wide class of (unbounded) marginals. Our approach relies on a stochastic interpretation of Sinkhorn iterations and on (synchronous and reflection) coupling techniques.
Area: CS34 - Advances in stochastic optimal transport and applications (Luca Tamanini)
Keywords: Sinkhorn's algorithm, Schrödinger bridges, Entropic Optimal Transport, couplings
Please Login in order to download this file