Distributed stochastic approximation: the cost of non-bistochasticity.

Summary We are interested in the problem of stochastic approximation in a distributed context. The iterative algorithm under study consists of two steps: a local stochastic approximation step performed by each agent, and a gossip step consisting of weighted averages of the local estimates. The matrix of weights used in the gossip step is assumed to be stochastic per row. We relax the bistochasticity assumption to have less restrictive communication protocols and characterize the resulting performance degradation.