On the linear convergence of the multi-marginal Sinkhorn algorithm

Carlier, Guillaume

Carlier, Guillaume (2022), On the linear convergence of the multi-marginal Sinkhorn algorithm, SIAM Journal on Optimization, 32, 2. 10.1137/21M1410634

View/Open

linear-sinkhorn.pdf (199.9Kb)

Type

Article accepté pour publication ou publié

Date

2022

Journal name

SIAM Journal on Optimization

Volume

Number

Publisher

SIAM - Society for Industrial and Applied Mathematics

Publication identifier

10.1137/21M1410634

Metadata

Show full item record

Author(s)

Carlier, Guillaume
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]

Abstract (EN)

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].

Subjects / Keywords

Block coordinate descent; Linear convergence; Sinkhorn algorithm; Multi-marginal entropic optimal transport