On the linear convergence of the multi-marginal Sinkhorn algorithm

Guillaume Carlier (1, 2)

1 CEREMADE - CEntre de REcherches en MAthématiques de la DEcision
2 MOKAPLAN - Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales

The aim of this short note is to give an elementary proof of linear convergence of the Sinkhorn algorithm for the entropic regularization of multi-marginal optimal transport. The proof simply relies on: i) the fact that Sinkhorn iterates are bounded, ii) strong convexity of the exponential on bounded intervals and iii) the convergence analysis of the coordinate descent (Gauss-Seidel) method of Beck and Tetruashvili [1].

Mots clés: Multi-marginal entropic optimal transport; Sinkhorn algorithm; Linear convergence; Block coordinate descent

Domaines: Optimisation et contrôle [math.OC]

Guillaume Carlier. On the linear convergence of the multi-marginal Sinkhorn algorithm. SIAM Journal on Optimization, 2022, 32 (2), pp.786-794. ⟨hal-03176512⟩