Decentralized optimization, particularly the class of decentralized composite convex optimization (DCCO) problems, has found many applications. Due to ubiquitous communication congestion and random dropouts in practice, it is highly desirable to design decentralized algorithms that can handle stochastic communication networks. However, most existing algorithms for DCCO only work in time-invariant networks and cannot be extended to stochastic networks because they inherently need knowledge of network topology $\textit{a priori}$. In this paper, we propose a new decentralized dual averaging (DDA) algorithm that can solve DCCO in stochastic networks. Under a rather mild condition on stochastic networks, we show that the proposed algorithm attains $\textit{global linear convergence}$ if each local objective function is strongly convex. Our algorithm substantially improves the existing DDA-type algorithms as the latter were only known to converge $\textit{sublinearly}$ prior to our work. The key to achieving the improved rate is the design of a novel dynamic averaging consensus protocol for DDA, which intuitively leads to more accurate local estimates of the global dual variable. To the best of our knowledge, this is the first linearly convergent DDA-type decentralized algorithm and also the first algorithm that attains global linear convergence for solving DCCO in stochastic networks. Numerical results are also presented to support our design and analysis.
翻译:分散式优化, 特别是分散式组合组合优化( DCCO) 问题, 已经找到许多应用。 由于通信拥堵和实践中随机辍学现象普遍存在, 设计分散式算法非常可取, 可以处理随机通信网络。 但是, DCCO 的大多数现有算法只能在时间变化网络中工作, 无法扩展至随机网络, 因为后者本身需要网络地形学知识 $\ textit{ a subline $ 。 在本文中, 我们提出一个新的分散式双均价( DDA) 算法, 可以在随机网络中解决DCCO 。 在随机网络中, 在相当温和的条件下, 我们非常理想的算法可以达到 $\ textitit{ global 趋同 。 我们的算法大大改进了现有的DADR类型算法, 因为后者在我们工作之前只知道将 $\ textitilit{ asubly rial $。 。 实现改进率的关键是设计一个新的动态平均一致式协议, 这在随机性网络中, 我们的直线性地导致更精确地将全球设计一个稳定的系统趋一致的排序。