Optimal structure learning and conditional independence testing
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Conditional Independence Test Based on Transport Maps
Testing conditional independence between two random vectors given a third is a fundamental and challenging problem in statistics, particularly in multivariate nonparametric settings due to the complexity of conditional s…
Predictive Independence Testing, Predictive Conditional Independence Testing, and Predictive Graphical Modelling
Testing (conditional) independence of multivariate random variables is a task central to statistical inference and modelling in general - though unfortunately one for which to date there does not exist a practicable work…
PhilosophyOn sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery
Motivated by conditional independence testing, an essential step in constraint-based causal discovery algorithms, we study the nonparametric Von Mises estimator for the entropy of multivariate distributions built on a ke…
Causal DiscoveryModel-X Sequential Testing for Conditional Independence via Testing by Betting
This paper develops a model-free sequential test for conditional independence. The proposed test allows researchers to analyze an incoming i.i.d. data stream with any arbitrary dependency structure, and safely conclude w…
validA Simple Unified Approach to Testing High-Dimensional Conditional Independences for Categorical and Ordinal Data
Conditional independence (CI) tests underlie many approaches to model testing and structure learning in causal inference. Most existing CI tests for categorical and ordinal data stratify the sample by the conditioning va…
Causal Inferencestatistical independence testing