Towards accelerated rates for distributed optimization over time-varying networks

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 varepsilon > 0 in O(√kappagchilog2(1/varepsilon)) communication steps and O(√kappaglog(1/varepsilon)) gradient computations at each node, where kappag is the global function number and chi characterizes connectivity of the communication network. In the case of a static network, chi = 1/γ where γ denotes the normalized spectral gap of communication matrix W. The complexity bound includes kappag, which can be significantly better than the worst-case condition number among the nodes.