Algorithmic High Dimensional Robust Statistics I

on YouTube ↗01h 00m

" summary

Goal: recover a Gaussian mean in d dimensions with an epsilon fraction of corruptions and identity covariance. Transcript claims sample complexity Theta(d/epsilon^2), naive estimators give error ~epsilon sqrt(d), and exponential-time Tukey/net methods solve it in 2^{O(d)}. Two polynomial-time approaches use spectral checks and empirical covariance spectral norm certificates plus iterative filtering to trim outliers, yielding provable errors O(epsilon sqrt(log d)) or O(epsilon sqrt(log 1/epsilon)) depending on the contamination model.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 1:20MOTIVATION
3. 2:25DETECTING OUTLIERS IN REAL DATASETS
4. 3:27DATA POISONING
5. 4:12THE STATISTICAL LEARNING PROBLEM
6. 6:37ROBUSTNESS IN A GENERATIVE MODEL
7. 7:41MODELS OF ROBUSTNESS
8. 11:25EXAMPLE: PARAMETER ESTIMATION
9. 13:04ROBUST STATISTICS
10. 13:20ROBUST ESTIMATION: ONE DIMENSION
11. 17:03GAUSSIAN ROBUST MEAN ESTIMATION
12. 18:38PREVIOUS APPROACHES: ROBUST MEAN ESTIMATION
13. 25:21THIS TALK: ROBUST GAUSSIAN MEAN ESTIMATION
14. 28:39HIGH-DIMENSIONAL GAUSSIAN MEAN ESTIMATION (0)
15. 31:16INFORMATION-THEORETIC LIMITS ON ROBUST ESTIMATION (1)
16. 35:08SAMPLE EFFICIENT ROBUST MEAN ESTIMATION (1)
17. 39:21SAMPLE EFFICIENT ROBUST MEAN ESTIMATION (III)
18. 43:43OUTLIER DETECTION ?
19. 44:46NAIVE OUTLIER REMOVAL (NAIVE PRUNING)
20. 45:38ON THE EFFECT OF CORRUPTIONS
21. 48:28THREE APPROACHES: OVERVIEW AND COMPARISON
22. 49:27OUTLINE
23. 49:49CERTIFICATE OF ROBUSTNESS FOR EMPIRICAL ESTIMATOR
24. 53:53PROOF OF KEY LEMMA: ADDITIVE CORRUPTIONS (1)
25. 55:25PROOF OF KEY LEMMA: ADDITIVE CORRUPTIONS (III)

" related talks

• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 07mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 31mRealizing RobustnessGautam Kamath · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 34mInformation/Computation Gaps in Heavy-Tailed StatisticsSam Hopkins · Computational Phase Transitions (Simons Institute, 2020)
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 30mHigh-Dimensional Statistics IMartin Wainwright · Big Data Boot Camp 2013
• 36mPrivately Learning High-Dimensional DistributionsGautam Kamath · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)