Семинар HDI&TFAIM Lab «Communication Efficient Algorithms for Decentralized Optimization: Stochastic Approximation Approach and Beyond»

Abstract. This talk presents a stochastic approximation (SA) perspective for the design of communication-efficient decentralized optimization on time-varying communication graphs. We demonstrate a flexible framework utilizing a primal-dual algorithm that naturally accounts for randomness in communication graphs, which motivates a set of communication-efficient algorithms. Focusing on smooth (possibly non-convex) problems, we first illustrate 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 the primal-dual SA scheme with majorization-minimization naturally 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.

Bio: 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 currently an Associate Editor for the IEEE Transactions on Signal Processing and Elsevier’s Signal Processing, and has previously served on the editorial board of IEEE Transactions on Signal and Information Processing over Networks. 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).

По всем вопросам обращайтесь к Зеленовой Карине Михайловне kzelenova@hse.ru или к Горностаевой Екатерине Дмитриевне egornostaeva@hse.ru