Byzantine-Resilient Collaborative Hierarchical Non-Bayesian Learning

Non-Bayesian learning is a computationally efficient approximation of Bayesian learning over multi-agent networks. As the network scale increases, existing fully distributed solutions start to lag behind real-world challenges such as slow information propagation and external adversarial attacks. In this paper, we consider a hierarchical system architecture in which the agents are clustered into M sub-networks, and a parameter server exists to facilitate the information exchange among sub-networks. Utilizing a hierarchical structure to speed up con-vergence and enhance adversarial resilience is largely under-explored. Byzantine resilience suffers the curse of dimensionality - no Byzantine consensus algorithms can withstand a fraction of Byzantine agents exceeding either one-third of the total agents or the reciprocal of the input dimension plus one, whichever is smaller. To get around this, we solve the non-Bayesian learning problem by running multiple scalar dynamics. We propose a novel Byzantine-resilient gossiping-type rule at the parameter server to facilitate information propagation across sub-networks. We show that under some technical conditions, each normal agent can asymptotically identify the underlying truth hypothesis with probability one. Notably, our theory implies that even if there exists a sub-network whose majority of agents are Byzantine, our algorithm still enables successful learning for normal agents in such sub-networks.