Exponential convergence of Sinkhorn’s algorithm: a coupling approach

Greco Giacomo, Eindhoven University of Technology

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