Push-Pull With Device Sampling

• 成果类型: Article
• 署名作者: Hsieh, Yu-Guan; Laguel, Yassine; Iutzeler, Franck; Malick, Jerome
• 署名单位: Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Rutgers University System; Rutgers University New Brunswick; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3250339
• 发表日期: 2023
• 页码: 7179-7194
• 关键词: Convex optimization; decentralized optimization; device sampling; random gossip

摘要

We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking with a network-level variance reduction (in contrast to variance reduction within each node). This enables the nodes to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors and confirm the linear convergence of our method on both synthetic and real-world datasets.