On the Convergence of Nested Decentralized Gradient Methods with\n Multiple Consensus and Gradient Steps

Abstract

In this paper, we consider minimizing a sum of local convex objective\nfunctions in a distributed setting, where the cost of communication and/or\ncomputation can be expensive. We extend and generalize the analysis for a class\nof nested gradient-based distributed algorithms (NEAR-DGD; Berahas,\nBollapragada, Keskar and Wei, 2018) to account for multiple gradient steps at\nevery iteration. We show the effect of performing multiple gradient steps on\nthe rate of convergence and on the size of the neighborhood of convergence, and\nprove R-Linear convergence to the exact solution with a fixed number of\ngradient steps and increasing number of consensus steps. We test the\nperformance of the generalized method on quadratic functions and show the\neffect of multiple consensus and gradient steps in terms of iterations, number\nof gradient evaluations, number of communications and cost.\n