An approximate Newton method for distributed optimization

Agents of a network have access to strongly convex local functions f_i and attempt to minimize the aggregate function f(x) = Σ_i=1ⁿf_i(x) while relying on variable exchanges with neighboring nodes. Various methods to solve this distributed optimization problem exist but they all rely on first order information. This paper introduces Network Newton, a method that incorporates second order information via distributed evaluation of approximations to Newton steps. The method is shown to converge linearly and to do so while exhibiting a quadratic phase. Numerical analyses show substantial reductions in convergence times relative to existing (first order) alternatives.