Asynchronous stochastic convex optimization: the noise is in the noise and SGD don't care

By Sorathan Chaturapruek, John C. Duchi, Christopher R'e. 2015

87 citations recorded by the source corpus.

We show that asymptotically, completely asynchronous stochastic gradient procedures achieve optimal (even to constant factors) convergence rates for the solution of convex optimization problems under nearly the same conditions required for asymptotic optimality of standard stochastic gradient procedures. Roughly, the noise inherent to the stochastic approximation scheme dominates any noise from asynchrony. We also give empirical evidence demonstrating the strong performance of asynchronous, parallel stochastic optimization schemes, demonstrating that the robustness inherent to stochastic approximation problems allows substantially faster parallel and asynchronous solution methods.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “This means that decentralized SGD methods are ideal for the optimization in the high-noise regime even when network connectivity is low and number of local steps is large (see also (Chaturapruek et al., 2015) and recent work (Pu et al., 2019)).”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “There are only a few pioneering works such as [Chaturapruek et al., 2015, Lian et al., 2015, Mania et al., 2017, Mitliagkas et al., 2016, Recht et al., 2011, Tsitsiklis et al., 1986] in this direction.”
Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization (2018, background): “The convergence behaviour of asynchronous SGD have been extensively analysed in many works (Chaturapruek et al., 2015; Zhao & Li, 2016; Zheng et al., 2017; De Sa et al., 2017).”
Asynchrony begets momentum, with an application to deep learning (2016, background): “Asynchrony A popular way of parallelizing SGD is the fully asynchronous execution of (2) byM different workers, also known as HOGWILD! by Niu et al. [4].”
1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed (2021, unknown): “Example techniques include quantization (Zhang et al., 2017; Wangni et al., 2018), decentralization (Lian et al., 2017; Koloskova* et al., 2020; Li et al., 2018), and asynchronous communication (Zheng et al., 2016; Chaturapruek et al., 2015).”
The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory (2018, background): “[12] considered Session 2A: Approximation and Learning PODC’18, July 23-27, 2018, Egham, United Kingdom”
Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (2018, methodology): “commensurate surge of interest in the asynchronous parallelization of first-order methods such as (stochastic) gradient descent (Agarwal & Duchi, 2011; Recht et al., 2011; Paine et al., 2013; Chaturapruek et al., 2015; Lian et al., 2015; Feyzmahdavian et al., 2016; Mania et al., 2017), coordinate de”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “Yet other works focus on sharp but asymptotic results, and do not provide guarantees after a ﬁxed number k of iterations (e.g., [4]).”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “finding comes as no surprise, as it agrees with previous results for SGD with delayed updates or with gradient compression (Chaturapruek et al., 2015; Arjevani et al., 2018; Stich et al., 2018; Karimireddy et al., 2019).”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “Asynchronous stochastic optimization in shared-memory and distributed-memory systems has also been widelystudied (Bertsekas & Tsitsiklis, 1989; Chaturapruek et al., 2015; Niu et al., 2011; Lian et al., 2015; 2018; Chen et al., 2016; Zheng et al., 2017; Mania et al., 2017; Leblond et al., 2017; Reddi”