Distributed optimization over time-varying directed graphs

By Angelia Nedić, Alexander Olshevsky. 2013

1,133 citations recorded by the source corpus.

We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O (ln t/√t), where the constant depends on the initial values at the nodes, the subgradient norms, and, more interestingly, on both the consensus speed and the imbalances of influence among the nodes.

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

In Graph Learning

In Mathematical Optimization

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “…with decentralized training: notably, high communication cost (Tang et al., 2018a; Wang et al., 2019; Koloskova et al., 2019), a need for time-varying topologies (Nedić & Olshevsky, 2014; Assran et al., 2019) and data-heterogeneity (Li et al., 2018; Karimireddy et al., 2019; Li et al., 2020a;b).”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “…other hand, 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…”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “There are two main types of decentralized learning algorithms: ﬁxed network topology [He et al., 2018], or time-varying [Lian et al., 2018, Nedić and Olshevsky, 2015] during training.”
Distributed Learning over Unreliable Networks (2018, background): “Recently, Nedic et al. (2017); Nedić and Olshevsky (2015) relax the assumption and consider the situation where the communication network is directed, but still, the row sum of the weight matrix is required to be 1.”
Collaborative Deep Learning in Fixed Topology Networks (2017, methodology): “Thus, the following relation can be obtained As ∞ k =1 α 2 k ∞ and λ 2 (Π) 1 then by Lemma 5 in [30], the desired result follows.”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “It is also worth noting that the recent work push-DGD [23] relaxes the symmetry condition, yet such relaxation for EXTRA is not trivial and is our future work.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “To overcome this issue, reference [40] is the ﬁrst to propose a diﬀerent distributed approach, namely a subgradient-push algorithm that combines the distributed subgradient method [47] with the push-sum protocol [27].”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, methodology): “In the proof of Theorem 1, we also use the following result, which is a generalization of Lemma 8 in [26].”
On Nonconvex Decentralized Gradient Descent (2016, background): “Its convergence in the convex setting was developed in [41].”
Decentralized Consensus Optimization With Asynchrony and Delays (2016, background): “Gossip [15], [16] Reduced No Yes Average Consensus Yes Randomized Consensus [17], [18] Reduced No Yes Average Consensus Yes Randomized DGD [19], [26] Reduced No Yes Aggregate Optimization No Asynchronous Diffusion [27]–[29] Reduced No Yes Aggregate stochastic Optimization No Randomized ADMM [20], [2”
Decentralized consensus optimization with asynchrony and delays (2016, background): “Our setting is also different from [23]–[26], in which other sources of asynchronous behavior in networks are allowed, such as different arrival times of data at the agents, random on/off activation of edges and neighbors, random on/off updates by the agents, and random link failures, etc.”
A geometrically convergent method for distributed optimization over time-varying graphs (2016, methodology): “…graphs, and both of them establish sublinear rates for the introduced primal-dual-like algorithms; [17] illustrates a second-order approximation of ADMM thus maintains the communication cost but brings a considerable saving of the computational cost. references [22]–[26] work with directed graphs.”
Robust Distributed Estimation by Networked Agents (2017, background): “Remark 2: Property (42) is less stringent and more general than analogous update vector assumptions appearing in [33]–[38].”
Distributed Gradient Methods for Convex Machine Learning Problems in Networks: Distributed Optimization (2020, methodology): “We note that while the work in [15] and [16] uses the special weight matrix A k (equal-out-neighbor weights), it is straightforward to extend it to the case of an arbitrary sequence These algorithms are not readily rendering accelerated variants that can perform nearly as quickly as the centralized…”