Distributed Subgradient Algorithm Over Non-Independent Randomly Time-Varying Graphs

We investigate the distributed stochastic optimization by nodes over the uncertain communication topologies to cooperatively minimize a sum of strongly convex local cost functions. The communication topologies are described by a sequence of time-varying stochastic directed graphs, in which every node and edge corresponds to a local optimizer and a link. We prove that if the subgradients of the local cost functions are Lipschitz continuous and the sequence of directed graphs is conditionally balanced and uniformly conditionally jointly connected, then by properly choosing the algorithm step sizes, the convergence of all nodes’ states to the global optimal solution is achieved almost surely and in mean square.