We develop a novel formulation of the Performance Estimation Problem (PEP) for decentralized optimization whose size is independent of the number of agents in the network. The PEP approach allows computing automatically the worst-case performance and worst-case instance of first-order optimization methods by solving an SDP. Unlike previous work, the size of our new PEP formulation is independent of the network size. For this purpose, we take a global view of the decentralized problem and we also decouple the consensus subspace and its orthogonal complement. We apply our methodology to different decentralized methods such as DGD, DIGing and EXTRA and obtain numerically tight performance guarantees that are valid for any network size.
翻译：我们为分散化优化开发了一种新型的“绩效估计问题”,其规模不取决于网络中的代理商数量。PEP方法允许通过解决 SDP 自动计算最坏的绩效和最坏的一阶优化方法。与以往的工作不同,我们新的PEP配置的规模不取决于网络的规模。为此,我们从全球的角度看待分散化问题,我们也将协商一致的子空间及其正向补充部分脱钩。我们运用我们的方法来应用不同的分散化方法,如DGD、Digiging和EXTRA, 并获得对网络规模都有效的、在数字上紧凑的绩效保证。
相关内容
微信扫码咨询专知VIP会员