The Fisher Dimension: Instance-Dependent Complexity for Causal Discovery

Luong Doan, Khanh Nguyen Quoc, Duc Hai Nguyen, Mai Phan Quoc Hung, Phong Ho, Nhung Duong, Tuan Do
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:25626-25642, 2026.

Abstract

Classical sample complexity bounds for causal structure learning are minimax in nature, characterizing worst-case difficulty without distinguishing between easy and hard instances. We study instance-specific complexity for Markov equivalence class (MEC) recovery in linear Gaussian structural equation models. We introduce the Fisher dimension, defined as the inverse squared minimum partial correlation that must be detected to recover the MEC. We prove that the Fisher dimension governs sample complexity: it provides both a lower bound and an upper bound (tight up to logarithmic factors) for MEC recovery. A key theoretical finding is that under spectrally well-conditioned models, with bounded noise variances, bounded covariance eigenvalues, and constant-order edge coefficients, the Fisher dimension is uniformly bounded regardless of graph structure. Thus, significant instance-specific variation arises from parametric rather than structural features. Empirical validation shows strong correlation between our predictor and observed sample complexity for structured graph families.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-doan26a, title = {The {F}isher Dimension: Instance-Dependent Complexity for Causal Discovery}, author = {Doan, Luong and Quoc, Khanh Nguyen and Nguyen, Duc Hai and Hung, Mai Phan Quoc and Ho, Phong and Duong, Nhung and Do, Tuan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {25626--25642}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/doan26a/doan26a.pdf}, url = {https://proceedings.mlr.press/v306/doan26a.html}, abstract = {Classical sample complexity bounds for causal structure learning are minimax in nature, characterizing worst-case difficulty without distinguishing between easy and hard instances. We study instance-specific complexity for Markov equivalence class (MEC) recovery in linear Gaussian structural equation models. We introduce the Fisher dimension, defined as the inverse squared minimum partial correlation that must be detected to recover the MEC. We prove that the Fisher dimension governs sample complexity: it provides both a lower bound and an upper bound (tight up to logarithmic factors) for MEC recovery. A key theoretical finding is that under spectrally well-conditioned models, with bounded noise variances, bounded covariance eigenvalues, and constant-order edge coefficients, the Fisher dimension is uniformly bounded regardless of graph structure. Thus, significant instance-specific variation arises from parametric rather than structural features. Empirical validation shows strong correlation between our predictor and observed sample complexity for structured graph families.} }
Endnote
%0 Conference Paper %T The Fisher Dimension: Instance-Dependent Complexity for Causal Discovery %A Luong Doan %A Khanh Nguyen Quoc %A Duc Hai Nguyen %A Mai Phan Quoc Hung %A Phong Ho %A Nhung Duong %A Tuan Do %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-doan26a %I PMLR %P 25626--25642 %U https://proceedings.mlr.press/v306/doan26a.html %V 306 %X Classical sample complexity bounds for causal structure learning are minimax in nature, characterizing worst-case difficulty without distinguishing between easy and hard instances. We study instance-specific complexity for Markov equivalence class (MEC) recovery in linear Gaussian structural equation models. We introduce the Fisher dimension, defined as the inverse squared minimum partial correlation that must be detected to recover the MEC. We prove that the Fisher dimension governs sample complexity: it provides both a lower bound and an upper bound (tight up to logarithmic factors) for MEC recovery. A key theoretical finding is that under spectrally well-conditioned models, with bounded noise variances, bounded covariance eigenvalues, and constant-order edge coefficients, the Fisher dimension is uniformly bounded regardless of graph structure. Thus, significant instance-specific variation arises from parametric rather than structural features. Empirical validation shows strong correlation between our predictor and observed sample complexity for structured graph families.
APA
Doan, L., Quoc, K.N., Nguyen, D.H., Hung, M.P.Q., Ho, P., Duong, N. & Do, T.. (2026). The Fisher Dimension: Instance-Dependent Complexity for Causal Discovery. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:25626-25642 Available from https://proceedings.mlr.press/v306/doan26a.html.

Related Material