Slow Learners are Fast

By Martin A. Zinkevich, Alex Smola, J. Langford. 2009

403 citations recorded by the source corpus.

Online learning algorithms have impressive convergence properties when it comes to risk minimization and convex games on very large problems. However, they are inherently sequential in their design which prevents them from taking advantage of modern multi-core architectures. In this paper we prove that online learning with delayed updates converges well, thereby facilitating parallel online learning.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, 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 Computer Networks and Communications

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “In contrast, asynchronous training (Zinkevich et al., 2009; Niu et al., 2011; Zhao and Li, 2016) updates the global model immediately after any worker responds.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of the notable references in a chronological order are Langford et al. (2009); Niu et al. (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…”
Deep learning with Elastic Averaging SGD (2014, methodology): “4 Stability analysis of EASGD and ADMM in the round-robin scheme In this section we study the stability of the asynchronous EASGD and ADMM methods in the roundrobin scheme [20].”
Optimal Distributed Online Prediction Using Mini-Batches (2010, methodology): “Langford et al. (2009) address the distributed online learning problem, with a similar motivation to ours: trying to address the scalability problem of online learning algorithms which are inherently sequential.”
Distributed delayed stochastic optimization (2011, background): “[10] also study asynchronous methods in the setup of stochastic optimization and attempt to remove the penalty for the delayed procedure under an additional smoothness assumption; however, their paper has a technical error (see the long version [2] for details).”
More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server (2013, methodology): “These properties can be used to prove convergence bounds for various algorithms; in this paper, we shall focus on stochastic gradient descent SGD [17]: Theorem 1 (SGD under SSP): Suppose we want to find the minimizer x∗ of a convex function f(x) = 1 T ∑T t=1 ft(x), via gradient descent on one compon”
A reliable effective terascale linear learning system (2011, background): “Langford et al. (2009) analyze a delayed version of distributed online learning.”
Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training (2018, methodology): “To prove the convergence of Pipe-SGD we adapt the derivation from parameter-server based asynchronous training [15, 23].”
Federated Collaborative Filtering for Privacy-Preserving Personalized Recommendation System (2019, methodology): “://spark.apache.org/docs/latest/mllib-collaborative-ﬁltering.html). Alternatively, SGD has become a widely adopted algorithm to implement matrix factorization for large-scale recommender applications [12, 13]. Contrary to ALS, the solution to latent factor matrices is based on a gradient descent app”
Parallel Coordinate Descent for L1-Regularized Loss Minimization (2011, methodology): “For example, it achieves better runtime bounds w.r.t. d than stochastic gradient methods such as SMIDAS (Shalev-Shwartz & Tewari, 2009) and truncated gradient (Langford et al., 2009a).”
Asynchronous Federated Optimization (2019, background): “Asynchronous training [17, 22, 23] is widely used in traditional distributed SGD.”
Communication Efficient Distributed Machine Learning with the Parameter Server (2014, methodology): “Other methods partition observations over several machines and update the model in a data parallel fashion [34, 17, 38, 3, 1, 19].”
Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning (2014, background): “Then when the InOrder property holds, HypBack with α = √ 2 ˜ R and G 0 = m 2 L”
Linear support vector machines via dual cached loops (2012, background): “However, SGD in its most basic form is inherently serial, and therefore there is a recent flurry of activity on developing parallel stochastic gradient descent solvers [23, 40, 15].”