Parameter Estimation For Undirected Graphical Models With Hard Constraints

on YouTube ↗35m

" summary

Parameter estimation for hard-constraint undirected graphical models uses the maximum pseudo-likelihood estimator, which for the hard-core model reduces to the explicit ratio CN/UN closed form (number of ones over free vertices) and is root-n consistent on graphs with uniformly bounded average degree. Proofs use exchangeable pairs for concentration and combinatorial control of the log partition function; more general H-coloring needs a rainbow positivity condition or stronger graph constraints, and gradient descent finds the estimator efficiently.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 1:19The Hard Core Model
3. 2:45An equivalent formulation of the hard-core model
4. 3:39Motivation and Question
5. 4:22Problem Statement: Single-Sample Estimation
6. 5:18Maximum Pseudolikelihood Estimator
7. 7:18Results: Single-Sample Estimator for the Hard-Core Model
8. 9:24Asymptotic Consistency
9. 10:44Idea of Proof
10. 13:19Graphical Models with Hard Constraints
11. 16:27Random H-coloring models
12. 17:48Form of the Estimator for the H-coloring model
13. 21:29Comments on the Assumptions
14. 24:24Computation of the Estimator
15. 28:08Counterexamples - 1
16. 31:09Conclusion

" related talks

• 51mHow to Predict When Estimation is Hard: Algorithms for Learning on GraphsSasha Rakhlin · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IVTamara Broderick · Foundations of Machine Learning Boot Camp 2017
• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 24mRobust Parameter Estimation For Random GraphsJayadev Acharya · Rigorous Evidence for Information-Computation Trade-offs
• 49mRecent Advances in Counting Sparse GraphsSourav Chatterjee · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 40mBoot camp on generalization theory for graph learningAntonios Vasileiou, Thien Le · Graph Learning Meets Theoretical Computer Science 2025
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)