REVIEW 6 cited by
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 6 Pith papers
-
Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
For any t, directed shortest paths can be computed with near-linear work plus n^{1+o(1)}t^2 work and roughly n/t parallel depth, matching the undirected tradeoff.
-
Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
A quantum extension of the low-degree method shows that state designs imply computational hardness for many single-copy quantum measurement strategies, yielding new information-computation gaps.
-
On optimal distinguishers for Planted Clique
Under the Planted Clique Hypothesis, the optimal efficient distinguishing advantage for Planted Clique is (1+o(1))*k^2/(sqrt(pi)*n), and there exist planted distributions that are much harder to detect than the usual one.
-
Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
A conditioning-based cumulant bound yields tight low-degree lower bounds for clustering, sparse clustering, and biclustering, recovering the BBP threshold with exact constants.
-
Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
A new 'hybrid DEC' complexity measure gives matching (up to logs) lower and upper bounds for decision-making under constrained adversaries, unifying SQ, LDP, robust, and smooth learning, with new LDP contextual bandit...
-
Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
A unified tensor-based lower bound shows low-coordinate-degree tests fail for generalized stochastic block models at the generalized Kesten-Stigum threshold.
Discussion (0). Continue with ORCID to comment.