A Dual Accelerated Method for Online Stochastic Distributed Averaging: From Consensus to Decentralized Policy Evaluation

• 成果类型: Article
• 署名作者: Zhang, Sheng; Pananjady, Ashwin; Romberg, Justin
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3562997
• 发表日期: 2025
• 页码: 6869-6876
• 关键词: STOCHASTIC PROCESSES; sensors; vectors; optimization; CONVERGENCE; Complexity theory; Distributed databases; Covariance matrices; training; Noise measurement; Accelerated methods; decentralized sensing; Distributed averaging; distributed optimization; multi-agent networks; Policy Evaluation

摘要

Motivated by decentralized sensing and policy evaluation problems, we consider a particular type of distributed stochastic optimization problem over a network, called the online stochastic distributed averaging problem. We design and analyze a dual-based, Polyak-Ruppert averaged method for this problem. We show that the proposed algorithm attains an accelerated deterministic error depending optimally on the condition number of the network, and also that it has optimal stochastic error. This improves on the guarantees of state-of-the-art distributed stochastic optimization algorithms when specialized to this setting, and yields-among other things-corollaries for decentralized policy evaluation. Numerical experiments validate our theoretical results and demonstrate that our approach outperforms existing methods in finite-sample scenarios on several natural network topologies.