Network Fault-tolerant and Byzantine-resilient Social Learning via
  Collaborative Hierarchical Non-Bayesian Learning
Connor Mclaughlin Matthew Ding Denis Edogmus Lili Su
As the network scale increases, existing fully distributed solutions start to
lag behind the real-world challenges such as (1) slow information propagation,
(2) network communication failures, and (3) external adversarial attacks. In
this paper, we focus on hierarchical system architecture and address the
problem of non-Bayesian learning over networks that are vulnerable to
communication failures and adversarial attacks. On network communication, we
consider packet-dropping link failures.
  We first propose a hierarchical robust push-sum algorithm that can achieve
average consensus despite frequent packet-dropping link failures. We provide a
sparse information fusion rule between the parameter server and arbitrarily
selected network representatives. Then, interleaving the consensus update step
with a dual averaging update with Kullback-Leibler (KL) divergence as the
proximal function, we obtain a packet-dropping fault-tolerant non-Bayesian
learning algorithm with provable convergence guarantees.
  On external adversarial attacks, we consider Byzantine attacks in which the
compromised agents can send maliciously calibrated messages to others
(including both the agents and the parameter server). To avoid the curse of
dimensionality of Byzantine consensus, we solve the non-Bayesian learning
problem via running multiple dynamics, each of which only involves Byzantine
consensus with scalar inputs. To facilitate resilient information propagation
across sub-networks, we use a novel Byzantine-resilient gossiping-type rule at
the parameter server.