Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

Abstract

Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach is to characterize the limits of restricted models of computation, which on the one hand yields strong computational lower bounds for powerful classes of algorithms and on the other hand helps guide the development of efficient algorithms. In this paper, we study two of the most popular restricted computational models, the statistical query framework and low-degree polynomials, in the context of high-dimensional hypothesis testing. Our main result is that under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. As corollaries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.

arXiv commentVersion 3 fixes typos and adds note on presentation at COLT 2021

References in corpus (20)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Scaling Laws for Neural Language Models
• Statistical physics of inference: Thresholds and algorithms
• Optimal Solutions for Sparse Principal Component Analysis
• Computational and Statistical Tradeoffs via Convex Relaxation
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Computational barriers in minimax submatrix detection
• Exact Recovery of Sparsely-Used Dictionaries
• Finding One Community in a Sparse Graph
• Risk and parameter convergence of logistic regression
• Phase Retrieval for Sparse Signals: Uniqueness Conditions
• Computational Barriers to Estimation from Low-Degree Polynomials
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Subexponential-Time Algorithms for Sparse PCA
• Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
• Counterexamples to the Low-Degree Conjecture
• How Hard Is Robust Mean Estimation?
• Statistical Query Lower Bounds for Tensor PCA
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds

Cited by in corpus (6)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Statistical Query Lower Bounds for Tensor PCA
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property
• Statistical Query Lower Bounds for List-Decodable Linear Regression
• Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise