Perturbed Iterate Analysis for Asynchronous Stochastic Optimization

By Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, B. Recht, Kannan Ramchandran, Michael I. Jordan. 2015

252 citations recorded by the source corpus.

We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a unified approach to analyze asynchronous implementations of stochastic optimization algorithms.In this framework, asynchronous stochastic optimization algorithms can be thought of as serial methods operating on noisy inputs. Using our perturbed iterate framework, we provide new analyses of the Hogwild! algorithm and asynchronous stochastic coordinate descent, that are simpler than earlier analyses, remove many assumptions of previous models, and in some cases yield improved upper bounds on the convergence rates. We proceed to apply our framework to develop and analyze KroMagnon: a novel, parallel, sparse stochastic variance-reduced gradient (SVRG) algorithm. We demonstrate experimentally on a 16-core machine that the sparse and parallel version of SVRG is in some cases more than four orders of magnitude faster than the standard SVRG algorithm.

Subfields: Artificial Intelligence, Computational Mechanics, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

In Optimization & Training

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “The “perturbed iterate” framework presented in Mania et al. (2017) is to the best of our knowledge the only one that does not suffer from this problem, and our convergence analysis builds heavily from their approach, while simplifying it. In particular, the authors assumed that f was both strongly c”
Revisiting Distributed Synchronous SGD (2016, background): “De Sa et al. (2015); Mania et al. (2015), most of which focus on individual algorithms, under strong assumptions that may not hold up in practice.”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “We prove convergence for the distributed sparsification and error compensation algorithm, without the assumption of [5], by using the perturbed iterate methods [18], [31].”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “Performing convergence analysis for the node-average version x̄ has been an important technique used in previous works on distributed consensus optimization (Lian et al., 2017; Mania et al., 2017; Stich, 2018; Yu et al., 2018; Jiang & Agrawal, 2018).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “In order to provide a bound on the mean squared distance to the optimum of the outer iterates, we introduce a ghost sequence Mania et al. (2015), i.e., a sequence of iterates which is not actually computed.”
Local SGD Converges Fast and Communicates Little (2018, methodology): “Inspired by the perturbed iterate framework of [20] we first define a virtual sequence {x̄t}t≥0 in the following way:”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “Related Work The large-scale nature of modern machine learning has spurred a great deal of novel research on distributed and parallel training algorithms and systems (Recht et al., 2011; Dean et al., 2012; Alistarh et al., 2017; Jaggi et al., 2014; Liu et al., 2014; Mania et al., 2015; Chen et al., ”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “In [Recht et al., 2011], a new asynchronous algorithm called Hogwild was proposed and analyzed under bounded gradient assumption that has been followed upon by several works such as [Lian et al., 2015, Mania et al., 2017].”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “…for centralized networks Agarwal and Duchi [2011], Avron et al. [2014], Feyzmahdavian et al. [2015], Feyzmahdavian et al. [2016], Liu et al. [2014], Mania et al. [2015], Paine et al. [2013], Recht et al. [2011], Sridhar et al. [2013], Tran et al. [2015], Zhang et al. [2014], this paper proposes an…”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, background): “…including stochastic gradient [Niu et al., 2011, Agarwal and Duchi, 2011, Zhang et al., 2014, Feyzmahdavian et al., 2015, Paine et al., 2013, Mania et al., 2015], stochastic coordinate descent [Avron et al., 2014, Liu et al., 2014a, Sridhar et al., 2013], dual stochastic coordinate ascent…”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “In fact, two recent works [60, 48] highlight subtle but important issue with labelling of iterates in the presence of asynchrony, rendering most of the existing analyses of asynchronous optimization algorithms incorrect.”
Sparsified SGD with Memory (2018, positive): “Inspired by the perturbed iterate framework in [22] and [18] we first define a virtual sequence {x̃t}t≥0 in the following way: x̃0 = x0 , x̃t+1 = x̃t − ηt∇fit(xt) , (11) where the sequences {xt}t≥0, {ηt}t≥0 and {it}t≥0 are the same as in (8).”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “Other approaches for low-communication training focus on sparsification of gradients, either by thresholding small entries or by random sampling [6, 22, 23, 24, 25, 26, 27, 28].”
Stochastic Variance Reduction for Nonconvex Optimization (2016, neutral): “Asynchronous VR frameworks are developed in (Reddi et al., 2015; Mania et al., 2015).”
Asynchrony begets momentum, with an application to deep learning (2016, background): “This assumption is valid on a CNN that performs dense updates, where the randomness in staleness comes from unmodeled implementation and system behavior.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “In fact, two recent works [110, 92] highlight subtle but important issue with labeling of iterates in the presence of asynchrony, rendering most of the existing analyses of asynchronous optimization algorithms incorrect.”
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption (2018, methodology): “In (Recht et al., 2011; Mania et al., 2015; De Sa et al., 2015) various variants of Hogwild! with a fixed step size are analyzed under the assumption that the gradients are bounded as in (5).”