A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems

By Björn Johansson, Maben Rabi, Mikael Johansson. 2009

383 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training, Mathematical Optimization

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 Numerical Analysis

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Privacy Amplification by Decentralization (2020, methodology): “Indeed, there exists a significant literature on decentralized algorithms for optimizing sums of local functions based on (deterministic or random) walks [30, 22, 27, 1].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “For general optimization problems, the most common algorithms are either combinations of standard gradient based methods with gossip-type averaging step (Nedić & Ozdaglar, 2009; Johansson et al., 2010), or specifically designed methods relying on problem structure, such as alternating direction meth”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “The most popular algorithms are based on (sub)gradient descent (Nedić & Ozdaglar, 2009; Johansson et al., 2010), alternating direction method of multipliers (ADMM) (Wei & Ozdaglar, 2012; Iutzeler et al.”
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ć & Ozdaglar, 2009; Ram et al., 2010; Bianchi & Jakubowicz, 2013), ADMM (Wei & Ozdaglar, 2012; 2013; Iutzeler et al.”
Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms (2015, background): “have been proposed [5, 11, 12, 21, 22, 23]; only a fraction of these algorithms have been analyzed in the asynchronous case.”
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “Since the early works [52, 53] to the more recent work [22, 34, 33, 23, 29, 30, 10, 18, 47, 31], problems in decentralised multi-agent optimisation have often been treated as a particular instance of consensus optimisation.”
Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization (2011, methodology): “The so-called incremental approach is used by [18], [24], [27], [28], [31]: a message containing an estimate of the desired minimizer iteratively travels all over the network.”
Private Weighted Random Walk Stochastic Gradient Descent (2020, background): “Early works on random walk for decentralized stochastic gradient descent (SGD) [4], [5] established the convergence rate for convex problems, assuming a reversible random walk with homogeneous transition matrix.”
Communication-efficient algorithms for statistical optimization (2012, positive): “Although we cannot survey the literature adequately—the papers Nedić and Ozdaglar (2009); Ram et al. (2010); Johansson et al. (2009); Duchi et al. (2012a); Dekel et al. (2012); Agarwal and Duchi (2011); Recht et al. (2011); Duchi et al. (2012b) and references therein contain a sample of relevant…”
Push-Sum Distributed Dual Averaging for convex optimization (2012, background): “Recently there has been a significant amount of research on developing consensus based algorithms for distributed optimization motivated by applications ranging from large scale machine learning to wireless sensor networks [1], [3], [4].”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, methodology): “Several classic algorithms have been ported and analyzed in the gossip setting, such as subgradient methods for convex objectives [37, 29, 44] or ADMM [50, 28].”
Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control (2014, positive): “The first rigorous analysis of this problem was given in [58] and the problem has received considerable attention in recent years due its repeated appearance throughout distributed computing and multi-agent control; we mention [58, 59, 52, 70, 72, 42, 41, 79, 81, 80, 84, 34, 35, 8, 51, 37, 76, 17], ”
Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication (2014, neutral): “Literature review : In distributed convex optimiza-(cid:63) tion, most coordination algorithms are time-varying, consensus-based dynamics [Boyd et al., 2010, Duchi et al., 2012, Johansson et al., 2009, Nedi´c and Ozdaglar, 2009, Zhu and Mart´ınez, 2012] implemented in discrete time.”
Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization (2012, background): “Among many proposed distributed approaches for solving (1), we focus on consensus-based distributed optimization [4], [5], [6], [7] where each component function in (1) is assigned to a different node in a network (i.e., the data is partitioned among the nodes), and the nodes interleave local…”
Distributed Algorithms for Aggregative Games on Graphs (2016, background): “This idea has attracted a lot of attention recently in an eﬀort to extend the algorithm of [57] to more general and broader range of problems [35, 46, 45, 19, 18, 36, 54, 33, 26, 58, 48, 59, 5].”