Learning and Testing Structured Distributions
summary
Covers algorithms and theoretical results for learning and testing probability distributions that have structure (e.g., monotone, log-concave, piecewise polynomial) with provable sample and time complexity guarantees. Focuses on approaches from property testing and distribution learning to design efficient testers and learners tailored to specific structured families of distributions.
AI-written summary · about
chapters (19)
- 0:00Start
- 2:14Main Message of the Talk
- 3:29Distribution Learning (Density Estimation)
- 4:00Distribution Learning: History
- 5:49Types of Structured Distributions
- 9:51Distribution Learning: Definition
- 11:41Agnostic Learning: Definition
- 15:03Learning Arbitrary Discrete Distributions
- 16:35Structure and Statistical Estimation
- 17:58Piecewise polynomial distributions
- 18:15Overview of Framework
- 23:16Results: Learning Structured Families
- 25:05Statistical Performance: Intuition (1)
- 25:16"Complexity measure" for learning a distribution family
- 26:32Statistical Estimator
- 27:47Difficulties in Implementing Estimator
- 28:03Agnostically Learning Piecewise Polynomials
- 30:10Overview of Techniques
- 30:40Application in Databases: Succinct Representation of Data
related talks
48mA New Paradigm for Learning with Distribution Shift
01h 03mOverview of Statistical Learning Theory Part 2
45mTesting and Learning Distributions Under Local Information Constraints
35mSublinear-Time Algorithms in Learning
01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) Data
59mTesting Assumptions of Learning Algorithms
01h 17mOverview of Statistical Learning Theory Part 1
37mEfficient Algorithms for Reliable Machine Learning