  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.
