This talk presents a stochastic approximation (SA) perspective for the design of communication-efficient decentralized optimization on time-varying graphs. We describe an SA framework utilizing a primal-dual algorithm that naturally accounts for randomness in communication graphs, which motivates two communication-efficient algorithms. Focusing on smooth (possibly non-convex) problems, we first demonstrate that accelerated convergence can be achieved by combining variance reduction with the primal-dual SA scheme, leading to the FSPDA-STORM algorithm that finds an O(1/T^{2/3}) stationary solution after T iterations. Second, we show that combining primal-dual SA with a majorization-minimization scheme suggests the agents to share a compressed difference term during the iteration, resulting in the TiCoPD algorithm. The TiCoPD algorithm incorporates a fast timescale mirror sequence for agent consensus on nonlinearly compressed terms with noise, in conjunction with a slow timescale primal-dual recursion for optimizing the objective function. We demonstrate that the TiCoPD algorithm converges with a constant step size. Additionally, it finds an O(1/sqrt{T}) stationary solution after T iterations. Numerical experiments on decentralized training of a neural network validate the efficacy of the proposed algorithms.

Hoi-To Wai received his PhD degree from Arizona State University (ASU) in Electrical Engineering in Fall 2017, B. Eng. (with First Class Honor) and M. Phil. degrees in Electronic Engineering from The Chinese University of Hong Kong (CUHK) in 2010 and 2012, respectively. He is an Associate Professor in the Department of Systems Engineering & Engineering Management at CUHK. He has held research positions at ASU, UC Davis, Telecom ParisTech, Ecole Polytechnique, MIT. He is also an Associate Editor for the IEEE Transactions on Signal and Information Processing over Networks, IEEE Transactions on Signal Processing, Elsevier’s Signal Processing. Hoi-To’s research interests are in the broad area of signal processing, machine learning and stochastic optimization. His dissertation has received the 2017’s Dean’s Dissertation Award from the Ira A. Fulton Schools of Engineering of ASU and he is a recipient of Best Student Paper Awards at ICASSP 2018, SAM 2024 (as a co-author), ICASSP 2025 (as a co-author).