Lucky Talk: Chebyshev Polynomials, Moment Matching and Optimal Estimation of the Unseen

on YouTube ↗21m

" summary

Claims that support-size can be estimated with sublinear samples in K and only polylogarithmic accuracy dependence, using a linear estimator that is a weighted sum of the fingerprint (histogram of histogram). Design uses Chebyshev polynomial coefficients (degree L ≈ log N, e.g., degree ~11 for 1,000,000 items with 200,000 samples), Poissonization for analysis, and thresholding for heavy hitters. A matching lower bound builds indistinguishable mixtures by moment matching (random U taking few values), so the estimator is essentially optimal.

AI-written summary · about

" chapters (7)

1. 0:00Introduction and setup
2. 1:22Statistical fundamental limits
3. 3:31Overview of estimation methods
4. 7:32Linear estimator design
5. 12:18Concrete example and application
6. 14:13Limitations of heavy hitters
7. 15:51Lower bound and bad instances

" related talks

• 45mEfficient Profile Maximum Likelihood for Universal Symmetric Property EstimationMoses Charikar · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 14mEfficient Universal Estimators For Symmetric Property EstimationKirankumar Shiragur · Meet the Fellows Welcome Event
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 02mImportance Sampling in High Dimensions via HashingMoses Charikar · Sublinear Algorithms and Nearest-Neighbor Search
• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)