Network Newton-Part I: Algorithm and Convergence

Understand

We study the problem of minimizing a sum of convex objective functions where the components of the objective are available at different nodes of a network and nodes are allowed to only communicate with their neighbors.

• The use of distributed gradient methods is a common approach to solve this problem.
• Their popularity notwithstanding, these methods exhibit slow convergence and a consequent large number of communications between nodes to approach the optimal argument because they rely on first order information only.
• This paper proposes the network Newton (NN) method as a distributed algorithm that incorporates second order information.