Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

By John C. Duchi, Alekh Agarwal, Martin J. Wainwright. 2010

1,313 citations recorded by the source corpus.

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. It arises in various application domains, including distributed tracking and localization, multi-agent coordination, estimation in sensor networks, and large-scale machine learning. We develop and analyze distributed algorithms based on dual subgradient averaging, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our analysis allows us to clearly separate the convergence of the optimization algorithm itself and the effects of communication dependent on the network structure. We show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network, and confirm this prediction's sharpness both by theoretical lower bounds and simulations for various networks. Our approach includes the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “, 2013), dual averaging (Duchi et al., 2012; Nedić et al., 2015; Rabbat, 2015), primal-dual methods (Alghunaim & Sayed, 2019), or block-coordinate methods for generalized linear models (He et al.”
Decentralized gradient methods: does topology matter? (2020, positive): “Existing theoretical works like (Nedi´c and Ozdaglar, 2009; Duchi et al., 2012; Nedi´c et al., 2018) derived bounds similar to (9) and concluded then that one should select the learning rate proportional to 1 − | λ 2 | to reduce the eﬀect of topology.”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “This assumption is diﬀerent from the one in classical decentralized distributed optimization, which typically assumes W is symmetric and doubly stochastic (e.g., Duchi et al. 2011) (i.e., the summations of both rows and columns are all 1).”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “• DualAvg (Duchi et al., 2011) Dual averaging.”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “…direction method of multipliers (ADMM) (Schizas et al., 2008; Boyd et al., 2011; Shi et al., 2014; Chang et al., 2015; Mokhtari et al., 2016), dual averaging (Duchi et al., 2012; Tsianos et al., 2012), and several dual based strategies (Seaman et al., 2017; Scaman et al., 2018; Uribe et al., 2018).”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “The most popular algorithms are based on (sub)gradient descent (Nedi´c & Ozdaglar, 2009; Johansson et al., 2010), alternating direction method of multipliers (ADMM) (Wei & Ozdaglar, 2012; Iutzeler et al., 2013) or dual averaging (Duchi et al., 2012; Nedi´c et al., 2015).”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “In this work, we focus on fully decentralized learning, which has recently attracted a lot of interest (Duchi et al., 2012; Wei and Ozdaglar, 2012; Colin et al., 2016; Lian et al., 2017; Jiang et al., 2017; Tang et al., 2018; Lian et al., 2018).”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “Decentralized averaging has a long history in the distributed and consensus optimization community (Tsitsik-lis et al., 1986; Nedic & Ozdaglar, 2009; Duchi et al., 2012; Tsianos et al., 2012; Zeng & Yin, 2016; Yuan et al., 2016; Sirb & Ye, 2018).”
COLA: Decentralized Linear Learning (2018, methodology): “In contrast, a second more recent line of work [Nedic and Ozdaglar, 2009, Duchi et al., 2012, Shi et al., 2015, Mokhtari and Ribeiro, 2016, Nedic et al., 2017, Scaman et al., 2017, 2018] considers minimization of a sum of individual local cost-functions F ( x ) = i F i ( x ) , which are potentially…”
D2: Decentralized Training over Decentralized Data (2018, methodology): “In Duchi et al. [2012], a dual averaging based method is proposed for solving the constrained decentralized SGD optimization.”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “Unlike existing work focusing on problems where agents seek to agree on a global consensus model (see e.g., Nedic and Ozdaglar, 2009; Wei and Ozdaglar, 2012; Duchi et al., 2012), we study the case where each agent learns a personalized model according to its own learning objective.”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, positive): “In the asynchronous setting, no convergence rate was known even for the distributed dual averaging al-gorithm of Duchi et al. (2012), which deals with the simpler problem of minimizing univariate functions.”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “A similar dependence occurs with other recently-proposed algorithms for distributed optimization (e.g. Yang, 2013; Mahajan et al., 2013; Dekel et al., 2012; Cotter et al., 2011; Duchi et al., 2012).”
Distributed delayed stochastic optimization (2011, methodology): “Locally Averaged Delayed Architecture At a high level, the protocol we now describe combines the delayed updates of the cyclic delayed architecture with averaging techniques of previous work [13, 7].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “As datasets continue to increase in size, and parallel computing platforms becoming more and more common (from multiple cores on a single CPU to large-scale and geographically distributed computing grids), distributed learning and optimization methods have been the focus of much research in recent y”
On the Convergence of Decentralized Gradient Descent (2013, methodology): “Convergence to x∗ can be achieved by using diminishing stepsizes in [8, 11, 29] at the price of slower rates of convergence.”