Above Average-Case Analysis?

on YouTube ↗39m

" summary

Claims a polynomial-time procedure that, under an adversary who corrupts an ε fraction of samples (or distributions ε-close in total variation), recovers mean and covariance of a d-dimensional Gaussian with error O(ε · polylog(1/ε)), using about O(d^2/ε^2) samples and O(nd^2) time. Core tools are a spectral test on second/flattened fourth moments, a restricted-eigenvalue lemma that detects compromise, and a fast filtering/pruning loop that empirically outperforms geometric median and RANSAC in moderate dimensions.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:58CLASSIC PARAMETER ESTIMATION
3. 3:13ROBUST STATISTICS
4. 11:53A COMPENDIUM OF APPROACHES
5. 15:13The Price of Robustness?
6. 20:33A GENERAL RECIPE
7. 29:56PARAMETER DISTANCE
8. 30:41UNKNOWN COVARIANCE

" related talks

• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 36mPrivately Learning High-Dimensional DistributionsGautam Kamath · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 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)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 07mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)