Fast Approximations of the Pattern Maximum Likelihood Estimate

on YouTube ↗25m

" summary

Defines the pattern maximum likelihood (PML) as the p that maximizes a permanent over a matrix parameterized by p and shows practical surrogates: a Bethe (beta) free‑energy approximation and a Sinkhorn (row/column scaling) approximation. Uses alternating maximization with sum‑product to find a doubly stochastic gamma that connects estimators. Gives deterministic guarantees of 2^n and e^n (Bethe conjectured ~sqrt2^n), and numerical evidence on 10,000 random 10x10 matrices that Bethe matches the permanent’s slope better than Sinkhorn. Valiant–Valiant uses Poissonization plus an LP over discretized probabilities.

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 1:46Overview
3. 2:31Simons pointer
4. 7:16Permutation Matrix
5. 14:02General Information
6. 15:26Free Energy
7. 17:26Approximations
8. 17:45Approximate
9. 19:01Sinkhole
10. 19:30Efficient Approximation
11. 20:35Linear Program
12. 23:12Conclusions

" related talks

• 14mEfficient Universal Estimators For Symmetric Property EstimationKirankumar Shiragur · Meet the Fellows Welcome Event
• 48mExact Minimax Estimation for Phase SynchronizationChao Gao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 45mEfficient Profile Maximum Likelihood for Universal Symmetric Property EstimationMoses Charikar · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 36mTo Be (Hard) or Not Be:...Florent Krzakala · Rigorous Evidence for Information-Computation Trade-offs
• 44mA Modern Maximum-Likelihood Theory for High-Dimensional Logistic RegressionPragya Sur · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 41mpMSE Mechanism: Differentially Private Synthetic Data with Maximal Distributional SimilarityJoshua Snoke · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022