Network independent rates in distributed learning
Angelia Nedić, Alex Olshevsky, César A. Uribe · 2016
We propose a novel belief update algorithm for Distributed Non-Bayesian learning over time-varying directed graphs, where a group of agents tries to collectively select a distribution that best describes the observed data. We show that the proposed update rule, inspired by the Push-Sum algorithm, is consistent; moreover we provide an explicit characterization of its convergence rate. Our main result states that, after a transient time, all agents will concentrate their beliefs at a network independent rate. Network independent rates were not available for other consensus based distributed learning algorithms on time-varying directed graphs.