Success and Failure of Adaptation-Diffusion Algorithms With Decaying Step Size in Multiagent Networks

This paper investigates the problem of distributed stochastic approximation in multiagent systems. The algorithm under study consists of two steps: A local stochastic approximation step and a diffusion step, which drives the network to a consensus. The diffusion step uses row-stochastic matrices to weight the network exchanges. As opposed to previous works, exchange matrices are not supposed to be doubly stochastic, and may also depend on the past estimate. We prove that nondoubly stochastic matrices generally influence the limit points of the algorithm. Nevertheless, the limit points are not affected by the choice of the matrices provided that the latter are doubly stochastic in expectation. This conclusion legitimates the use of broadcast-like diffusion protocols, which are easier to implement. Next, by means of a central limit theorem, we prove that doubly stochastic protocols perform asymptotically as well as centralized algorithms and we quantify the degradation caused by the use of nondoubly stochastic matrices. Throughout this paper, a special emphasis is put on the special case of distributed nonconvex optimization as an illustration of our results.