  We consider distributed optimization where $N$ nodes in a connected network
minimize the sum of their local costs subject to a common constraint set. We
propose a distributed projected gradient method where each node, at each
iteration $k$, performs an update (is active) with probability $p_k$, and stays
idle (is inactive) with probability $1-p_k$. Whenever active, each node
performs an update by weight-averaging its solution estimate with the estimates
of its active neighbors, taking a negative gradient step with respect to its
local cost, and performing a projection onto the constraint set; inactive nodes
perform no updates. Assuming that nodes' local costs are strongly convex, with
Lipschitz continuous gradients, we show that, as long as activation probability
$p_k$ grows to one asymptotically, our algorithm converges in the mean square
sense (MSS) to the same solution as the standard distributed gradient method,
i.e., as if all the nodes were active at all iterations. Moreover, when $p_k$
grows to one linearly, with an appropriately set convergence factor, the
algorithm has a linear MSS convergence, with practically the same factor as the
standard distributed gradient method. Simulations on both synthetic and real
world data sets demonstrate that, when compared with the standard distributed
gradient method, the proposed algorithm significantly reduces the overall
number of per-node communications and per-node gradient evaluations
(computational cost) for the same required accuracy.
