Abstract

In this paper, we develop a communication efficient second order distributed Newton-type algorithm. For communication efficiency, we consider a generic class of $\delta$-approximate compressors (Karimireddy et al., 2019), which includes \emph{sign}-based compression and top-$k$ sparsification. We provide three potential settings where compression can be employed; and provide rate of convergence for smooth objectives. We show that, in the regime where $\delta$ is constant, our theoretical convergence rate matches that of a state-of-the-art distributed second order algorithm called \emph{DINGO} (Crane and Roosta, 2019). This implies that we get the compression for free in this regime. The full paper can be found at: https://tinyurl.com/ujnpt4c.


Presenters

Avishek Ghosh

University of California, Berkeley

Raj Kumar Maity

University of Massachusetts, Amherst

Arya Mazumdar

University of Massachusetts Amherst

Kannan Ramchandran

University of California, Berkeley

Session Chair

Lav Varshney

University of Illinois, Urbana-Champaign