ISL colloquium presents "Computational Barriers to Estimation from Low-Degree Polynomials"

Computational Barriers to Estimation from Low-Degree Polynomials
Thursday, October 8, 2020 - 4:30pm
Zoom registration required
Alex Wein (NYU's Courant Institute)
Abstract / Description: 

One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data. A growing body of work studies low-degree polynomials as a restricted model of computation for such problems. Many leading algorithmic paradigms (such as spectral methods and approximate message passing) can be captured by low-degree polynomials, and thus, lower bounds against low-degree polynomials serve as evidence for computational hardness of statistical problems.

Prior work has studied the power of low-degree polynomials for the detection (i.e. hypothesis testing) task. In this work, we extend these methods to address problems of estimating (i.e. recovering) the planted signal instead of merely detecting its presence. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree-D polynomial. These are the first results to establish low-degree hardness of recovery problems for which the associated detection problem is easy. As applications, we study the planted submatrix and planted dense subgraph problems, resolving (in the low-degree framework) open problems about the computational complexity of recovery in both cases.

Joint work with Tselil Schramm, available at:


Alex Wein is a Courant Instructor (postdoc) in the department of mathematics at NYU's Courant Institute. He received a PhD from the MIT department of mathematics in 2018, advised by Ankur Moitra. His research interests are centered around understanding the computational complexity of problems in high-dimensional statistics.