mlsanityData to 14 Oct 2026

Near-Optimal Degree Testing for Bayes Nets

arXiv 2304.06733 ↗First posted 13 Apr 2023cs.LG cs.DS cs.ITcited by 3

Not on the map. Why?

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.

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

16 of 28 references.

References · 16

  1. 2021Convex optimizationcited by 2,515
  2. 2020A Tutorial on Learning With Bayesian Networkscited by 57
  3. 2015Optimal Testing for Properties of Distributionscited by 36
  4. 2018Learning and Testing Causal Models with Interventionscited by 29
  5. 2016Testing Ising Modelscited by 23
  6. 2016Testing Bayesian Networkscited by 23
  7. 2020Near-Optimal Learning of Tree-Structured Distributions by Chow-Liucited by 20
  8. 2017Which Distribution Distances are Sublinearly Testable?cited by 14
  9. 2016Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testingcited by 11
  10. 2022Learning and Testing Latent-Tree Ising Models Efficientlycited by 7
  11. 2023Concentration Bounds for Discrete Distribution Estimation in KL Divergencecited by 7
  12. 2019Lower bounds for testing graphical models: colorings and antiferromagnetic Ising modelscited by 6
4 more
  1. 2017Concentration of Multilinear Functions of the Ising Model with Applications to Network Datacited by 5
  2. 2022Independence Testing for Bounded Degree Bayesian Networkcited by 5
  3. 2022Near-Optimal Bounds for Testing Histogram Distributionscited by 4
  4. 2017Property Testing in High Dimensional Ising modelscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 0; 2025: 1.

3 papers.

  1. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  2. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  3. 2025Estimation of discrete distributions with high probability under chi2-divergencecited by 1