Efficient Distance Estimation And Causal Inference For Discrete Models
summary
Proves that TV computation is #P‑hard even for product distributions and that deciding TV zero versus nonzero becomes NP‑hard once node degree ≥2; gives an additive estimator via sampling from P that achieves ±ε with O(ε^-2) samples by evaluating p(x), q(x) on draws from P; shows interventional distributions are learnable as sampler or evaluator when C‑components and in‑degree are bounded, with sample complexity scaling like N·ε^-2·α^-K and evaluator learning can be SZK‑hard.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:55Causal Model
- 5:12Assumptions
- 6:16Total Variation Distance
- 10:33Proof
- 15:55Additive approximation
- 18:49Relative approximations
- 20:54Distribution learning
- 27:49C component
- 30:49interventional
- 33:24results
- 36:36conclusion
related talks
23mTowards Practical Distribution Testing
01h 07mRecent Progress in High-Dimensional Learning
31mLearning And Testing Causal Models: A Property Testing Viewpoint
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
21mTesting Distribution Families
01h 08mData Driven Optimization Models and Algorithms
01h 11mStatistical Limits of Causal Inference
48mHow Hard Is Inference for Structured Prediction?