Research map / Learning theory and algorithms / Sample complexity
Distribution Learning Meets Graph Structure Sampling
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.
Links PAC-learning of Bayes nets in KL divergence to online learning (EWA/RWM) and efficient counting/sampling of DAGs and arborescences, yielding the first efficient agnostic learners for chordal-skeleton bounded-indegree Bayes nets and an improved tree learner.
Problem
Efficiently PAC-learning high-dimensional Bayesian networks (and trees/polytrees/chordal-skeleton models) in KL divergence with near-optimal sample complexity, where naive online-learning over exponentially many DAG experts is computationally intractable.
Approach
Reduce distribution learning to online prediction with expert weights over DAG structures, then use the fact that RWM/EWA weights factorize so that weighted counting/sampling of arborescences (matrix-tree theorem) and acyclic orientations (dynamic programming over clique trees for chordal graphs) makes the learner polynomial-time.
Key results
- Efficient agnostic proper and improper PAC-learners for Bayes nets with known chordal skeleton and indegree d using Õ(n^3/(ε²δ²)+nk^{d+1}/ε) and Õ(n^4/ε^4+nk^{d+1}/ε) samples, running in poly(n,k,1/ε,1/δ) time for constant d.
- Tree distribution learner in the realizable setting with Õ(nk²/ε) samples, improving the Chow-Liu bound Õ(nk³/ε) in k and matching the Ω(nk²) lower bound.
- Improper agnostic learner for bounded-indegree Bayes nets with Õ(nk^{d+1}/ε) samples, sample-optimal up to polylog factors but computationally inefficient.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed tree-structured learner instead of Chow–Liu | Tree-structured distributions · Tree, unknown skeleton; realizable | sample complexity dependence on alphabet size: \widetilde{O}(nk^3/\varepsilon) -> \widetilde{O}(nk^2\varepsilon^{-1}) | Helped |
Limitations
- Running time exponential in indegree d for unbounded d; sample complexity exponential dependence inevitable for unbounded indegree.
- Efficient algorithms require the skeleton to be known and chordal; general bounded-treewidth or unknown-DAG case left open.
- Proper learner has worse 1/δ² dependence; the efficient improper learner has polynomial but non-optimal dependence in n and ε.
Experimental setup
Metrics: sample complexity running time
Baselines: Chow-Liu Abbeel-Koller-Ng Bhattacharyya et al. add-one estimator
Builds on: Chow-Liu algorithm Exponential Weighted Average Randomized Weighted Majority add-one (Laplace) estimator
Closest papers by meaning
- Efficient Bayesian network structure learning via local Markov boundary search (NeurIPS 2021 · similarity 0.90)
- The Complexity of Bayesian Network Learning: Revisiting the Superstructure (NeurIPS 2021 · similarity 0.89)
- SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples (ICML 2021 · similarity 0.88)
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.86)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.86)
- Quantifying Distributional Invariance in Causal Subgraph for IRM-Free Graph Generalization (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.