Distributed Second Order Methods with Fast Rates and Compressed Communication

Abstract

We develop several new communication-efficient second-order methods for distributed optimization. Our first method, NEWTON-STAR, is a variant of Newton's method from which it inherits its fast local quadratic rate. However, unlike Newton's method, NEWTON-STAR enjoys the same per iteration communication cost as gradient descent. While this method is impractical as it relies on the use of certain unknown parameters characterizing the Hessian of the objective function at the optimum, it serves as the starting point which enables us design practical variants thereof with strong theoretical guarantees. In particular, we design a stochastic sparsification strategy for learning the unknown parameters in an iterative fashion in a communication efficient manner. Applying this strategy to NEWTON-STAR leads to our next method, NEWTON-LEARN, for which we prove local linear and superlinear rates independent of the condition number. When applicable, this method can have dramatically superior convergence behavior when compared to state-of-the-art methods. Finally, we develop a globalization strategy using cubic regularization which leads to our next method, CUBIC-NEWTON-LEARN, for which we prove global sublinear and linear convergence rates, and a fast superlinear rate. Our results are supported with experimental results on real datasets, and show several orders of magnitude improvement on baseline and state-of-the-art methods in terms of communication complexity.

44 pages, 5 algorithms, 7 theorems, 7 figures, 4 tables

References in corpus (17)

• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Sparsified SGD with Memory
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• AIDE: Fast and Communication Efficient Distributed Optimization
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Natural Compression for Distributed Deep Learning
• Stochastic Optimization with Importance Sampling
• On Biased Compression for Distributed Learning
• Distributed learning with compressed gradients
• DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization
• Linearly convergent stochastic heavy ball method for minimizing generalization error
• Adaptive Gradient Descent without Descent
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Fast Linear Convergence of Randomized BFGS

Cited by in corpus (6)

• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• What Do We Mean by Generalization in Federated Learning?
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Towards Tight Communication Lower Bounds for Distributed Optimisation