Data Encoding Methods for Byzantine-Resilient Distributed Optimization
Authors:
- 1 July 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2719-2723
Abstract
We consider distributed gradient computation, where both data and computation are distributed among m worker machines, t of which can be Byzantine adversaries, and a designated (master) node computes the model/parameter vector for generalized linear models, iteratively, using proximal gradient descent (PGD), of which gradient descent (GD) is a special case. The Byzantine adversaries can (collaboratively) deviate arbitrarily from their gradient computation. To solve this, we propose a method based on data encoding and (real) error correction to combat the adversarial behavior. We can tolerate up to $ \leq \left\lfloor {\frac{{m - 1}}{2}} \right\rfloor $ corrupt worker nodes, which is information-theoretically optimal. Our method does not assume any probability distribution on the data. We develop a sparse encoding scheme which enables computationally efficient data encoding. We demonstrate a trade-off between the number of adversaries tolerated and the resource requirement (storage and computational complexity). As an example, our scheme incurs a constant overhead (storage and computational complexity) over that required by the distributed PGD algorithm, without adversaries, for $t \leq \frac{m}{3}$ . Our encoding works as efficiently in the streaming data setting as it does in the offline setting, in which all the data is available beforehand.
Keywords
This publication has 10 references indexed in Scilit:
- Will Distributed Computing Revolutionize Peace? The Emergence of Battlefield IoT2018
- Gradient Coding Using the Stochastic Block Model2018
- Improving Distributed Gradient Descent Using Reed-Solomon Codes2018
- Distributed Statistical Machine Learning in Adversarial SettingsProceedings of the ACM on Measurement and Analysis of Computing Systems, 2017
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017
- The tail at scaleCommunications of the ACM, 2013
- A Frame Construction and a Universal Distortion Bound for Sparse RepresentationsIEEE Transactions on Signal Processing, 2008
- MapReduceCommunications of the ACM, 2008
- Decoding by Linear ProgrammingIEEE Transactions on Information Theory, 2005
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982