How to Predict When Estimation is Hard: Algorithms for Learning on Graphs

on YouTube ↗51m

" summary

Claim: sequential predictors achieve the same error as the NP‑hard best graph labeling while avoiding model estimation by using improper prediction and Cover‑style potentials. Construction uses potential differences, sequential symmetrization, and SDP/SOS relaxations so the integrality gap α only inflates a lower‑order regret term. Implementations beat Laplacian regularization on real graphs, scale to ~10k nodes with current matrix solves, and extend to contextual bandits (initial 3/4 bound improved to 2/3), aiming for 1/2.

AI-written summary · about

" chapters (12)

1. 0:00Introduction to speaker
2. 1:26Prediction vs estimation
3. 2:56Defining the prediction problem
4. 5:44Minimax bounds and oracles
5. 8:27Cover's result on achievability
6. 12:31Martingales and algorithms
7. 15:16Rademacher averages and width
8. 19:56Algorithmic implementation
9. 25:22Graph-based learning constraints
10. 30:56Relaxation and approximation
11. 39:22Extensions and future work
12. 48:01Concluding remarks and Q&A

" related talks

• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 35mParameter Estimation For Undirected Graphical Models With Hard ConstraintsKavita Ramanan · Algorithmic Aspects of Causal Inference 2022
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive PriorsNikita Zhivotovskiy · Joint IFML/MPG Symposium 2024
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 28mSketching for M-Estimators: A Unified Approach to Robust RegressionDavid P. Woodruff · Information Theory, Learning and Big Data (Simons Institute, 2015)