An approximate Newton method for distributed optimization
Aryan Mokhtari, Qing Ling, Alejandro Ribeiro
Abstract
Agents of a network have access to strongly convex local functions f <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> and attempt to minimize the aggregate function f(x) = Σ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i=1</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> f <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> (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.
BibTeX
@inproceedings{icassp2015_anapproximatenew,
title = {An approximate Newton method for distributed optimization},
author = {Aryan Mokhtari and Qing Ling and Alejandro Ribeiro},
booktitle = {ICASSP 2015},
year = {2015}
}