Statistics and Learning Theory
L.3.1
Lecture
Distributed Learning Performance Analysis

# Communication Efficient Distributed Approximate Newton Method

Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar, Kannan Ramchandran

## Date & Time

01:00 am – 01:00 am

## 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

Paper

## Session Chair

#### Lav Varshney

University of Illinois, Urbana-Champaign