Towards Lower Bounds for Efficient Robust Estimation From Worst Case Assumptions
summary
Shows that beating O(sqrt(epsilon)) under only moment or resilience assumptions is probably impossible by reductions from small‑set expansion variants: constant‑factor hardness for maximizing K‑th moment norms and for certifying resilience, plus a direct reduction (via the isotropic spectral embedding) from a unique small‑set expansion promise to robust mean estimation. Highlights that an SQ algorithm exists so barriers must be non‑SQ, and pins the computational bottleneck to solving the degree‑K tensor / K‑moment tensor optimization needed to detect outlier directions.
AI-written summary · about
chapters (12)
- 0:00Intro
- 1:34Robust mean estimation from bounded moments
- 4:08Robust mean estimation from resilience
- 7:44Efficient algorithms (cont.)
- 9:32Barriers to efficient methods
- 12:36How do we prove hardness?
- 19:29The small set expansion hypotheses
- 21:21Two paths diverged in a complexity landscape...
- 22:58Isotropic spectral embeddings
- 24:27From spectral embeddings to resilient sets
- 26:31From a variant of SSE to robust mean estimation
- 28:01Open directions
related talks
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
01h 04mAlgorithmic High Dimensional Robust Statistics II
17mTowards Practical Algorithms for Outlier-Robust Estimation
45mHigh Dimensional Robust Sparse Regression
41mEfficient Algorithms for Outlier-Robust Regression
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
01h 00mAlgorithmic High Dimensional Robust Statistics I
44mMixture Models, Robustness, and Sum of Squares Proofs