Stochastic Approximation for Consensus: A New Approach via Ergodic Backward Products
Author:
- 14 May 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 57 (12) , 2994-3008
Abstract
This paper considers both synchronous and asynchronous consensus algorithms with noisy measurements. For stochastic approximation based consensus algorithms, the existing convergence analysis with dynamic topologies heavily relies on quadratic Lyapunov functions, whose existence, however, may be difficult to ensure for switching directed graphs. Our main contribution is to introduce a new analytical approach. We first show a fundamental role of ergodic backward products for mean square consensus in algorithms with additive noise. Subsequently, we develop ergodicity results for backward products of degenerating stochastic matrices converging to a 0-1 matrix via a discrete time dynamical system approach. These results complement the existing ergodic theory of stochastic matrices and provide an effective tool for analyzing consensus problems. Under a joint connectivity assumption, our approach may deal with switching topologies, delayed measurements and correlated noises, and it does not require the double stochasticity condition typically assumed for the existence of quadratic Lyapunov functions.Keywords
This publication has 42 references indexed in Scilit:
- Stochastic consensus over noisy networks with Markovian and arbitrary switchesAutomatica, 2010
- Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic SignalsIEEE Transactions on Signal Processing, 2007
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- Structure theorems for partially asynchronous iterations of a nonnegative matrix with random delaysSādhanā, 1999
- Asynchronous stochastic approximation and Q-learningMachine Learning, 1994
- Convergence of sequential and asynchronous nonlinear paracontractionsNumerische Mathematik, 1992
- Stochastic approximation algorithms for parallel and distributed processingStochastics, 1987
- Distributed asynchronous deterministic and stochastic gradient optimization algorithmsIEEE Transactions on Automatic Control, 1986
- Products of Indecomposable, Aperiodic, Stochastic MatricesProceedings of the American Mathematical Society, 1963