# Optimal structure learning and conditional independence testing

arXiv: https://arxiv.org/abs/2507.05689 · HTML: https://mlsanity.com/paper/2507.05689/

## 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 (most cited first, 28 of 28)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information](https://mlsanity.com/paper/1709.01447/) (2017)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Local permutation tests for conditional independence](https://mlsanity.com/paper/2112.11666/) (2021)
- [Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm](https://mlsanity.com/paper/1301.6696/) (2013)
- [Nonparametric independence testing via mutual information](https://mlsanity.com/paper/1711.06642/) (2017)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [The Recovery of Causal Poly-Trees from Statistical Data](https://mlsanity.com/paper/1304.2736/) (2013)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [A Weaker Faithfulness Assumption based on Triple Interactions](https://mlsanity.com/paper/2010.14265/) (2020)
- [Structure Learning for Directed Trees](https://mlsanity.com/paper/2108.08871/) (2021)
- [Maximum Likelihood Bounded Tree-Width Markov Networks](https://mlsanity.com/paper/1301.2311/) (2013)
- [Information-theoretic limits of Bayesian network structure learning](https://mlsanity.com/paper/1601.07460/) (2016)
- [A Scalable Conditional Independence Test for Nonlinear, Non-Gaussian Data](https://mlsanity.com/paper/1401.5031/) (2014)
- [A Fast Non-parametric Approach for Local Causal Structure Learning](https://mlsanity.com/paper/2111.14969/) (2021)
- [On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery](https://mlsanity.com/paper/2310.13553/) (2023)
- [Conditional Independence Testing for Discrete Distributions: Beyond chi2- and G-tests](https://mlsanity.com/paper/2308.05373/) (2023)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs](https://mlsanity.com/paper/2308.16859/) (2023)

## 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.