Statistical Optimality in Causal Structure Learning

Causal graphical models are fundamental tools for representing complex dependency structures in probabilistic machine learning. When the underlying structure is unknown, a central task is structure learning, which aims to recover the causal graph from data. A key open problem is to characterize its statistical optimality and identify procedures that achieve it. While the statistical limits are well understood for undirected models, the directed setting remains much less explored. We study this problem through the lens of minimax sample complexity, focusing on both structure learning and its core subroutines. For parametric Gaussian models, we establish sharp optimal sample complexity results for (i) DAGs under the equal-variance assumption and (ii) tree-structured models under faithfulness. Moving beyond parametric settings, we develop a general reduction from structure learning to conditional independence (CI) testing, showing that the optimal rate for structure learning is governed by that of CI testing. This provides a unified framework applicable to a broad class of models, including fully nonparametric settings. Moving towards general DAGs, we investigate neighborhood selection as a key subroutine. We first study variable selection in linear regression under general design and show that best subset selection (BSS) achieves optimal sample complexity, while no polynomial time algorithm can attain this optimality under standard complexity conjectures, revealing a fundamental statistical–computational trade-off. We then demonstrate that, under structured designs induced by linear structural equation models, BSS can be improved. We propose a new estimator, KL-BSS, which exploits the unknown structure to achieve better sample complexity with weaker eigenvalue conditions, and establish both pointwise and minimax optimal guarantees. Together, these results provide a comprehensive perspective on statistical optimality in causal structure learning, highlighting the roles of the model assumptions, problem parameters, and basic subroutines.