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

The DANE algorithm is an approximate Newton method popularly used for communication-efficient distributed machine learning. Reasons for the interest in DA NE include scalability and versatility. Convergence of DANE, however, can be tricky; its appealing convergence rate is only rigorous for quadratic objective, and for more genera l convex functions the known results are no stronger than those of the classic first-ord er methods. To remedy these drawbacks, we propose in this paper some new alternatives o f 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 sharp er 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 accele rate the convergence of DANE, showing that nearly tight local rate of convergence can be e stablished for strongly convex functions, and with proper modification of algorithm the sam e result applies globally to linear prediction models. Numerical evidence is provided to confi rm the theoretical and practical advantages of our methods. Keywords: Communication-efficient distributed learning, Approximate Newton m ethod, Global convergence, Heavy-Ball acceleration.