Dr. P. Dvurechensky (WIAS Berlin)
Tuesday, February 20, 2018 - 15:00
Weierstraß-Institut
Mohrenstr. 39, 10117 Berlin, Weierstraß-Hörsaal (Raum: 406), 4. Etage
Seminar Modern Methods in Applied Stochastics and Nonparametric Statistics
We propose an alternative to ubiquitous Sinkhorn algorithm for solving regularized optimal transport problem. Our approach is based on accelerated gradient descent applied to the dual problem and allows to solve not only entropy-regularized optimal transport problem, but also squared-2-norm-regularized OT problem, which produces sparser optimal transport plan approximation. We prove that, our algorithm, allows to solve non-regularized optimal transport problem with support size $p$ up to accuracy $epsilon$ in $Oleft(minleftfracp^9/4epsilon, fracp^2epsilon^2 rightright)$ arithmetic operations, which is better than state-of-the-art result $Oleft(fracp^2epsilon^3right)$.
submitted by chschnei (christine.schneider@wias-berlin.de, 030 20372574)