Decentralized Proximal Gradient Algorithms With Linear Convergence Rates

• 成果类型: Article
• 署名作者: Alghunaim, Sulaiman A.; Ryu, Ernest K.; Yuan, Kun; Sayed, Ali H.
• 署名单位: Kuwait University; Seoul National University (SNU); Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3009363
• 发表日期: 2021
• 页码: 2787-2794
• 关键词: Symmetric matrices; CONVERGENCE; ELECTRONIC MAIL; cost function; Convex functions; Approximation algorithms; decentralized optimization; diffusion; gradient tracking; linear convergence; proximal gradient algorithms; unified decentralized algorithm

摘要

This article studies a class of nonsmooth decentralized multiagent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common nonsmooth term. We propose a general primal-dual algorithmic framework that unifies many existing state-of-the-art algorithms. We establish linear convergence of the proposed method to the exact minimizer in the presence of the nonsmooth term. Moreover, for the more general class of problems with agent specific nonsmooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and nonsmooth parts, respectively. We further provide a numerical counterexample that shows how some state-of-the-art algorithms fail to converge linearly for strongly convex objectives and different local non smooth terms.