Communication Efficient Curvature Aided Primal-Dual Algorithms for Decentralized Optimization

• 成果类型: Article
• 署名作者: Li, Yichuan; Voulgaris, Petros G.; Stipanovic, Dusan M.; Freris, Nikolaos M.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; Nevada System of Higher Education (NSHE); University of Nevada Reno; Chinese Academy of Sciences; University of Science & Technology of China, CAS
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3244904
• 发表日期: 2023
• 页码: 6573-6588
• 关键词: Asynchronous algorithms; Control; decentralized optimization; Network analysis; primal-dual algorithms.

摘要

This article presents a family of algorithms for decentralized convex composite problems. We consider the setting of a network of agents that cooperatively minimize a global objective function composed of a sum of local functions plus a regularizer. Through the use of intermediate consensus variables, we remove the need for inner communication loops between agents when computing curvature-guided updates. A general scheme is presented, which unifies the analysis for a plethora of computing choices, including gradient descent, Newton updates, and Broyden, Fletcher, Goldfarb, and Shanno updates. Our analysis establishes sublinear convergence rates under convex objective functions with Lipschitz continuous gradients, as well as linear convergence rates when the local functions are further assumed to be strongly convex. Moreover, we explicitly characterize the acceleration due to curvature information. Last but not the least, we present an asynchronous implementation for the proposed algorithms, which removes the need for a central clock, with linear convergence rates established in expectation under strongly convex objectives. We ascertain the effectiveness of the proposed methods with numerical experiments on benchmark datasets.