Fast and Robust Distributed Learning in High Dimension
Authors:
- 1 September 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 71-80
Abstract
Could a gradient aggregation rule (GAR) for distributed machine learning be both robust and fast? This paper answers by the affirmative through MULTI-BULYAN. Given n workers, f of which are arbitrary malicious (Byzantine) and $m=n-f$ are not, we prove that MULTI-BULYAN can ensure a strong form of Byzantine resilience, as well as an $\frac{m}{n}$ slowdown, compared to averaging, the fastest (but non Byzantine resilient) rule for distributed machine learning. When $m\approx n$ (almost all workers are correct), MULTI-BULYAN reaches the speed of averaging. We also prove that MULTI-BULYAN’s cost in local computation is $O(d)$ (like averaging), an important feature for ML where d commonly reaches 10 9 , while robust alternatives have at least quadratic cost in d. Our theoretical findings are complemented with an experimental evaluation which, in addition to supporting the linear O(d) complexity argument, conveys the fact that MULTI-BULYAN’s parallelisability further adds to its efficiency.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- ByRDiE: Byzantine-Resilient Distributed Coordinate Descent for Decentralized LearningIEEE Transactions on Signal and Information Processing over Networks, 2019
- Scaling Distributed Machine Learning with the Parameter Server2014
- Understanding Machine Learning2014
- The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines, Second editionSynthesis Lectures on Computer Architecture, 2013
- Principal component analysisChemometrics and Intelligent Laboratory Systems, 1987
- Multivariate Estimation with High Breakdown Point1985