Optimal structure learning and conditional independence testing
Ming Gao, Yuhao Wang, Bryon Aragam · 2025
Read Optimal structure learning and conditional independence testing by Ming Gao, Yuhao Wang, Bryon Aragam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05689.txt.
Introduction
Ming Gao and co-authors prove that learning a causal chart and testing independence share one best possible speed, in this 2025 paper. Structure learning rebuilds a network of causes from data alone. Conditional independence tests ask whether two variables are linked given others.
The pair of problems look different, yet their hard limits coincide. The team prove this by a general reduction for a broad class of networks. Worked examples cover simple coins, bell-curve data, and flexible models. A tuned version of the classic PC algorithm hits the optimal rate. The unity result tells data scientists where effort stops paying off. Causal discovery tools can now be judged against a firm yardstick.
Catalog record
| CREATOR | Ming Gao, Yuhao Wang, Bryon Aragam |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-05689
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal structure learning and conditional independence testing Ming Gao, Yuhao Wang, Bryon Aragam Abstract 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. † † Contact: [email protected] , [email protected] , [email protected] 1 Introduction Graphical models are important tools in machine learning for representing complex dependency structures that arise in a wide range of applications in causality, artificial intelligence, and statistics ( Spirtes et al. 2000 ; Pearl 2010 ; Murphy 2012 ; Zhang et al. 2013 ) . A crucial preliminary step when using graphical models is structure learning , which seeks to recover the underlying graph from data. The accuracy of structure learning directly impacts the performance of downstream tasks. It is well-known that structure learning is closely related to conditional independence (CI) testing, which itself is a fundamental topic that has attracted significant attention in recent years. Owing to its foundational role, CI testing has been extensively studied both methodologically and theoretically, leading to a rich body of literature on its statistical properties ( Zhang et al. 2011 ; Shah and Peters 2020 ; Canonne et al. 2018 ; Neykov et al. 2021 ) . In particular, structure learning methods often rely on CI testing as a subroutine for inferring graphical dependencies ( Spirtes and Glymour 1991 ; Maathuis et al. 2018 ) . The relationship between CI testing and structure learning has long been understood from the algorithmic perspective, which takes CI tests as black-box oracles and often assumes perfect CI information to guarantee graph recovery. However, the relationship between their finite-sample complexity and statistical hardness has yet to be formalized. Specifically, given that graphical models are intrinsically defined by the Markov property, a deeper understanding of how the statistical difficulty of CI testing governs the learning of graphical structures is both natural and fundamental. In undirected graphical models (Markov random fields), the information-theoretic limits of structure learning—specifically, the minimum number of samples required for reliable graph recovery—have been widely investigated ( Wang et al. 2010 ; Drton and Maathuis 2017 ; Misra et al. 2020 ) . For directed acyclic graphs (DAGs), however, much of the optimality literature has focused on the Gaussian setting, where the analysis can leverage strong distributional properties. As a result, existing optimality results do not readily extend to discrete or nonparametric settings. In contrast, CI testing in its own right has been studied more broadly, with well-established minimax results across various distributional settings ( Canonne et al. 2018 ; Neykov et al. 2021 ) . This contrast suggests an opportunity to leverage statistical results in CI testing to better understand the sample complexity of structure learning for DAGs in general. In this paper, we establish a fundamental relationship between the minimax optimality of structure learning in DAG models and the minimax optimality of CI testing, going beyond the Gaussian setup to general statistical models. We focus on poly-forests, a tractable yet rich subclass of DAGs that captures structured dependencies ( Chow and Liu 1968 ; Dasgupta 1999 ) , serving as a principled starting point toward fully general DAGs. Although optimality for learning general DAGs has been studied ( Gao et al. 2022 ) , specific distributional assumptions are needed in the analysis (e.g. linear SEM with equal error variances). We develop results under generic conditions that apply to both parametric and nonparametric distributions. Our work provides a framework connecting the statistical complexity of CI testing with that of structure learning, offering new insights into the understanding of sample-efficient DAG recovery in diverse modeling settings. 1.1 Contributions Our contributions in this work are twofold: 1. We establish a connection (Theorem 3.1 ) between the statistical complexity of conditional independence testing and structure learning problems. We show that the optimal sample complexity of learning any poly-forest is \displaystyle n\asymp\frac{\log d}{c^{\alpha}}\,, when the optimal testing radius of the corresponding CI testing problem is n^{-1/\alpha} for some \alpha>0 depending on the modeling setup, and c is a parameter that captures the signal strength (cf. Section 2 ). 2. We apply this general result to derive the minimax optimal sample complexity for several practical examples, including Bernoulli, Gaussian, and nonparametric continuous distributions, and discuss their differences. We also show that the optimal sample complexity is achieved by an efficient algorithm based on the classical PC algorithm. In addition, we conduct experiments to verify our theoretical findings. 1.2 Related work Conditional independence testing CI testing forms a crucial building block in machine learning and reasoning tasks. Given a triplet of random variables (X,Y,Z) , the problem asks whether X is conditionally independent of Y given Z . Numerous methods ( Dawid 1979 ; Fukumizu et al. 2007 ; Ramsey 2014 ; Li and Fan 2020 , e.g.) have been developed to address this fundamental problem. One prominent class of methods relies on measuring the distance between the conditional distribution P(X,Y\,|\,Z) and the product of the marginals P(X\,|\,Z)P(Y\,|\,Z) . For Gaussian variables, the problem reduces to testing whether the partial correlation is zero ( Fisher 1915 ) . For discrete variables, hypothesis tests based on chi-squared statistics are widely employed Ireland and Kullback 1968 ; Darroch et al. 1980 . Recent advancements have also explored kernel-based methods Gretton et al. 2007 ; Zhang et al. 2011 and information-theoretic measures such as conditional mutual information ( Runge 2018 ; Berrett and Samworth 2019 ) that can capture complex nonlinear dependencies in a nonparametric fashion. From the theoretical standpoint, CI testing has been investigated from the perspective of minimax optimality. For discrete distributions, the problem is well-understood and the minimax optimal rates have been established ( Chan et al. 2014 ; Diakonikolas and Kane 2016 ; Canonne et al. 2018 ) . In the nonparametric setting, Neykov et al. 2021 studied the fundamental limits of CI testing, deriving minimax optimal rates under smoothness assumptions. In addition, practical CI tests have been proposed ( Kim et al. 2022 ; Kim et al. 2024 ) . In particular, Jamshidi et al. 2024 devised a Von Mises estimator for mutual information as a valid CI test, and showed it achieves the parametric rate once the density is sufficiently smooth. These theoretical results provide valuable insights into the inherent difficulty of CI testing under different distributional setups. Graphical model structure learning Learning the structure of graphical models from observational data is a fundamental problem in machine learning. For undirected graphical models, the problem reduces to support recovery of the precision matrix ( MEINSHAUSEN and BÜHLMANN 2006 ; Friedman et al. 2008 ; Cai et al. 2011 ; Liu et al. 2009 ) . For DAG learning, approaches can be broadly categorized into three