Distribution Estimation and Applications I

on YouTube ↗01h 10m

" summary

Establishes concrete minimax rates and practical reductions: empirical frequencies give L1 risk Θ(√(K/N)) and KL risk ≈ (K−1)/(2N), so naive IID learning needs ~K/δ^2 samples. Adding structure cuts that drastically — an envelope class P_i ≤ C i^{−α} yields error O(N^{−(α−1)/(2α−1)}) (e.g. α=1.5 → N^{−1/4}), and monotone distributions admit error O((log K / N)^{1/3}). Key tools are minimax bounds, domain contraction to effective support, and explicit sample-count tradeoffs.

AI-written summary · about

" chapters (12)

1. 0:00Start
2. 8:34Approaches
3. 11:50Probability's Original Scene
4. 16:37Learning Large Alphabets
5. 22:13Empirical Sample Complexity
6. 27:05Universal Compression Recall estimation
7. 33:48Universal Compression Real estimation
8. 38:34Approximation Sample Complexity
9. 47:07Structure
10. 49:00Approximability of a Class
11. 51:24Approximability Implies Estimation
12. 53:56Envelope Distributions

" related talks

• 45mImproved Learning from Time-bounded Kolmogorov ComplexityHalley Goldberg · Lower Bounds, Learning, and Average-Case Complexity
• 29mExtended Formulations and Information ComplexityAnkur Moitra · Information Theory in Complexity Theory and Combinatorics 2015
• 30mStreaming Lower Bounds for Approximating MAX-CUTMichael Kapralov · Information Theory in Complexity Theory and Combinatorics 2015
• 38mLearning with Distributional InvertersMarco Carmosino · Lower Bounds, Learning, and Average-Case Complexity
• 26mComplete Problems for Multi-Pseudodeterministic ComputationsPeter Dixon, A Pavan, N. V. Vinodchandran · ITCS 2021
• 30mA New Look at Gallager's BoundsNati Linial · Information Theory in Complexity Theory and Combinatorics 2015
• 33mLucky Talk: Exponential Separation of Information and CommunicationGillat Kol · Information Theory in Complexity Theory and Combinatorics 2015
• 36mExponential Separation of Information and CommunicationGillat Kol · Information Theory in Complexity Theory and Combinatorics 2015