Age-Based Coded Computation for Bias Reduction in Distributed Learning
Authors:
Preprint
Abstract
Coded computation can be used to 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 will be 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. 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 the conventional static partial recovery schemes.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Timely Distributed Computation With StragglersIEEE Transactions on Communications, 2020
- Age-Based Scheduling Policy for Federated Learning in Mobile Edge Networks2020
- Age of Information with Gilbert-Elliot Servers and Samplers2020
- Age of Information: A New Metric for Information FreshnessSynthesis Lectures on Communication Networks, 2019
- On the Optimal Recovery Threshold of Coded Matrix MultiplicationIEEE Transactions on Information Theory, 2019
- Fast and Efficient Distributed Matrix-vector Multiplication Using Rateless Fountain Codes2019
- Computation Scheduling for Distributed Machine Learning with Straggling Workers2019
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017