Monotone Estimation Framework and its Applications for Scalable Analytics of Large Data Sets

on YouTube ↗40m

" summary

Defines a monotone sampling with seed u model where each sample reveals a set of consistent data vectors and estimators must be unbiased, nonnegative and admissible with bounded variance. Gives explicit admissible estimators and a unique monotone L-star estimator that follows the lower-bound function; it strictly dominates Horvitz–Thompson for multi-instance queries. Proves a variance-competitive ratio 4 guarantee (tight), reports experiments on coordinated weighted samples for segment sums and L1/L2 differences showing much lower error than independent sampling, and suggests small improvements and open bounds.

AI-written summary · about

" chapters (6)

1. 0:00Introduction to monotone schemes
2. 3:53Properties of estimators
3. 9:32Applications and coordination
4. 17:13Horvitz-Thompson estimation
5. 23:43Optimal monotone estimators
6. 34:24Summary and open questions

" related talks

• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 35mSampling for Subset Selection and ApplicationsAmit Deshpande · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 10mSketching High-Dimensional DataJelani Nelson · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 41mIntegrating Functions via Distance Sensitive HashingMoses Charikar · Real-Time Decision Making 2018
• 01h 04mSampling Big Ideas in Sublinear AlgorithmsEdith Cohen · Sublinear Algorithms Boot Camp 2024
• 37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?Rachel Ward · Optimization, Statistics and Uncertainty
• 37mApproaches to online quantile estimationJoe Ross · Data Con LA 2020