Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
Hadi Reisizadeh, Behrouz Touri, Soheil Mohajer
Abstract
We study strongly convex distributed optimization problems where a set of agents are interested in solving a separable optimization problem collaboratively. In this paper, we propose and study a two time-scale decentralized gradient descent algorithm for a broad class of lossy sharing of information over time-varying graphs. One time-scale fades out the (lossy) incoming information from neighboring agents, and one time-scale regulates the local loss functions' gradients. We show that assuming a proper choice of step-size sequences, certain connectivity conditions, and bounded gradients along the trajectory of the dynamics, the agents' estimates converge to the optimal solution with the rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal{O}(\mathsf{T}^{-1/2})$</tex-math></inline-formula> . We also provide novel tools to study distributed optimization with diminishing averaging weights over time-varying graphs.