Towards Practical Algorithms for Outlier-Robust Estimation

on YouTube ↗17m

" summary

Claims the first algorithm for sparse mean estimation with provable sub-quadratic runtime (for any Q>3) while maintaining near‑optimal error and sample complexity polynomial in k and log d with no explicit dependence on d. It achieves this by reducing the sparse PCA step to a correlation‑detection / light‑bulb primitive so covariance never needs to be written down. Current limits: requires Gaussian inliers, is not differentially private, and is sub‑quadratic but not yet linear time.

AI-written summary · about

" chapters (16)

1. 0:00Introduction
2. 1:08Outliers disrupt ML pipelines
3. 2:11Robust mean estimation challenge
4. 3:16High-dimensional robust algorithms
5. 3:58Algorithm design metrics
6. 4:38Sparse mean estimation runtime
7. 6:43Quadratic runtime barrier
8. 7:28Subquadratic sparse mean estimation
9. 8:10Minimal-resource ML directions
10. 10:37Future directions and open problems
11. 10:58Extending robustness beyond mean
12. 12:25Outliers in classification
13. 13:28Partitioning inliers and outliers
14. 13:51Privacy in robust estimation
15. 14:44Information-computation tradeoffs
16. 15:46Limitations and next steps

" related talks

• 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
• 41mEfficient Algorithms for Outlier-Robust RegressionAdam R. Klivans · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 31mRealizing RobustnessGautam Kamath · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 44mSome Problems of Robust High-dimensional StatisticsGilad Lerman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)