Technical Program

Paper Detail

Paper Title Data Encoding Methods for Byzantine-Resilient Distributed Optimization FR2.R6.1 Deepesh Data, University of California, Los Angeles, United States; Linqi Song, City University of Hong Kong, Hong Kong SAR of China; Suhas Diggavi, University of California, Los Angeles, United States Coding for Distributed Computation Sorbonne, Level 5 Friday, 12 July, 11:40 - 13:00 Friday, 12 July, 11:40 - 12:00 Click here to download the manuscript 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 {\em generalized linear models}, iteratively, using {\em 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 $t\leq \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 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.