EE Student Information

The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • •

EE Student Information, Spring Quarter through Academic Year 2020-2021: FAQs and Updated EE Course List.

Updates will be posted on this page, as well as emailed to the EE student mail list.

Please see Stanford University Health Alerts for course and travel updates.

As always, use your best judgement and consider your own and others' well-being at all times.

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

Topic: 
Computational Barriers to Estimation from Low-Degree Polynomials
Thursday, October 8, 2020 - 4:30pm
Venue: 
Zoom registration required
Speaker: 
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: https://arxiv.org/abs/2008.02269

Bio:

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.