DSAG: A Mixed Synchronous-Asynchronous Iterative Method for Straggler-Resilient Learning
- 7 December 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 71 (2) , 808-822
Abstract
We consider straggler-resilient learning. In many previous works, e.g., in the coded computing literature, straggling is modeled as random delays that are independent and identically distributed between workers. However, in many practical scenarios, a given worker may straggle over an extended period of time. We propose a latency model that captures this behavior and is substantiated by traces collected on Microsoft Azure, Amazon Web Services (AWS), and a small local cluster. Building on this model, we propose DSAG, a mixed synchronous-asynchronous iterative optimization method, based on the stochastic average gradient (SAG) method, that combines timely and stale results. We also propose a dynamic load-balancing strategy to further reduce the impact of straggling workers. We evaluate DSAG for principal component analysis, cast as a finite-sum optimization problem, of a large genomics dataset, and for logistic regression on a cluster composed of 100 workers on AWS, and find that DSAG is up to about 50% faster than SAG, and more than twice as fast as coded computing methods, for the particular scenario that we consider.Keywords
All Related Versions
Funding Information
- NSF (CNS-1801630)
- Swedish Research Council (2020-03687)
This publication has 33 references indexed in Scilit:
- Model Accuracy and Runtime Tradeoff in Distributed Deep Learning: A Systematic Study2016
- Minimizing finite sums with the stochastic average gradientMathematical Programming, 2016
- A global reference for human genetic variationNature, 2015
- ICE: An Integrated Configuration Engine for Interference Mitigation in Cloud Services2015
- Large-scale cluster management at Google with Borg2015
- Randomized Iterative Methods for Linear SystemsSIAM Journal on Matrix Analysis and Applications, 2015
- Searching for exotic particles in high-energy physics with deep learningNature Communications, 2014
- The tail at scaleCommunications of the ACM, 2013
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976