DINE: Decentralized Inexact Newton With Exact Linear Convergence Rate
Haishan Ye, Shiyuan He, Xiangyu Chang · IEEE Transactions on Signal Processing · 2023
Decentralized learning has recently attracted much research attention because of its robustness and user privacy advantages. Decentralized algorithms play central roles in training machine learning models in decentralized learning. Due to the slow convergence of first-order algorithms (e.g., SGD), several works try to exploit the second-order information of the local functions to obtain faster convergence rates and achieve the communication efficiency of decentralized learning. However, existing decentralized second-order algorithms, such asNetwork_DANEandNewton_tracking, can not achieve both computation and communication efficiency because they are required either to solve an expensive sub-problem up to the target precision precisely or to compute the Hessian inverse. Therefore, this causes these algorithms to suffer from high computation costs and hinders their wide applications. In this paper, we design a novel decentralized second-order algorithm called Decentralized Inexact Newton with Exact linear convergence rate (DINE) to overcome the high computation costs of the existed ones.DINEextends the famous inexact Newton to the decentralized setting and combines it with the gradient tracking method to achieve a linear convergence rate. Almost the same as the inexact Newton, the descent direction approximating the exact Newton direction up to a constant less than$1/3$is sufficient forDINEto obtain a linear convergence rate. Thus, the descent direction ofDINEcan be computed cheaply, andDINEcan achieve both communication and computation efficiency. Our empirical study also validates the advantages ofDINEover the extant decentralized second-order algorithms.