Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time
This addresses robust learning for Bayesian networks in the presence of adversarial noise, offering a significant speedup for applications in data analysis, though it is incremental as it builds on prior robust learning techniques.
The paper tackles the problem of learning Bayesian networks with adversarial corruptions in samples, presenting a nearly-linear time algorithm with dimension-independent error guarantees, achieving a runtime improvement by a factor of (d/ε) compared to previous methods.
We study the problem of learning Bayesian networks where an $ε$-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/ε)$, where $d$ is the number of variables in the Bayesian network and $ε$ 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.