  We investigate fast and communication-efficient algorithms for the classic
problem of minimizing a sum of strongly convex and smooth functions that are
distributed among $n$ different nodes, which can communicate using a limited
number of bits. Most previous communication-efficient approaches for this
problem are limited to first-order optimization, and therefore have
\emph{linear} dependence on the condition number in their communication
complexity. We show that this dependence is not inherent:
communication-efficient methods can in fact have sublinear dependence on the
condition number. For this, we design and analyze the first
communication-efficient distributed variants of preconditioned gradient descent
for Generalized Linear Models, and for Newton's method. Our results rely on a
new technique for quantizing both the preconditioner and the descent direction
at each step of the algorithms, while controlling their convergence rate. We
also validate our findings experimentally, showing faster convergence and
reduced communication relative to previous methods.
