TY - GEN
T1 - Achieving Globally Superlinear Convergence for Distributed Optimization with Adaptive Newton Method
AU - Zhang, Jiaqi
AU - You, Keyou
AU - Basar, Tamer
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/12/14
Y1 - 2020/12/14
N2 - In this paper, we study the distributed optimization problem over a peer-to-peer network, where nodes optimize the sum of local objective functions via local computation and communicating with neighbors. Most existing algorithms cannot achieve globally superlinear convergence since they rely on either asymptotic consensus methods with linear convergence rates that bottleneck the global rate, or the pure Newton method that converges only locally. To this end, we introduce a finite-time set-consensus method, and then incorporate it into Polyak's adaptive Newton method, leading to our distributed adaptive Newton algorithm (DAN). Then, we propose a communication-efficient version of DAN called DAN-LA, which adopts a low-rank approximation idea to compress the Hessian and reduce the size of transmitted messages from O(p2) to O(p), where p is the dimension of decision vectors. We show that DAN and DAN-LA can globally achieve quadratic and superlinear convergence rates, respectively. Numerical experiments are conducted to show the advantages over existing methods.
AB - In this paper, we study the distributed optimization problem over a peer-to-peer network, where nodes optimize the sum of local objective functions via local computation and communicating with neighbors. Most existing algorithms cannot achieve globally superlinear convergence since they rely on either asymptotic consensus methods with linear convergence rates that bottleneck the global rate, or the pure Newton method that converges only locally. To this end, we introduce a finite-time set-consensus method, and then incorporate it into Polyak's adaptive Newton method, leading to our distributed adaptive Newton algorithm (DAN). Then, we propose a communication-efficient version of DAN called DAN-LA, which adopts a low-rank approximation idea to compress the Hessian and reduce the size of transmitted messages from O(p2) to O(p), where p is the dimension of decision vectors. We show that DAN and DAN-LA can globally achieve quadratic and superlinear convergence rates, respectively. Numerical experiments are conducted to show the advantages over existing methods.
UR - http://www.scopus.com/inward/record.url?scp=85099885060&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85099885060&partnerID=8YFLogxK
U2 - 10.1109/CDC42340.2020.9304321
DO - 10.1109/CDC42340.2020.9304321
M3 - Conference contribution
AN - SCOPUS:85099885060
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 2329
EP - 2334
BT - 2020 59th IEEE Conference on Decision and Control, CDC 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 59th IEEE Conference on Decision and Control, CDC 2020
Y2 - 14 December 2020 through 18 December 2020
ER -