Information/Computation Gaps in Heavy-Tailed Statistics

on YouTube ↗34m

" summary

Open problem: match the Gaussian high-probability confidence radius r = sqrt(d/n) + sqrt(log(1/δ)/n) for covariance under only bounded moments. Exponential-time high-dimensional medians achieve that, but the polynomial-time algorithm here gets the same form with an extra factor log(1/δ)^{1/4}, requires eighth-moment plus certifiability, and builds a spectral r-center via bucketing and a sum-of-squares SDP certification. A planted-bucket construction gives evidence that certifying below the 1/4 exponent is hard.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:50High dimensional estimation
3. 3:57State of the art
4. 8:43Open problem
5. 12:21Covariance estimator
6. 13:40Spectral R center
7. 16:22Theorem
8. 16:50Rcenter
9. 17:38Partial Progress
10. 19:48Algorithm
11. 21:22Certification
12. 23:50Certification for smaller values of R
13. 25:58Questions

" related talks

• 01h 01mRecent Advances in Algorithmic Heavy-Tailed StatisticsSam Hopkins · Concentration of Measure Phenomena
• 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
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs
• 45mSub-Gaussian Mean Estimation in Polynomial TimeSamuel Hopkins · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)