Timezone: »

Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity
Vladimir Kostic · Saverio Salzo · Massimiliano Pontil

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #636

In this work we propose a batch multimarginal version of the Greenkhornalgorithm for the entropic-regularized optimal transport problem. This framework is general enough to cover, as particular cases, existing Sinkhorn and Greenkhorn algorithms for the bi-marginal setting, and greedy MultiSinkhorn for the general multimarginal case. We provide a comprehensive convergence analysis based on the properties of the iterative Bregman projections method with greedy control.Linear rate of convergence as well as explicit bounds on the iteration complexity are obtained. When specialized to the above mentioned algorithms, our results give new convergence rates or provide key improvements over the state-of-the-art rates. We present numerical experiments showing that the flexibility of the batch can be exploited to improve performance of Sinkhorn algorithm both in bi-marginal and multimarginal settings.

Author Information

Vladimir Kostic (Istituto Italiano di Tecnologia)
Saverio Salzo (Istituto Italiano di Tecnologia)
Massimiliano Pontil ( Istituto Italiano di Tecnologia & University College London)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors