Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization

By Angelia Nedić, Alexander Olshevsky, Michael G. Rabbat. 2017

601 citations recorded by the source corpus.

In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of applications..decentralized estimation in sensor networks, fitting models to massive data sets, and decentralized control of multirobot systems, to name a few..significant advances have been made toward the development of robust, practical algorithms with theoretical performance guarantees. This paper presents an overview of recent work in this area. In general, rates of convergence depend not only on the number of nodes involved and the desired level of accuracy, but also on the structure and nature of the network over which nodes communicate (e.g., whether links are directed or undirected, static or time varying). We survey the state-of-theart algorithms and their analyses tailored to these different scenarios, highlighting the role of the network topology.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, ML Systems & Hardware

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 Optimization & Training

In ML Systems & Hardware

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “, 2006) or time-varying graphs (Nedić & Olshevsky, 2014; Nedić & Olshevsky, 2016), see also (Nedić et al., 2018) for an overview.”
Decentralized gradient methods: does topology matter? (2020, methodology): “…matrix G(k) is bounded in expectation over the vector ⇠ of minibatches randomly drawn at nodes, i.e., there exists E, such that E ⇠ h kG(k)k2F i E. Assumptions A1-A4 are standard ones in the related literature, see for example (Nedić and Ozdaglar, 2009; Duchi et al., 2012; Nedić et al., 2018).”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “For decentralized topology, decentralized gradient descent (DGD) has been investigated in (Nedić et al., 2018).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “For a comprehensive overview we refer to e.g. (Nedić et al., 2018; Koloskova et al., 2019) and the references therein.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “While there has been extensive literature studying the first factor [22, 7, 21], the second factor is less explored from a theoretical point of view.”
Stochastic Gradient Push for Distributed Deep Learning (2018, background): “Numerous decentralized optimization algorithms have been studied in the control-systems literature that leverage consensus-based approaches for the computation of aggregate information; see the survey [11] and references therein.”
D2: Decentralized Training over Decentralized Data (2018, methodology): “For directed networks, the algorithm DIGing is proposed in Nedi´c et al. [2017], where two exchanges are needed in each iteration.”
Accelerating the Convergence Rates of Distributed Subgradient Methods with Adaptive Quantization (2018, background): “We refer interested readers to the recent survey paper [21] for a summary of existing results in this area.”
Distributed Learning in Wireless Networks: Recent Progress and Future Challenges (2021, methodology): “authors in [20], [64], and [65] used decentralized averaging methods to update the local ML model of each device.”
The Role of Network Topology for Distributed Machine Learning (2019, background): “References [14], [5] study the convergence of DSM.”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, unknown): “Under decentralized architectures, the convergence of gradient descent and stochastic gradient descent algorithms has been investigated in [46], [47] and [48], respectively.”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, background): “These rates match those for the standard, unquantized verion of DSG [4].”
Federated Multi-Task Learning under a Mixture of Distributions (2021, background): “We refer to [49] for a comprehensive survey of fully decentralized optimization (also known as consensus-based optimization), and to [31] for a unified theoretical analysis of decentralized SGD.”
Decentralized Federated Learning: A Survey and Perspective (2023, background): “The algorithms of gossip and broadcast have been well established for use in networks [142].”
Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “esign plays a key role in alleviating the communication bottleneck in decentralized scenarios. In addition, the convergence rate of the decentralized algorithm also depends on the topology of network [106]. We should note that the decentralized edge AI system suffers from the same issues as the syst”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, unknown): “Although the sparsity of network graphs yields slow convergence speeds [176], the reductions of convergence speed in D-GADMM compared to the standard PS-based ADMM can be compensated by continuously altering neighbors with D-GADMM.”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, background): “First, a more connected topology leads to faster convergence in terms of iterations or communication rounds, as quantified by classic worst-case convergence bounds in terms of the spectral properties of the topology [75, 24, 89, 90, 103, 40].”