On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond

Abstract

The DANE algorithm is an approximate Newton method popularly used for communication-efficient distributed machine learning. Reasons for the interest in DANE include scalability and versatility. Convergence of DANE, however, can be tricky; its appealing convergence rate is only rigorous for quadratic objective, and for more general convex functions the known results are no stronger than those of the classic first-order methods. To remedy these drawbacks, we propose in this paper some new alternatives of DANE which are more suitable for analysis. We first introduce a simple variant of DANE equipped with backtracking line search, for which global asymptotic convergence and sharper local non-asymptotic convergence rate guarantees can be proved for both quadratic and non-quadratic strongly convex functions. Then we propose a heavy-ball method to accelerate the convergence of DANE, showing that nearly tight local rate of convergence can be established for strongly convex functions, and with proper modification of algorithm the same result applies globally to linear prediction models. Numerical evidence is provided to confirm the theoretical and practical advantages of our methods.

References in corpus (8)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Distributed Coordinate Descent Method for Learning with Big Data
• Communication Complexity of Distributed Convex Learning and Optimization
• Communication-Efficient Distributed Dual Coordinate Ascent
• AIDE: Fast and Communication Efficient Distributed Optimization
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Linearly convergent stochastic heavy ball method for minimizing generalization error

Cited by in corpus (6)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• Collaborative Distributed Machine Learning
• Distributed Saddle-Point Problems Under Similarity
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Newton Method over Networks is Fast up to the Statistical Precision