Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation

on YouTube ↗45m

" summary

Algorithm computes an approximate profile maximum likelihood distribution with objective value within a factor exp(O(N^{2/3})) of optimal, running in near‑linear time in profile size. Method lower‑bounds atom probabilities (≥1/(2N^2)), discretize probabilities into O(log N / ε) geometric levels and discretize frequencies, aggregate terms by combinatorial “types”, then replace the integer type assignment by a convex relaxation and round to an integral solution. Practical implementation shows the pipeline is implementable and yields usable universal estimators for symmetric properties.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 0:53Setting
3. 5:08Sequence v/s Profile Maximum Likelihood
4. 11:28Profile Maximum Likelihood Computation
5. 14:30Symmetric property estimation
6. 21:24PML is a universal symetric property estimator
7. 25:10Universal Estimator Approaches
8. 28:40Structured approximate distribution
9. 40:08Experiments : Entropy estimation

" related talks

• 14mEfficient Universal Estimators For Symmetric Property EstimationKirankumar Shiragur · Meet the Fellows Welcome Event
• 29mEfficient Minimax Optimal Strategies for Universal PredictionPeter Bartlett · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 25mFast Approximations of the Pattern Maximum Likelihood EstimatePascal Vontobel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 21mLucky Talk: Chebyshev Polynomials, Moment Matching and Optimal Estimation of the UnseenYihong Wu · 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
• 30mStatistical Property Testing and Estimation Beyond the i.i.d. SettingGregory Valiant · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 28mNear-Optimal Hypothesis Testing via Convex OptimizationArkadi Nemirovski · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 53mOptimality in Locally Private Estimation and LearningJohn Duchi · Privacy and the Science of Data Analysis 2019