Distributed second order methods with increasing number of working nodes

DOI10.1109/TAC.2019.2922191MaRDI QIDQ6290889arXivWikidataFDO

Authors Nataša Krklec Jerinkić, Dušan Jakovetić, Nataša Krejić, Dragana Bajović

Publication date 5 September 2017

Published in arXiv

Full work available at URL https://doi.org/10.1109/TAC.2019.2922191

Mathematics Subject Classification ID

Convex programming (90C25) Methods of quasi-Newton type (90C53) Networked control (93B70)

arXiv classification

cs.IT math.IT math.OC

Abstract: Recently, an idling mechanism has been introduced in the context of distributed emph{first order} methods for minimization of a sum of nodes' local convex costs over a generic, connected network. With the idling mechanism, each node

i

, at each iteration

k

, is active -- updates its solution estimate and exchanges messages with its network neighborhood -- with probability

p_{k}

, and it stays idle with probability

1 - p_{k}

, while the activations are independent both across nodes and across iterations. In this paper, we demonstrate that the idling mechanism can be successfully incorporated in emph{distributed second order methods} also. Specifically, we apply the idling mechanism to the recently proposed Distributed Quasi Newton method (DQN). We first show theoretically that, when

p_{k}

grows to one across iterations in a controlled manner, DQN with idling exhibits very similar theoretical convergence and convergence rates properties as the standard DQN method, thus achieving the same order of convergence rate (R-linear) as the standard DQN, but with significantly cheaper updates. Simulation examples confirm the benefits of incorporating the idling mechanism, demonstrate the method's flexibility with respect to the choice of the

p_{k}

's, and compare the proposed idling method with related algorithms from the literature.

This page was built for publication: Distributed second order methods with increasing number of working nodes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6290889)