A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks
This work addresses the challenge of efficient optimization in unreliable and bandwidth-constrained decentralized systems, representing an incremental improvement with novel algorithmic variants.
The paper tackles the problem of decentralized optimization on random and time-varying networks by proposing a stochastic approximation approach with the Fully Stochastic Primal Dual Algorithm (FSPDA) framework, resulting in algorithms that achieve convergence rates of O(1/√T) and O(1/T^{2/3}) for smooth non-convex objectives.
A challenging problem in decentralized optimization is to develop algorithms with fast convergence on random and time varying topologies under unreliable and bandwidth-constrained communication network. This paper studies a stochastic approximation approach with a Fully Stochastic Primal Dual Algorithm (FSPDA) framework. Our framework relies on a novel observation that randomness in time varying topology can be incorporated in a stochastic augmented Lagrangian formulation, whose expected value admits saddle points that coincide with stationary solutions of the decentralized optimization problem. With the FSPDA framework, we develop two new algorithms supporting efficient sparsified communication on random time varying topologies -- FSPDA-SA allows agents to execute multiple local gradient steps depending on the time varying topology to accelerate convergence, and FSPDA-STORM further incorporates a variance reduction step to improve sample complexity. For problems with smooth (possibly non-convex) objective function, within $T$ iterations, we show that FSPDA-SA (resp. FSPDA-STORM) finds an $\mathcal{O}( 1/\sqrt{T} )$-stationary (resp. $\mathcal{O}( 1/T^{2/3} )$) solution. Numerical experiments show the benefits of the FSPDA algorithms.