DINE: Decentralized Inexact Newton With Exact Linear Convergence Rate

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 as Network_DANE and Newton_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. DINE extends 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 for DINE to obtain a linear convergence rate. Thus, the descent direction of DINE can be ...
Source: IEEE Transactions on Signal Processing - Category: Biomedical Engineering Source Type: research