Nonasymptotic convergence rates for cooperative learning over time-varying directed graphs

By Angelia Nedić, Alexander Olshevsky, César A. Uribe. 2014

95 citations recorded by the source corpus.

We study the problem of cooperative learning with a network of agents where some agents repeatedly access information about a random variable with unknown distribution. The group objective is to globally agree on a joint hypothesis (distribution) that best describes the observed data at all nodes. The agents interact with their neighbors in an unknown sequence of time-varying directed graphs. Following the pioneering work of Jadbabaie, Molavi, Sandroni, and Tahbaz-Salehi and others, we propose local learning dynamics which combine Bayesian updates at each node with a local aggregation rule of private agent signals. We show that these learning dynamics drive all agents to the set of hypotheses which best explain the data collected at all nodes as long as the sequence of interconnection graphs is uniformly strongly connected. Our main result establishes a non-asymptotic, explicit, geometric convergence rate for the learning dynamic.

Subfields: Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Decentralized Bayesian Learning over Graphs (2019, positive): “Our theoretical and conceptual contributions are as follows: (i) Our decentralized learning rule generalizes a learning rule considered in the social literature [1–3] by restricting the posterior distribution to a predetermined family of distributions for computational tractability.”
Peer-to-peer Federated Learning on Graphs (2019, methodology): “…in statistics, economics, and operations research and encompasses canonical problems of consensus DeGroot (1974), belief propagation (Olfati-Saber et al., 2005), and distributed hypothesis testing (Jad-babaie et al., 2013; Nedi ´ c et al., 2015; Shahrampour et al., 2016; Lalitha et al., 2018).”
Defending non-Bayesian learning against adversarial attacks (2016, positive): “The existing non-Bayesian learning algorithms [10,11,13,14,15,16,17,18] are not robust to Byzantine agents, since the malicious messages sent by the Byzantine agents are indiscriminatingly utilized in the local belief updates.”
Social learning and distributed hypothesis testing (2014, result): “In a simultaneous and independent works [7] and [8], a slight variant of our learning rule in [9] is proposed and similar convergence results are obtained.”