Efficient Universal Estimators For Symmetric Property Estimation

on YouTube ↗14m

" summary

Describes an algorithm that computes an approximate PML (profile maximum likelihood) distribution for discrete IID samples and proves it is sample-optimal for estimating symmetric properties like support and entropy. Shows the profile is a sufficient statistic, links profile likelihood to permanent maximization of a matrix, and gives the first provable, efficient method to maximize that objective so the output distribution assigns mass to unseen symbols and yields near-optimal property estimates.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 1:39INFERENCE FROM LIMITED DATA
3. 2:14MOTIVATING QUESTION
4. 3:48SYMMETRIC PROPERTY ESTIMATION
5. 4:45PLUG-IN APPROACH
6. 5:21PROFILE MAXIMUM LIKELIHOOD
7. 8:22PML IS A UNIVERSAL ESTIMATOR
8. 10:41TAKE AWAY
9. 11:27INTERDISCIPLINARY RESEARCH

" related talks

• 45mEfficient Profile Maximum Likelihood for Universal Symmetric Property EstimationMoses Charikar · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 25mFast Approximations of the Pattern Maximum Likelihood EstimatePascal Vontobel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 30mStatistical Property Testing and Estimation Beyond the i.i.d. SettingGregory Valiant · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 41mpMSE Mechanism: Differentially Private Synthetic Data with Maximal Distributional SimilarityJoshua Snoke · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 29mEfficient Minimax Optimal Strategies for Universal PredictionPeter Bartlett · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 27mDetection and Estimation through an Information Theory LensSergio Verdú · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 48mExact Minimax Estimation for Phase SynchronizationChao Gao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 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)