A Newton Tracking Algorithm With Exact Linear Convergence for Decentralized Consensus Optimization

作者：Jiaojiao Zhang, Qing Ling, Anthony Man–Cho So · 发表于：IEEE Transactions on Signal and Information Processing over Networks · 年份：2021 · DOI：10.1109/tsipn.2021.3083975 · 被引用次数：28 · 研究领域：Distributed Control Multi-Agent Systems、Cooperative Communication and Network Coding、Energy Efficient Wireless Sensor Networks

This 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} + κf2, \fracκg3/2κf+ κf√{κg} }log\frac1Δ) iterations to find a Δ-optimal solution, where κfand κgare condition numbers of the objective function and the graph, respectively. Our numerical results demonstrate the efficacy of Newton tracking and validate the theoretical findings.