Distributed adaptive Newton methods with global superlinear convergence. (April 2022)

• Record Type: Journal Article
• Authors: Zhang, Jiaqi; You, Keyou; Başar, Tamer
• Is Part Of: Automatica. Volume 138(2022)
• Publication Date: 2022-04
• Subjects: Distributed optimization -- Newton method -- Low-rank approximation -- Superlinear convergence; Automatic control -- Periodicals; Automation -- Periodicals; 629.805
• DOI: 10.1016/j.automatica.2021.110156
• Languages: English
• ISSNs: 0005-1098

Abstract

Abstract: This paper considers the distributed optimization problem where each node of a peer-to-peer network minimizes a finite sum of objective functions by communicating with its neighboring nodes. In sharp contrast to the existing literature where the fastest distributed algorithms converge either with a global linear or a local superlinear rate, we propose a distributed adaptive Newton (DAN) algorithm with a global quadratic convergence rate. Our key idea lies in the design of a finite-time set-consensus method with Polyak's adaptive stepsize. Moreover, we introduce a low-rank matrix approximation (LA) technique to compress the innovation of Hessian matrix so that each node only needs to transmit message of dimension O ( p ) (where p is the dimension of decision vectors) per iteration, which is essentially the same as that of first-order methods. Nevertheless, the resulting DAN-LA converges to an optimal solution with a global superlinear rate. Numerical experiments on logistic regression problems are conducted to validate their advantages over existing methods.