Age-Based Coded Computation for Bias Reduction in Distributed Learning
Authors:
- 1 December 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
Coded computation can speed up distributed learning in the presence of straggling workers. Partial recovery of the gradient vector can further reduce the computation time at each iteration; however, this can result in biased estimators, which may slow down convergence, or even cause divergence. Estimator bias is particularly prevalent when the straggling behavior is correlated over time, which results in the gradient estimators being dominated by a few fast servers. To mitigate biased estimators, we design a timely dynamic encoding framework for partial recovery that includes an ordering operator that changes the codewords and computation orders at workers over time. To regulate the recovery frequencies, we adopt an age metric in the design of the dynamic encoding scheme. The proposed age-based scheme prioritizes the recovery of computations with relatively large age. We show through numerical results that the proposed dynamic encoding strategy increases the timeliness of the recovered computations, which, as a result, reduces the bias in model updates, and accelerates the convergence compared to conventional static partial recovery schemes.Keywords
All Related Versions
Funding Information
- European Research Council (ERC) (675891,677854)
This publication has 23 references indexed in Scilit:
- Fast and Efficient Distributed Matrix-vector Multiplication Using Rateless Fountain Codes2019
- Distributed Gradient Descent with Coded Partial Gradient Computations2019
- Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding2018
- Improving Distributed Gradient Descent Using Reed-Solomon Codes2018
- Exploitation of Stragglers in Coded Computation2018
- Hierarchical Coded Computation2018
- Hierarchical Coding for Distributed Computing2018
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- Scaling Distributed Machine Learning with the Parameter Server2014
- Real-time status: How often should one update?2012