Automatic Performance Estimation for Decentralized Optimization

• 成果类型: Article
• 署名作者: Colla, Sebastien; Hendrickx, Julien M.
• 署名单位: Universite Catholique Louvain
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3251902
• 发表日期: 2023
• 页码: 7136-7150
• 关键词: CONSENSUS; distributed optimization; performance estimation problem (PEP); Rates Of Convergence; Worst-case analysis

摘要

In this article, we present a methodology to automatically compute worst-case performance bounds for a large class of first-order decentralized optimization algorithms. These algorithms aim at minimizing the average of local functions that are distributed across a network of agents. They typically combine local computations and consensus steps. Our methodology is based on the approach of performance estimation problem (PEP), which allows computing the worst-case performance and a worst-case instance of first-order optimization algorithms by solving a semidefinite program. We propose two ways of representing consensus steps in PEPs, which allow writing and solving PEPs for decentralized optimization. The first formulation is exact but specific to a given averaging matrix. The second formulation is a relaxation but provides guarantees valid over an entire class of averaging matrices, characterized by their spectral range. This formulation often allows recovering a posteriori the worst possible averaging matrix for the given algorithm. We apply our methodology to three different decentralized methods. For each of them, we obtain numerically tight worst-case performance bounds that significantly improve on the existing ones, as well as insights about the parameters tuning and the worst communication networks.