## Walkman: A Communication-Efﬁcient Random-Walk Algorithm for Decentralized OptimizationXianghui Mao, Kun Yuan, Yubin Hu, Yuantao Gu, Ali H. Sayed, Wotao YinSubmitted ## OverviewThis 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.
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.
## Citation
« Back |