Computational-Statistical Tradeoffs in Robust High-Dimensional Estimation

on YouTube ↗48m

" summary

Shows that beating the current epsilon·sqrt(log(1/epsilon)) error for robust high‑dimensional Gaussian mean estimation forces either statistical query model algorithms to use accuracy like D^{-M} (hence D^{M} samples) or at least D^{M} queries, so any superconstant improvement costs superpolynomial time or samples. Proof builds explicit hard families by embedding a one‑dimensional moment‑matching construction into high dimensions (think parallel “pancake” Gaussians) and analyzes projections via the Ornstein‑Uhlenbeck operator, framing the core hardness as non‑Gaussian component analysis.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 1:31ROBUST HIGH-DIMENSIONAL ESTIMATION
3. 2:17THE UNSUPERVISED LEARNING PROBLEM
4. 3:16ROBUSTLY LEARNING A GAUSSIAN - PRIOR WORK
5. 5:05ROBUST LEARNING - OPEN QUESTION
6. 7:11STATISTICAL QUERIES KEARNS' 93
7. 9:00POWER OF SQ ALGORITHMS?
8. 10:17METHODOLOGY FOR SQ LOWER BOUNDS Statistical Query Dimension
9. 12:27STATISTICAL QUERY LOWER BOUND FOR ROBUSTLY LEARNING A GAUSSIAN
10. 19:54GENERAL LOWER BOUND CONSTRUCTION
11. 20:20APPLICATIONS: CONCRETE SQ LOWER BOUNDS Unified technique yielding a range of applications
12. 24:12SEPARATION ASSUMPTIONS
13. 25:16LEARNING GMMS-OPEN QUESTION
14. 25:51STATISTICAL QUERY LOWER BOUND FOR LEARNING GMMS
15. 27:28OUTLINE
16. 27:57GENERAL RECIPE FOR (SQ) LOWER BOUNDS
17. 29:47HIDDEN DIRECTION DISTRIBUTION
18. 30:31GENERIC SQ LOWER BOUND
19. 34:07WHY IS FINDING A HIDDEN DIRECTION HARD?
20. 35:00ONE-DIMENSIONAL PROJECTIONS ARE ALMOST GAUSSIAN
21. 37:51PROOF OF KEY LEMMA (1)
22. 39:12EIGENFUNCTIONS OF ORNSTEIN-UHLENBECK OPERATOR
23. 40:13APPLICATION: SQ LOWER BOUND FOR GMMS (II)
24. 41:23SUMMARY AND FUTURE DIRECTIONS

" related talks

• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 01h 07mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 31mTowards Lower Bounds for Efficient Robust Estimation From Worst Case AssumptionsJerry Li · Rigorous Evidence for Information-Computation Trade-offs
• 01h 30mHigh-Dimensional Statistics IMartin Wainwright · Big Data Boot Camp 2013
• 34mInformation/Computation Gaps in Heavy-Tailed StatisticsSam Hopkins · Computational Phase Transitions (Simons Institute, 2020)
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)