Timezone: »

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

Wed Jun 12 04:25 PM -- 04:30 PM (PDT) @ Room 103
in Convex Optimization »
We study the complexity of approximating Wassertein barycenter of $m$ discrete measures, or histograms of size $n$ by contrasting two alternative approaches using 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 $\frac{mn^2}{\varepsilon^2}$ to approximate the original non-regularized barycenter. Using an alternative accelerated-gradient-descent-based approach, we obtain a complexity proportional to $\frac{mn^{2}}{\varepsilon} $. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to $\e$, 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.
[ Slides]  [ Video] 

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