[Statlist] ETH Young Data Science Researcher Seminar Zurich, Virtual Seminar by Alex Wein NYU, New York University, 9 October 2020

[Maurer Letizia]

Dear all

We are glad to announce the following talk in the virtual ETH Young Data Science Researcher Seminar Zurich

"Computational Barriers to Estimation from Low-Degree Polynomials"  
by Alex Wein, NYU, New York University

Time: Friday, 09 October 2020, 15:00-​16:00
Place: Zoom at https://ethz.zoom.us/j/92367940258

Abstract: 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


Best wishes,

M. Löffler, A. Taeb, Y. Chen

Seminar website: https://math.ethz.ch/sfs/news-and-events/young-data-science.html