mlsanityData to 14 Oct 2026

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

arXiv 2105.05555 ↗First posted 12 May 2021cs.LG cs.DS math.STcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 29 of its 53 references that are in the map. First posted on arXiv 12 May 2021.

Builds on

29 of 53 references.

References · 29

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 125
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  5. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  6. 2016Learning from Untrusted Datacited by 90
  7. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  8. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  9. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  10. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  11. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  12. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
17 more
  1. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  2. 2015Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Modelcited by 47
  3. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  4. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  5. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  6. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  7. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 32
  8. 2018High Dimensional Robust Sparse Regressioncited by 29
  9. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  10. 2016Testing Bayesian Networkscited by 23
  11. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  12. 2020Robust estimation via generalized quasi-gradientscited by 19
  13. 2020List-Decodable Mean Estimation in Nearly-PCA Timecited by 17
  14. 2020High-Dimensional Robust Mean Estimation via Gradient Descentcited by 16
  15. 2020Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Timecited by 9
  16. 2014Structure learning of antiferromagnetic Ising modelscited by 8
  17. 2016Robust Learning of Fixed-Structure Bayesian Networkscited by 8

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Distribution Learning Meets Graph Structure Samplingcited by 1