Distributed delayed stochastic optimization

By Alekh Agarwal, John C. Duchi. 2011

657 citations recorded by the source corpus.

We analyze the convergence of gradient-based optimization algorithms that base their updates on delayed stochastic gradient information. The main application of our results is to gradient-based distributed optimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to asynchrony. We take motivation from statistical problems where the size of the data is so large that it cannot fit on one computer; with the advent of huge datasets in biology, astronomy, and the internet, such problems are now common. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible and we can achieve order-optimal convergence results. We show n-node architectures whose optimization error in stochastic problems-in spite of asynchronous delays-scales asymptotically as O(1/√nT) after T iterations. This rate is known to be optimal for a distributed system with n nodes even in the absence of delays. We additionally complement our theoretical results with numerical experiments on a logistic regression task.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, Optimization & Training, Algorithms & Complexity

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 Algorithms & Complexity

Citations in the corpus

Federated Learning With Differential Privacy: Algorithms and Performance Analysis (2019, methodology): “In [16], [17], bounds for FL convergence performance were developed based on distributed SGD, with a one-step local update before global aggregation.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “[2] shows that limited amount of delay can be tolerated while preserving linear speedup for convex optimization problems.”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “Two main designs are developed to parallelize the computation: 1) centralized parallel learning [Agarwal and Duchi, 2011, Recht et al., 2011], where all the workers are ensured to obtain information from all others; 2) decentralized parallel learning [Dvurechenskii et al., 2018, He et al., 2018, Li…”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “…of distributed learning, such as communication efﬁcient learning (Alistarh et al., 2017; Bernstein et al., 2018a; Seide et al., 2014), de-centralized learning (He et al., 2018b; Lian et al., 2017b), and asynchronous learning (Agarwal & Duchi, 2011; Lian et al., 2015; Recht et al., 2011).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “(2011); Agarwal and Duchi (2011); Paine et al. (2013); Li et al. (2014b); Zhang et al. (2014); Keuper and Pfreundt (2015); De and Goldstein (2015); Feyzmahdavian et al. (2015); Lian et al. (2015); Mania et al. (2015); Zhao and Li (2015); Duchi et al. (2015); Chen et al. (2016a); Lian et al. (2017a);”
Distributed Learning over Unreliable Networks (2018, background): “he network. In Drumond et al. [2018], authors proposed a compressed DNN training strategy in order to save the computational cost of ﬂoating point. Centralized parallel training Centralized parallel [Agarwal and Duchi, 2011, Recht et al., 2011] training 3 works on the network that is designed to ens”
COLA: Decentralized Linear Learning (2018, methodology): “Other centralized algorithm representatives are parallel SGD variants such as [Agarwal and Duchi, 2011, Zinkevich et al., 2010] and more recent distributed second-order methods [Zhang and Lin, 2015, Reddi et al., 2016, Gargiani, 2017, Lee and Chang, 2017, Dünner et al., 2018, Lee et al., 2018].”
Distributed learning of deep neural network over multiple agents (2018, background): “Such techniques can be utilized to train very large scale deep neural networks spanning several machines[11] or to eﬃciently utilize several GPUs on a single machine[12].”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “when multiple processors or machines are working asynchronously, reading iterates, taking some time to perform the oracle accesses and computation, then communicating the results back (or updating the iterate accordingly) [1, 6, 16, 18, 24].”
Local SGD Converges Fast and Communicates Little (2018, neutral): “The analysis of Agarwal & Duchi [2] shows that asynchronous SGD on convex functions can tolerated delays up to O( √ T/K), which is identical to the maximal length of the local sequences in local SGD.”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “every learner only updates a part of the central parameter vector w at every iteration and are thus essentially different in spirit from conventional asynchronous SGD settings [41, 44] where every learner updates the entire w.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “The Asynchronous Parallel Stochastic Gradient Descent ( A-PSGD ) [Agarwal and Duchi, 2011, Feyzmah-davian et al., 2016, Paine et al., 2013, Recht et al., 2011] breaks the synchronization in S-PSGD.”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “Centralized parallel SGD For CENTRALIZED PARALLEL SGD (C-PSGD) algorithms, the most popular implementation is based on the parameter server, which is essentially the mini-batch SGD admitting a convergence rate ofO(1/ √ Kn) [Agarwal and Duchi, 2011, Dekel et al., 2012, Lian et al., 2015], where in ea”
Deep learning with Elastic Averaging SGD (2014, methodology): “…the distinctive feature of EASGD is that it allows the local workers for signiﬁcantly more exploration as opposed to ADMM -like methods, DOWNPOUR and many others Borkar (1998); Nedi´c et al. (2001); Langford et al. (2009); Agarwal & Duchi (2011); Recht et al. (2011); Zinkevich et al. (2010).”
Better Mini-Batch Algorithms via Accelerated Gradient Methods (2011, background): “Recently, [10] has shown that a mini-batching distributed framework is capable of attaining asymptotically optimal speed-up in general (see also [1]).”
Adaptive Federated Learning in Resource Constrained Edge Computing Systems (2018, background): “of distributed gradient descent are obtained in [27]–[29], which only allow one step of local update before global aggregation.”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “The main contributions of this paper are highlighted as follows: • Our result for A sy SG-con generalizes and improves earlier analysis of A sy SG-con for convex optimization in [Agarwal and Duchi, 2011].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “As an alternative, no synchronization between workers is assumed in [71, 2, 31].”
Communication Compression for Decentralized Training (2018, background): “In Agarwal and Duchi [2011], Zinkevich et al. [2010], the eﬀectiveness of C-PSGD is studied with latency taken into consideration.”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “Recent advances in parallel and distributed computing technologies have generated renewed interest in the theoretical understanding and practical implementation of parallel stochastic algorithms [15–20].”