论文标题
在线随机分布平均的双重加速方法：从共识到分散政策评估
A Dual Accelerated Method for Online Stochastic Distributed Averaging: From Consensus to Decentralized Policy Evaluation
论文作者
论文摘要
通过分散的感应和政策评估问题的激励，我们考虑了一种特定类型的分布式随机优化问题，即在网络上称为在线随机分布式平均问题。我们设计了一种基于双重分布式共识问题的方法，并使用Polyak-Ruppert平均并分析其行为。我们表明，所提出的算法根据网络的条件数量最佳地达到了加速的确定性误差，并且它具有最佳的随机误差。当专门针对此设置时，这可以改善最先进的分布式随机优化算法，并产生（除其他方面）的推论，以进行分散的政策评估。我们的证据依赖于明确研究几种相关线性系统的演变，并且可能具有独立的兴趣。提供了数值实验，从而验证了我们的理论结果，并证明我们的方法在几种自然网络拓扑的有限样本方案中优于现有方法。
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 a dual-based method for this distributed consensus problem with Polyak--Ruppert averaging and analyze its behavior. 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 an order-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. Our proofs rely on explicitly studying the evolution of several relevant linear systems, and may be of independent interest. Numerical experiments are provided, which validate our theoretical results and demonstrate that our approach outperforms existing methods in finite-sample scenarios on several natural network topologies.
