Distributed Subgradient Methods for Convex Optimization Over Random Networks

By Ilan Lobel, Asuman E. Ozdaglar. 2011

363 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

Citations in the corpus

Distributed Learning over Unreliable Networks (2018, background): “However, most of the previous work (Li and Zhang, 2010; Lobel and Ozdaglar, 2011) made the assumption that the randomized network should be doubly-stochastic.”
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination (2012, background): “Further results on this topic can be found in [111]–[113], where a similar distributed multi-agent optimization problem was studied within various scenarios, under constraints [111], over random networks [112], and with broadcast-based communications in an asynchronous setting [113].”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “ng agents to propagate the distributed information to every location in the network. One of the most well-studied techniques in decentralized optimization are the subgradient based methods (see e.g., [39,35,57,37,14,27,52]), where at each step a local subgradient is taken at each node, followed by t”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, methodology): “) where Ak is a stochastic (or double stochastic), and random with A = E[A‘]. Assuming that the graph G A is undirected and connected, the above decentralized subgradient method has been studied in [83]. A related version of the distributed dual averaging algorithm is studied in the setting of iid u”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “, [11]–[16] and references therein).”
Distributed optimization over time-varying directed graphs (2013, background): “Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, methodology): “Our work here contributes to the growing literature on distributed methods for optimization over networks [5], [9], [12], [14]–[16], [19]–[23], [28], [32], [34], [40], [43].”
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms (2018, methodology): “…approaches to decentralizing an optimization problem primarily consist of subgradient-based algorithms (Nedic et al., 2008; Nedic & Ozdaglar, 2009; Lobel & Ozdaglar, 2011), ADMM-based algorithms (Wei & Ozdaglar, 2012; Ling & Ribeiro, 2014; Shi et al., 2014; Zhang & Kwok, 2014; Ling et al., 2016),…”
Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization (2015, background): “, see [27] and [28] for distributed optimization on directed graphs, and [29] for computation over random networks.”
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].”
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 Rates for Distributed Stochastic Optimization Over Random Networks (2018, background): “Distributed optimization over random networks has been studied in [4]–[6], [18].”
Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms (2016, background): “Although the basic evolution relation has been obtained for failure-free distributed algorithms [9, 19, 31, 15], since our eﬀective objective function is time-dependent ( p ( · ) in (11)), their analysis does not apply directly to our problem.”
Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, background): “Early work on time-varying communication among the agents can be found in [38], [39], where the exchange is undirected and in [40], where the exchange is directed.”
A survey of distributed optimization (2019, methodology): “In summary, the existing distributed algorithms for random graphs either use the gradient information (see, e.g., Jakoveti ´c et al., 2014a; Lobel & Ozdaglar, 2011; Wu, Yang, Wu et al., 2017 ) and diminishing step-sizes or ﬁxed step-sizes and the Hessian information (see, e.g., Carli et al., 2015;…”
Designing games for distributed optimization (2011, background): “There are similarities between our contributions and the algorithmic structure of existing distributed algorithms [25], [28] where an underlying state space is introduced to estimate parameters relevant to the gradients.”
A Second-Order Multi-Agent Network for Bound-Constrained Distributed Optimization (2015, background): “For distributed optimization, most of the works build on consensus algorithms which are described by discrete-time dynamics to search for optimal solutions [21], [25].”