Learning Ill-Conditioned Gaussian Graphical Models
summary
Claims first fixed polynomial-time algorithms that learn attractive GGMs and walk-summable GGMs using logarithmic samples without condition-number assumptions. Algorithm is greedy-prune: grow a candidate neighborhood by maximal conditional-variance reduction (equivalent to OMP), then remove weak neighbors; for attractive models it needs ~d log P / kappa^2 samples and runs in roughly quadratic time, for walk-summable models the proven bound is worse (about d^2 log P / kappa^6, improvable to d log P / kappa^4 with L1), and experiments show existing methods fail on long dependency chains while greedy-prune succeeds.
AI-written summary · about
chapters (21)
- 0:00Intro
- 1:01Gaussian Graphical Models (GGMs)
- 4:28Bigger Picture
- 5:24Example: "Random Walk" Model
- 6:38Learning Sparse GGMS
- 7:02Structure Learning for GGMs
- 8:56Example: Unknown order Random Walk
- 12:02Previous Work: MVL18
- 14:16Information-Theoretic Limits: MVL18
- 15:08GGMS: Main Learning Challenge
- 16:07Attractive GGMS
- 18:13Walk-Summable GGMs
- 20:36Learning GGMs Greedily
- 21:23Phase 1: Growing a neighborhood
- 22:41Phase 2: Pruning a neighborhood
- 23:18Experiments: A Simple Challenge
- 24:09A Simple Challenge: Path + Clique
- 24:56A Simple Challenge: Random walk
- 25:33Analysis for Attractive: Supermodularity
- 26:32Analysis for Walk-Summable
- 27:20Analysis: Bounded Conditional Variances
related talks
01h 01mML for discrete optimization: Theoretical foundations
54mGraph Machine Learning & Random Graph Models
18mFast Inference for Probabilistic Graphical Models
30mComputational Barriers For Learning Some Generalized Linear Models
27mDistribution Learning Meets Graph Structure Sampling
01h 23mProbabilistic Graphical Models, HMMs using PGMPY
23mDynamic inference in probabilistic graphical models
35mLearning General Gaussian Mixtures With Efficient Score Matching