Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent

Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, Tselil Schramm
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:774-774, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-brennan21a, title = {Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent}, author = {Brennan, Matthew S and Bresler, Guy and Hopkins, Sam and Li, Jerry and Schramm, Tselil}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {774--774}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/brennan21a/brennan21a.pdf}, url = {https://proceedings.mlr.press/v134/brennan21a.html}, 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.} }
Endnote
%0 Conference Paper %T Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent %A Matthew S Brennan %A Guy Bresler %A Sam Hopkins %A Jerry Li %A Tselil Schramm %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-brennan21a %I PMLR %P 774--774 %U https://proceedings.mlr.press/v134/brennan21a.html %V 134 %X 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.
APA
Brennan, M.S., Bresler, G., Hopkins, S., Li, J. & Schramm, T.. (2021). Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:774-774 Available from https://proceedings.mlr.press/v134/brennan21a.html.

Related Material