Khanh Quoc

The Fisher Dimension: Instance-Dependent Complexity for Causal Discovery

Classical sample complexity bounds for causal structure learning are minimax in nature, characterizing worst-case difficulty without distinguishing between easy and hard instances. We study instance-specific complexity for Markov equivalence class (MEC) recovery in linear Gaussian structural equatio…