Sub-Gaussian Mean Estimation in Polynomial Time
Talkat Robust and High-Dimensional Statistics (Simons Institute workshop, 2018) · 2018-10-29..11-02·
summary
Proposes a polynomial-time algorithm called median SDP that, after bucketing samples and using the median-of-means idea, finds a center whose confidence radius matches the Gaussian sub-Gaussian rate up to constants while assuming only two finite moments. The method formulates a direction-wise median certification as an SDP built from the sum-of-squares framework, analyzes expected value via a 2→1 matrix norm and gets exponential concentration via bounded-differences, and runs in polynomial but practically large time.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:26Estimating the mean of a random vector
- 3:53Heavy Tails and the Empirical Mean
- 9:07Prior Work
- 14:20Main Theorem
- 20:47Median of means in higher dimensions
- 23:20Lugosi and Mendelson's median
- 24:45Lugosi and Mendelson's estimator
- 26:43Main lemma for Lugosi-Mendelson estimator
- 32:00Certifying the median
- 37:14Glimpse of the analysis
- 39:26Proof insights
- 40:24Conclusion
related talks
34mInformation/Computation Gaps in Heavy-Tailed Statistics
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
39mAbove Average-Case Analysis?
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
01h 00mAlgorithmic High Dimensional Robust Statistics I
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
01h 02mEstimation Beyond the IID Setting (Two Vignettes)
17mTowards Practical Algorithms for Outlier-Robust Estimation