Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization

By Xiangru Lian, Yijun Huang, Yuncheng Li, Ji Liu. 2015

537 citations recorded by the source corpus.

Asynchronous parallel implementations of stochastic gradient (SG) have been broadly used in solving deep neural network and received many successes in practice recently. However, existing theories cannot explain their convergence and speedup properties, mainly due to the nonconvexity of most deep learning formulations and the asynchronous parallel mechanism. To fill the gaps in theory and provide theoretical supports, this paper studies two asynchronous parallel implementations of SG: one is on the computer network and the other is on the shared memory system. We establish an ergodic convergence rate $O(1/\sqrt{K})$ for both algorithms and prove that the linear speedup is achievable if the number of workers is bounded by $\sqrt{K}$ ($K$ is the total number of iterations). Our results generalize and improve existing analysis for convex minimization.

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

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “, 2015), Sgd for non-convex problems (De Sa et al., 2015; Lian et al., 2015), Sgd for stochastic optimization (Duchi et al.”
Federated Learning With Differential Privacy: Algorithms and Performance Analysis (2019, methodology): “In [15], [16], bounds for FL convergence performance were developed based on distributed SGD, with a one-step local update before global aggregations.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “To mitigate synchronization delay, asynchronous SGD method are studied in [28, 8, 19].”
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).”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, background): “With N parallel workers, parallel mini-batch SGD can solve problem (1) withO(1/ √ NT ) convergence, which is N times faster1 than the O(1/ √ T ) convergence attained by SGD over a single node (Ghadimi & Lan, 2013; Lian et al., 2015).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, neutral): “…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); Pedregosa et al. (2017);…”
Distributed Learning over Unreliable Networks (2018, background): “D C ] 2 2 N (2013); Lian et al. (2015).”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “Instead, the expected gradient norm is used as an indicator of convergence (Ghadimi & Lan, 2013; Lian et al., 2015; Zeng & Yin, 2016; Bottou et al., 2018).”
Local SGD Converges Fast and Communicates Little (2018, background): “Allowing asynchronous updates provides an alternative solution to disguise the communication overhead to a certain amount [16, 25, 30], though alternative strategies might be better when high accuracy is desired [6].”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “• Instead of the bounded delay assumption in [Lian et al., 2015], we use a general staleness bound E [ ||∇F (wj)−∇F (wτ(l,j))||22 ] ≤ γE [ ||∇F (wj)||22 ] , which allows for large, but rare delays.”
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, background): “The asynchronous version of centralized parallel SGD is proved to maintain a linear speedup on convex, strongly convex and nonconvex objectives when the staleness of the gradient is bounded [Agarwal and Duchi, 2011, Feyzmahdavian et al., 2015, Lian et al., 2015, 2016, Recht et al., 2011].”
QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks (2016, methodology): “In this context, the following follows from [26, Theorem 1]: Theorem D.1.”
On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization (2017, background): “With fixed stepsize, the expected average gradient norms is (see also Lian et al. [2015], Theorem 3) is”
Bayesian Nonparametric Federated Learning of Neural Networks (2019, background): “There is also significant work on distributed deep learning (Lian et al., 2015; 2017; Moritz et al., 2015; Li et al., 2014; Dean et al., 2012).”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, methodology): “The second involves studying the black-box optimization algorithms that are often used for training these networks (e.g. [Hardt et al., 2015, Lian et al., 2015]).”
Communication Compression for Decentralized Training (2018, background): “T 2 3 ) , that is slightly better the rate of D-PSGD proved in Lian et al. [2017b]”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “Modern large-scale machine learning applications require scaling stochastic optimization algorithms [30, 28, 15, 11] to distributed computational architectures [10, 39, 12, 20, 19, 38] or multicore systems [26, 9, 22, 25].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 16].”