On optimization aspects of finding Wasserstain(-Kantorovich) barycenter

Aleksey Gasnikov (MITP, Moscow)
Wednesday, June 10, 2015 - 10:00am
WIAS, Raum 4.13, Hausvogteiplatz 11, 10117 Berlin

In the talk we'll discuss recent works by Marco Cuturi (Kyoto Univ.) et al. devoted to the fast algorithm of computation of Wasserstain barycenter (Wb). In our approach we try to reduce a problem to another high dimensional convex optimization problem . The idea is to freeze the measures support by allowing the cardinalities of the support sets to be large enough. Then we have to solve a sadle-point convex-concave optimization problem (Cuturi et al. considered this problem to be nonsmooth convex optimization problem). We propose new different numerical approaches to solve this problem. 1. We generalize the approach by Cuturi and obtain a sharp bound on the rate of convergence. We have to solve a inner linear programming problem or entropy-linear problem. We have to propose optimal primal-dual methods for these problems and we need to choose optimal relation between the precision of solution for the inner problem and the precision of solution of the whole problem. Since we can't obtain the exact solution of the inner problem we have to properly choose the method for external problem which have the ability to work with inexact oracle. Here we used recent results by Dvurechensky-Gasnikov arXiv:1411.2876, Gasnikov-Dvurechensky-Nesterov arXiv:1411.4218 and Gasnikov-Nesterov et al. arXiv:1410.7719 2. We propose randomized (mirror descent) and non-randomized (mirror-prox) approaches for sadle-point problem which go back to the recent works of Nemirovski-Juditsky http://www2.isye.gatech.edu/~nemirovs/. 3. We propose randomized approaches based on the randomization of functional which has the form of a sum of large number of functions (see Agarwal-Bouttou arXiv:1410.0723v2 and references therein). This context is interesting in case when we have to find a Wb of huge number of empirical measures. Literature http://www.iip.ist.i.kyoto-u.ac.jp/member/cuturi/Papers/cuturi14fast.pdf http://www.iip.ist.i.kyoto-u.ac.jp/member/cuturi/Papers/cuturi13sinkhorn...