Distributed stochastic approximation: The price of non-double stochasticity

This paper investigates the problem of distributed stochastic approximation in multi-agent systems. The algorithm under study consists of two steps: a local stochastic approximation step at each agent and a gossip step which drives the network to a consensus. The gossip step uses row-stochastic matrices to weight network exchanges. Gossip-matrices are often also assumed column-stochastic in the literature. Unfortunately, column-stochasticity implies significant restrictions on the communication protocol and prevents from using simple broadcast protocols. Under the assumption of decreasing step sizes, it is proved that the network is driven to a consensus at overwhelming speed and that the average estimate converges to the sought consensus. When the gossip matrices are doubly stochastic, a central limit theorem is established and it is proved that the performance of the algorithm is identical to that of a centralized algorithm. When the gossip matrices are non doubly stochastic, an excess variance term is added to the limiting distribution. In that case, a performance gap w.r.t. the centralized algorithm exists and is characterized.