A Newton Tracking Algorithm with Exact Linear Convergence Rate for Decentralized Consensus Optimization

Abstract

This paper considers the decentralized consensus optimization problem defined over a network where each node holds a second-order differentiable local objective function. Our goal is to minimize the summation of local objective functions and find the exact optimal solution using only local computation and neighboring communication. We propose a novel Newton tracking algorithm, where each node updates its local variable 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 second-order algorithms. Under the strong convexity assumption, we prove that it converges to the exact optimal solution at a linear rate. Numerical experiments demonstrate the efficacy of Newton tracking and validate the theoretical findings.

arXiv comment9 pages, 7 figures, journal

References in corpus (10)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Distributed Optimal Power Flow for Smart Microgrids
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Decentralized Online Learning with Kernels
• Privacy-Preserving Blockchain-Based Federated Learning for IoT Devices
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• A Fast Distributed Asynchronous Newton-Based Optimization Algorithm