Optimal structure learning and conditional independence testing

2025/07/08 by Ming Gao, Yuhao Wang, Gao, Ming +3
Computer Science · #Bayesian Modeling and Causal Inference #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2507.05689

openalex publication_date 2025/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Learning Gaussian DAG Models without Condition Number Bounds
• Optimal estimation of Gaussian (poly)trees
• On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery
• Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs
• Conditional Independence Testing for Discrete Distributions: Beyond χ²- and G-tests
• Optimal estimation of Gaussian DAG models
• Local permutation tests for conditional independence
• A Fast Non-parametric Approach for Local Causal Structure Learning
• Efficient Bayesian network structure learning via local Markov boundary\n search
• Structure Learning for Directed Trees
• Minimax Optimal Conditional Independence Testing
• Testing Conditional Independence of Discrete Distributions
• Nonparametric independence testing via mutual information
• Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information
• Community Detection and Stochastic Block Models
• Structure Learning in Graphical Modeling
• High-dimensional consistency in score-based and hybrid structure\n learning
• Efficiently learning Ising models on arbitrary graphs
• A Scalable Conditional Independence Test for Nonlinear, Non-Gaussian Data
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Identifiability of Gaussian structural equation models with equal error variances
• Identifiability of Causal Graphs using Functional Models
• Kernel-based Conditional Independence Test and Application in Causal Discovery
• A Constrained L1 Minimization Approach to Sparse Precision Matrix Estimation
• Learning High-Dimensional Markov Forest Distributions: Analysis of Error Rates
• Forest Density Estimation
• Information-theoretic limits of selecting binary graphical models in high dimensions
• The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs
• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• Maximum Likelihood Bounded Tree-Width Markov Networks
• Learning Bayesian Network Structure from Massive Datasets: The "Sparse\n Candidate" Algorithm
• Learning Polytrees
• An Algorithm for Fast Recovery of Sparse Causal Graphs
• The Recovery of Causal Poly-Trees from Statistical Data

Related

• Optimal estimation of Gaussian (poly)trees
• Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests
• Conditional Independence Testing for Discrete Distributions: Beyond χ²- and G-tests
• Minimax optimal testing by classification
• Learning High-Dimensional Markov Forest Distributions: Analysis of Error Rates