Distributed Optimization With Uncertain Communications

In this article, we consider a distributed optimization problem for the sum of convex functions where the underlying communication network connecting nodes at each time epoch is drawn at random from a collection of directed graphs. We propose a modified version of the subgradient-push algorithm that provably almost surely converges to an optimizer on any such sequence of random directed graphs. We also prove that the convergence rate of our proposed algorithm is upper bounded as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$ O(\frac{1}{\sqrt{t}})$</tex-math></inline-formula>, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$t$</tex-math></inline-formula> is the time horizon.