Provable local acceleration in HBNET-GIANT: An accelerated Newton-type distributed optimization algorithm

This article presents a second-order fully distributed optimization algorithm, HBNET-GIANT, driven by heavy-ball momentum, for L-smooth and μ-strongly convex objective functions. We perform a rigorous convergence analysis and demonstrate global linear convergence under certain sufficient conditions. We also establish local acceleration of HBNET-GIANT. As our primary theoretical result, we establish tight upper and lower bounds on the actual convergence rate of the optimization error, defined as the gap between the average of the local decision variables and the optimal solution (if it exists). To the best of our knowledge, this is the first work to provide a detailed analysis of local acceleration induced by heavy-ball momentum in fully distributed approximate Newton-type algorithms. Through extensive numerical experiments, we demonstrate that HBNET-GIANT with heavy-ball momentum achieves acceleration, and the corresponding rate of convergence is strictly faster than its non-accelerated version, Network-GIANT. We also compared HBNET-GIANT with several state-of-the-art algorithms, both momentum-based and without momentum, and reported significant performance improvement in convergence to the optimum.