Distribution Estimation and Applications III

on YouTube ↗01h 05m

" summary

Establishes concrete limits and algorithms: empirical frequency yields L1 error roughly sqrt(k/n) so sample complexity grows quadratically in k; worst-case degradation can be as bad as 1/2 when k >> n (example k = 4n gives e = 0 but any learner errs). Good‑Turing variants estimate combined probabilities at rate n^{-1/4}, and a label‑invariant classifier built from those estimates drives the excess error down (proved bound about n^{-1/5}*), independent of k, with linear-time implementation.

AI-written summary · about

" chapters (9)

1. 0:00Review
2. 2:38Classification
3. 7:33OmniClassification
4. 10:54Competitive Classification
5. 19:56Labeling Variant Classification
6. 25:08Example
7. 29:51Empirical Frequency Classifier
8. 43:31Label Invariant Classifier
9. 53:45Experiment

" related talks

• 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)
• 26mDiscrete Probability Distributions: Learn & Test with tools from Fourier AnalysisBala Priya · PyCon India 2020
• 59mTesting Assumptions of Learning AlgorithmsArsen Vasilyan · Sublinear Algorithms Boot Camp 2024
• 21mTesting Distribution FamiliesJayadev Acharya · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 45mTractability And Overparametrization In Some Simple ModelsAndrea Montanari · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 42mDistribution-Specific Analysis of Nearest Neighbor Search and ClassificationSanjoy Dasgupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 02mEstimation Beyond the IID Setting (Two Vignettes)Gregory Valiant · Algorithmic Advances for Statistical Inference with Combinatorial Structure