When do dependencies in your data help?

on YouTube ↗59m

" summary

Assumes samples come from Glauber dynamics and proves bounded‑degree k‑wise Markov random fields are learnable in roughly n^2 log n time from a single n log n trajectory, replacing the previous n^{Ω(k)} computational barrier. Key ingredients are using contiguous update patterns like the i,i,j,i,i signature to estimate second moments (a population‑of‑means / shrinkage idea), anti‑concentration of low‑degree polynomials, and simple empirical tests; result removes the k exponent and succeeds with polynomial samples.

AI-written summary · about

" chapters (8)

1. 0:00Introduction to graphical models
2. 1:54Defining graphical models
3. 8:31Structure learning challenges
4. 19:19Correlation decay and Gibbs
5. 32:37Glauber dynamics overview
6. 36:56Temporal dependencies in learning
7. 40:00Proof sketch and strategy
8. 46:52Population of means problem

" related talks

• 43mLearning from DynamicsAnkur Moitra · Joint IFML/MPG Symposium 2024
• 23mDynamic inference in probabilistic graphical modelsWeiming Feng, Kun He, Xiaoming Sun, Yitong Yin · ITCS 2021
• 44mLearning Restricted Boltzman MachinesAnkur Moitra · Algorithmic Aspects of Causal Inference 2022
• 01h 04mLearning StaircasesEmmanuel Abbe, Enric Boix, Theodor Misiakiewicz · Deep Learning Theory Symposium 2021
• 50mAttributes: Selective Learning and InfluenceArjada Bardhi · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 01h 05mDistribution Estimation and Applications IIIAlon Orlitsky · Information Theory Boot Camp 2015
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 39mDynamics Programming for Machine Learning- Hidden Markov ModelsAvik Das · PyData Los Angeles 2019