Timezone: »

 
Poster
Distributed Newton Can Communicate Less and Resist Byzantine Workers
Avishek Ghosh · Raj Kumar Maity · Arya Mazumdar

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1134
in Poster Session 4 »

We develop a distributed second order optimization algorithm that is communication-efficient as well as robust against Byzantine failures of the worker machines. We propose an iterative approximate Newton-type algorithm, where the worker machines communicate \emph{only once} per iteration with the central machine. This is in sharp contrast with the state-of-the-art distributed second order algorithms like GIANT \cite{giant}, DINGO\cite{dingo}, where the worker machines send (functions of) local gradient and Hessian sequentially; thus ending up communicating twice with the central machine per iteration. Furthermore, we employ a simple norm based thresholding rule to filter-out the Byzantine worker machines. We establish the linear-quadratic rate of convergence of our proposed algorithm and establish that the communication savings and Byzantine resilience attributes only correspond to a small statistical error rate for arbitrary convex loss functions. To the best of our knowledge, this is the first work that addresses the issue of Byzantine resilience in second order distributed optimization. Furthermore, we validate our theoretical results with extensive experiments on synthetically generated and benchmark LIBSVM \cite{libsvm} data-set and demonstrate convergence guarantees.

Author Information

Avishek Ghosh (University of California, Berkeley)
Raj Kumar Maity (University of Massachusetts Amherst)
Arya Mazumdar (University of California, San Diego)

More from the Same Authors