Data Encoding for Byzantine-Resilient Distributed Gradient Descent

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

20 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, iteratively using gradient descent (GD). 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$t\leq \displaystyle \lfloor\frac{m-1}{2}\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 GD algorithm, without adversaries, for$t\leq \displaystyle \frac{m}{3}$.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, positive): “The second approach instead assigns each node redundant gradients, and uses this redundancy to eliminate the effect of Byzantine failures [7, 8, 9].”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, neutral): “[29] is concurrent to our conference versions in Allerton 2018 [1] and ISIT 2019 [2], [3], on which this article is based.”
Byzantine Fault-Tolerant Parallelized Stochastic Gradient Descent for Linear Regression (2019, background): “Unlike most works that rely on gradient filters, [6], [9] propose coding schemes that increase the computational workload of the workers to guarantee recovery of correct gradients by the master in presence of Byzantine faulty workers.”
Learning from History for Byzantine Robust Optimization (2020, background): “within a datacenter) coding theory based solutions which can correct for the mistakes have also been proposed (Chen et al., 2018; Rajput et al., 2019; Gupta & Vaidya, 2019; Konstantinidis & Ramamoorthy, 2020; Data et al., 2018; 2019).”