Network Newton-Part I: Algorithm and Convergence

Abstract

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. This is done via distributed implementation of approximations of a suitably chosen Newton step. The approximations are obtained by truncation of the Newton step's Taylor expansion. This leads to a family of methods defined by the number $K$ of Taylor series terms kept in the approximation. When keeping $K$ terms of the Taylor series, the method is called NN-$K$ and can be implemented through the aggregation of information in $K$-hop neighborhoods. Convergence to a point close to the optimal argument at a rate that is at least linear is proven and the existence of a tradeoff between convergence time and the distance to the optimal argument is shown. Convergence rate, several practical implementation matters, and numerical analyses are presented in a companion paper [3].

13 pages, submitted to a journal

References in corpus (7)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Convex Optimization for Big Data
• DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements
• On the Convergence of Decentralized Gradient Descent
• Network Newton-Part II: Convergence Rate and Implementation
• EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
• Accelerated Backpressure Algorithm

Cited by in corpus (8)

• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Decentralized Quasi-Newton Methods
• DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers
• Distributed Gradient Methods with Variable Number of Working Nodes
• Superlinearly Convergent Asynchronous Distributed Network Newton Method
• Balancing Communication and Computation in Distributed Optimization
• A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization