An approximate Newton method for distributed optimization
Aryan Mokhtari, Qing Hua Ling, Alejandro Ribeiro · 2015
Agents of a network have access to strongly convex local functions fiand attempt to minimize the aggregate function f(x) = Σi=1nfi(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.