Convex Programs, Computational Phase Transitions, and Robust Algorithms

on YouTube ↗09m

" summary

Claims a polynomial-time algorithm that, under only bounded covariance (two finite moments), returns mean estimates with the same Gaussian-optimal confidence radius (up to constants) and works even when the empirical mean fails; the construction uses sum-of-squares convex programs. On the hardness side it gives concrete evidence that those same sum-of-squares relaxations cannot detect a planted n^{1/3} clique in Erdős–Rényi graphs, framing a route to formalize low-degree hardness.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 1:32Algorithm Design
3. 2:20Example Problem
4. 3:53HighDimensional Median
5. 4:47polynomial time
6. 5:38easy problems
7. 7:04hypothesis testing problems
8. 8:19other topics
9. 8:39next week

" related talks

• 39mAbove Average-Case Analysis?Ankur Moitra · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 43mComputational and Statistical Tradeoffs via Convex RelaxationVenkat Chandrasekaran · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 44mMixture Models, Robustness, and Sum of Squares ProofsJerry Li · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 34mInformation/Computation Gaps in Heavy-Tailed StatisticsSam Hopkins · Computational Phase Transitions (Simons Institute, 2020)