Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
We study the decentralized distributed computation of discrete approximations for the regularized Wasserstein barycenter of a finite set of continuous probability measures distributedly stored over a network. We assume there is a network of agents/machines/computers, and each agent holds a private continuous probability measure and seeks to compute the barycenter of all the measures in the network by getting samples from its local measure and exchanging information with its neighbors. Motivated by this problem, we develop, and analyze, a novel accelerated primal-dual stochastic gradient method for general stochastic convex optimization problems with linear equality constraints. Then, we apply this method to the decentralized distributed optimization setting to obtain a new algorithm for the distributed semi-discrete regularized Wasserstein barycenter problem. Moreover, we show explicit non-asymptotic complexity for the proposed algorithm. Finally, we show the effectiveness of our method on the distributed computation of the regularized Wasserstein barycenter of univariate Gaussian and von Mises distributions, as well as some applications to image aggregation.
This paper presents a distributed algorithm for computing Wasserstein barycenters.  The basic setup is that each agent in the decentralized system has access to one probability distribution; similar to “gossip” based optimization techniques in the classical case (e.g. popularized via ADMM-style techniques) here the distributed algorithm exchanges samples from local measures along edges of a graph.  It seems this paper missed the closest related work, “Stochastic Wasserstein Barycenters” (Claici et al., ArXiv/ICML), which proposes a nonconvex semidiscrete barycenter optimization algorithm.  Certainly any final version of this paper needs to compare to that work carefully.  It may also be worth noting that the Wasserstein propagation algorithm in “Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains” (2015) could be implemented easily on a network in a similar fashion to what is proposed in this paper; see their Algorithm 4.  Like lots of previous work in OT, this technique uses entropic regularization to make transport tractable; they solve the smoothed dual.  The basic model for translating this problem to a network problem is similar to that in many other distributed optimization algorithm; you duplicate the unknown barycenter variable per vertex and add equality conditions along the edges.  In general, I found the idea in this paper to be compelling, and I appreciate the careful theoretical and experimental analysis.  I’m not sure the paper actually makes a strong case for network-based optimization (I’m guessing the experiments here were largely on a single machine than some huge network of computers), and I’d love to see truly large-scale experiments that better justify ML applications----but this can be a great topic for future work.   Other:  L40:  No need to capitalize “entropic”  L46, “privacy constraints:”  Is it clear the technique in this paper has any privacy-preserving properties?   L150:  [this comment is likely a mistake on my part but I’ll ask it anyway!]  I’m not sure I follow why sqrt(W)*p=0 implies that all the p’s are equal.  For example, consider the line graph with vertex labels 0-1-2-3-4-5-6.  Notice the label of every vertex on the graph is the average of the labels of its neighbors, but the signal is not a constant.  Why does that not happen for this paper?  To fix the issue on the previous line, I would think a simpler way to write the constraint is Dp=0, where D is the E x V incidence matrix that takes  one value per vertex and subtracts along edges; one way to obtain the graph Laplacian is by writing D^T * D = L.  I believe the rest of the algorithm would work out identically.  It seems a large part of sec 3.1-3.2 is a standard application of proximal methods (problem (P) is a standard one of course); perhaps it could be shortened if the authors need to expand their discussion elsewhere.  In particular, two different algorithms are given which are both at a level of generality greater than what is needed later in the paper.  Currently this section and sec 4 are quite dense and hard to follow relative to the other discussion.  Given that the optimization problem is entropically regularized, why in sec 3.2 is it chosen to use quadratic terms for the proximal algorithm?  I would have guessed entropy/KL would be a better fit here.  Figure 1 is a great idea!  It answer’s my main question, which is dependence of convergence on topology of the graph.  What caught me by surprise is that convergence for the star graph is so slow --- I would have expected faster “mixing time” (I know, not in the MCMC sense!) since all the distributions are two links away in the topology.  Is there intuition for why this doesn’t happen?  [took a look at the rebuttal and it's all reasonable to me --- this is a nice paper!]