A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Wotao Yin, Xianghui Mao, Kun Yuan, Yuantao Gu, and Ali H. Sayed



This paper addresses consensus optimization problem in a multi-agent network, where all the agents collaboratively find a common minimizer to the sum of their private functions. We develop a decentralized algorithm in which there is no center agent and every agent only communicates with its neighbors.

Our algorithm is more communication efficient than existing approaches. Existing decentralized algorithms for the same kind of problem use fixed step sizes but involve communications among either all, or a random subset, of the agents at each iteration. Another existing approach uses a random-walk incremental strategy, which activates a succession of nodes and their links, only one node and one link each time; unfortunately, the existing algorithms following this approach use diminishing step sizes, slowly converging to the optimal solution.

Our random-walk algorithm uses a fixed step size and converges much faster than the existing random-walk incremental algorithms. We derive our algorithm by modifying ADMM and analyze its convergence. We establish linear convergence for least squares problems, along with a state-of-the-art communication complexity. Numerical experiments support our claims.


W. Yin, X. Mao, K. Yuan, Y. Gu, and A. Sayed, A communication-efficient random-walk algorithm for decentralized optimization, UCLA CAM Report 18-19, 2018.

« Back