Stochastic Approximation Approach for Decentralized Optimization on Time Varying Random Networks

This paper initiates the study of a stochastic approximation approach with the Fully Stochastic Primal Dual Algorithm (FSPDA) framework for decentralized optimization on random and time varying topologies. Our framework relies on a novel observation that randomnesses in time varying topology can be incorporated into a stochastic equality constrained optimization formulation. We derived two new algorithms supporting sparsified communication on time varying topologies — FSPDA-SA allows agents to execute multiple local gradient steps to accelerate convergence, and FSPDA-STORM further incorporates variance reduction to improve sample complexity. For problems with smooth (possibly non-convex) objective function, within $T$ iterations, FSPDA-SA (resp. FSPDA-STORM) finds an $\mathcal{O}(1/\sqrt{T})$-stationary (resp. $\mathcal{O}(1/T^{2/3})$) solution. The latter shows the first near-optimal convergence rate over time varying topology.