Computational Barriers to Estimation from Low-Degree Polynomials
summary
Considers the spiked Gaussian matrix model with K = N^alpha nonzeros and SNR lambda = N^{beta-alpha}, and shows a concrete lower bound: against no polylog-degree polynomial one can do better than the trivial estimator. Uses the low-degree polynomial framework, defines a degree-D MMSE (estimation analogue of the LD testing statistic), and proves the MMSE at degree polylog N equals the trivial baseline K/N − (K/N)^2 − o(1) in the detection–recovery gap. Result is unconditional for additive Gaussian and many binary-channel models and complements reductions from planted clique/densest k-subgraph.
AI-written summary · about
chapters (9)
- 0:00Introduction to the topic
- 1:00Planted gaussian matrix models
- 2:53Algorithmic goals
- 4:41The phase diagram
- 8:24Evidence for hardness
- 13:34Main results and approach
- 15:24Hypothesis testing background
- 21:05Estimation results
- 25:44Q&A session
related talks
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
19mCounterexamples to the Low-Degree Conjecture
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
31mStatistical Estimation on Graphs
53mOptimality in Locally Private Estimation and Learning
01h 30mAnalytic Methods for Supervised Learning IV
01h 06mAnalytic Methods for Supervised Learning III