Chebyshev Polynomials, Moment Matching and Optimal Estimation of the Unseen

on YouTube ↗29m

" summary

This work gives an explicit linear estimator on fingerprint counts that uses Chebyshev polynomials (degree about log n) and Poissonization to reduce bias and achieve sublinear sampling: roughly K / log K samples with error dependence polylogarithmic (about log^2(1/epsilon)) instead of 1/epsilon^2. Duality to moment matching yields the matching lower bound, so the procedure is minimax-optimal up to constants; simple experiments (e.g., Shakespeare passages) match the theory.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 0:26Problem setup
3. 0:49Estimating the unseen
4. 1:43Classical results
5. 3:09Mathematical formulation
6. 4:15Sample complexity
7. 7:30Sufficient statistics
8. 11:40Minimax risk
9. 12:36Best polynomial approximation
10. 13:19Moment matching
11. 15:16Unbiased estimators?
12. 16:23Linear estimators
13. 18:03Chebyshev polynomial
14. 18:31Final estimator
15. 19:06Analysis
16. 19:48Randomization
17. 20:32Key construction: reduction to one dimension
18. 21:48Optimize the lower bound
19. 23:07Comparison
20. 23:55Species problem
21. 25:15Estimating entropy
22. 25:26Concluding remarks

" related talks

• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 45mEfficient Profile Maximum Likelihood for Universal Symmetric Property EstimationMoses Charikar · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 48mExact Minimax Estimation for Phase SynchronizationChao Gao · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 30mSparse Polynomial Interpolation: Compressed Sensing, Super-resolution, or Prony?Jean-Bernard Lasserre · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 14mEfficient Universal Estimators For Symmetric Property EstimationKirankumar Shiragur · Meet the Fellows Welcome Event
• 35mTesting Positive Semidefiniteness and Eigenvalue ApproximationDavid P. Woodruff · Sketching and Algorithm Design 2023