Fast Distributed Gradient Methods

By Dusan Jakovetic, Joao Xavier, José M. F. Moura. 2011

635 citations recorded by the source corpus.

We study distributed optimization problems when N nodes minimize the sum of their individual costs subject to a common vector variable. The costs are convex, have Lipschitz continuous gradient (with constant L), and bounded gradient. We propose two fast distributed gradient algorithms based on the centralized Nesterov gradient algorithm and establish their convergence rates in terms of the per-node communications K and the per-node gradient evaluations k. Our first method, Distributed Nesterov Gradient, achieves rates O( logK/K) and O(logk/k). Our second method, Distributed Nesterov gradient with Consensus iterations, assumes at all nodes knowledge of L and μ(W) - the second largest singular value of the N ×N doubly stochastic weight matrix W. It achieves rates O( 1/ K2-ξ) and O( 1/k2) ( ξ > 0 arbitrarily small). Further, we give for both methods explicit dependence of the convergence constants on N and W. Simulation examples illustrate our findings.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

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, methodology): “For the deterministic (non-stochastic) descentralized optimization a recent line of work developed optimal algorithms based on acceleration (Jakovetić et al., 2014; Scaman et al., 2017; 2018; Uribe et al., 2018; Fallah et al., 2019).”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “On the 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…”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “The most popular ﬁrst-order choices for the convex setting are distributed gradient descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of…”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “For the deterministic (non-stochastic) convex version of (1) a recent line of work developed optimal algorithms based on acceleration (Jakoveti´c et al., 2014; Scaman et al., 2017, 2018; Uribe et al., 2018).”
Stochastic Gradient Push for Distributed Deep Learning (2018, methodology): “The work of Jakovetić et al. (2014) studies gossip-based versions of the Nesterov gradient method for smooth stronglyconvex functions with deterministic gradients.”
On the Convergence of Decentralized Gradient Descent (2013, methodology): “Convergence to x∗ can be achieved by using diminishing stepsizes in [8, 11, 29] at the price of slower rates of convergence.”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, methodology): “For the general convex case, under assumptions of ﬁxed step size and Lipschitz continuous, bounded gradient, [14] shows an outer–loop convergence rate of O 1 k 2 in terms of objective error, utilizing Nesterov’s acceleration, provided that the inner loop performs substantial consensus computation,…”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “Many algorithms were proposed to solve the decentralized optimization of an average of functions (see for example [1, 11, 3, 4, 12, 2, 13, 5]), and a sheer amount of work was devoted to improving the convergence rate of these algorithms [5, 6].”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, methodology): “Decentralized optimization has been extensively studied and early methods such as decentralized gradient descent (Nedic & Ozdaglar, 2009; Jakovetić et al., 2014) or decentralized dual averaging (Duchi et al.”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “1Under further assumption of Lipschitz and bounded gradient, gradient methods can converge at rate O(1/k2), see [7].”
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2016, methodology): “By utilizing multi-consensus inner loop, adapt-then-combine (ATC) strategy, and Nesterov’s acceleration, the algorithm proposed in [26] is shown to have O ( ln(k)/k(2) )”
DSA: Decentralized Double Stochastic Averaging Gradient Algorithm (2015, methodology): “These methods include decentralized gradient descent (DGD) (Nedi´c and Ozdaglar (2009); Jakovetic et al. (2014); Yuan et al. (2013)), network Newton (Mokhtari et al. (2015a,b)), decentralized dual averaging (Duchi et al. (2012); Tsianos et al. (2012b)), the exact ﬁrst order al-gorithm (EXTRA) (Shi…”
On Nonconvex Decentralized Gradient Descent (2016, methodology): “When fi’s are convex, the existing algorithms include the (sub)gradient methods [8], [10], [24], [37], [40], [46], [59], [65], and the primal-dual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [9], [51], [52], DLM [31], and EXTRA [53], [54].”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, neutral): “In the distributed optimization literature, there are a variety of algorithms that are broadly categorized into primal meth-ods [27]–[30] and primal-dual methods [31]–[33].”
Harnessing smoothness to accelerate distributed optimization (2016, methodology): “They can also be applied to smooth functions, but when doing so it either does not guarantee exact convergence when using a fix constant step size [12], [17], or has a convergence rate at most Ω( 1 t2/3 ) when using a diminishing step size [18], slower than the normal Centralized Gradient Descent (C”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “1) has been studied extensively in the literature under various distributed algorithms [43, 25, 26, 19, 15, 16, 39, 11, 35, 23, 45, 34], among which the distributed gradient descent (DGD) method proposed in [25] has drawn the greatest attention.”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, background): “In particular, works in [33], [34] employ multi-consensus inner loops, Nesterov’s acceleration, and/or the adapt-then-combine (ATC) strategy.”