We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. Specifically, we place ourselves in an asynchronous model where only a random portion of nodes perform computation at each iteration, while the information exchange can be conducted between all the nodes and in an asymmetric fashion. For this setting, we propose an algorithm that combines gradient tracking and variance reduction over the entire network. This enables each node to track the average of the gradients of the objective functions. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex, under mild connectivity conditions on the expected mixing matrices. In particular, our result does not require the mixing matrices to be doubly stochastic. In the experiments, we investigate a broadcast mechanism that transmits information from computing nodes to their neighbors, and confirm the linear convergence of our method on both synthetic and real-world datasets.
翻译:我们考虑了分散化优化问题,其中一些代理商通过交换一个基本通信图来合作尽量减少其本地功能的平均值。 具体地说,我们把自己置于一个无同步模式中,只有节点的随机部分在每次迭代中进行计算,而信息交流可以在所有节点之间以不对称的方式进行。 对于这一环境,我们建议一种算法,将整个网络的梯度跟踪和差异减少结合起来。这使每个节点能够跟踪目标函数的梯度平均值。我们的理论分析表明,当本地目标函数在预期的混合矩阵上处于温和连通性条件下时,算法会线性地趋同。特别是,我们的结果并不要求混合矩阵具有双重性。在实验中,我们调查一个将信息从计算节点传送到邻居的广播机制,并证实我们在合成和真实世界数据集上的方法的线性融合。