COMPUTATIONAL BARRIERS TO ESTIMATION FROM LOW-DEGREE POLYNOMIALS

• 成果类型: Article
• 署名作者: Schramm, Tselil; Wein, Alexander S.
• 署名单位: Stanford University; New York University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/22-AOS2179
• 发表日期: 2022
• 页码: 1833-1858
• 关键词: message-passing algorithms; community detection; LARGEST EIGENVALUE; sparse submatrix; local algorithms; deformation; matrices; graphs; SUM

摘要

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: 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. Prior work has studied the power of low-degree polynomials for the task of detecting the presence of hidden structures. In this work, we extend these methods to address problems of estimation and recovery (instead of detection). 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. To our knowledge, these are the first results to establish low-degree hardness of recovery problems for which the associated detection problem is easy. As applications, we give a tight characterization of the low-degree minimum mean squared error for 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.