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.

本文研究在高维假设检验中的受限计算模型，特别是统计查询框架和低次多项式，在测试问题上的表现。主要结果表明，在测试问题的温和条件下，这两类算法在能力上基本等效，并提供了有限制的统计查询下界和植入团问题的几个变种。

统计查询算法与低阶检验几乎等效