On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond

Xiao Tong Yuan, Ping Li

Research output: Contribution to journalArticlepeer-review


The DANE algorithm is an approximate Newton method popularly used for communicatione ficient distributed machine learning. Reasons for the interest in DANE include scalability and efficiency. Convergence of DANE, however, can be tricky; its appealing convergence rate is only rigorous for quadratic objective function, 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 article 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 nonasymptotic convergence 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 the near-tight local rate of convergence can be established for strongly convex functions, and with proper modification of the algorithm about the same result applies globally to linear prediction models. Numerical evidence is provided to confirm the theoretical and practical advantages of our methods.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
StatePublished - Aug 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


  • Approximate Newton method
  • Communication-efficient distributed learning
  • Global convergence
  • Heavy-Ball acceleration


Dive into the research topics of 'On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond'. Together they form a unique fingerprint.

Cite this