Computational Barriers to Estimation from Low-Degree Polynomials

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

v2 adds new results on planted clique

References in corpus (46)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Higher criticism for detecting sparse heterogeneous mixtures
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
• Detection of an anomalous cluster in a network
• Incoherence-Optimal Matrix Completion
• Finding large average submatrices in high dimensional data
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Algorithmic barriers from phase transitions
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Local algorithms for independent sets are half-optimal
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• A statistical model for tensor PCA
• Algorithmic thresholds for tensor PCA
• Statistical and computational trade-offs in estimation of sparse principal components
• Suboptimality of local algorithms for a class of max-cut problems
• Tensor principal component analysis via sum-of-squares proofs
• Phase Transitions in Sparse PCA
• (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
• Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure
• Computational Lower Bounds for Community Detection on Random Graphs
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Walksat stalls well below the satisfiability threshold
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Subexponential-Time Algorithms for Sparse PCA
• Average-case Hardness of RIP Certification
• Submatrix localization via message passing
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
• Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
• A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
• The Overlap Gap Property in Principal Submatrix Recovery
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Counterexamples to the Low-Degree Conjecture
• Statistical Query Lower Bounds for Tensor PCA
• Planting trees in graphs, and finding them back
• A greedy anytime algorithm for sparse PCA
• Computationally efficient sparse clustering
• The Overlap Gap Property and Approximate Message Passing Algorithms for $p$-spin models
• Statistical and Computational Limits for Sparse Matrix Detection

Cited by in corpus (8)

• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• The Overlap Gap Property in Principal Submatrix Recovery
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials
• Group testing and local search: is there a computational-statistical gap?
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Precise Error Rates for Computationally Efficient Testing