Towards accelerated rates for distributed optimization over time-varying networks

Abstract

We study the problem of decentralized optimization over time-varying networks with strongly convex smooth cost functions. In our approach, nodes run a multi-step gossip procedure after making each gradient update, thus ensuring approximate consensus at each iteration, while the outer loop is based on accelerated Nesterov scheme. The algorithm achieves precision $\epsilon >0$ in $O(\sqrt{{\kappa }_g}\chi {\log }^2(1/\epsilon ))$ communication steps and $O(\sqrt{{\kappa }_g}\log (1/\epsilon ))$ gradient computations at each node, where ${\kappa }_g$ is the global function number and $\chi$ characterizes connectivity of the communication network. In the case of a static network, $\chi =1/\gamma$ where $\gamma$ denotes the normalized spectral gap of communication matrix $\mathbf{W}$. The complexity bound includes ${\kappa }_g$, which can be significantly better than the worst-case condition number among the nodes.