Data Encoding Methods for Byzantine-Resilient Distributed Optimization

By Deepesh Data, Linqi Song, Suhas N. Diggavi. 2019

18 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

Citations in the corpus