A geometrically convergent method for distributed optimization over time-varying graphs
Angelia Nedić, Alex Olshevsky, Wei Shi · 2016
This paper considers the problem of distributed optimization over time-varying undirected graphs. We discuss a distributed algorithm, which we call DIGing, for solving this problem based on a combination of an inexact gradient method and a gradient tracking technique. This algorithm deploys fixed step size but converges exactly to the global and consensual minimizer. Under strong convexity assumption, we prove that the algorithm converges at an R-linear (geometric) convergence rate as long as the step size is less than a specific bound; we give an explicit estimate of this rate over uniformly connected graph sequences and show it scales polynomially with the number of nodes. Numerical experiments demonstrate the efficacy of the introduced algorithm and validate our theoretical findings.