Communication-Efficient Distributed Optimization with Quantized\n Preconditioners

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