Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

The goal of decentralized optimization over a network is to optimize a global\nobjective formed by a sum of local (possibly nonsmooth) convex functions using\nonly local computation and communication. It arises in various application\ndomains, including distributed tracking and localization, multi-agent\nco-ordination, estimation in sensor networks, and large-scale optimization in\nmachine learning. We develop and analyze distributed algorithms based on dual\naveraging of subgradients, and we provide sharp bounds on their convergence\nrates as a function of the network size and topology. Our method of analysis\nallows for a clear separation between the convergence of the optimization\nalgorithm itself and the effects of communication constraints arising from the\nnetwork structure. In particular, we show that the number of iterations\nrequired by our algorithm scales inversely in the spectral gap of the network.\nThe sharpness of this prediction is confirmed both by theoretical lower bounds\nand simulations for various networks. Our approach includes both the cases of\ndeterministic optimization and communication, as well as problems with\nstochastic optimization and/or communication.\n