Introduction to Experimental Design

on YouTube ↗54m

" summary

Shows that with no observational data identifying any P‑node DAG needs floor(log2 P)+1 unbounded interventions, while with observational data the count depends on the interventional essential graph’s clique number ω and can be achieved by binary‑coding an optimal coloring (and p−1 suffices for single‑node interventions). Single‑node objective (expected oriented edges) is submodular, monotone, so greedy gives a 1−1/e approximation; uniform sampling from a Markov equivalence class is now polynomial time, enabling Monte‑Carlo estimates.

AI-written summary · about

" chapters (6)

1. 0:00Intervention bounds
2. 2:25Induction proof
3. 6:50Observational setting
4. 16:26Identification strategies
5. 26:06Budget-based optimization
6. 44:50Q&A and final remarks

" related talks

• 33mSimple Yet Efficient Estimators For Network Causal Inference...Christina Yu · Algorithmic Aspects of Causal Inference 2022
• 01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IVTamara Broderick · Foundations of Machine Learning Boot Camp 2017
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 24mA Friendly Introduction To CausalityAlex Dimakis · MLconf SF 2016
• 44mEquitable ColoringsAfonso Bandeira · Computational Phase Transitions (Simons Institute, 2020)
• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 47mExploiting Combinatorial Structure in Constraint Programming: ...Gilles Pesant · Satisfiability: Theory, Practice, and Beyond 2023
• 38mSome Easy Optimization Problems Have the Overlap-Gap PropertyTselil Schramm · Joint IFML/MPG Symposium 2024