Skip to main navigation Skip to search Skip to main content

Distributed stochastic approximation: The price of non-double stochasticity

  • CNRS LTCI
  • CNRS UMR 5157 SAMOVAR

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationConference Record of the 46th Asilomar Conference on Signals, Systems and Computers, ASILOMAR 2012
PublisherIEEE Computer Society
Pages1473-1477
Number of pages5
ISBN (Print)9781467350518
DOIs
Publication statusPublished - 1 Jan 2012
Externally publishedYes
Event46th Asilomar Conference on Signals, Systems and Computers, ACSSC 2012 - Pacific Grove, CA, United States
Duration: 4 Nov 2012 → 7 Nov 2012

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393

Conference

Conference46th Asilomar Conference on Signals, Systems and Computers, ACSSC 2012
Country/TerritoryUnited States
CityPacific Grove, CA
Period4/11/12 → 7/11/12

Fingerprint

Dive into the research topics of 'Distributed stochastic approximation: The price of non-double stochasticity'. Together they form a unique fingerprint.

Cite this