A Communication-Efficient Algorithm for Exponentially Fast Non-Bayesian Learning in Networks
This work addresses communication bottlenecks in distributed learning for multi-agent systems, offering incremental improvements in efficiency and performance.
The paper tackles the problem of communication-efficient non-Bayesian learning in networks by proposing a distributed algorithm with geometrically increasing communication intervals, showing that agents can rule out false hypotheses exponentially fast with probability 1 for finite intervals. It demonstrates that when communication occurs at every time-step, the learning rates are network-structure independent and improve upon existing methods, while for sparse communication, rates depend on network topology and signal structures, with optimal allocations analyzed using graph centrality measures.
We introduce a simple time-triggered protocol to achieve communication-efficient non-Bayesian learning over a network. Specifically, we consider a scenario where a group of agents interact over a graph with the aim of discerning the true state of the world that generates their joint observation profiles. To address this problem, we propose a novel distributed learning rule wherein agents aggregate neighboring beliefs based on a min-protocol, and the inter-communication intervals grow geometrically at a rate $a \geq 1$. Despite such sparse communication, we show that each agent is still able to rule out every false hypothesis exponentially fast with probability $1$, as long as $a$ is finite. For the special case when communication occurs at every time-step, i.e., when $a=1$, we prove that the asymptotic learning rates resulting from our algorithm are network-structure independent, and a strict improvement upon those existing in the literature. In contrast, when $a>1$, our analysis reveals that the asymptotic learning rates vary across agents, and exhibit a non-trivial dependence on the network topology coupled with the relative entropies of the agents' likelihood models. This motivates us to consider the problem of allocating signal structures to agents to maximize appropriate performance metrics. In certain special cases, we show that the eccentricity centrality and the decay centrality of the underlying graph help identify optimal allocations; for more general scenarios, we bound the deviation from the optimal allocation as a function of the parameter $a$, and the diameter of the communication graph.