Computational Barriers to Estimation from Low-Degree Polynomials

Abstract: One fundamental goal of high-dimensional statistics is to detect and recover structure from noisy data. But even for simple settings (e.g. a planted low-rank matrix perturbed by noise), the computational complexity of estimation is sometimes poorly understood. A growing body of work studies low-degree polynomials as a proxy for computational complexity: it has been demonstrated in various settings that low-degree polynomials of the data can match the statistical performance of the best known polynomial-time algorithms for detection. But prior work has failed to address settings in which there is a "detection-recovery gap" and detection is qualitatively easier than recovery.

In this talk, I'll describe a recent result in which we extend the method of low-degree polynomials to address recovery problems. As applications, we resolve (in the low-degree framework) open problems about the computational complexity of recovery for the planted submatrix and planted dense subgraph problems.

Based on joint work with Alex Wein.

analysis of PDEsmetric geometryprobability

Audience: researchers in the topic

Online asymptotic geometric analysis seminar

Series comments: The link: technion.zoom.us/j/99202255210

If you are interested in giving a talk, please let one of the organizers know. Also, please suggest speakers which you would like to hear talk. Most talks are 50 minutes, but some 20-minute talks will be paired up as well. The talks will be video recorded conditioned upon the speakers' agreement.