High-Dimensional Consistency in Score-Based and Hybrid Structure Learning
The main approaches for learning Bayesian networks can be classified as constraint-based, score-based or hybrid methods. Although high-dimensional consistency results are available for the constraint-based PC algorithm, such results have been lacking for score-based and hybrid methods, and most hybrid methods are not even proved to be consistent in the classical setting where the number of variables remains fixed. We study the score-based Greedy Equivalence Search (GES) algorithm, as well as hybrid algorithms that are based on GES. We show that such hybrid algorithms can be made consistent in the classical setting by using an adaptive restriction on the search space. This leads to the adaptively restricted GES (ARGES) algorithm. Moreover, we prove consistency of GES and ARGES for certain sparse high-dimensional scenarios.
This is joint work with Preetam Nandy and Alain Hauser