Statistically Efficient Greedy Equivalence Search
Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:241-249, 2020.
We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.