2020/09/23 by Rogozin, Alexander, Lukoshkin, Vladislav, Gasnikov, Alexander +2
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2009.11069
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 ε > 0 in O(√(κg)χlog2(1/ε)) communication steps and O(√(κg)log(1/ε)) gradient computations at each node, where κg is the global function number and χ characterizes connectivity of the communication network. In the case of a static network, χ= 1/γ where γ denotes the normalized spectral gap of communication matrix W. The complexity bound includes κg, which can be significantly better than the worst-case condition number among the nodes.