Exact Minimax Estimation for Phase Synchronization

on YouTube ↗48m

" summary

Proves the minimax risk equals sigma^2/(n p), derives a matching lower bound and shows MLE, generalized power method (GPM) with eigenvector initialization, and SDP (with eigenvector post‑processing) all attain that rate and the claimed leading constant 102 under the consistency regime sigma^2 = o(n p); analysis uses an iterative map F, Burer–Monteiro factorization and fixed‑point arguments to link algorithms to the MLE, and requires p = Ω((log n)/n) for graph connectivity.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 1:31Phase synchronization problem
3. 3:24Existing literature and algorithms
4. 7:27General framework and results
5. 12:12Structured linear model framework
6. 16:41Iterative algorithm analysis
7. 21:25Application to Gaussian mixtures
8. 26:24Analysis of phase synchronization
9. 28:55SDP and lower bounds
10. 34:48Comparison with Z2 synchronization
11. 40:53Generalization and Q&A

" related talks

• 25mFast Approximations of the Pattern Maximum Likelihood EstimatePascal Vontobel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 27mInformation Measure Estimation and Applications: Boosting the Sample Size from n to n log nJiantao Jiao · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 51mMin-max Optimization: From Complexity to AlgorithmsEmmanouil Zampetakis · Adversarial Approaches in Machine Learning 2022
• 14mEfficient Universal Estimators For Symmetric Property EstimationKirankumar Shiragur · Meet the Fellows Welcome Event