Timezone: »

 
Poster
On the Complexity of Approximating Wasserstein Barycenters
Alexey Kroshnin · Nazarii Tupitsa · Darina Dvinskikh · Pavel Dvurechenskii · Alexander Gasnikov · Cesar Uribe

Wed Jun 12 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #203
in Posters Wed »
We study the complexity of approximating the Wasserstein barycenter of $m$ discrete measures, or histograms of size $n$, by contrasting two alternative approaches that use entropic regularization. The first approach is based on the Iterative Bregman Projections (IBP) algorithm for which our novel analysis gives a complexity bound proportional to ${mn^2}/{\varepsilon^2}$ to approximate the original non-regularized barycenter. On the other hand, using an approach based on accelerated gradient descent, we obtain a complexity proportional to~${mn^{2}}/{\varepsilon}$. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to $\varepsilon$, which causes instability of both algorithms when the desired accuracy is high. To overcome this issue, we propose a novel proximal-IBP algorithm, which can be seen as a proximal gradient method, which uses IBP on each iteration to make a proximal step. We also consider the question of scalability of these algorithms using approaches from distributed optimization and show that the first algorithm can be implemented in a centralized distributed setting (master/slave), while the second one is amenable to a more general decentralized distributed setting with an arbitrary network topology.
Keywords: Convex Optimization · Large Scale Learning and Big Data · Optimization - Others · Parallel and Distributed Learning

Author Information

Alexey Kroshnin (Institute for Information Transmission Problems)
Nazarii Tupitsa (Institute for Information Transmission Problems)
Darina Dvinskikh (Weierstrass Institute for Applied Analysis and Stochastics)
Pavel Dvurechenskii (Weierstrass Institute)

Graduated with honors from Moscow Institute of Physics and Technology. PhD on differential games in the same university. At the moment research associate in the area of optimization under inexact information in Berlin. Research interest include - algorithms for convex and non-convex large-scale optimization problems; - optimization under deterministic and stochastic inexact information; - randomized algorithms: random coordinate descent, random (derivative-free) directional search; - numerical aspects of Optimal Transport - Algorithms for saddle-point problems and variational inequalities

Alexander Gasnikov (Moscow Institute of Physics and Technology)
Cesar Uribe (MIT)

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

More from the Same Authors