# Technical Program

## Paper Detail

Paper Title Byzantine-Tolerant Distributed Coordinate Descent FR2.R6.2 Deepesh Data, 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, 12:00 - 12:20 Click here to download the manuscript 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.