# A Communication-Efficient Decentralized Newton's Method with Provably Faster Convergence

arXiv: https://arxiv.org/abs/2210.00184 · HTML: https://mlsanity.com/paper/2210.00184/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2022.

## Built on by (most cited first, 2 of 2)

- [Federated Cubic Regularized Newton Learning with Sparsification-amplified Differential Privacy](https://mlsanity.com/paper/2408.04315/) (2024)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)

## Abstract (arXiv)

In this paper, we consider a strongly convex finite-sum minimization problem over a decentralized network and propose a communication-efficient decentralized Newton's method for solving it. We first apply dynamic average consensus (DAC) so that each node is able to use a local gradient approximation and a local Hessian approximation to track the global gradient and Hessian, respectively. Second, since exchanging Hessian approximations is far from communication-efficient, we require the nodes to exchange the compressed ones instead and then apply an error compensation mechanism to correct for the compression noise. Third, we introduce multi-step consensus for exchanging local variables and local gradient approximations to balance between computation and communication. To avoid each node transmitting the entire local Hessian approximation, we design a compression procedure with error compensation to estimate the global Hessian in a communication-efficient way. With novel analysis, we establish the globally linear (resp., asymptotically super-linear) convergence rate of the proposed method when m is constant (resp., tends to infinity), where m is the number of consensus inner steps. To the best of our knowledge, this is the first super-linear convergence result for a communication-efficient decentralized Newton's method. Moreover, the rate we establish is provably faster than those of first-order methods. Our numerical results on various applications corroborate the theoretical findings.