Related papers: Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

URL: http://arxiv.org/abs/2506.10748v1
Date: Thu, 12 Jun 2025 14:35:26 GMT
Title: Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
Authors: Alexander S. Wein,
Abstract summary: This is a survey on the use of low-degrees to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems.
Score: 57.377943721487966
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This is a survey on the use of low-degree polynomials to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems. In a nutshell, this framework measures the complexity of a statistical task by the minimum degree that a polynomial function must have in order to solve it. The main goals of this survey are to (1) describe the types of problems where the low-degree framework can be applied, encompassing questions of detection (hypothesis testing), recovery (estimation), and more; (2) discuss some philosophical questions surrounding the interpretation of low-degree lower bounds, and notably the extent to which they should be treated as evidence for inherent computational hardness; (3) explore the known connections between low-degree polynomials and other related approaches such as the sum-of-squares hierarchy and statistical query model; and (4) give an overview of the mathematical tools used to prove low-degree lower bounds. A list of open problems is also included.

Related papers

Computational lower bounds in latent models: clustering, sparse-clustering, biclustering [32.472822302123234]
In many high-dimensional problems, like sparse-PCA, planted clustering, or clustering, the best known algorithms with complexity time fail to reach the statistical performance provably achievable by algorithms free of computational constraints.<n>This observation has given rise to the conjecture of the existence, for some problems, of gaps between the best possible statistical performance achievable without computational constraints, and the best performance achievable with poly-time algorithms.<n>A powerful approach to assess the best performance achievable in poly-time is to investigate the best performance achievable by cliques with low-degrees.
arXiv Detail & Related papers (2025-06-16T16:08:30Z)
From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy [3.44747819522562]
We show that languages allowing addition and marginalization yield NPPP, PSPACE, and NEXP-complete satisfiability problems, depending on the level of the PCH.<n>On the other hand, in the case of full languages, i.e. allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels.
arXiv Detail & Related papers (2024-05-12T20:25:36Z)
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics [73.1090889521313]
This paper aims to make a rigorous connection between the different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness. Results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools.
arXiv Detail & Related papers (2022-05-19T17:39:29Z)
Average-Case Communication Complexity of Statistical Problems [48.03761288397421]
Communication complexity is the main tool for proving lower bounds in streaming, sketching, and query-based models. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. We derive two-party and multi-party communication lower bounds for detecting or finding planted cliques.
arXiv Detail & Related papers (2021-07-03T03:31:37Z)
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
We study two of the most popular restricted computational models, the statistical query framework and low-degree corollas, in the context of high-dimensional hypothesis testing. Under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. Asries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.
arXiv Detail & Related papers (2020-09-13T22:55:18Z)
Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
We study the power of low-degrees for the task of detecting the presence of hidden structures. 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. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
arXiv Detail & Related papers (2020-08-05T17:52:10Z)
Marginal likelihood computation for model selection and hypothesis testing: an extensive review [66.37504201165159]
This article provides a comprehensive study of the state-of-the-art of the topic. We highlight limitations, benefits, connections and differences among the different techniques. Problems and possible solutions with the use of improper priors are also described.
arXiv Detail & Related papers (2020-05-17T18:31:58Z)
The empirical duality gap of constrained statistical learning [115.23598260228587]
We study the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all modern information processing. We propose to tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory. We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.
arXiv Detail & Related papers (2020-02-12T19:12:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.