A Newton Tracking Algorithm with Exact Linear Convergence for Decentralized Consensus Optimization
Publication in refereed journal


Times Cited
Altmetrics Information
.

Other information
AbstractThis paper considers the problem of decentralized consensus optimization over a network, where each node holds a strongly convex and twice-differentiable local objective function. Our goal is to minimize the sum of the local objective functions and find the exact optimal solution using only local computation and neighboring communication. We propose a novel Newton tracking algorithm, which updates the local variable in each node along a local Newton direction modified with neighboring and historical information. We investigate the connections between the proposed Newton tracking algorithm and several existing methods, including gradient tracking and primal-dual methods. We prove that the proposed algorithm converges to the exact optimal solution at a linear rate. Furthermore, when the iterate is close to the optimal solution, we show that the proposed algorithm requires O(max{κ f √{κ g } + κ f 2 , \fracκ g 3/2 κ f + κ f √{κ g } }log\frac1Δ) iterations to find a Δ-optimal solution, where κ f and κ g are condition numbers of the objective function and the graph, respectively. Our numerical results demonstrate the efficacy of Newton tracking and validate the theoretical findings.
All Author(s) ListJiaojiao Zhang, Qing Ling, Anthony Man-Cho So
Journal nameIEEE Transactions on Signal and Information Processing over Networks
Year2021
Month5
Day27
Volume Number7
PublisherIEEE
Pages346 - 358
eISSN2373-776X
LanguagesEnglish-United States

Last updated on 2024-09-04 at 00:28