Technical Program

Paper Detail

Paper Title Byzantine-Tolerant Distributed Coordinate Descent
Paper IdentifierFR2.R6.2
Authors Deepesh Data, Suhas Diggavi, University of California, Los Angeles, United States
Session Coding for Distributed Computation
Location Sorbonne, Level 5
Session Time Friday, 12 July, 11:40 - 13:00
Presentation Time Friday, 12 July, 12:00 - 12:20
Manuscript  Click here to download the manuscript
Abstract 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 $\lceil\frac{m-1}{2}\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 {\em 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.