Problems in decentralized decision making and computation

By John N. Tsitsiklis. 1984

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “The study of decentralized optimization algorithms can be tracked back at least to (Tsitsiklis, 1984).”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “The study of decentralized optimization algorithms can be tracked back at least to the 1980s (Tsitsiklis, 1984).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, neutral): “In contrast, gossip algorithms (Tsitsiklis, 1984; Boyd et al., 2006; Kempe et al., 2003; Shah, 2009) are tailored to this setting because they only rely on simple peer-to-peer communication: each agent only exchanges information with one neighbor at a time.”
Distributed delayed stochastic optimization (2011, methodology): “Certainly distributed optimization has been studied for several decades, tracing back at least to seminal work of Tsitsiklis and colleagues ([Tsi84, BT89]) on minimization of smooth functions where the parameter vector is distributed.”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling (2010, neutral): “We first note tha t the classical problem of consensus averaging [6], [12], [25 ] is a special case of the problem (1) when fi(x) = ‖x − θi‖(2)2.”
On the Convergence of Decentralized Gradient Descent (2013, background): “The study on decentralized optimization can be traced back to the seminal work in the 1980s [30, 31].”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “The role of W is the similar as that in DGD [5, 31, 36] and average consensus [33].”
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization (2008, background): “An important extension is to consider the properties of the algorithm in asynchronous networks with communication delays, as in [20].”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “hui Lan et al. 1.3 Literature review Decentralized optimization has been extensively studied in recent years due to the emergence of large-scale networks. The seminal work on distributed optimization [60,59] has been followed by distributed incremental (sub)gradient methods and proximal methods [36,”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “Worst-case scaling of decentralized averaging One might wonder about the worst-case complexity of average consensus: how long does it take to get close to the average on any graph? Initial bounds were exponential in the number of nodes [5], [6], [23], [37].”
Fast Distributed Gradient Methods (2011, background): “2 (48)a t) 2 22 i i 2j i p i(1 i) : Next, very interestingly: kD i H(t)D i(t)k 1 = D i H(t)D i(t) 11 + D i H(t)D i(t) 12 = 1 4 (a 2 t +(2 a t)2) i+ 1 2 a t(2 a t) i;= i: for any a t 2 [0;2], which is the case here because a t = 3=(t+ 3), t = 0;1;:::, and a 1 = 0: Thus, as kAk kAk 1 for a Herm”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “First, many of these algorithms are based on first-order subgradient methods [1], [12], [9], which for general convex problems have slow convergence rates (given by O(1/ √ k) where k is the iteration number),1 making them impractical in many large scale applications.”
Distributed subgradient methods and quantization effects (2008, methodology): “Our proposed method builds on the work in [24], [25] (see also, [3]).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Optimization in distributed setting has been studied for decades, tracing back to at least works of Bertsekas and Tsitsiklis [14, 13, 177].”
An Exact Quantized Decentralized Gradient Descent Algorithm (2018, background): “2932876 Distributed optimization has been largely studied in the literature starting from seminal works in the 80s [8], [9].”
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks (2018, methodology): “1) DGD-Based Algorithms for Network Consensus: Network consensus optimization can trace its roots to the seminal work by Tsitsiklis [15], where the system model and the analysis framework were first developed.”
Nested Distributed Gradient Methods with Adaptive Quantized Communication (2019, methodology): “Our work is closely related to a few lines of research that we delineate below: 1) distributed first-order primal algorithms [9]–[11], [29]–[32]: methods that use only gradient information, 2) nested [11], [33]–[35]: methods that decompose the communication and computation steps, 3) communication ef”