An asynchronous mini-batch algorithm for regularized stochastic optimization

By Hamid Reza Feyzmahdavian, Arda Aytekin, Mikael Johansson. 2015

128 citations recorded by the source corpus.

Mini-batch optimization has proven to be a powerful paradigm for large-scale learning. However, the state of the art mini-batch algorithms assume synchronous operation or cyclic update orders. When worker nodes are heterogeneous (due to different computational capabilities, or different communication delays), synchronous and cyclic operations are inefficient since they will leave workers idle waiting for the slower nodes to complete their work. We propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems that eliminates idle waiting and allows workers to run at their maximal update rates. We show that the time necessary to compute an ϵ-optimal solution is asymptotically O(1/ϵ2), and the algorithm enjoys near-linear speedup if the number of workers is O(1/√ϵ). Theoretical results are confirmed in real implementations on a distributed computing infrastructure.

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

In Optimization & Training

Citations in the corpus

DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “aining Unlike Synchronous SGD where all workers need to stand and wait for one iteration to be nished, Asynchronous SGD enables a lock-free implementation for parallel SGD Agarwal & Duchi (2011); Feyzmahdavian et al. (2015); Recht et al. (2011). In Lian et al. (2015); Liu et al. (2015) authors g”
Communication trade-offs for synchronized distributed SGD with large step size (2019, neutral): “…(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.…”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “Under the bounded delay assumption the best guarantee we are aware of for delayed update SGD is (see [10] improving over [1])”
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].”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “…speedup many state-of-the-art optimization algorithms 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…”
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].”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “There are two typical implementations of ASGD.”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “[8] improve the bound to O ( σ √ k + τ2 + 1 k )”
Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation (2017, background): “It is worth pointing out that there is a subtle difference between the definition of the delayed stochastic gradient considered here, and those considered in [22], [39], [40].”
Multi-agent mirror descent for decentralized stochastic optimization (2015, background): “An asynchronous mini-batch framework based on mirror descent in the master-worker setting has recently been studied in [7].”
Blockchain Empowered Asynchronous Federated Learning for Secure Data Sharing in Internet of Vehicles (2020, background): “For example, in [40], the authors proposed an asynchronous mini-batch algorithm by exploiting”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “This allows to use smaller stepsizes: whilst e.g. Feyzmahdavian et al. (2016) had to use stepsizes O ( 1 τ2 ) , we can use stepsizes O ( 1 τ ) (only showing the dependency on τ), similar as in (Arjevani et al., 2018).”
Budgeted Training: Rethinking Deep Neural Network Training Under Resource Constraints (2019, background): “Such budget-aware schedules have been proposed in previous work [19, 38], but often for a fixed learning rate that depends on dataset statistics.”
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”
Asynchronous Decentralized Online Learning (2021, background): “Learner i t receives a convex function f t from environment, and suffers the loss f t ( w i t ( t )) .”