mlsanityData to 14 Oct 2026

Optimal structure learning and conditional independence testing

arXiv 2507.05689 ↗First posted 8 Jul 2025math.ST stat.ML stat.THcited by 0

Not on the map. Why?

Abstract (arXiv)

We establish a fundamental connection between optimal structure learning and optimal conditional independence testing by showing that the minimax optimal rate for structure learning problems is determined by the minimax rate for conditional independence testing in these problems. This is accomplished by establishing a general reduction between these two problems in the case of poly-forests, and demonstrated by deriving optimal rates for several examples, including Bernoulli, Gaussian and nonparametric models. Furthermore, we show that the optimal algorithm in these settings is a suitable modification of the PC algorithm. This theoretical finding provides a unified framework for analyzing the statistical complexity of structure learning through the lens of minimax testing.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 28 of its 73 references that are in the map. First posted on arXiv 8 Jul 2025.

Builds on

28 of 73 references.

References · 28

  1. 2017Community Detection and Stochastic Block Modelscited by 319
  2. 2013Causal Discovery with Continuous Additive Noise Modelscited by 255
  3. 2013High-dimensional learning of linear causal networks via inverse covariance estimationcited by 87
  4. 2017Conditional independence testing based on a nearest-neighbor estimator of conditional mutual informationcited by 70
  5. 2016Structure Learning in Graphical Modelingcited by 66
  6. 2018On Causal Discovery with Equal Variance Assumptioncited by 59
  7. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  8. 2015High-dimensional consistency in score-based and hybrid structure learningcited by 46
  9. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  10. 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
  11. 2021Local permutation tests for conditional independencecited by 23
  12. 2013Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithmcited by 22
16 more
  1. 2017Nonparametric independence testing via mutual informationcited by 22
  2. 2017Testing Conditional Independence of Discrete Distributionscited by 22
  3. 2013The Recovery of Causal Poly-Trees from Statistical Datacited by 19
  4. 2022Optimal estimation of Gaussian DAG modelscited by 17
  5. 2013Learning Polytreescited by 14
  6. 2021Efficient Bayesian network structure learning via local Markov boundary searchcited by 14
  7. 2020A Weaker Faithfulness Assumption based on Triple Interactionscited by 10
  8. 2021Structure Learning for Directed Treescited by 9
  9. 2013Maximum Likelihood Bounded Tree-Width Markov Networkscited by 7
  10. 2016Information-theoretic limits of Bayesian network structure learningcited by 7
  11. 2014A Scalable Conditional Independence Test for Nonlinear, Non-Gaussian Datacited by 5
  12. 2021A Fast Non-parametric Approach for Local Causal Structure Learningcited by 5
  13. 2023On sample complexity of conditional independence testing with Von Mises estimator with application to causal discoverycited by 4
  14. 2023Conditional Independence Testing for Discrete Distributions: Beyond chi2- and G-testscited by 3
  15. 2024Optimal estimation of Gaussian (poly)treescited by 3
  16. 2023Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphscited by 2

Built on by

Not cited yet.