We develop a methodology to automatically compute worst-case performance bounds for a class of decentralized algorithms that optimize the average of local functions distributed across a network. We extend the recently proposed PEP approach to decentralized optimization. This approach allows computing the exact worst-case performance and worst-case instance of centralized algorithms by solving an SDP. We obtain an exact formulation when the network matrix is given, and a relaxation when considering entire classes of network matrices characterized by their spectral range. We apply our methodology to the decentralized (sub)gradient method, obtain a nearly tight worst-case performance bound that significantly improves over the literature, and gain insights into the worst communication networks for a given spectral range.
翻译:我们开发了一种方法来自动计算最坏的性能极限,用于一系列分散式算法,优化整个网络分布的当地功能的平均数。我们将最近提出的PEP方法扩大到分散式优化。这种方法通过解决一个SDP,可以计算准确的最坏的性能和最坏的集中式算法实例。当给出网络矩阵时,我们得到精确的表述,在考虑以其光谱范围为特征的全类网络矩阵时,我们得到放松。我们将我们的方法应用到分散式(子)分级法,获得近乎紧凑的最坏式的性能,大大改进文献,并深入了解特定光谱范围最差的通信网络。