Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time

2021/05/12 by Cheng, Yu, Lin, Honghao
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2105.05555

Abstract

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.

Related

• Robust Learning of Fixed-Structure Bayesian Networks
• High-Dimensional Robust Mean Estimation in Nearly-Linear Time
• Structure Learning in Bayesian Networks of Moderate Size by Efficient Sampling
• Unsupervised Learning of Noisy-Or Bayesian Networks
• Large-Sample Learning of Bayesian Networks is NP-Hard