# Robust Learning of Fixed-Structure Bayesian Networks

arXiv: https://arxiv.org/abs/1606.07384 · HTML: https://mlsanity.com/paper/1606.07384/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2016.

## Built on by (most cited first, 8 of 8)

- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [MBGDT:Robust Mini-Batch Gradient Descent](https://mlsanity.com/paper/2206.07139/) (2022)

## Abstract (arXiv)

We investigate the problem of learning Bayesian networks in a robust model where an ε-fraction of the samples are adversarially corrupted. In this work, we study the fully observable discrete case where the structure of the network is given. Even in this basic setting, previous learning algorithms either run in exponential time or lose dimension-dependent factors in their error guarantees. We provide the first computationally efficient robust learning algorithm for this problem with dimension-independent error guarantees. Our algorithm has near-optimal sample complexity, runs in polynomial time, and achieves error that scales nearly-linearly with the fraction of adversarially corrupted samples. Finally, we show on both synthetic and semi-synthetic data that our algorithm performs well in practice.