Fast and Robust Distributed Learning in High Dimension

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 \fracmn 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 109, 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.