Distributed Optimization over Time-Varying Networks: Imperfect Information with Feedback is as Good as Perfect Information

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.