How Hard Is Inference for Structured Prediction?

on YouTube ↗48m

" summary

Asks whether recovering binary vertex labels from noisy edge parity is possible and when; proves the simple minimize-disagreements (correlation‑clustering) estimator is information‑theoretically optimal on grid‑like planar graphs with expected error Θ(P^2·N), uses a flipping lemma, Chernoff bounds, dual‑graph cycle counting and matching to get a polynomial‑time solution there, shows expanders only guarantee O(P·N) error, the path fails (constant fraction wrong), and notes NP‑hardness outside planar cases.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 1:24Structured Prediction
3. 2:43Recovery From Exact Parities
4. 4:32Recovery From Noisy Parities
5. 8:09Research Agenda
6. 10:09Analogy: Stochastic Block Model
7. 13:45The Graph Matters
8. 15:59The Grid: Empirical Evidence
9. 20:03Approximate Recovery
10. 22:13MLE/Correlation Clustering
11. 26:57Flipping Lemma
12. 29:32Warm-Up #1: Expanders
13. 38:12Grid-Like Graphs: Analysis
14. 40:44A Subtlety and a Fix
15. 42:52More Open Questions

" 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)
• 40mTesting Correlation of Unlabeled Random GraphsJiaming Xu · Computational Phase Transitions (Simons Institute, 2020)
• 33mLearning a Tree-Structured Ising Model in Order to Make PredictionsGuy Bresler · Approximate Counting, Markov Chains and Phase Transitions
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 49mRecent Advances in Counting Sparse GraphsSourav Chatterjee · Random Instances and Phase Transitions (Simons Institute, 2016)
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 54mExact Matching Of Random Graphs With Constant CorrelationCheng Mao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)