Byzantine-Tolerant Distributed Coordinate Descent

By Deepesh Data, Suhas N. Diggavi. 2019

8 citations recorded by the source corpus.

We study distributed coordinate descent (CD) in the master-worker architecture under adversarial attacks, where the data is partitioned (across the parameter space) and distributed among m worker nodes (t of which can be maliciously corrupt), which update some coordinates of their part of the parameter vector, in parallel and iteratively, using CD updates, with the help of the master. We propose a method based on data encoding and real error correction to combat the adversary. Our method can tolerate up to $\left\lceil {\frac{{m - 1}}{2}} \right\rceil $ corrupt nodes, which is information-theoretically optimal. Our design gives a trade-off between the resiliency t, the required redundancy, and the computation at master and worker nodes. For example, with constant overhead in the storage and computational complexity over that required by the plain distributed CD, we can tolerate up to m/3 corrupt nodes. We design a sparse encoding scheme, which yields low encoding complexity.

Subfields: Artificial Intelligence

Citations in the corpus

• 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-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, unknown): “A different line of work [CWCP18,RWCP19,DSD19b,DD19,DSD19a,LXC + 19,GHYR19] provide robustness with heterogeneous data, but without local iterations or sampling of clients: [CWCP18, RWCP19,DSD19b,DD19,DSD19a] use coding across datasets, which is hard to implement in FL; [LXC + 19] changes the objecti”