Timezone: »

 
Poster
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 Poster Session 1 »

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.

Keywords: Optimization · OPT: Convex · OPT: Large Scale, Parallel and Distributed · T: Miscellaneous Aspects of Machine Learning · T: Optimization · MISC: Scalable Algorithms
[ Slides]  [ Poster]  [ Paper PDF] 

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