Distributed Optimization over Time-Varying Networks: Imperfect Information with Feedback is as Good as Perfect Information
Hadi Reisizadeh, Behrouz Touri, Soheil Mohajer · 2022 American Control Conference (ACC) · 2022
The convergence of an error-feedback algorithm is studied for decentralized stochastic gradient descent (DSGD) algorithm with compressed information sharing over time-varying graphs. It is shown that for both strongly-convex and convex cost functions, despite of imperfect information sharing, the convergence rates match those with perfect information sharing. To do so, we show that for strongly-convex loss functions, with a proper choice of a step-size, the state of each node converges to the global optimizer at the rate of $\mathcal{O}\left( {{T^{ - 1}}} \right)$. Similarly, for general convex cost functions, with a proper choice of step-size, we show that the value of loss function at a temporal average of each node’s estimates converges to the optimal value at the rate of $\mathcal{O}\left( {{T^{ - 1/2 + \varepsilon }}} \right)$ for any ϵ > 0.