Realizing Robustness
Talkat Robust and High-Dimensional Statistics (Simons Institute workshop, 2018) · 2018-10-29..11-02·
summary
Claim: efficient algorithms achieve O(ε) error for mean (and covariance) estimation under ε-corruption with no dimension-dependent factor; method: compute empirical covariance, take the top-eigenvector filtering direction, project and truncate heavy tails, repeat. Empirically with 10% adversarial noise on 100–400 dimensional Gaussians the filter outperforms sample mean, RANSAC and prior methods; PCA on genomic data recovers the Europe-like map after injected outliers; SEVER (filtering gradients, run few times) defends regression and SVMs against targeted poisoning with substantially lower test error.
AI-written summary · about
chapters (21)
- 0:00Intro
- 0:55Huber's (1997) Call to Arms
- 1:29Classic Motivations
- 2:32Modern Motivations
- 4:53Robust Estimation
- 6:08A Sample Result
- 8:05Filtering for Gaussian Mean Estimation
- 10:32Does the filter "work"?
- 11:13Synthetic Experiments, Unknown Mean
- 12:49Synthetic Experiments, Unknown Covariance
- 15:25Gene Expression PCA Contains Europe
- 17:47Naively, Corruptions Destroy Europe
- 18:05Europe is RANSACked
- 18:22Our Algorithms Fix Europe!
- 19:50Beyond Robust Statistics
- 22:10Sever: Robust Stochastic Optimization
- 23:58Making it practical
- 26:18Attacks
- 28:17Ridge Regression
- 29:36SVMs, synthetic data
- 30:04Conclusions
related talks
01h 04mAlgorithmic High Dimensional Robust Statistics II
01h 00mAlgorithmic High Dimensional Robust Statistics I
45mHigh Dimensional Robust Sparse Regression
39mAbove Average-Case Analysis?
12mDistribution-Free Robustness
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
53mDesigning Robust Learners
17mTowards Practical Algorithms for Outlier-Robust Estimation