Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

By Angelia Nedić, Alexander Olshevsky. 2014

355 citations recorded by the source corpus.

We investigate the convergence rate of the recently proposed subgradient-push method for distributed optimization over time-varying directed graphs. The subgradient-push method can be implemented in a distributed way without requiring knowledge of either the number of agents or the graph sequence; each node is only required to know its out-degree at each time. Our main result is a convergence rate of O((ln t)/t) for strongly convex functions with Lipschitz gradients even if only stochastic gradient samples are available; this is asymptotically faster than the O((ln t)/√t) rate previously known for (general) convex functions.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Graph Learning, Optimization & Training

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 Computer Networks and Communications

In Graph Learning

In Optimization & Training

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “…is a rich literature in the control community that discusses various special cases—motivated by particular applications—such as for instance asynchronity (Boyd et al., 2006) or time-varying graphs (Nedi´c & Olshevsky, 2014; Nedi´c & Olshevsky, 2016), see also (Nedi´c et al., 2018) for an overview.”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “The proofs of following two lemmas can be found in existing literature (Nedi´c and Olshevsky, 2014, 2016; Assran and Rabbat, 2018; Assran et al., 2018).”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, methodology): “SLOWMO runs on top of a base algorithm, which could be local SGD or a decentralized method such as stochastic gradient push (SGP) (Nedić & Olshevsky, 2016; Assran et al., 2019).”
Stochastic Gradient Push for Distributed Deep Learning (2018, background): “SGP was first proposed and analyzed in [10] assuming the local objectives fi(x) are strongly convex.”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “A better rate of O ln is proved for the (sub)gradient-push method in [24] under the strong convexity and Lipschitz gradient assumptions, in terms of expected objective error plus squared consensus residual.”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “Also, we note that R ( k ) is actually a row stochastic matrix, i.e., every row of R ( k ) sums to 1 (see Lemma 4 of [41]). e Inwhat follows, we will use following notation for any k = 0 , 1 , . . . and b = 0 , 1 , . . . with the convention that C b ( k ) = I for any needed k < 0 and C 0 ( k ) = I…”
Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging (2014, methodology): “Initial work in this direction suggests that similar improvements are possible in the distributed multiagent setting using primal and dual methods similar to the one described in this paper [18], [26].”
Distributed Online Convex Optimization on Time-Varying Directed Graphs (2017, background): “We also recall the following result from [26], without stating its proof.”
Accelerated Distributed Nesterov Gradient Descent (2017, neutral): “, [32, 4, 22, 15, 8, 30, 19, 20, 17, 26, 38, 16], most of which are distributed gradient descent algorithms based on a consensus scheme [24].”
Harnessing smoothness to accelerate distributed optimization (2016, background): “Extensions of these work have been proposed that deal with various realistic conditions, such as stochastic subgradient errors [9], directed or random communication graph [10]–[12], linear scaling in network size [13], heterogeneous local constraints [14], [15].”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “Proof: The following arguments are inspired by those in [35].”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “1) include the (sub)gradient method [21, 25, 36], the (sub)gradient-push method [23, 24], the fast (sub)gradient method [5, 14], and the dual averaging method [8].”
Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes (2015, background): “Some extension has also been made for cases under constraints [11], [12], cases where only noisy gradient is available [13], [14] and directed graphs [15].”
Decentralized Consensus Algorithm with Delayed and Stochastic Gradients (2016, neutral): “Therefore projecting x to X, i.e., projecting to [−R,∞)m and then (−∞, R]m, reduces ‖(I − J)x‖2.”