Recent Advances in Algorithmic Heavy-Tailed Statistics

on YouTube ↗01h 01m

" summary

Constructs a polynomial-time estimator for heavy-tailed covariance with operator-norm error about sqrt(d/n)·log(1/δ)^{1/4} + sqrt(log(1/δ)/n} under a certifiable 2→8 hypercontractivity moment assumption, using log(1/δ) median-of-means buckets. Core tools are a new convex sum-of-squares Bernstein inequality, a certification oracle for a spectral R-center (a direction-wise 60% quantile), and a bounded-differences concentration argument; the algorithm works but leaves a conjectural log(1/δ) gap to optimal.

AI-written summary · about

" chapters (12)

1. 0:00Introduction
2. 3:10Example
3. 10:27Agenda
4. 13:40A cottage industry
5. 17:10Robustness
6. 22:20Hypercontractivity
7. 26:07Algorithm Design
8. 35:20Optimization
9. 38:00Optimization Problem
10. 40:09NonConcave Problem
11. 51:13Sum of squares norms
12. 54:07Open problems

" related talks

• 34mInformation/Computation Gaps in Heavy-Tailed StatisticsSam Hopkins · Computational Phase Transitions (Simons Institute, 2020)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 30mHigh-Dimensional Statistics IMartin Wainwright · Big Data Boot Camp 2013
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 01h 30mHigh-Dimensional Statistics IIMartin Wainwright · Big Data Boot Camp 2013