Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

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

Submitted

Overview

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.

We found our algorithm the most communication efficient one. 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 using this approach use diminishing step sizes, slowly converging to the optimal solution.

(Walkman visits nodes randomly) 
(Walkman visits nodes randomly)

Our method Walkman 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.

(Above: Comparisons on decentralized least squares) 
(Above: Comparisons on decentralized least squares)
(Above: Comparisons on decentralized nonnegative PCA) 
(Above: Comparisons on decentralized nonnegative PCA)

Citation

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


« Back