Timezone: »

 
Poster
Distributed Dual Averaging In Networks
John Duchi · Alekh Agarwal · Martin J Wainwright

Wed Dec 08 12:00 AM -- 12:00 AM (PST) @
in Poster Session »

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. We develop and analyze distributed algorithms based on dual averaging of subgradients, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our analysis clearly separates the convergence of the optimization algorithm itself from the effects of communication constraints arising from the network structure. We show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network. The sharpness of this prediction is confirmed both by theoretical lower bounds and simulations for various networks.

[ PDF] 

Author Information

John Duchi (Stanford)
Alekh Agarwal (Google Research)
Martin J Wainwright (UC Berkeley)

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

More from the Same Authors