# Near-Optimal Degree Testing for Bayes Nets

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 28 references that are in the map.
- First posted on arXiv 13 Apr 2023.

## Builds on (most cited first, 16 of 16)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Tutorial on Learning With Bayesian Networks](https://mlsanity.com/paper/2002.00269/) (2020)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Concentration Bounds for Discrete Distribution Estimation in KL Divergence](https://mlsanity.com/paper/2302.06869/) (2023)
- [Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models](https://mlsanity.com/paper/1901.07361/) (2019)
- [Concentration of Multilinear Functions of the Ising Model with Applications to Network Data](https://mlsanity.com/paper/1710.04170/) (2017)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Property Testing in High Dimensional Ising models](https://mlsanity.com/paper/1709.06688/) (2017)

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

- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach](https://mlsanity.com/paper/2305.13289/) (2023)
- [Estimation of discrete distributions with high probability under chi2-divergence](https://mlsanity.com/paper/2510.25400/) (2025)

## Abstract (arXiv)

This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution P over 0,1n, given sample access to P. We show that the sample complexity of the problem is tildeTheta(2n/2/varepsilon2). Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers; in order to apply this framework, we develop new algorithms for ``near-proper'' learning of Bayes nets, and high-probability learning under chi2 divergence, which are of independent interest.