Distributed first and second order methods with increasing number of working nodes

Abstract

© 2016 IEEE. We consider distributed optimization problems where nodes in a connected network collaboratively minimize the sum of their locally known convex costs subject to a common (vector-valued) optimization variable. In this paper, we present a mechanism to significantly improve the computational and communication efficiency of some recently proposed first and second order distributed methods for solving such problems. The presented mechanism relaxes the requirement that all nodes are active (i.e., update their solution estimates and communicate with neighbors) at all iterations k. Instead, each node is active at iteration k with probability pk, where pk is increasing to unity, while the activations are independent both across nodes and across iterations. Assuming strongly convex and twice continuously differentiable local costs and that pk grows to one geometrically, both first and second order methods with the idling schedule exhibit very similar theoretical convergence and convergence rate properties as if all nodes were active at all iterations. Simulation examples demonstrate that incorporating the idling schedule in first and second order distributed methods significantly improves their computational and communication efficiencies.