Distributed Subgradient Methods for Multi-Agent Optimization

By Angelia Nedić, Asuman E. Ozdaglar. 2009

3,947 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, 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 Computational Mechanics

In Computer Networks and Communications

In Optimization & Training

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…optimization problems, the most common algorithms are either combinations of standard gradient based methods with gossip-type averaging step (Nedi´c & Ozdaglar, 2009; Johansson et al., 2010), or speciﬁcally designed methods relying on problem structure, such as alternating direction method…”
Robust Aggregation for Federated Learning (2019, methodology): “[52] A.”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “…there are a variety of distributed optimization algorithms proposed in the literature, such as primal methods (Jakoveti´c et al., 2014; Nedi´c and Olshevsky, 2014; Nedi´c and Ozdaglar, 2009; Shi et al., 2015) and primal-dual methods (Chang et al., 2014a; Koppel et al., 2017; Bedi et al., 2019).”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “The most popular ﬁrst-order choices for the convex setting are distributed gradient descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of…”
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 proposed schemes in (Carli et al., 2007; Nedi´c et al., 2008; Aysal et al., 2008; Carli et al., 2010b; Yuan et al., 2012) do only converge to a neighborhood (whose size depends on the compression accuracy) of the solution.”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, background): “3See the non-ergodic convergent rate in Proposition 3(b) in Nedic and Ozdaglar [2009].”
COLA: Decentralized Linear Learning (2018, neutral): “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…”
DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, methodology): “They use techniques ranging from distributed (sub)gradient descent [4], [5] to more elaborate techniques such as EXTRA [6], distributed ADMM [7], [8], dual averaging [9], and distributed augmented Lagrangean [10].”
D2: Decentralized Training over Decentralized Data (2018, methodology): “The D-PSGD algorithm [Nedic and Ozdaglar, 2009, Ram et al., 2010a,b] requires each worker to compute a stochastic gradient and exchange its local model with neighbors.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, neutral): “The subgradient version was considered in Nedic and Ozdaglar [2009], Ram et al. [2009].”
Personalized and Private Peer-to-Peer Machine Learning (2017, background): “Most of the work in fully decentralized learning and optimization has focused on the distributed consensus problem, where the goal is to find a single global model which minimizes the sum of the local loss functions (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “The most popular algorithms are based on (sub)gradient descent (Johansson et al., 2010; Nedi´c & Ozdaglar, 2009; Ram et al., 2010; Bianchi & Jakubow-icz, 2013), ADMM (Wei & Ozdaglar, 2012; 2013; Iutzeler et al., 2013) or dual averaging (Duchi et al., 2012; Yuan et al., 2012; Lee et al., 2015;…”
Differentially Private Distributed Optimization (2014, background): “Categories and Subject Descriptors D.1.3 [Software]: Concurrent Programming—Distributed programming General Terms Algorithm Keywords Distributed Optimization, Differential Privacy, Iterative Consensus”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “There have been extensive studies on distributed optimization with inaccurate or delayed subgradient information, but mostly without the smoothness assumption (e.g., Nedi´c et al., 2001; Nedi´c and Ozdaglar, 2009).”
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].”