A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization

Puya Latafat, Nikolaos M. Freris, Panagiotis Patrinos

Published 2017-06-09Version 1

We consider the problem of minimizing the sum of a Lipschitz differentiable function and two nonsmooth proximable functions one of which is composed with a linear mapping. We propose a novel primal-dual algorithm that takes into account a metric for the Lipschitz continuity instead of a scalar. Moreover, we devise a randomized block-coordinate version of our scheme that captures many random coordinate activation scenarios in a unified fashion. The block-coordinate version of the algorithm converges under identical stepsize conditions as the full algorithm. We show that both the full and block-coordinate schemes feature linear convergence rates if the functions involved are either piecewise linear-quadratic, or if they satisfy a quadratic growth condition. We apply the proposed algorithms to the problem of distributed multi-agent optimization, thus yielding synchronous and asynchronous distributed algorithms. The proposed algorithms are fully distributed in the sense that the stepsizes of each agent only depend on local information. In fact, no prior global coordination is required. Finally, we showcase our distributed algorithms for Network Utility Maximization.