Research map / Learning theory and algorithms / Sample complexity
Entropy testing and its application to testing Bayesian networks
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.
Gives a near-optimal sample complexity bound for entropy identity testing of discrete distributions and applies it to identity testing of degree-d Bayesian networks without structural assumptions.
Problem
Testing whether a sample-accessed distribution p equals a known reference q or differs from it in Shannon entropy by at least epsilon, and using this to test identity of bounded in-degree Bayesian networks.
Approach
Reduces entropy identity testing to a chi-squared test on high-probability elements plus a linear statistic for the log(1/q_i) term, with a tail-cutting threshold tau = eps/log(k/eps) that controls entropy loss; the Bayes net result follows by local entropy tests and a KL-based local identity test.
Key results
- Entropy identity testing has sample complexity O(sqrt(k log(k/eps))/eps + log^2(k)/eps^2), nearly matched by an Omega(sqrt(k)/eps + log^2(k)/eps^2) lower bound.
- Identity testing for degree-d n-dimensional Bayes nets uses O~(2^{d/2} n^{3/2}/eps^2 + n^2/eps^4) samples, improving on the O~(2^{d/2} n^2/eps^4) bound of CDKS20 which required structural assumptions.
- The Bayes net tester runs in time polynomial in n^d and 1/eps, versus the n^{O(dn)} enumeration needed by learning-based testing.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply entropy identity testing to degree-d Bayesian-network identity testing | Identity testing for degree-d Bayesian networks · Degree-d Bayesian networks | sample complexity: O(2^{d/2}n²/ε⁴) -> O(2^{d/2}nd^{3/2} log n · √log(n/ε)/ε² + d³n² log n/ε⁴ + 2^{d/2}n^{3/2} log n/ε²) | Helped |
| Use the entropy identity tester rather than estimating entropy | Entropy testing over a domain of size k · Entropy identity testing | sample complexity: Θ(k/ε log k + log² k/ε²) -> O(√(k log(k/ε))/ε + log²(k)/ε²) | Helped |
| Remove the shared-topological-ordering assumption | Bayesian-network identity testing · Degree-d Bayesian networks | sample complexity | Helped |
| Use the proposed test instead of testing by learning | Degree-d Bayesian-network identity testing · Degree-d Bayesian networks with d ≫ log(n/ε) | sample complexity: O(2^d n/ε²) -> O(2^{d/2}nd^{3/2} log n · √log(n/ε)/ε² + d³n² log n/ε⁴ + 2^{d/2}n^{3/2} log n/ε²) | Helped |
Surprising findings
- Entropy identity testing is strictly easier than TV identity testing in the worst case: the Paninski hard instances have entropy gap only Theta(eps^2) from uniform, giving sqrt(k)/eps rather than sqrt(k)/eps^2.
Limitations
- Only the one-sample (identity) variant is studied; the two-sample closeness testing variant is left open.
- Bayes net bounds are polynomial in n and 1/eps but exponential in d (2^{d/2} factor), and the ~O notation hides polylog factors.
- The paper contains no experiments.
Experimental setup
Metrics: sample complexity
Baselines: CDKS20 DP16 testing-by-learning (CDKS20) TV identity testing
Builds on: DKW18 chi-squared identity tester Wu-Yang entropy estimation DP16 Bayes net testing CDKS20 Bayes net testing
Closest papers by meaning
- Independence Testing for Bounded Degree Bayesian Networks (NeurIPS 2022 · similarity 0.87)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.86)
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.84)
- Learnability of Parameter-Bounded Bayes Nets (AAAI 2025 · similarity 0.83)
- Hypothesis Testing for Generalized Thurstone Models (ICML 2025 · similarity 0.83)
- On the sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery (ICML 2024 · similarity 0.83)
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.