Research map / Learning theory and algorithms / Sample complexity

Learnability of Parameter-Bounded Bayes Nets

AAAI 2025 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of ranking and selection · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that finding a parameter-bounded Bayes net for a distribution is NP-hard even under the promise that one exists, and gives a sample complexity bound for TV-approximating such a Bayes net.

Problem

Given a distribution known to be Markov with respect to some Bayes net with at most p parameters, finding such a Bayes net is computationally hard; also, how many samples suffice to learn a close parameter-bounded Bayes net.

Approach

Extends the Chickering et al. NP-hardness of LEARN to a promise search variant (REALIZABLE-LEARN) via a reduction from degree-bounded feedback arc set using an independence oracle, and generalizes the degree-bounded sample complexity of Brustle et al. to a parameter-bounded setting via an epsilon-net over DAGs and conditional distributions plus Scheffé tournaments.

Key results

• REALIZABLE-LEARN (promise search version of LEARN) is NP-hard, even given an independence oracle.
• Parameter-bounded Bayes nets can be TV-approximated from O(log(1/delta)/eps^2 (p log(n|Sigma|/eps) + n log(p/(n(|Sigma|-1)))/log|Sigma| log n)) samples, generalizing the degree-bounded bound of Brustle et al.

Limitations

• Hardness is for exact parameter bound; a multiplicative gap (alpha*p parameters) is left open.
• Sample algorithm has exponential dependency on the number of samples/candidate-set size (candidate count is exponential in n-related quantities).

Experimental setup

Builds on: LEARN NP-hardness (Chickering et al. 2004) Brustle et al. 2020 degree-bounded sample complexity Scheffé tournament DBFAS NP-hardness

Closest papers by meaning

• Learning Bayesian Networks with Bounded Tree-width via Guided Search (AAAI 2016 · similarity 0.86)
• Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables (NeurIPS 2016 · similarity 0.86)
• PAC-Bayes Learning Bounds for Sample-Dependent Priors (NeurIPS 2020 · similarity 0.86)
• The Complexity of Bayesian Network Learning: Revisiting the Superstructure (NeurIPS 2021 · similarity 0.86)
• Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.85)
• On the Hardness of Approximating Distributions with Tractable Probabilistic Models (NeurIPS 2025 · similarity 0.84)