Optimal structure learning and conditional independence testing

Ming Gao, Yuhao Wang, Bryon Aragam
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:33659-33686, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-gao26ab, title = {Optimal structure learning and conditional independence testing}, author = {Gao, Ming and Wang, Yuhao and Aragam, Bryon}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {33659--33686}, 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/gao26ab/gao26ab.pdf}, url = {https://proceedings.mlr.press/v306/gao26ab.html}, 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.} }
Endnote
%0 Conference Paper %T Optimal structure learning and conditional independence testing %A Ming Gao %A Yuhao Wang %A Bryon Aragam %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-gao26ab %I PMLR %P 33659--33686 %U https://proceedings.mlr.press/v306/gao26ab.html %V 306 %X 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.
APA
Gao, M., Wang, Y. & Aragam, B.. (2026). Optimal structure learning and conditional independence testing. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:33659-33686 Available from https://proceedings.mlr.press/v306/gao26ab.html.

Related Material