An approximate Newton method for distributed optimization
Lists
Only you see this
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{mokhtari2015approximate,
author = {Aryan Mokhtari and Qing Ling and Alejandro Ribeiro},
title = {{An approximate Newton method for distributed optimization}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2015},
doi = {10.1109/icassp.2015.7178513},
}Loading related content...