Communication-Efficient Distributed Optimization with Quantized Preconditioners

Abstract

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 fast convergence and reduced communication.

References in corpus (16)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Communication-Computation Efficient Gradient Coding
• Communication Complexity of Distributed Convex Learning and Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• AIDE: Fast and Communication Efficient Distributed Optimization
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• Distributed learning with compressed gradients
• The Convergence of Sparsified Gradient Methods
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• New Bounds For Distributed Mean Estimation and Variance Reduction
• Towards Tight Communication Lower Bounds for Distributed Optimisation