Computational Barriers in Statistical Estimation and Learning

Explore the complexities of statistical estimation and learning in this Richard M. Karp Distinguished Lecture delivered by Andrea Montanari from Stanford University. Delve into topics such as coin tossing accuracy, information theoretic proofs, high-dimensional estimation, and the information computation gap. Examine the concept of packing numbers, various reduction techniques, and different classes of algorithms. Gain insights into optimal statistical accuracy and engage with thought-provoking questions in this comprehensive talk on computational barriers in the field of statistics and machine learning.

Syllabus

Introduction
What people think
Coins coin tossing
How accurate is this estimate
Can you do better
Information Theoretic Proof
High Dimension
Estimating the difference
What does this mean mathematically
The packing number
Information computation gap
Reductions
Rough idea
Classes of algorithms
Optimal statistical accuracy
Questions