Algorithmic High Dimensional Robust Statistics II

on YouTube ↗01h 04m

" summary

Proves a concrete certificate: if the empirical covariance spectral norm stays within 1+δ then the empirical mean is robust under strong contamination, with error bound ≈ ε sqrt(log(1/ε)) for sub‑Gaussian data; additive corruption gives ε. Uses a key lemma about removing any ε fraction changing moments by at most log(1/ε), combines naive pruning, projection thresholds and a recursive dimension‑halving or iterative filtering procedure. Algorithm runs in roughly N·d^2 time, removes more corrupt than good points, and matches known SQ lower bounds for computational hardness.

AI-written summary · about

" chapters (30)

1. 0:00Intro
2. 0:27PROOF OF KEY LEMMA: ADDITIVE CORRUPTIONS (IV)
3. 3:09HANDLING STRONG CORRUPTIONS
4. 3:42PROOF OF KEY LEMMA: STRONG CORRUPTIONS (1)
5. 11:51PROOF OF KEY LEMMA: STRONG CORRUPTIONS (V)
6. 16:51OUTLINE
7. 18:12RECURSIVE DIMENSION-HALVING LRV 16
8. 20:53PROOF OF GOOD SUBSPACE LEMMA (1)
9. 23:26PROOF OF GOOD SUBSPACE LEMMA (IV)
10. 29:15RECURSIVE DIMENSION-HALVING ALGORITHM LRV 16
11. 32:51ITERATIVE FILTERING DKKLMS'16
12. 40:34FILTERING SUBROUTINE: ANALYSIS SKETCH
13. 43:02FILTERING SUBROUTINE: PSEUDO-CODE
14. 44:30SKETCH OF CORRECTNESS (II)
15. 45:16SUMMARY: ROBUST MEAN ESTIMATION VIA FILTERING
16. 46:47SOFT OUTLIER REMOVAL
17. 48:14APPROXIMATE SEPARATION ORACLE
18. 49:22ROBUST MEAN ESTIMATION: SUB-GAUSSIAN CASE
19. 50:31OPTIMAL GAUSSIAN ROBUST MEAN ESTIMATION?
20. 51:00GAUSSIAN ROBUST MEAN ESTIMATION: ADDITIVE ERRORS
21. 51:41COMPUTATIONAL LIMITATIONS TO ROBUST MEAN ESTIMATION
22. 52:55POWER OF SQ ALGORITHMS
23. 53:30METHODOLOGY FOR SQ LOWER BOUNDS
24. 54:06GENERIC LOWER BOUND CONSTRUCTION
25. 56:31FURTHER APPLICATIONS OF GENERIC CONSTRUCTION
26. 56:54ROBUST MEAN ESTIMATION: GENERAL CASE
27. 57:44ROBUST COVARIANCE ESTIMATION
28. 57:59SUMMARY AND CONCLUSIONS
29. 58:23BEYOND ROBUST STATISTICS: ROBUST SUPERVISED LEARNING
30. 59:36OPEN QUESTIONS

" related talks

• 31mRealizing RobustnessGautam Kamath · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 07mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 31mTowards Lower Bounds for Efficient Robust Estimation From Worst Case AssumptionsJerry Li · Rigorous Evidence for Information-Computation Trade-offs
• 01h 01mRecent Advances in Algorithmic Heavy-Tailed StatisticsSam Hopkins · Concentration of Measure Phenomena
• 09mFrom Robustness to Privacy and BackLydia Zakynthinou · 9th Annual Simons Institute Industry Day
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis