Robust convergence analysis of distributed optimization algorithms
Robust convergence analysis of distributed optimization algorithms
复制标题
DOI：
10.1109/allerton.2017.8262874
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Akhil Sundararajan;B. Hu;Laurent Lessard
中科院分区：
文献类型：
--
作者：
Akhil Sundararajan;B. Hu;Laurent Lessard
通过构造一个半定规划(SDP)，我们给出了一个分析分布式优化算法收敛的统一框架，该规划可以有效地求解以限制线性收敛速度。考虑了两种不同的SDP配方。首先，我们建立了一个显式依赖于网络图的八卦矩阵的SDP。此结果提供了明确依赖于图形拓扑的界限，但SDP维度随图形的大小而扩展。其次，我们构造了一个通过八卦矩阵的光谱间隙隐含地依赖于八卦矩阵的SDP。这一结果提供了更粗略的界限，但产生了与图形大小无关的较小的SDP。我们的方法改进了我们分析的算法的现有界限，数值模拟表明我们的界限可能很紧。我们分析的高效和自动化性质使其成为算法选择和调整以及发现新算法的强大工具。
We present a unified framework for analyzing the convergence of distributed optimization algorithms by formulating a semidefinite program (SDP) which can be efficiently solved to bound the linear rate of convergence. Two different SDP formulations are considered. First, we formulate an SDP that depends explicitly on the gossip matrix of the network graph. This result provides bounds that depend explicitly on the graph topology, but the SDP dimension scales with the size of the graph. Second, we formulate an SDP that depends implicitly on the gossip matrix via its spectral gap. This result provides coarser bounds, but yields a small SDP that is independent of graph size. Our approach improves upon existing bounds for the algorithms we analyzed, and numerical simulations reveal that our bounds are likely tight. The efficient and automated nature of our analysis makes it a powerful tool for algorithm selection and tuning, and for the discovery of new algorithms as well.