Robust List Decoding of Spherical Gaussians

on YouTube ↗49m

" summary

An algorithm uses multi-filters plus spectral checks and degree-d polynomial tests to list-decode a spherical Gaussian when only an alpha fraction of samples are good. It returns an O(1/alpha) list and proves error O(alpha^{-1/(2d)}), with quasi-polynomial samples/time pushing error toward O(sqrt(log(1/alpha))). Implementation needs roughly poly(n^d/alpha) samples and similar runtime; the method reduces detectability to multilinear tests on independent Gaussian copies and matches statistical-query lower bounds for improved error without exponential cost.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 0:11Outline
3. 4:07Problem
4. 10:24Hypotheses
5. 14:07Counting
6. 15:27Notes
7. 18:05Summary
8. 18:34Algorithms
9. 19:45Identifying Errors
10. 21:34Moderately Robust Algorithm
11. 26:12Multifilter Case
12. 29:58General Situation
13. 31:10Basic Multifilter Algorithm
14. 32:41Analysis
15. 34:15Obstacle at -1/2
16. 36:15Computational Difficulty
17. 37:48Basic Idea
18. 38:27A Failed Attempt
19. 40:52Requirements
20. 41:15Final Results
21. 41:58SQ Lower Bounds
22. 45:19Conclusion

" related talks

• 29mApproximating Spherical Gaussian MixturesAnanda Suresh · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 30mAnalytic Methods for Supervised Learning IVAdam R. Klivans · Real Analysis Boot Camp 2013
• 01h 31mUnsupervised LearningSantosh Vempala · The Brain and Computation Boot Camp
• 37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian MixturesPravesh K. Kothari · Computational Phase Transitions (Simons Institute, 2020)
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 36mPrivately Learning High-Dimensional DistributionsGautam Kamath · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)