Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear
  Time
  We study the problem of learning Bayesian networks where an
$\epsilon$-fraction of the samples are adversarially corrupted. We focus on the
fully-observable case where the underlying graph structure is known. In this
work, we present the first nearly-linear time algorithm for this problem with a
dimension-independent error guarantee. Previous robust algorithms with
comparable error guarantees are slower by at least a factor of $(d/\epsilon)$,
where $d$ is the number of variables in the Bayesian network and $\epsilon$ is
the fraction of corrupted samples.
  Our algorithm and analysis are considerably simpler than those in previous
work. We achieve this by establishing a direct connection between robust
learning of Bayesian networks and robust mean estimation. As a subroutine in
our algorithm, we develop a robust mean estimation algorithm whose runtime is
nearly-linear in the number of nonzeros in the input samples, which may be of
independent interest.
