  This paper addresses consensus optimization problems in a multi-agent
network, where all agents collaboratively find a minimizer for the sum of their
private functions. We develop a new decentralized algorithm in which each agent
communicates only with its neighbors.
  State-of-the-art decentralized algorithms use communications between either
all pairs of adjacent agents or a random subset of them at each iteration.
Another class of algorithms uses a random walk incremental strategy, which
sequentially activates a succession of nodes; these incremental algorithms
require diminishing step sizes to converge to the solution, so their
convergence is relatively slow.
  In this work, we propose a random walk algorithm that uses a fixed step size
and converges faster than the existing random walk incremental algorithms. Our
algorithm is also communication efficient. Each iteration uses only one link to
communicate the latest information for an agent to another. Since this
communication rule mimics a man walking around the network, we call our new
algorithm Walkman. We establish convergence for convex and nonconvex
objectives. For decentralized least squares, we derive a linear rate of
convergence and obtain a better communication complexity than those of other
decentralized algorithms. Numerical experiments verify our analysis results.
