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

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

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

Jiaojiao Zhang; Qing Ling; Anthony Man-Cho So

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−−√+κ2f,κ3/2gκf+κfκg−−√}log1Δ)  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.

SPS on Twitter

  • Registration for ICIP 2021 is now open! This hybrid event will take place 19-22 September, with the in-person compo… https://t.co/s3kiGP4EPh
  • The Brain Space Initiative Talk Series continues on Friday, 30 July when Dr. Ioulia Kovelman presents "The Bilingua… https://t.co/6EqwqmBD0Q
  • There’s still time to register your team to win the US$5,000 grand prize in the 5-Minute Video Clip Contest, “Autom… https://t.co/76kh4jeL6i
  • Join the SPS Vizag Bay, Long Island, and Finland Chapters for the Seasonal School on Signal Processing and Communic… https://t.co/l04xac8qP5
  • Calling students and graduate students! The 5-Minute Video Clip Contest returns for ICIP 2021, and there's still ti… https://t.co/4hxYYY2Va3

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar