Recent Progress in High-Dimensional Learning
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28·
summary
1D robust estimation uses the median absolute deviation to get O(ε) TV guarantees, but high dimensions face hardness: the Tukey median is robust but NP‑hard, while coordinatewise medians lose a √D factor. The main claim is a polynomial‑time algorithm that agnostically learns a d‑dimensional Gaussian from a distribution ε‑close in TV with dimension‑independent error Õ(ε) for mean and covariance. Key tools are fourth moment flattening and spectral filtering to remove adversarial outliers; SQ lower bounds show ε√log(1/ε) is unavoidable in some strong models.
AI-written summary · about
chapters (22)
- 0:00Introduction
- 1:35Parametric Statistics
- 2:56Maximum likelihood estimation
- 5:15How to constrain noise
- 8:08Estimating parameters
- 10:10Do empirical mean and empirical variance work
- 13:42Folklore Theorem
- 17:57Robustness and Hardness
- 24:35Price of Robustness
- 26:14Recent Results
- 28:44Robust Estimation Recipe
- 35:22WinWin Algorithm
- 45:46Birds Eye View
- 46:04O of epsilon
- 48:47Relaxing Distributional Assumption
- 49:43Robust Estimation
- 50:55Conclusion
- 52:56Does the error guarantee tend to O
- 54:09Is there a sense that some adversaries are complete
- 56:18gaussian mean estimation
- 57:40adversary efficiency
- 59:20improper learning
related talks
01h 00mAlgorithmic High Dimensional Robust Statistics I
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
45mHigh Dimensional Robust Sparse Regression
01h 04mAlgorithmic High Dimensional Robust Statistics II
36mPrivately Learning High-Dimensional Distributions
39mAbove Average-Case Analysis?
01h 30mHigh-Dimensional Statistics I
01h 30mAnalytic Methods for Supervised Learning IV