Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Dmitriy Kunisky Alexander S. Wein Afonso S. Bandeira
math.ST cs.CC cs.DS stat.ML stat.TH


Role of coherence in the plasmonic control of molecular absorption
    Stefano Corni
    December 30, 2023
==================================================================





These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems. In short, the method posits that a certain quantity – the second moment of the low-degree likelihood ratio – gives insight into how much computational time is required to solve a given hypothesis testing problem, which can in turn be used to predict the computational hardness of a variety of statistical inference tasks. While this method originated in the study of the sum-of-squares (SoS) hierarchy of convex programs, we present a self-contained introduction that does not require knowledge of SoS. In addition to showing how to carry out predictions using the method, we include a discussion investigating both rigorous and conjectural consequences of these predictions.

These notes include some new results, simplified proofs, and refined conjectures. For instance, we point out a formal connection between spectral methods and the low-degree likelihood ratio, and we give a sharp low-degree lower bound against subexponential-time algorithms for tensor PCA.













§ OVERVIEW

tocsectionOverview

Many problems in high-dimensional statistics are believed to exhibit gaps between what can be achieved information-theoretically (or statistically, i.e., with unbounded computational power) and what is possible with bounded computational power (e.g., in polynomial time). Examples include finding planted cliques <cit.> or dense communities <cit.> in random graphs, extracting variously structured principal components of random matrices <cit.> or tensors <cit.>, and solving or refuting random constraint satisfaction problems <cit.>.

Although current techniques cannot prove that such average-case problems require super-polynomial time (even assuming P  NP), various forms of rigorous evidence for hardness have been proposed. These include:

    
  * failure of Markov chain Monte Carlo methods <cit.>;
    
  * failure of local algorithms <cit.>;
    
  * methods from statistical physics which suggest failure of belief propagation or approximate message passing algorithms <cit.> (see <cit.> for a survey or <cit.> for expository notes);
    
  * structural properties of the solution space <cit.>;
    
  * geometric analysis of non-convex optimization landscapes <cit.>;
    
  * reductions from planted clique (which has become a “canonical” problem believed to be hard in the average case) <cit.>;
    
  * lower bounds in the statistical query model <cit.>;
    
  * lower bounds against the sum-of-squares hierarchy <cit.> (see <cit.> for a survey).
 

In these notes, we survey another emerging method, which we call the low-degree method, for understanding computational hardness in average-case problems. 
In short, we explore a conjecture that the behavior of a certain quantity – the second moment of the low-degree likelihood ratio – reveals the computational complexity of a given statistical task. 
We find the low-degree method particularly appealing because it is simple, widely applicable, and can be used to study a wide range of time complexities (e.g., polynomial, quasipolynomial, or nearly-exponential).
Furthermore, rather than simply positing a certain “optimal algorithm,” the underlying conjecture captures an interpretable structural feature that seems to dictate whether a problem is easy or hard. 
Finally, and perhaps most importantly, predictions using the low-degree method have been carried out for a variety of average-case problems, and so far have always reproduced widely-believed results.

Historically, the low-degree method arose from the study of the sum-of-squares (SoS) semidefinite programming hierarchy. In particular, the method is implicit in the pseudo-calibration approach to proving SoS lower bounds <cit.>. Two concurrent papers <cit.> later articulated the idea more explicitly. In particular, Hopkins and Steurer <cit.> were the first to demonstrate that the method can capture sharp thresholds of computational feasibility such as the Kesten–Stigum threshold for community detection in the stochastic block model. The low-degree method was developed further in the PhD thesis of Hopkins <cit.>, which includes a precise conjecture about the complexity-theoretic implications of low-degree predictions. In comparison to sum-of-squares lower bounds, the low-degree method is much simpler to carry out and appears to always yield the same results for natural average-case problems.

In these notes, we aim to provide a self-contained introduction to the low-degree method; we largely avoid reference to SoS and instead motivate the method in other ways. We will briefly discuss the connection to SoS in Section <ref>, but we refer the reader to <cit.> for an in-depth exposition of these connections.

These notes are organized as follows. In Section <ref>, we present the low-degree method and motivate it as a computationally-bounded analogue of classical statistical decision theory. In Section <ref>, we show how to carry out the low-degree method for a general class of additive Gaussian noise models. In Section <ref>, we specialize this analysis to two classical problems: the spiked Wigner matrix and spiked Gaussian tensor models. Finally, in Section <ref>, we discuss various forms of heuristic and formal evidence for correctness of the low-degree method; in particular, we highlight a formal connection between low-degree lower bounds and the failure of spectral methods (Theorem <ref>).




§ TOWARDS A COMPUTATIONALLY-BOUNDED DECISION THEORY




 §.§ Statistical-to-Computational Gaps in Hypothesis Testing


The field of statistical decision theory (see, e.g., <cit.> for general references) is concerned with the question of how to decide optimally (in some quantitative sense) between several statistical conclusions.
The simplest example, and the one we will mainly be concerned with here, is that of simple hypothesis testing: we observe a dataset that we believe was drawn from one of two probability distributions, and want to make an inference (by performing a statistical test) about which distribution we think the dataset was drawn from.

However, one important practical aspect of statistical testing usually is not included in this framework, namely the computational cost of actually performing a statistical test.
In these notes, we will explore ideas from a line of recent research about how one mathematical method of classical decision theory might be adapted to predict the capabilities and limitations of computationally bounded statistical tests.

The basic problem that will motivate us is the following.
Suppose = (_n)_n ∈ and = (_n)_n ∈ are two sequences of probability distributions over a common sequence of measurable spaces = ((_n, _n))_n ∈.
(In statistical parlance, we will think throughout of  as the model of the alternative hypothesis and  as the model of the null hypothesis. Later on, we will consider hypothesis testing problems where the distributions  include a “planted” structure, making the notation a helpful mnemonic.)
Suppose we observe ∈_n which is drawn from one of _n or _n.
We hope to recover this choice of distribution in the following sense.


    We say that a sequence of events (A_n)_n ∈ with A_n ∈_n occurs with high probability (in n) if the probability of A_n tends to 1 as n →∞.



    A sequence of (measurable) functions f_n: _n →{, } is said to strongly distinguish[We will only consider this so-called strong version of distinguishability, where the probability of success must tend to 1 as n →∞, as opposed to the weak version where this probability need only be bounded above 1/2. For high-dimensional problems, the strong version typically coincides with important notions of estimating the planted signal (see Section <ref>), whereas the weak version is often trivial.]  and  if f_n() = with high probability when ∼_n, and f_n() = with high probability when ∼_n. If such f_n exist, we say that  and  are statistically distinguishable.


In our computationally bounded analogue of this definition, let us for now only consider polynomial time tests (we will later consider various other restrictions on the time complexity of f_n, such as subexponential time).
Then, the analogue of Definition <ref> is the following.


     and  are said to be computationally distinguishable if there exists a sequence of measurable and computable in time polynomial in n functions f_n: _n →{, } such that f_n strongly distinguishes  and .


Clearly, computational distinguishability implies statistical distinguishability.
On the other hand, a multitude of theoretical evidence suggests that statistical distinguishability does not in general imply computational distinguishability.
Occurrences of this phenomenon are called statistical-to-computational (stat-comp) gaps.
Typically, such a gap arises in the following slightly more specific way. Suppose the sequence  has a further dependence on a signal-to-noise parameter λ > 0, so that _λ = (_λ, n)_n ∈.
This parameter should describe, in some sense, the strength of the structure present under  (or, in some cases, the number of samples received). The following is one canonical example.

[Planted Clique Problem <cit.>]
Under the null model _n, we observe an n-vertex Erdős-Rényi graph (n,1/2), i.e., each pair {i, j} of vertices is connected with an edge independently with probability 1/2. The signal-to-noise parameter λ is an integer 1 ≤λ≤ n. Under the planted model _λ,n, we first choose a random subset of vertices S ⊆ [n] of size |S| = λ uniformly at random. We then observe a graph where each pair {i, j} of vertices is connected with probability 1 if {i,j}⊆ S and with probability 1/2 otherwise. In other words, the planted model consists of the union of (n,1/2) with a planted clique (a fully-connected subgraph) on λ vertices.


As λ varies, the problem of testing between _λ and  can change from statistically impossible, to statistically possible but computationally hard, to computationally easy.
That is, there exists a threshold λ_𝗌𝗍𝖺𝗍 such that for any λ > λ_𝗌𝗍𝖺𝗍, _λ and  are statistically distinguishable, but for λ < λ_𝗌𝗍𝖺𝗍 are not.
There also exists a threshold λ_𝖼𝗈𝗆𝗉 such that for any λ > λ_𝖼𝗈𝗆𝗉, _λ and  are computationally distinguishable, and (conjecturally) for λ < λ_𝖼𝗈𝗆𝗉 are not.
Clearly we must have λ_𝖼𝗈𝗆𝗉≥λ_𝗌𝗍𝖺𝗍, and a stat-comp gap corresponds to strict inequality λ_𝖼𝗈𝗆𝗉 > λ_𝗌𝗍𝖺𝗍. For instance, the two models in the planted clique problem are statistically distinguishable when λ≥ (2+ε) log_2 n (since 2log_2 n is the typical size of the largest clique in (n,1/2)), so λ_𝗌𝗍𝖺𝗍 = 2 log_2 n. However, the best known polynomial-time distinguishing algorithms only succeed when λ = Ω(√(n)) <cit.>, and so (conjecturally) λ_𝖼𝗈𝗆𝗉≈√(n), a large stat-comp gap.

The remarkable method we discuss in these notes allows us, through a relatively straightforward calculation, to predict the threshold λ_𝖼𝗈𝗆𝗉 for many of the known instances of stat-comp gaps.
We will present this method as a modification of a classical second moment method for studying λ_𝗌𝗍𝖺𝗍.




 §.§ Classical Asymptotic Decision Theory


In this section, we review some basic tools available from statistics for understanding statistical distinguishability.
We retain the same notations from the previous section in the later parts, but in the first part of the discussion will only be concerned with a single pair of distributions  and  defined on a single measurable space (, ).
For the sake of simplicity, let us assume in either case that _n (or ) is absolutely continuous with respect to _n (or , as appropriate).[For instance, what will be relevant in the examples we consider later, any pair of non-degenerate multivariate Gaussian distributions satisfy this assumption.]



  §.§.§ Basic Notions


We first define the basic objects used to make hypothesis testing decisions, and some ways of measuring their quality.


    A test is a measurable function f: →{, }.



    The type I error of f is the event of falsely rejecting the null hypothesis, i.e., of having f() = when ∼.
    The type II error of f is the event of falsely failing to reject the null hypothesis, i.e., of having f() = when ∼.
    The probabilities of these errors are denoted
    
    α(f)    (f() = ), 
    β(f)    (f() = ).

    The probability 1 - β(f) of correctly rejecting the null hypothesis is called the power of f.

There is a tradeoff between type I and type II errors.
For instance, the trivial test that always outputs  will have maximal power, but will also have maximal probability of type I error, and vice-versa for the trivial test that always outputs .
Thus, typically one fixes a tolerance for one type of error, and then attempts to design a test that minimizes the probability of the other type.



  §.§.§ Likelihood Ratio Testing


We next present the classical result showing that it is in fact possible to identify the test that is optimal in the sense of the above tradeoff.[It is important to note that, from the point of view of statistics, we are restricting our attention to the special case of deciding between two “simple” hypotheses, where each hypothesis consists of the dataset being drawn from a specific distribution. Optimal testing is more subtle for “composite” hypotheses in parametric families of probability distributions, a more typical setting in practice. The mathematical difficulties of this extended setting are discussed thoroughly in <cit.>.]


    Let  be absolutely continuous with respect to . The likelihood ratio[For readers not familiar with the Radon–Nikodym derivative: if ,  are discrete distributions then L() = ()/(); if ,  are continuous distributions with density functions p, q (respectively) then L() = p()/q().] of  and  is
    
    L() d/d().

    The thresholded likelihood ratio test with threshold η is the test
    
    L_η() {[               : L() > η;               :  L() ≤η ]}.



Let us first present a heuristic argument for why thresholding the likelihood ratio might be a good idea. Specifically, we will show that the likelihood ratio is optimal in a particular “L^2 sense” (which will be of central importance later), i.e., when its quality is measured in terms of first and second moments of a testing quantity.


    For (measurable) functions f,g: →, define the inner product and norm induced by :
    
    f, g    _∼[ f() g() ], 
    f   √(⟨ f,f ⟩).

    Let L^2() denote the Hilbert space consisting of functions f for which f < ∞, endowed with the above inner product and norm.[For a more precise definition of L^2(_n) (in particular including issues around functions differing on sets of measure zero) see a standard reference on real analysis such as <cit.>.]



    
    If  is absolutely continuous with respect to , then the unique solution f^* of the optimization problem
    
    [       maximize       _∼ [f()];     subject to _∼ [f()^2] = 1 ]

    is the (normalized) likelihood ratio
    
    f^⋆ = L/L,

    and the value of the optimization problem is L.


    We may rewrite the objective as
    
    _∼ f() = _∼[L() f() ] = ⟨ L,f ⟩,

    and rewrite the constraint as f = 1. The result now follows since ⟨ L, f ⟩≤L·f = L by the Cauchy-Schwarz inequality, with equality if and only if f is a scalar multiple of L.

In words, this means that if we want a function to be as large as possible in expectation under  while remaining bounded (in the L^2 sense) under , we can do no better than the likelihood ratio.
We will soon return to this type of L^2 reasoning in order to devise computationally-bounded statistical tests.

The following classical result shows that the above heuristic is accurate, in that the thresholded likelihood ratio tests achieve the optimal tradeoff between type I and type II errors.

    
    Fix an arbitrary threshold η≥ 0. Among all tests f with α(f) ≤α(L_η) = (L() > η), L_η is the test that maximizes the power 1 - β(f).

We provide the standard proof of this result in Appendix <ref> for completeness. (The proof is straightforward but not important for understanding the rest of these notes, and it can be skipped on a first reading.)



  §.§.§ Le Cam's Contiguity



Since the likelihood ratio is, in the sense of the Neyman–Pearson lemma, an optimal statistical test, it stands to reason that it should be possible to argue about statistical distinguishability solely by computing with the likelihood ratio.
We present one simple method by which such arguments may be made, based on a theory introduced by Le Cam <cit.>.

We will work again with sequences of probability measures = (_n)_n ∈ and = (_n)_n ∈, and will denote by L_n the likelihood ratio d _n/d _n. Norms and inner products of functions are those of L^2(_n).
The following is the crucial definition underlying the arguments to come.


    A sequence  of probability measures is contiguous to a sequence , written ◃, if whenever A_n ∈_n with _n(A_n) → 0 (as n →∞), then _n(A_n) → 0 as well.



    If ◃ or ◃, then  and  are statistically indistinguishable (in the sense of Definition <ref>, i.e., no test can have both type I and type II error probabilities tending to 0).


    We give the proof for the case ◃, but the other case may be shown by a symmetric argument.
    For the sake of contradiction, let (f_n)_n ∈ be a sequence of tests distinguishing  and , and let A_n = {: f_n() = }.
    Then, _n(A_n^c) → 0 and _n(A_n) → 0.
    But, by contiguity, _n(A_n) → 0 implies _n(A_n) → 0 as well, so _n(A_n^c) → 1, a contradiction.

It therefore suffices to establish contiguity in order to prove negative results about statistical distinguishability.
The following classical second moment method gives a means of establishing contiguity through a computation with the likelihood ratio.

    
    If L_n^2 _∼_n[L_n()^2] remains bounded as n →∞ (i.e., lim sup_n →∞L_n^2 < ∞), then ◃.


    Let A_n ∈_n.
    Then, using the Cauchy–Schwarz inequality,
    
    _n(A_n) = _∼_n [_A_n()] = _∼_n[ L_n() _A_n()] ≤(_∼_n[L_n()^2])^1/2(_n(A_n))^1/2,

    and so _n(A_n) → 0 implies _n(A_n) → 0.


This second moment method has been used to establish contiguity for various high-dimensional statistical problems (see e.g., <cit.>). Typically the null hypothesis _n is a “simpler” distribution than _n and, as a result, d_n/d_n is easier to compute than d_n/d_n. In general, and essentially for this reason, establishing ◃ is often more difficult than ◃, requiring tools such as the small subgraph conditioning method (introduced in <cit.> and used in, e.g., <cit.>). Fortunately, one-sided contiguity _n ◃_n is sufficient for our purposes.

Note that L_n, the quantity that controls contiguity per the second moment method, is the same as the optimal value of the L^2 optimization problem in Proposition <ref>:

    {[         maximize       _∼_n [f()];       subject to _∼_n [f()^2] = 1 ]} = L_n.

We might then be tempted to conjecture that  and  are statistically distinguishable if and only if L_n→∞ as n →∞. However, this is incorrect: there are cases when  and  are not distinguishable, yet a rare “bad” event under _n causes L_n to diverge.
To overcome this failure of the ordinary second moment method, some previous works (e.g., <cit.>) have used conditional second moment methods to show indistinguishability, where the second moment method is applied to a modified  that conditions on these bad events not occurring.



 §.§ Basics of the Low-Degree Method



We now describe the low-degree analogues of the notions described in the previous section, which together constitute a method for restricting the classical decision-theoretic second moment analysis to computationally-bounded tests.
The premise of this low-degree method is to take low-degree multivariate polynomials in the entries of the observation  as a proxy for efficiently-computable functions. The ideas in this section were first developed in a sequence of works in the sum-of-squares optimization literature <cit.>.

In the computationally-unbounded case, Proposition <ref> showed that the likelihood ratio optimally distinguishes  from  in the L^2 sense.
Following the same heuristic, we will now find the low-degree polynomial that best distinguishes  from  in the L^2 sense. In order for polynomials to be defined, we assume here that 𝒮_n ⊆^N for some N = N(n), i.e., our data (drawn from _n or _n) is a real-valued vector (which may be structured as a matrix, tensor, etc.).


    Let ^≤ D_n ⊂ L^2(_n) denote the linear subspace of polynomials _n → of degree at most D.
    Let ^≤ D: L^2(_n) →^≤ D_n denote the orthogonal projection[To clarify, orthogonal projection is with respect to the inner product induced by _n (see Definition <ref>).] operator to this subspace.
    Finally, define the D-low-degree likelihood ratio (D-LDLR) as L_n^≤ D^≤ D L_n.

We now have a low-degree analogue of Proposition <ref>, which first appeared in <cit.>.

    The unique solution f^* of the optimization problem
    
    [          maximize        _∼_n [f()];        subject to _∼_n [f()^2] = 1,;                          f ∈_n^≤ D, ]

    is the (normalized) D-LDLR
    
    f^⋆ = L^≤ D_n/L^≤ D_n,

    and the value of the optimization problem is L_n^≤ D.


As in the proof of Proposition <ref>, we can restate the optimization problem as maximizing ⟨ L_n,f ⟩ subject to f = 1 and f ∈_n^≤ D. Since _n^≤ D is a linear subspace of L^2(_n), the result is then simply a restatement of the variational description and uniqueness of the orthogonal projection in L^2(_n) (i.e., the fact that L_n^≤ D is the unique closest element of _n^≤ D to L_n).


The following informal conjecture is at the heart of the low-degree method. It states that a computational analogue of the second moment method for contiguity holds, with L_n^≤ D playing the role of the likelihood ratio. Furthermore, it postulates that polynomials of degree roughly log(n) are a proxy for polynomial-time algorithms. This conjecture is based on <cit.>, particularly Conjecture 2.2.4 of <cit.>.


    
    For “sufficiently nice” sequences of probability measures  and , if there exists ε > 0 and D = D(n) ≥ (log n)^1+ε for which L_n^≤ D remains bounded as n →∞, then there is no polynomial-time algorithm that strongly distinguishes (see Definition <ref>)  and .

We will discuss this conjecture in more detail later (see Section <ref>), including the informal meaning of “sufficiently nice” and a variant of the LDLR based on coordinate degree considered by <cit.> (see Section <ref>). A more general form of the low-degree conjecture (Hypothesis 2.1.5 of <cit.>) states that degree-D polynomials are a proxy for time-n^Θ̃(D) algorithms, allowing one to probe a wide range of time complexities. We will see that the converse of these low-degree conjectures often holds in practice; i.e., if L_n^≤ D→∞, then there exists a distinguishing algorithm of runtime roughly n^D. As a result, the behavior of L_n^≤ D precisely captures the (conjectured) power of computationally-bounded testing in many settings.

The remainder of these notes is organized as follows.
In Section <ref>, we work through the calculations of L_n, L_n^≤ D, and their norms for a general family of additive Gaussian noise models. In Section <ref>, we apply this analysis to a few specific models of interest: the spiked Wigner matrix and spiked Gaussian tensor models.
In Section <ref>, we give some further discussion of Conjecture <ref>, including evidence (both heuristic and formal) in its favor.





§ THE ADDITIVE GAUSSIAN NOISE MODEL



We will now describe a concrete class of hypothesis testing problems and analyze them using the machinery introduced in the previous section.
The examples we discuss later (spiked Wigner matrix and spiked tensor) will be specific instances of this general class.



 §.§ The Model




Let N = N(n) ∈ and let  (the “signal”) be drawn from some distribution _n (the “prior”) over ^N. Let ∈^N (the “noise”) have i.i.d. entries distributed as (0,1). Then, we define  and  as follows.

    
  * Under _n, observe =  +.
    
  * Under _n, observe =.


One typical situation takes  to be a low-rank matrix or tensor. The following is a particularly important and well-studied special case, which we will return to in Section <ref>.

[Wigner Spiked Matrix Model]

Consider the additive Gaussian noise model with N = n^2, ^N identified with n × n matrices with real entries, and _n defined by = λ^⊤∈^n × n, where λ = λ(n) > 0 is a signal-to-noise parameter and  is drawn from some distribution _n over ^n. Then, the task of distinguishing _n from _n amounts to distinguishing λ^⊤ + from  where ∈^n × n has i.i.d. entries distributed as (0, 1). (This variant is equivalent to the more standard model in which the noise matrix is symmetric; see Appendix <ref>.)


This problem is believed to exhibit stat-comp gaps for some choices of _n but not others; see, e.g., <cit.>.
At a heuristic level, the typical sparsity of vectors under _n seems to govern the appearance of a stat-comp gap.


In the spiked Wigner problem, as in many others, one natural statistical task besides distinguishing the null and planted models is to non-trivially estimate the vector  given ∼_n, i.e., to compute an estimate = () such that |⟨, ⟩|/(·) ≥ε with high probability, for some constant ε > 0. Typically, for natural high-dimensional problems, non-trivial estimation of  is statistically or computationally possible precisely when it is statistically or computationally possible (respectively) to strongly distinguish  and ; see Section <ref> for further discussion.




 §.§ Computing the Classical Quantities


We now show how to compute the likelihood ratio and its L^2-norm under the additive Gaussian noise model. (This is a standard calculation; see, e.g., <cit.>.)


    
    Suppose  and  are as defined in Definition <ref>, with a sequence of prior distributions (_n)_n ∈.
    Then, the likelihood ratio of _n and _n is
    
    L_n() = d_n/d_n() = _∼_n[ exp(-1/2^2 + , )].



    Write  for the Lebesgue measure on ^N.
    Then, expanding the gaussian densities,
    
    d_n/d() 
               = (2π)^-N / 2·exp(-1/2^2) 
    d_n/d() 
               = (2π)^-N / 2·_∼_n[exp(-1/2 - ^2)] 
       = (2π)^-N / 2·exp(-1/2^2) ·_∼_n[exp(-1/2^2 + , )],

    and L_n is given by the quotient of (<ref>) and (<ref>).




Suppose  and  are as defined in Definition <ref>, with a sequence of prior distributions (_n)_n ∈.
Then,

    L_n^2 = _^1, ^2 ∼_nexp(⟨^1, ^2 ⟩),

where ^1, ^2 are drawn independently from _n.


We apply the important trick of rewriting a squared expectation as an expectation over the two independent “replicas” ^1, ^2 appearing in the result:

    L_n^2    = _∼_n[(_∼_nexp(⟨,⟩ - 1/2^2))^2] 
       = _∼_n_^1, ^2 ∼_nexp(⟨,^1 + ^2⟩ - 1/2^1^2 - 1/2^2^2),
    where ^1 and ^2 are drawn independently from _n. We now swap the order of the expectations,   = _^1,^2 ∼_n[exp(-1/2^1^2 - 1/2^2^2)_∼_nexp(⟨,^1 + ^2⟩)],
    and the inner expectation may be evaluated explicitly using the moment-generating function of a Gaussian distribution (if y ∼(0,1), then for any fixed t ∈, [exp(ty)] = exp(t^2/2)),   = _^1,^2exp(-1/2^1^2 - 1/2^2^2 + 1/2^1 + ^2^2),

from which the result follows by expanding the term inside the exponential.[Two techniques from this calculation are elements of the “replica method” from statistical physics: (1) writing a power of an expectation as an expectation over independent “replicas” and (2) changing the order of expectations and evaluating the moment-generating function. The interested reader may see <cit.> for an early reference, or <cit.> for two recent presentations.]


To apply the second moment method for contiguity, it remains to show that (<ref>) is O(1) using problem-specific information about the distribution _n. For spiked matrix and tensor models, various general-purpose techniques for doing this are given in <cit.>.




 §.§ Computing the Low-Degree Quantities



In this section, we will show that the norm of the LDLR (see Section <ref>) takes the following remarkably simple form under the additive Gaussian noise model.

    
    Suppose  and  are as defined in Definition <ref>, with a sequence of prior distributions (_n)_n ∈.
    Let L_n^≤ D be as in Definition <ref>.
    Then,
    
    L_n^≤ D^2 = _^1, ^2 ∼_n[ ∑_d = 0^D 1/d!^1, ^2 ^d ],

    where ^1, ^2 are drawn independently from _n.



Note that (<ref>) can be written as _^1,^2 [exp^≤ D(⟨^1,^2 ⟩)], where exp^≤ D(t) denotes the degree-D truncation of the Taylor series of exp(t). This can be seen as a natural low-degree analogue of the full second moment (<ref>). However, the low-degree Taylor series truncation in exp^≤ D is conceptually distinct from the low-degree projection in L_n^≤ D, because the latter corresponds to truncation in the Hermite orthogonal polynomial basis (see below), while the former corresponds to truncation in the monomial basis.


Our proof of Theorem <ref> will follow the strategy of <cit.> of expanding L_n in a basis of orthogonal polynomials with respect to _n, which in this case are the Hermite polynomials.

We first give a brief and informal review of the multivariate Hermite polynomials (see Appendix <ref> or the reference text <cit.> for further information).
The univariate Hermite polynomials[We will not actually use the definition of the univariate Hermite polynomials (although we will use certain properties that they satisfy as needed), but the definition is included for completeness in Appendix <ref>.] are a sequence h_k(x) ∈[x] for k ≥ 0, with h_k = k.
They may be normalized as h_k(x) = h_k(x) / √(k!), and with this normalization satisfy the orthonormality conditions

    _y ∼(0, 1)h_k(y)h_ℓ(y) = δ_kℓ.

The multivariate Hermite polynomials in N variables are indexed by α∈^N, and are merely products of the h_k: H_α() = ∏_i = 1^N h_α_i(x_i).
They also admit a normalized variant H_α() = ∏_i = 1^N h_α_i(x_i), and with this normalization satisfy the orthonormality conditions

    _∼(0,  I_N)H_α()H_β() = δ_αβ,

which may be inferred directly from (<ref>).

The collection of those H_α for which |α| ∑_i = 1^N α_i ≤ D form an orthonormal basis for _n^≤ D (which, recall, is the subspace of polynomials of degree ≤ D).
Thus we may expand

    L_n^≤ D() = ∑_α∈^N 
     |α| ≤ D L_n, H_αH_α() = ∑_α∈^N 
     |α| ≤ D1/∏_i = 1^N α_i! L_n, H_α H_α(),

and in particular we have

    L_n^≤ D^2 = ∑_α∈^N 
     |α| ≤ D1/∏_i = 1^N α_i! L_n, H_α^2.

Our main task is then to compute quantities of the form L_n, H_α. Note that these can be expressed either as _∼_n[L_n() H_α()] or _∼_n[H_α()].
We will give three techniques for carrying out this calculation, each depending on a different identity satisfied by the Hermite polynomials. Each will give a proof of the following remarkable formula, which shows that the quantities L_n, H_α are simply the moments of _n.


    
    For any α∈^N,
    
    ⟨ L_n, H_α⟩ = _∼_n[ ∏_i = 1^N X_i^α_i].



Before continuing with the various proofs of Proposition <ref>, let us show how to use it to complete the proof of Theorem <ref>.


    By Proposition <ref> substituted into (<ref>), we have
    
    L_n^≤ D^2
               = ∑_α∈^N 
     |α| ≤ D1/∏_i = 1^N α_i!(_∼_n[∏_i = 1^N X_i^α_i])^2, 
    and performing the “replica” manipulation (from the proof of Proposition <ref>) again, this may be written   = _^1, ^2 ∼_n[∑_α∈^N 
     |α| ≤ D1/∏_i = 1^N α_i!∏_i = 1^N (X^1_iX^2_i)^α_i] 
       = _^1, ^2 ∼_n[∑_d = 0^D 1/d!∑_α∈^N 
     |α| = ddα_1 ⋯α_N∏_i = 1^N (X^1_iX^2_i)^α_i] 
       = _^1, ^2 ∼_n[∑_d = 0^D 1/d!^1, ^2 ^d ],

    where the last step uses the multinomial theorem.


We now proceed to the three proofs of Proposition <ref>. For the sake of brevity, we omit here the (standard) proofs of the three Hermite polynomial identities these proofs are based on, but the interested reader may review those proofs in Appendix <ref>.



  §.§.§ Proof 1: Hermite Translation Identity


The first (and perhaps simplest) approach to proving Proposition <ref> uses the following formula for the expectation of a Hermite polynomial evaluated on a Gaussian random variable of non-zero mean.


    
    For any k ≥ 0 and μ∈,
    
    _y ∼(μ, 1)[h_k(y)] = μ^k.




    We rewrite L_n, H_α as an expectation with respect to _n:
    
    L_n, H_α   = _∼_n[L_n()H_α()] 
       = _∼_n[H_α()] 
       = _∼_n[∏_i = 1^N h_α_i(Y_i) ]
        and recall =  + for ∼_n and ∼( 0,  I_N) under _n,   = _∼_n[_∼( 0,  I_N)∏_i = 1^N h_α_i(X_i + Z_i) ] 
       = _∼_n[∏_i = 1^N_z ∼(X_i, 1)h_α_i(z)] 
       = _∼_n[∏_i = 1^N X_i^α_i],

    where we used Proposition <ref> in the last step.





  §.§.§ Proof 2: Gaussian Integration by Parts


The second approach to proving Proposition <ref> uses the following generalization of a well-known integration by parts formula for Gaussian random variables.

    
    If f: → is k times continuously differentiable and f(y) and its first k derivatives are bounded by O(exp(|y|^α)) for some α∈ (0, 2), then
    
    _y ∼(0, 1)[h_k(y)f(y)] = _y ∼(0, 1)[d^k f/dy^k(y)].


(The better-known case is k = 1, where one may substitute h_1(x) = x.)


We simplify using Proposition <ref>:

    L_n, H_α = _∼_n[L_n()∏_i = 1^N h_α_i(Y_i)] = _∼_n[ ∂^|α|L_n/∂ Y_1^α_1⋯∂ Y_N^α_N()].

Differentiating L_n under the expectation, we have

    ∂^|α|L/∂ Y_1^α_1⋯∂ Y_N^α_N() = _∼_n[ ∏_i = 1^N X_i^α_i exp(-1/2^2 + , )].

Taking the expectation over , we have _∼_nexp(, ) = exp(1/2^2), so the entire second term cancels and the result follows.





  §.§.§ Proof 3: Hermite Generating Function


Finally, the third approach to proving Proposition <ref> uses the following generating function for the Hermite polynomials.


    
    For any x, y ∈,
    
    exp(xy - 1/2x^2) = ∑_k = 0^∞1/k!x^k h_k(y).




    We may use Proposition <ref> to expand L_n in the Hermite polynomials directly:
    
    L_n()
               = _∼_n[exp(,  - 1/2^2)] 
       = _∼_n[ ∏_i = 1^N(∑_k = 0^∞1/k!X_i^k h_k(Y_i))] 
       = ∑_α∈^N1/∏_i = 1^N α_i! _∼_n[ ∏_i = 1^N X_i^α_i] H_α( Y).

    Comparing with the expansion (<ref>) then gives the result.


Now that we have the simple form (<ref>) for the norm of the LDLR, it remains to investigate its convergence or divergence (as n →∞) using problem-specific statistics of . In the next section we give some examples of how to carry out this analysis.





§ EXAMPLES: SPIKED MATRIX AND TENSOR MODELS



In this section, we perform the low-degree analysis for a particular important case of the additive Gaussian model: the order-p spiked Gaussian tensor model, also referred to as the tensor PCA (principal component analysis) problem. This model was introduced by <cit.> and has received much attention recently. The special case p=2 of the spiked tensor model is the so-called spiked Wigner matrix model which has been widely studied in random matrix theory, statistics, information theory, and statistical physics; see <cit.> for a survey.

In concordance with prior work, our low-degree analysis of these models illustrates two representative phenomena: the spiked Wigner matrix model exhibits a sharp computational phase transition, whereas the spiked tensor model (with p ≥ 3) has a “soft” tradeoff between statistical power and runtime which extends through the subexponential-time regime. A low-degree analysis of the spiked tensor model has been carried out previously in <cit.>; here we give a sharper analysis that more precisely captures the power of subexponential-time algorithms.

In Section <ref>, we carry out our low-degree analysis of the spiked tensor model. In Section <ref>, we devote additional attention to the special case of the spiked Wigner model, giving a refined analysis that captures its sharp phase transition and applies to a variety of distributions of “spikes.”




 §.§ The Spiked Tensor Model



We begin by defining the model.


An n-dimensional order-p tensor ∈ (^n)^⊗ p is a multi-dimensional array with p dimensions each of length n, with entries denoted T_i_1,…,i_p where i_j ∈ [n]. For a vector ∈^n, the rank-one tensor ^⊗ p∈ (^n)^⊗ p has entries (^⊗ p)_i_1,…,i_p = x_i_1 x_i_2⋯ x_i_p.




Fix an integer p ≥ 2. The order-p spiked tensor model is the additive Gaussian noise model (Definition <ref>) with = λ^⊗ p, where λ = λ(n) > 0 is a signal-to-noise parameter and ∈^n (the “spike”) is drawn from some probability distribution _n over ^n (the “prior”), normalized so that ^2 → n in probability as n →∞. In other words:

    
  * Under _n, observe = λ^⊗ p +.
    
  * Under _n, observe =.

Here,  is a tensor with i.i.d. entries distributed as (0,1).[This model is equivalent to the more standard model in which the noise is symmetric with respect to permutations of the indices; see Appendix <ref>.]


Throughout this section we will focus for the sake of simplicity on the Rademacher spike prior, where  has i.i.d. entries x_i ∼({± 1}). We focus on the problem of strongly distinguishing _n and _n (see Definition <ref>), but, as is typical for high-dimensional problems, the problem of estimating  seems to behave in essentially the same way (see Section <ref>). 

We first state our results on the behavior of the LDLR for this model.


Consider the order-p spiked tensor model with  drawn from the Rademacher prior, x_i ∼({± 1}) i.i.d. for i ∈ [n]. Fix sequences D = D(n) and λ = λ(n). For constants 0 < A_p < B_p depending only on p, we have the following.[Concretely, one may take A_p = 1/√(2) p^-p/4-1/2 and B_p = √(2) e^p/2 p^-p/4.]

    
  (i) If λ≤ A_p  n^-p/4 D^(2-p)/4 for all sufficiently large n, then L_n^≤ D = O(1).
    
  (ii) If λ≥ B_p  n^-p/4 D^(2-p)/4 and D ≤2/pn for all sufficiently large n, and D = ω(1), then L_n^≤ D = ω(1).

(Here we are considering the limit n →∞ with p held fixed, so O(1) and ω(1) may hide constants depending on p.)


Before we prove this, let us interpret its meaning. If we take degree-D polynomials as a proxy for n^Θ̃(D)-time algorithms (as discussed in Section <ref>), our calculations predict that an n^O(D)-time algorithm exists when λ≫ n^-p/4 D^(2-p)/4 but not when λ≪ n^-p/4 D^(2-p)/4. (Here we ignore log factors, so we use A ≪ B to mean A ≤ B/polylog(n).) These predictions agree precisely with the previously established statistical-versus-computational tradeoffs in the spiked tensor model! It is known that polynomial-time distinguishing algorithms exist when λ≫ n^-p/4 <cit.>, and sum-of-squares lower bounds suggest that there is no polynomial-time distinguishing algorithm when λ≪ n^-p/4 <cit.>. 

Furthermore, one can study the power of subexponential-time algorithms, i.e., algorithms of runtime n^n^δ = exp(Õ(n^δ)) for a constant δ∈ (0,1). Such algorithms are known to exist when λ≫ n^-p/4-δ(p-2)/4 <cit.>, matching our prediction.[Some of these results only apply to minor variants of the spiked tensor problem, but we do not expect this difference to be important.]
These algorithms interpolate smoothly between the polynomial-time algorithm which succeeds when λ≫ n^-p/4, and the exponential-time exhaustive search algorithm which succeeds when λ≫ n^(1-p)/2. (Distinguishing the null and planted distributions is information-theoretically impossible when λ≪ n^(1-p)/2 <cit.>, so this is indeed the correct terminal value of λ for computational questions.) The tradeoff between statistical power and runtime that these algorithms achieve is believed to be optimal, and our results corroborate this claim. Our results are sharper than the previous low-degree analysis for the spiked tensor model <cit.>, in that we pin down the precise constant δ in the subexponential runtime. (Similarly precise analyses of the tradeoff between subexponential runtime and statistical power have been obtained for CSP refutation <cit.> and sparse PCA <cit.>.)

We now begin the proof of Theorem <ref>. Since the spiked tensor model is an instance of the additive Gaussian model, we can apply the formula from Theorem <ref>: letting ^1,^2 be independent draws from _n,

    L_n^≤ D^2 = _^1,^2exp^≤ D(λ^2 ⟨^1,^2 ⟩^p) = ∑_d=0^Dλ^2d/d!_^1,^2 [⟨^1,^2 ⟩^pd].

We will give upper and lower bounds on this quantity in order to prove the two parts of Theorem <ref>.



  §.§.§ Proof of Theorem <ref>: Upper Bound




We use the moment bound

    _^1,^2[|⟨^1,^2 ⟩|^k] ≤ (2n)^k/2 k Γ(k/2)

for any integer k ≥ 1. This follows from  ⟨^1,^2 ⟩ being a subgaussian random variable with variance proxy n (see Appendix <ref> for details on this notion, and see Proposition <ref> for the bound (<ref>)). Plugging this into (<ref>),

    L_n^≤ D^2 ≤ 1 + ∑_d=1^D λ^2d/d! (2n)^pd/2pd Γ(pd/2) =: 1 + ∑_d=1^D T_d.

Note that T_1 = O(1) provided λ = O(n^-p/4) (which will be implied by (<ref>) below). Consider the ratio between successive terms:

    r_d := T_d+1/T_d = λ^2/d+1 (2n)^p/2 p  Γ(p(d+1)/2)/Γ(pd/2).

Using the bound Γ(x+a)/Γ(x) ≤ (x+a)^a for all a, x > 0 (see Proposition <ref>), we find

    r_d ≤λ^2/d+1 (2n)^p/2 p [p(d+1)/2]^p/2≤λ^2 p^p/2+1 n^p/2 (d+1)^p/2-1.

Thus if λ is small enough, namely if

    λ≤1/√(2)  p^-p/4-1/2 n^-p/4 D^(2-p)/4,

then r_d ≤ 1/2 for all 1 ≤ d < D.
In this case, by comparing with a geometric sum we may bound L_n^≤ D^2 ≤ 1 + 2 T_1 = O(1).








  §.§.§ Proof of Theorem <ref>: Lower Bound




Note that ⟨^1,^2 ⟩ = ∑_i=1^n s_i where s_1, …, s_n are i.i.d. Rademacher random variables, so _^1,^2[⟨^1,^2 ⟩^2k + 1] = 0, and

    _^1,^2[⟨^1,^2 ⟩^2k] = [(∑_i=1^n s_i)^2k] = ∑_i_1,i_2,…,i_2k∈ [n][s_i_1 s_i_2⋯ s_i_2k].

By counting only the terms [s_i_1 s_i_2⋯ s_i_2k] in which each s_i appears either 0 or 2 times, we have

    _^1,^2 [⟨^1,^2 ⟩^2k] ≥nk(2k)!/2^k.

Let d be the largest integer such that d ≤ D and pd is even. By our assumption D ≤2/pn, we then have pd/2 ≤ n.
We now bound L_n^≤ D^2 by only the degree-pd term of (<ref>), and using the bounds nk≥ (n/k)^k (for 1 ≤ k ≤ n) and (n/e)^n ≤ n! ≤ n^n, we can lower bound that term as follows:

    L_n^≤ D^2    ≥λ^2d/d!_^1,^2[⟨^1,^2 ⟩^pd] 
       ≥λ^2d/d!npd/2(pd)!/2^pd/2
       ≥λ^2d/d^d(2n/pd)^pd/2(pd/e)^pd/2^pd/2
       = (λ^2 e^-p p^p/2 n^p/2 d^p/2-1)^d.

Now, if λ is large enough, namely if

    λ≥√(2) e^p/2 p^-p/4 n^-p/4 D^(2-p)/4

and D = ω(1), then L_n^≤ D^2 ≥ (2-o(1))^d = ω(1).





 §.§ The Spiked Wigner Matrix Model: Sharp Thresholds



We now turn our attention to a more precise understanding of the case p = 2 of the spiked tensor model, which is more commonly known as the spiked Wigner matrix model.
Our results from the previous section (specialized to p=2) suggest that if λ≫ n^-1/2 then there should be a polynomial-time distinguishing algorithm, whereas if λ≪ n^-1/2 then there should not even be a subexponential-time distinguishing algorithm (that is, no algorithm of runtime exp(n^1-ε) for any ε > 0). In this section, we will give a more detailed low-degree analysis that identifies the precise value of λ√(n) at which this change occurs. This type of sharp threshold has been observed in various high-dimensional inference problems; another notable example is the Kesten-Stigum transition for community detection in the stochastic block model <cit.>. It was first demonstrated by <cit.> that the low-degree method can capture such sharp thresholds.

To begin, we recall the problem setup. Since the interesting regime is λ = Θ(n^-1/2), we define λ̂= λ√(2n) and take λ̂ to be constant (not depending on n). With this notation, the spiked Wigner model is as follows:

    
  * Under _n, observe = λ̂/√(2n)^⊤ + where ∈^n is drawn from _n.
    
  * Under _n, observe =.

Here  is an n × n random matrix with i.i.d. entries distributed as (0,1). (This asymmetric noise model is equivalent to the more standard symmetric one; see Appendix <ref>.) We will consider various spike priors _n, but require the following normalization.


The spike prior (_n)_n ∈ is normalized so that ∼_n satisfies ^2 → n in probability as n →∞.





  §.§.§ The Canonical Distinguishing Algorithm: PCA



There is a simple reference algorithm for testing in the spiked Wigner model, namely PCA (principal component analysis), by which we simply mean thresholding the largest eigenvalue of the (symmetrized) observation matrix.


    The PCA test for distinguishing  and  is the following statistical test, computable in polynomial time in n.
    Let ( + ^⊤) / √(2n) = λ̂/n^⊤ +, where = ( + ^⊤) / √(2n) is a random matrix with the GOE distribution.[Gaussian Orthogonal Ensemble (GOE):  is a symmetric n × n matrix with entries W_ii∼(0,2/n) and W_ij = W_ji∼(0,1/n), independently.]
    Then, let
    
    f_λ̂^𝖯𝖢𝖠() {[                               : λ_max() > t(λ̂);                               : λ_max() ≤ t(λ̂) ]}

    where the threshold is set to  t(λ̂)  2 + (λ̂+ λ̂^-1 - 2) / 2.

The theoretical underpinning of this test is the following seminal result from random matrix theory, the analogue for Wigner matrices of the celebrated “BBP transition” <cit.>.

    
    Let λ̂ be constant (not depending on n). Let = λ̂/n^⊤ + with ∼(n) and arbitrary ∈^n with ^2 = n.
    
        
  * If λ̂≤ 1, then λ_max() → 2 as n →∞ almost surely, and _max(), /√(n)^2 → 0 almost surely (where λ_max denotes the largest eigenvalue and _max denotes the corresponding unit-norm eigenvector).
        
  * If λ̂> 1, then λ_max() →λ̂+ λ̂^-1 > 2 as n →∞ almost surely, and _max(), /√(n)^2 → 1 - λ̂^-2 almost surely.
    


Thus, the PCA test exhibits a sharp threshold: it succeeds when λ̂> 1, and fails when λ̂≤ 1. (Furthermore, the leading eigenvector achieves non-trivial estimation of the spike  when λ̂> 1 and fails to do so when λ̂≤ 1.)


    For any λ̂> 1 and any spike prior family (_n)_n ∈ valid per Assumption <ref>, f_λ̂^𝖯𝖢𝖠 is a polynomial-time statistical test strongly distinguishing _λ and .


For some spike priors (_n), it is known that PCA is statistically optimal, in the sense that distinguishing (or estimating the spike) is information-theoretically impossible when λ̂< 1.
These priors include the prior with  drawn uniformly from the sphere of radius √(n) and the priors with  having i.i.d. (0, 1) or Rademacher (uniformly ± 1) entries <cit.>. For these priors, we thus have λ̂_𝗌𝗍𝖺𝗍 = λ̂_𝖼𝗈𝗆𝗉 = 1, and there is no stat-comp gap.

A different picture emerges for other spike priors, such as the sparse Rademacher prior[In the sparse Rademacher prior, each entry of  is nonzero with probability ρ (independently), and the nonzero entries are drawn uniformly from {± 1/√(ρ)}.] with constant density ρ = Θ(1). If ρ is smaller than a particular small constant (roughly 0.09 <cit.>), it is known that λ̂_𝗌𝗍𝖺𝗍 < 1. More precisely, an exponential-time exhaustive search algorithm succeeds in part of the regime where PCA fails <cit.>. For any given ρ, the precise threshold λ̂_𝗌𝗍𝖺𝗍 can be computed using the replica-symmetric formula from statistical physics (see, e.g., <cit.>, or <cit.> for a survey). However, for any constant ρ, it is believed that λ̂_𝖼𝗈𝗆𝗉 = 1, i.e., that no polynomial-time algorithm can “beat PCA.” This has been conjectured in the same statistical physics literature based on failure of the approximate message passing (AMP) algorithm <cit.>.

We will next give a low-degree analysis corroborating that conjecture: for a large class of spike priors (including the sparse Rademacher prior with constant ρ), our predictions suggest that any distinguishing algorithm requires nearly-exponential time whenever λ̂< 1.
One interesting case we will not cover is that of the sparse Rademacher prior with ρ = o(1). In such models, there actually are subexponential-time algorithms that succeed for some λ̂< 1; these are described in <cit.> along with matching lower bounds using the low-degree method. Furthermore, there are polynomial-time algorithms that can beat the PCA threshold once ρ≲ 1/√(n); this is the much-studied “sparse PCA” regime (see, e.g., <cit.>).





  §.§.§ Low-Degree Analysis: Informally, with the “Gaussian Heuristic”



We first give a heuristic low-degree analysis of the spiked Wigner model which suggests λ̂_𝖼𝗈𝗆𝗉 = 1 (matching PCA) for sufficiently “reasonable” spike priors (_n). In the next section, we will state and prove a rigorous statement to this effect.

Recall from (<ref>) the expression for the norm of the LDLR:

    L_n^≤ D^2 = ∑_d=0^Dλ^2d/d!_^1,^2 [⟨^1,^2 ⟩^2d] = ∑_d=0^D1/d!(λ̂^2/2n)^d _^1,^2 [⟨^1,^2 ⟩^2d].


To predict λ̂_𝖼𝗈𝗆𝗉, it remains to determine whether L_n^≤ D converges or diverges as n →∞, as a function of λ̂.
Recall that, per Assumption <ref>, _n is normalized so that ^2 ≈ n. Thus when, e.g.,  has i.i.d. entries, we may expect the following informal central limit theorem:

    “When ^1, ^2 ∼_n independently, ^1, ^2 is distributed approximately as (0, n).”

Assuming this heuristic applies to the first 2D moments of ^1, ^2, and recalling that the Gaussian moments are _g ∼(0,1) [g^2k] = (2k-1)!! = ∏_i = 1^k (2i - 1), we may estimate

    L_n^≤ D^2 ≈∑_d=0^D1/d!(λ̂^2/2n)^d _g ∼(0, n) [g^2d] = ∑_d=0^D1/d!(λ̂^2/2n)^d n^d(2d - 1)!! =: ∑_d=0^D T_d.

Imagine D grows slowly with n (e.g., D ≈log n) in order to predict the power of polynomial-time algorithms. The ratio of consecutive terms above is 
    T_d+1/T_d = λ̂^2·2d+1/2(d+1)≈λ̂^2,

suggesting that L_n^≤ D should diverge if λ̂> 1 and converge if λ̂< 1.

While this style of heuristic analysis is often helpful for guessing the correct threshold, this type of reasoning can break down if D is too large or if  is too sparse. In the next section, we therefore give a rigorous analysis of L_n^≤ D.





  §.§.§ Low-Degree Analysis: Formally, with Concentration Inequalities



We now give a rigorous proof that L_n^≤ D = O(1) when λ̂< 1 (and L_n^≤ D = ω(1) when λ̂> 1), provided the spike prior is “nice enough.” Specifically, we require the following condition on the prior.


A spike prior (_n)_n ∈ admits a local Chernoff bound if for any η > 0 there exist δ > 0 and C > 0 such that for all n,

    {|^1,^2 | ≥ t}≤ C exp(-1/2n(1-η)t^2)   for all  t ∈ [0,δ n]

where ^1,^2 are drawn independently from _n.

For instance, any prior with i.i.d. subgaussian entries admits a local Chernoff bound; see Proposition <ref> in Appendix <ref>. This includes, for instance, the sparse Rademacher prior with any constant density ρ. The following is the main result of this section, which predicts that for this class of spike priors, any algorithm that beats the PCA threshold requires nearly-exponential time.


Suppose (_n)_n ∈ is a spike prior that (i) admits a local Chernoff bound, and (ii) has then ^2 ≤√(2)n almost surely if ∼_n. Then, for the spiked Wigner model with λ̂< 1 and any D = D(n) = o(n/log n), we have L_n^≤ D = O(1) as n →∞.



The upper bound ^2 ≤√(2)n is without loss of generality (provided ^2 → n in probability). This is because we can define a modified prior _n that draws ∼_n and outputs  if ^2 ≤√(2)n and 0 otherwise. If (_n)_n ∈ admits a local Chernoff bound then so does (_n)_n ∈. And, if the spiked Wigner model is computationally hard with the prior (_n)_n ∈, it is also hard with the prior (_n)_n ∈, since the two differ with probability o(1).


Though we already know that a polynomial-time algorithm (namely PCA) exists when λ̂> 1, we can check that indeed L_n^≤ D = ω(1) in this regime. For the sake of simplicity, we restrict this result to the Rademacher prior.

Consider the spiked Wigner model with the Rademacher prior:  has i.i.d. entries x_i ∼({± 1}). If λ̂> 1, then for any D = ω(1) we have L_n^≤ D = ω(1).

The proof is a simple modification of the proof of Theorem <ref>(ii) in Section <ref>; we defer it to Appendix <ref>. The remainder of this section is devoted to proving Theorem <ref>.


Starting from the expression for L_n^≤ D^2 (see Theorem <ref> and Remark <ref>), we split L_n^≤ D^2 into two terms, as follows:

    L_n^≤ D^2 = _^1, ^2[exp^≤ D(λ^2^1, ^2 ^2)]
    =: R_1 + R_2,

where

    R_1    _^1, ^2[_|⟨^1,^2 ⟩| ≤ε n exp^≤ D(λ^2^1, ^2 ^2)], 
    
    R_2    _^1, ^2[_|⟨^1,^2 ⟩| > ε n exp^≤ D(λ^2^1, ^2 ^2)].

Here ε > 0 is a small constant to be chosen later. We call R_1 the small deviations and R_2 the large deviations, and we will bound these two terms separately.


  
Bounding the large deviations.
Using that ^2 ≤√(2)n, that exp^≤ D(t) is increasing for t ≥ 0, and the local Chernoff bound (taking ε to be a sufficiently small constant),

    R_2    ≤{|⟨^1,^2 ⟩| > ε n}exp^≤ D(2 λ^2 n^2)
       ≤ C exp(-1/3ε^2 n) ∑_d=0^D (λ̂^2 n)^d/d!and noting that the last term of the sum is the largest since λ̂^2 n > D,   ≤ C exp(-1/3ε^2 n) (D+1) (λ̂^2 n)^D/D!
       = exp[log C - 1/3ε^2 n + log(D+1) + 2D logλ̂+ D log n - log(D!)]
       = o(1)

provided D = o(n/log n).



  
Bounding the small deviations.

We adapt an argument from <cit.>. Here we do not need to make use of the truncation to degree D at all, and instead simply use the bound exp^≤ D(t) ≤exp(t) for t ≥ 0.
With this, we bound

    R_1    = _^1, ^2[_|⟨^1,^2 ⟩| ≤ε n exp^≤ D(λ^2^1, ^2 ^2)]
       ≤_^1, ^2[_|⟨^1,^2 ⟩| ≤ε n exp(λ^2^1, ^2 ^2)]
       = ∫_0^∞{_|⟨^1,^2 ⟩| ≤ε n exp(λ^2^1, ^2 ^2) ≥ u} du
       = 1 + ∫_1^∞{_|⟨^1,^2 ⟩| ≤ε n exp(λ^2^1, ^2 ^2) ≥ u} du
       = 1 + ∫_0^∞{_|⟨^1,^2 ⟩| ≤ε n ⟨^1,^2 ⟩^2 ≥ t}λ^2exp(λ^2 t) dt where exp(λ^2 t) = u
       ≤ 1 + ∫_0^∞ C exp(-1/2n(1-η)t)  λ^2exp(λ^2 t) dt  using the local Chernoff bound
       ≤ 1 + C λ̂^2/2n∫_0^∞exp(-1/2n(1 - η - λ̂^2)t) dt
       = 1 + C λ̂^2 (1 - η - λ̂^2)^-1provided λ̂^2 < 1-η
       = O(1).

Since λ̂< 1, we can choose η > 0 small enough so that λ̂^2 < 1 - η, and then choose ε small enough so that the local Chernoff bound holds. (Here, η and ε depend on λ̂ and the spike prior, but not on n.)






§ MORE ON THE LOW-DEGREE METHOD



In this section, we return to the general considerations introduced in Section <ref> and describe some of the nuances in and evidence for the main conjecture underlying the low-degree method (Conjecture <ref>). Specifically, we investigate the question of what can be concluded (both rigorously and conjecturally) from the behavior of the low-degree likelihood ratio (LDLR) defined in Definition <ref>. We present conjectures and formal evidence connecting the LDLR to computational complexity, discussing various caveats and counterexamples along the way. 

In Section <ref>, we explore to what extent the D-LDLR controls whether or not degree-D polynomials can distinguish  from . Then, in Section <ref>, we explore to what extent the LDLR controls whether or not any efficient algorithm can distinguish  and .




 §.§ The LDLR and Thresholding Polynomials



Heuristically, since L_n^≤ D is the value of the L^2 optimization problem (<ref>), we might expect the behavior of L_n^≤ D as n →∞ to dictate whether or not degree-D polynomials can distinguish  from : it should be possible to strongly distinguish (in the sense of Definition <ref>, i.e., with error probabilities tending to 0)  from  by thresholding a degree-D polynomial (namely L_n^≤ D) if and only if L_n^≤ D = ω(1). We now discuss to what extent this heuristic is correct.


If L_n^≤ D = ω(1), does this imply that it is possible to strongly distinguish  and  by thresholding a degree-D polynomial?


We have already mentioned (see Section <ref>) a counterexample when D = ∞: there are cases where  and  are not statistically distinguishable, yet L_n→∞ due to a rare “bad” event under _n. Examples of this phenomenon are fairly common (e.g., <cit.>). However, after truncation to only low-degree components, this issue seems to disappear. For instance, in sparse PCA, L_n^≤ D→∞ only occurs when either (i) there actually is an n^Õ(D)-time distinguishing algorithm, or (ii) D is “unreasonably large,” in the sense that there is a trivial n^t(n)-time exhaustive search algorithm and D ≫ t(n) <cit.>. Indeed, we do not know any example of a natural problem where L_n^≤ D diverges spuriously for a “reasonable” value of D (in the above sense), although one can construct unnatural examples by introducing a rare “bad” event in _n. Thus, it seems that for natural problems and reasonable growth of D, the smoothness of low-degree polynomials regularizes L_n^≤ D in such a way that the answer to Question <ref> is typically “yes.” This convenient feature is perhaps related to the probabilistic phenomenon of hypercontractivity; see Appendix <ref> and especially Remark <ref>.

Another counterexample to Question <ref> is the following. Take  and  that are “easy” for degree-D polynomials to distinguish, i.e., L_n^≤ D→∞ and , can be strongly distinguished by thresholding a degree-D polynomial. Define a new sequence of “diluted” planted measures ^' where ^'_n samples from _n with probability 1/2, and otherwise samples from _n. Letting L'_n = d'_n/d_n, we have (L'_n)^≤ D→∞, yet ' and  cannot be strongly distinguished (even statistically). While this example is perhaps somewhat unnatural, it illustrates that a rigorous positive answer to Question <ref> would need to restrict to  that are “homogeneous” in some sense.

Thus, while we have seen some artificial counterexamples, the answer to Question <ref> seems to typically be “yes” for natural high-dimensional problems, so long as D is not unreasonably large. We now turn to the converse question.


If L_n^≤ D = O(1), does this imply that it is impossible to strongly distinguish  and  by thresholding a degree-D polynomial?


Here, we are able to give a positive answer in a particular formal sense.
The following result addresses the contrapositive of Question <ref>: it shows that distinguishability by thresholding low-degree polynomials implies exponential growth of the norm of the LDLR.


Suppose  draws ∈^N with entries either i.i.d. (0,1) or i.i.d. ({± 1}). Let  be any measure on ^N that is absolutely continuous with respect to . Let f: ^N → be a polynomial of degree ≤ d satisfying

    _∼[f()] ≥ A   and  (|f()| ≥ B) ≤δ

for some A > B > 0 and some δ≤1/2· 3^-4kd. Then for any k ∈,

    L^≤ 2kd≥1/2(A/B)^2k.



We defer the proof to Appendix <ref>. To understand what the result shows, imagine, for example, that A > B are both constants, and k grows slowly with n (e.g., k ≈log n). Then, if a degree-d polynomial (where d may depend on n) can distinguish  from  in the sense of (<ref>) with δ = 1/2· 3^-4kd, then L_n^≤ 2kd→∞ as n →∞. Note though, that one weakness of this result is that we require the explicit quantitative bound δ≤1/2· 3^-4kd, rather than merely δ = o(1).

The proof (see Appendix <ref>) is a straightforward application of hypercontractivity (see e.g., <cit.>), a type of result stating that random variables obtained by evaluating low-degree polynomials on weakly-dependent distributions (such as i.i.d. ones) are well-concentrated and otherwise “reasonable.”
We have restricted to the case where  is i.i.d. Gaussian or Rademacher because hypercontractivity results are most readily available in these cases, but we expect similar results to hold more generally.




 §.§ Algorithmic Implications of the LDLR



Having discussed the relationship between the LDLR and low-degree polynomials, we now discuss the relationship between low-degree polynomials and the power of any computationally-bounded algorithm.

Any degree-D polynomial has at most n^D monomial terms and so can be evaluated in time n^O(D) (assuming that the individual coefficients are easy to compute). However, certain degree-D polynomials can of course be computed faster, e.g., if the polynomial has few nonzero monomials or has special structure allowing it to be computed via a spectral method (as in the color coding trick <cit.> used by <cit.>).
Despite such special cases, it appears that for average-case high-dimensional hypothesis testing problems, degree-D polynomials are typically as powerful as general n^Θ̃(D)-time algorithms; this informal conjecture appears as Hypothesis 2.1.5 in <cit.>, building on the work of <cit.> (see also our previous discussion in Section <ref>). We will now explain the nuances and caveats of this conjecture, and give evidence (both formal and heuristic) in its favor.



  §.§.§ Robustness



An important counterexample that we must be careful about is XOR-SAT. In the random 3-XOR-SAT problem, there are n {± 1 }-valued variables x_1,…,x_n and we are given a formula consisting of m random constraints of the form x_i_ℓ x_j_ℓ x_k_ℓ = b_ℓ for ℓ∈ [m], with b_ℓ∈{± 1}. The goal is to determine whether there is an assignment x ∈{± 1}^n that satisfies all the constraints. Regardless of m, this problem can be solved in polynomial time using Gaussian elimination over the finite field 𝔽_2. However, when n ≪ m ≪ n^3/2, the low-degree method nevertheless predicts that the problem should be computationally hard, i.e., it is hard to distinguish between a random formula (which is unsatisfiable with high probability) and a formula with a planted assignment. This pitfall is not specific to the low-degree method: sum-of-squares lower bounds, statistical query lower bounds, and the cavity method from statistical physics also incorrectly suggest the same (this is discussed in <cit.>).

The above discrepancy can be addressed (see, e.g., Lecture 3.2 of <cit.>) by noting that Gaussian elimination is very brittle, in the sense that it no longer works to search for an assignment satisfying only a 1-δ fraction of the constraints (as in this case it does not seem possible to leverage the problem's algebraic structure over 𝔽_2). Another example of a brittle algorithm is the algorithm of <cit.> for linear regression, which uses Lenstra-Lenstra-Lovász lattice basis reduction <cit.> and only tolerates an exponentially-small level of noise. Thus, while there sometimes exist efficient algorithms that are “high-degree”, these tend not to be robust to even a tiny amount of noise. As with SoS lower bounds, we expect that the low-degree method correctly captures the limits of robust hypothesis testing <cit.> for high-dimensional problems. (Here, “robust” refers to the ability to handle a small amount of noise, and should not be confused with the specific notion of robust inference <cit.> or with other notions of robustness that allow adversarial corruptions <cit.>.)



  §.§.§ Connection to Sum-of-Squares



The sum-of-squares (SoS) hierarchy <cit.> is a hierarchy of increasingly powerful semidefinite programming (SDP) relaxations for general polynomial optimization problems. Higher levels of the hierarchy produce larger SDPs and thus require more time to solve: level d typically requires time n^O(d). SoS lower bounds show that certain levels of the hierarchy fail to solve a given problem. As SoS seems to be at least as powerful as all known algorithms for many problems, SoS lower bounds are often thought of as the “gold standard” of formal evidence for computational hardness of average-case problems. For instance, if any constant level d of SoS fails to solve a problem, this is strong evidence that no polynomial-time algorithm exists to solve the same problem (modulo the robustness issue discussed above). 

In order to prove SoS lower bounds, one needs to construct a valid primal certificate (also called a pseudo-expectation) for the SoS SDP. The pseudo-calibration approach <cit.> provides a strategy for systematically constructing a pseudo-expectation; however, showing that the resulting object is valid (in particular, showing that a certain associated matrix is positive semidefinite) often requires substantial work. As a result, proving lower bounds against constant-level SoS programs is often very technically challenging (as in <cit.>). We refer the reader to <cit.> for a survey of SoS and pseudo-calibration in the context of high-dimensional inference.

On the other hand, it was observed by the authors of <cit.> that the bottleneck for the success of the pseudo-calibration approach seems to typically be a simple condition, none other than the boundedness of the norm of the LDLR (see Conjecture 3.5 of <cit.> or Section 4.3 of <cit.>).[More specifically, (L_n^≤ D^2 - 1) is the variance of a certain pseudo-expectation value generated by pseudo-calibration, whose actual value in a valid pseudo-expectation must be exactly 1. It appears to be impossible to “correct” this part of the pseudo-expectation if the variance is diverging with n.] Through a series of works <cit.>, the low-degree method emerged from investigating this simpler condition in its own right. It was shown in <cit.> that SoS can be used to achieve sharp computational thresholds (such as the Kesten–Stigum threshold for community detection), and that the success of the associated method also hinges on the boundedness of the norm of the LDLR. So, historically speaking, the low-degree method can be thought of as a “lite” version of SoS lower bounds that is believed to capture the essence of what makes SoS succeed or fail (see <cit.>).

A key advantage of the low-degree method over traditional SoS lower bounds is that it greatly simplifies the technical work required, allowing sharper results to be proved with greater ease. Moreover, the low-degree method is arguably more natural in the sense that it is not specific to any particular SDP formulation and instead seems to capture the essence of what makes problems computationally easy or hard. On the other hand, some would perhaps argue that SoS lower bounds constitute stronger evidence for hardness than low-degree lower bounds (although we do not know any average-case problems for which they give different predictions).

We refer the reader to <cit.> for more on the relation between SoS and the low-degree method, including evidence for why the two methods are believed to predict the same results.





  §.§.§ Connection to Spectral Methods



For high-dimensional hypothesis testing problems, a popular class of algorithms are the spectral methods, algorithms that build a matrix  using the data and then threshold its largest eigenvalue. (There are also spectral methods for estimation problems, usually extracting an estimate of the signal from the leading eigenvector of .) Often, spectral methods match the best[Here, “best” is in the sense of strongly distinguishing _n and _n throughout the largest possible regime of model parameters.] performance among all known polynomial-time algorithms. Some examples include the non-backtracking and Bethe Hessian spectral methods for the stochastic block model <cit.>, the covariance thresholding method for sparse PCA <cit.>, and the tensor unfolding method for tensor PCA <cit.>. As demonstrated in <cit.>, it is often possible to design spectral methods that achieve the same performance as SoS; in fact, some formal evidence indicates that low-degree spectral methods (where each matrix entry is a constant-degree polynomial of the data) are as powerful as any constant-degree SoS relaxation <cit.>[In <cit.>, it is shown that for a fairly general class of average-case hypothesis testing problems, if SoS succeeds in some range of parameters then there is a low-degree spectral method whose maximum positive eigenvalue succeeds (in a somewhat weaker range of parameters). However, the resulting matrix could a priori have an arbitrarily large (in magnitude) negative eigenvalue, which would prevent the spectral method from running in polynomial time. For this same reason, it seems difficult to establish a formal connection between SoS and the LDLR via spectral methods.].

As a result, it is interesting to try to prove lower bounds against the class of spectral methods. Roughly speaking, the largest eigenvalue in absolute value of a polynomial-size matrix  can be computed using O(log n) rounds of power iteration, and thus can be thought of as an O(log n)-degree polynomial; more specifically, the associated polynomial is (^2k) where k ∼log(n). The following result makes this precise, giving a formal connection between the low-degree method and the power of spectral methods. The proof is given in Appendix <ref> (and is similar to that of Theorem <ref>).


Suppose  draws ∈^N with entries either i.i.d. (0,1) or i.i.d. ({± 1}). Let  be any measure on ^N that is absolutely continuous with respect to . Let = () be a real symmetric L × L matrix, each of whose entries is a polynomial in  of degree ≤ d. Suppose

    _∼≥ A   and  (≥ B) ≤δ

(where · denotes matrix operator norm) for some A > B > 0 and some δ≤1/2· 3^-4kd. Then, for any k ∈,

    L^≤ 2kd≥1/2L(A/B)^2k.


For example, suppose we are interested in polynomial-time spectral methods, in which case we should consider L = poly(n) and d = O(1). If there exists a spectral method with these parameters that distinguishes  from  in the sense of (<ref>) for some constants A > B, and with δ→ 0 faster than any inverse polynomial (in n), then there exists a choice of k = O(log n) such that L^≤ O(log n) = ω(1). And, by contrapositive, if we could show that L^≤ D = O(1) for some D = ω(log n), that would imply that there is no spectral method with the above properties. This justifies the choice of logarithmic degree in Conjecture <ref>. Similarly to Theorem <ref>, one weakness of Theorem <ref> is that we can only rule out spectral methods whose failure probability is smaller than any inverse polynomial, instead of merely o(1).


Above, we have argued that polynomial-time spectral methods correspond to polynomials of degree roughly log(n). What if we are instead interested in subexponential runtime exp(n^δ) for some constant δ∈ (0,1)? One class of spectral method computable with this runtime is that where the dimension is L ≈exp(n^δ) and the degree of each entry is d ≈ n^δ (such spectral methods often arise based on SoS <cit.>). To rule out such a spectral method using Theorem <ref>, we would need to take k ≈log(L) ≈ n^δ and would need to show L^≤ D = O(1) for D ≈ n^2δ. However, Conjecture <ref> postulates that time-exp(n^δ) algorithms should instead correspond to degree-n^δ polynomials, and this correspondence indeed appears to be the correct one based on the examples of tensor PCA (see Section <ref>) and sparse PCA (see <cit.>).

Although this seems at first to be a substantial discrepancy, there is evidence that there are actually spectral methods of dimension L ≈exp(n^δ) and constant degree d = O(1) that achieve optimal performance among exp(n^δ)-time algorithms. Such a spectral method corresponds to a degree-n^δ polynomial, as expected. These types of spectral methods have been shown to exist for tensor PCA <cit.>.






  §.§.§ Formal Conjecture



We next discuss the precise conjecture that Hopkins <cit.> offers on the algorithmic implications of the low-degree method. Informally, the conjecture is that for “sufficiently nice”  and , if L_n^≤ D = O(1) for some D ≥ (log n)^1+ε, then there is no polynomial-time algorithm that strongly distinguishes  and . We will not state the full conjecture here (see Conjecture 2.2.4 in <cit.>) but we will briefly discuss some of the details that we have not mentioned yet.

Let us first comment on the meaning of “sufficiently nice” distributions. Roughly speaking, this means that: 

    
  * _n is a product distribution,
    
  * _n is sufficiently symmetric with respect to permutations of its coordinates, and
    
  * _n is then perturbed by a small amount of additional noise.

Conditions (1) and (2) or minor variants thereof are fairly standard in high-dimensional inference problems. The reason for including (3) is to rule out non-robust algorithms such as Gaussian elimination (see Section <ref>).

One difference between the conjecture of <cit.> and the conjecture discussed in these notes is that <cit.> considers the notion of coordinate degree rather than polynomial degree. A polynomial has coordinate degree ≤ D if no monomial involves more than D variables; however, each individual variable can appear with arbitrarily-high degree in a monomial.[Indeed, coordinate degree need not be phrased in terms of polynomials, and one may equivalently consider the linear subspace of L^2(_n) of functions that is spanned by functions of at most D variables at a time.] In <cit.>, the low-degree likelihood ratio is defined as the projection of L_n onto the space of polynomials of coordinate degree ≤ D. The reason for this is to capture, e.g., algorithms that preprocess the data by applying a complicated high-degree function entrywise. However, we are not aware of any natural problem in which it is important to work with coordinate degree instead of polynomial degree. While working with coordinate degree gives lower bounds that are formally stronger, we work with polynomial degree throughout these notes because it simplifies many of the computations.




  §.§.§ Empirical Evidence and Refined Conjecture


Perhaps the strongest form of evidence that we have in favor of the low-degree method is simply that it has been carried out on many high-dimensional inference problems and seems to always give the correct predictions, coinciding with widely-believed conjectures. These problems include planted clique <cit.> (implicit in <cit.>), community detection in the stochastic block model <cit.>, the spiked tensor model <cit.>, the spiked Wishart model <cit.>, and sparse PCA <cit.>. In these notes we have also carried out low-degree calculations for the spiked Wigner model and spiked tensor model (see Section <ref>). Some of the early results <cit.> showed only L_n^≤ D = n^o(1) as evidence for hardness, which was later improved to O(1) <cit.>. Some of the above results <cit.> use coordinate degree instead of degree (as we discussed in Section <ref>). Throughout the above examples, the low-degree method has proven to be versatile in that it can predict both sharp threshold behavior as well as precise smooth tradeoffs between subexponential runtime and statistical power (as illustrated in the two parts of Section <ref>).

As discussed earlier, there are various reasons to believe that if L_n^≤ D = O(1) for some D = ω(log n) then there is no polynomial-time distinguishing algorithm; for instance, this allows us to rule out a general class of spectral methods (see Theorem <ref>). However, we have observed that in numerous examples, the LDLR actually has the following more precise behavior that does not involve the extra factor of log(n).

Let  and  be “sufficiently nice.” If there exists a polynomial-time algorithm to strongly distinguish  and  then L_n^≤ D = ω(1) for any D = ω(1).


In other words, if L_n^≤ D = O(1) for some D = ω(1), this already constitutes evidence that there is no polynomial-time algorithm.
The above seems to be a cleaner version of the main low-degree conjecture that remains correct for many problems of practical interest.



  §.§.§ Extensions



While we have focused on the setting of hypothesis testing throughout these notes, we remark that low-degree arguments have also shed light on other types of problems such as estimation (or recovery) and certification.

First, as we have mentioned before, non-trivial estimation[Non-trivial estimation of a signal ∈^n means having an estimator x̂ achieving |⟨, ⟩|/(·) ≥ε with high probability, for some constant ε > 0.] typically seems to be precisely as hard as strong distinguishing (see Definition <ref>), in the sense that the two problems share the same λ_𝗌𝗍𝖺𝗍 and λ_𝖼𝗈𝗆𝗉. For example, the statistical thresholds for testing and recovery are known to coincide for problems such as the two-groups stochastic block model <cit.> and the spiked Wigner matrix model (for a large class of spike priors) <cit.>. Also, for any additive Gaussian noise model, any lower bound against hypothesis testing using the second moment method (Lemma <ref>) or a conditional second moment method also implies a lower bound against recovery <cit.>. More broadly, we have discussed (see Section <ref>) how suitable spectral methods typically give optimal algorithms for high-dimensional problems; such methods typically succeed at testing and recovery in the same regime of parameters, because whenever the leading eigenvalue undergoes a phase transition, the leading eigenvector will usually do so as well (see Theorem <ref> for a simple example). Thus, low-degree evidence that hypothesis testing is hard also constitutes evidence that non-trivial recovery is hard, at least heuristically. Note, however, that there is no formal connection (in either direction) between testing and recovery (see <cit.>), and there are some situations in which the testing and recovery thresholds differ (e.g., <cit.>).

In a different approach, Hopkins and Steurer <cit.> use a low-degree argument to study the recovery problem more directly. In the setting of community detection in the stochastic block model, they examine whether there is a low-degree polynomial that can non-trivially estimate whether two given network nodes are in the same community. They show that such a polynomial exists only when the parameters of the model lie above the problem's widely-conjectured computational threshold, the Kesten–Stigum threshold. This constitutes direct low-degree evidence that recovery is computationally hard below the Kesten–Stigum threshold.

A related (and more refined) question is that of determining the optimal estimation error (i.e., the best possible correlation between the estimator and the truth) for any given signal-to-noise parameter λ. Methods such as approximate message passing can often answer this question very precisely, both statistically and computationally (see, e.g., <cit.>, or <cit.> for a survey). One interesting question is whether one can recover these results using a variant of the low-degree method.

Another type of statistical task is certification. Suppose that ∼_n has some property  with high probability. We say an algorithm certifies the property  if (i) the algorithm outputs “yes” with high probability on ∼_n, and (ii) if  does not have property  then the algorithm always outputs “no.” In other words, when the algorithm outputs “yes” (which is usually the case), this constitutes a proof that  indeed has property . Convex relaxations (including SoS) are a common technique for certification. In <cit.>, the low-degree method is used to argue that certification is computationally hard for certain structured PCA problems. The idea is to construct a quiet planting _n, which is a distribution for which (i) ∼_n never has property , and (ii) the low-degree method indicates that it is computationally hard to strongly distinguish _n and _n. In other words, this gives a reduction from a hypothesis testing problem to a certification problem, since any certification algorithm can be used to distinguish _n and _n. (Another example of this type of reduction, albeit relying on a different heuristic for computational hardness, is <cit.>.)




§ ACKNOWLEDGMENTS

tocsectionAcknowledgments
We thank the participants of a working group on the subject of these notes, organized by the authors at the Courant Institute of Mathematical Sciences during the spring of 2019.
We also thank Samuel B. Hopkins, Philippe Rigollet, and David Steurer for helpful discussions. 


tocsectionReferences
alpha






§ OMITTED PROOFS




 §.§ Neyman-Pearson Lemma



We include here, for completeness, a proof of the classical Neyman–Pearson lemma <cit.>.


    Note first that a test f is completely determined by its rejection region, R_f = {: f() = }.
    We may rewrite the power of f as
    
    1 - β(f) = [f() = ] = ∫_R_fd() = ∫_R_fL()d().

    On the other hand, our assumption on α(f) is equivalent to
    
    [R_f] ≤[L() > η].

    Thus, we are interested in solving the optimization
    
    [          maximize       ∫_R_fL()d();        subject to            R_f ∈,;                   [R_f] ≤[L() > η]. ]

    
    From this form it is intuitive how to proceed: let us write R_⋆{: L() > η} = R_L_η, then the difference of powers is
    
    (1 - β(L_η)) - (1 - β(f))
               = ∫_R_⋆L()d() - ∫_R_fL()d() 
       = ∫_R_⋆∖ R_fL()d() - ∫_R_f ∖ R_⋆L()d() 
       ≥η([R_⋆∖ R_f] - [R_f ∖ R_⋆]) 
       = η([R_⋆] - [R_f]) 
       ≥ 0,

    completing the proof.






 §.§ Equivalence of Symmetric and Asymmetric Noise Models



For technical convenience, in the main text we worked with an asymmetric version of the spiked Wigner model (see Section <ref>), = λ^⊤ + where  has i.i.d. (0,1) entries. A more standard model is to instead observe = 1/2( + ^⊤) = λ^⊤ +, where  is symmetric with (0,1) diagonal entries and (0,1/2) off-diagonal entries, all independent. These two models are equivalent, in the sense that if we are given a sample from one then we can produce a sample from the other. Clearly, if we are given , we can symmetrize it to form . Conversely, if we are given , we can draw an independent matrix  with i.i.d. (0,1) entries, and compute + 1/2( - ^⊤); one can check that the resulting matrix has the same distribution as  (we are adding back the “skew-symmetric part” that is present in  but not ).

In the spiked tensor model (see Section <ref>), our asymmetric noise model is similarly equivalent to the standard symmetric model defined in <cit.> (in which the noise tensor  is averaged over all permutations of indices). Since we can treat each entry of the symmetric tensor separately, it is sufficient to show the following one-dimensional fact: for unknown x ∈, k samples of the form y_i = x + (0,1) are equivalent to one sample of the form ỹ = x + (0,1/k). Given {y_i}, we can sample ỹ by averaging: 1/k∑_i=1^k y_i. For the converse, fix unit vectors _1,…,_k at the corners of a simplex in ^k-1; these satisfy ⟨_i,_j ⟩ = -1/k-1 for all i  j. Given ỹ, draw ∼(0, I_k-1) and let y_i = ỹ + √(1-1/k) ⟨_i,⟩; one can check that these have the correct distribution.




 §.§ Low-Degree Analysis of Spiked Wigner Above the PCA Threshold




We follow the proof of Theorem <ref>(ii) in Section <ref>. For any choice of d ≤ D, using the standard bound 2dd≥ 4^d/(2√(d)),

    L_n^≤ D^2    ≥λ^2d/d!_^1,^2[⟨^1,^2 ⟩^2d] 
       ≥λ^2d/d!nd(2d)!/2^dusing the moment bound (<ref>) from Section <ref>
       = λ^2d/d!n!/d!(n-d)!(2d)!/2^d
       = λ^2d2ddn!/(n-d)! 2^d
       ≥λ^2d4^d/2√(d)(n-d)^d/2^d
       = 1/2√(d)(2λ^2 (n-d))^d 
       = 1/2√(d)(λ̂^2 (1 - d/n))^d.

Since λ̂> 1, this diverges as n →∞ provided we choose d ≤ D with ω(1) ≤ d ≤ o(n).








§ HERMITE POLYNOMIALS



Here we give definitions and basic facts regarding the Hermite polynomials (see, e.g, <cit.> for further details), which are orthogonal polynomials with respect to the standard Gaussian measure.


    
    The univariate Hermite polynomials are the sequence of polynomials h_k(x) ∈[x] for k ≥ 0 defined by the recursion
    
    h_0(x)    = 1, 
    
            h_k + 1(x)    = xh_k(x) - h_k^'(x).

    The normalized univariate Hermite polynomials are h_k(x) = h_k(x) / √(k!).


The following is the key property of the Hermite polynomials, which allows functions in L^2((0, 1)) to be expanded in terms of them.


    The normalized univariate Hermite polynomials form a complete orthonormal system of polynomials for L^2((0, 1)).


The following are the multivariate generalizations of the above definition that we used throughout the main text.


    The N-variate Hermite polynomials are the polynomials H_α() ∏_i = 1^N h_α_i(X_i) for α∈^N.
    The normalized N-variate Hermite polynomials in N variables are the polynomials H_α() ∏_i = 1^N h_α_i(X_i) = (∏_i = 1^N α_i!)^-1/2∏_i = 1^N h_α_i(X_i) for α∈^N.


Again, the following is the key property justifying expansions in terms of these polynomials.


    The normalized N-variate Hermite polynomials form a complete orthonormal system of (multivariate) polynomials for L^2(( 0,  I_N)).


For the sake of completeness, we also provide proofs below of the three identities concerning univariate Hermite polynomials that we used in Section <ref> to derive the norm of the LDLR under the additive Gaussian noise model.
It is more convenient to prove these in a different order than they were presented in Section <ref>, since one identity is especially useful for proving the others.


    Recall that we are assuming a function f: → is k times continuously differentiable and f and its derivatives are O(exp(|x|^α)) for α∈ (0, 2), and we want to show the identity
    
    _y ∼(0, 1)[h_k(y) f(y)] = _y ∼(0, 1)[ d^k f/dy^k(y)].

    We proceed by induction.
    Since h_0(y) = 1, the case k = 0 follows immediately.
    We also verify by hand the case k = 1, with h_1(y) = y:
    
    _y ∼(0, 1)[yf(y) ] = 1/√(2π)∫_-∞^∞ f(y) · ye^-y^2 / 2dy = 1/√(2π)∫_-∞^∞ f^'(y) e^-y^2 / 2dy = _y ∼(0, 1)[f^'(y) ],

    where we have used ordinary integration by parts.
    
    Now, suppose the identity holds for all degrees smaller than some k ≥ 2, and expand the degree k case according to the recursion:
    
    _y ∼(0, 1)[h_k(y) f(y)] 
               = _y ∼(0, 1)[y h_k - 1(y) f(y)] - _y ∼(0, 1)[h_k - 1^'(y) f(y)] 
       = _y ∼(0, 1)[h_k - 1^'(y)f(y)] + _y ∼(0, 1)[h_k - 1(y)f^'(y)] - _y ∼(0, 1)[h_k - 1^'(y) f(y)] 
       = _y ∼(0, 1)[h_k - 1(y)f^'(y)] 
       = _y ∼(0, 1)[d^k f/dy^k(y)],

    where we have used the degree 1 and then the degree k - 1 hypotheses.



    Recall that we want to show, for all k ≥ 0 and μ∈, that
    
    _y ∼(μ, 1)[h_k(y)] = μ^k.

    We proceed by induction on k.
    Since h_0(y) = 1, the case k = 0 is immediate.
    Now, suppose the identity holds for degree k - 1, and expand the degree k case according to the recursion:
    
    _y ∼(μ, 1)[h_k(y)] 
           = _y ∼(0, 1)[h_k(μ + y)] 
       = μ_y ∼(0, 1)[h_k - 1(μ + y)] + _y ∼(0, 1)[y h_k - 1(μ + y)] - _y ∼(0, 1)[h_k - 1^'(μ + y)]
        which may be simplified by the Gaussian integration by parts to   = μ_y ∼(0, 1)[h_k - 1(μ + y)] + _y ∼(0, 1)[h_k - 1^'(μ + y)] - _y ∼(0, 1)[h_k - 1^'(μ + y)] 
       = μ_y ∼(0, 1)[h_k - 1(μ + y)],

    and the result follows by the inductive hypothesis.



    Recall that we want to show the series identity for any x, y ∈,
    
    exp(xy - 1/2x^2) = ∑_k = 0^∞1/k!x^k h_k(y).

    For any fixed x, the left-hand side belongs to L^2((0, 1)) in the variable y.
    Thus this is merely a claim about the Hermite coefficients of this function, which may be computed by taking inner products.
    Namely, let us write
    
    f_x(y) exp(xy - 1/2x^2),

    then using Gaussian integration by parts,
    
    f_x, h_k  = 1/√(k!)_y ∼(0, 1)[f_x(y) h_k(y)] = 1/√(k!)_y ∼(0, 1)[d^k f_x/dy^k(y) ] = 1/√(k!)x^k _y ∼(0, 1)[f_x(y) ].

    A simple calculation shows that _y ∼(0, 1)[f_x(y)] = 1 (this is an evaluation of the Gaussian moment-generating function that we have mentioned in the main text), and then by the Hermite expansion
    
    f_x(y) = ∑_k = 0^∞ f_x, h_k h_k(y) = ∑_k = 0^∞1/k!x^k h_k(y),

    giving the result.






§ SUBGAUSSIAN RANDOM VARIABLES



Many of our rigorous arguments rely on the concept of subgaussianity, which we now define. See, e.g., <cit.> for more details.


For σ^2 > 0, we say that a real-valued random variable π is σ^2-subgaussian if [π] = 0 and for all t ∈, the moment-generating function M(t) = [exp(t π)] of π exists and is bounded by M(t) ≤exp(σ^2 t^2 / 2).

Here σ^2 is called the variance proxy, which is not necessarily equal to the variance of π (although it can be shown that σ^2 ≥Var[π]). The name subgaussian refers to the fact that exp(σ^2 t^2 / 2) is the moment-generating function of (0,σ^2). 

The following are some examples of (laws of) subgaussian random variables. Clearly, (0,σ^2) is σ^2-subgaussian. By Hoeffding's lemma, any distribution supported on an interval [a,b] is (b-a)^2/4-subgaussian. In particular, the Rademacher distribution ({± 1}) is 1-subgaussian. Note also that the sum of n independent σ^2-subgaussian random variables is σ^2 n-subgaussian.

Subgaussian random variables admit the following bound on their absolute moments; see Lemmas 1.3 and 1.4 of <cit.>.

If π is σ^2-subgaussian then

    [|π|^k] ≤ (2σ^2)^k/2 k Γ(k/2)

for every integer k ≥ 1.


Here Γ(·) denotes the gamma function which, recall, is defined for all positive real numbers and satisfies Γ(k) = (k-1)! when k is a positive integer. We will need the following property of the gamma function.

For all x > 0 and a > 0,

    Γ(x+a)/Γ(x)≤ (x+a)^a.



This follows from two standard properties of the gamma function. The first is that (similarly to the factorial) Γ(x+1)/Γ(x) = x for all x > 0. The second is Gautschi's inequality, which states that Γ(x+s)/Γ(x) < (x+s)^s for all x > 0 and s ∈ (0,1).



In the context of the spiked Wigner model (Section <ref>), we now prove that subgaussian spike priors admit a local Chernoff bound (Definition <ref>).


Suppose π is σ^2-subgaussian (for some constant σ^2 > 0) with [π] = 0 and [π^2] = 1. Let (_n) be the spike prior that draws each entry of  i.i.d. from π (where π does not depend on n). Then (_n) admits a local Chernoff bound.



Since π is subgaussian, π^2 is subexponential, which implies [exp(t π^2)] < ∞ for all |t| ≤ s for some s > 0 (see e.g., Lemma 1.12 of <cit.>).

Let π, π^' be independent copies of π, and set Π = ππ^'. The moment-generating function of Π is

    M(t) = [exp(t Π)] = _π_π'[exp(t ππ')] ≤_π[exp(σ^2 t^2 π^2/2)] < ∞

provided 1/2σ^2 t^2 < s, i.e. |t| < √(2s/σ^2). Thus M(t) exists in an open interval containing t=0, which implies M'(0) = [Π] = 0 and M”(0) = [Π^2] = 1 (this is the defining property of the moment-generating function: its derivatives at zero are the moments).

Let η > 0 and f(t) exp(t^2/2(1-η)). Since M(0) = 1, M'(0) = 0, M”(0) = 1 and, as one may check, f(0) = 1, f'(0) = 0, f”(0) = 1/1-η > 1, there exists δ > 0 such that, for all t ∈ [-δ,δ], M(t) exists and M(t) ≤ f(t).

We then apply the standard Chernoff bound argument to ^1,^2  = ∑_i=1^n Π_i where Π_1,…,Π_n are i.i.d. copies of Π. For any α > 0,

    {^1,^2 ≥ t}   = {exp(α^1,^2 ) ≥exp(α t)}
       ≤exp(-α t) [exp(α^1,^2 )] by Markov's inequality
       = exp(-α t) [exp(α∑_i=1^n Π_i)]
       = exp(-α t) [M(α)]^n
       ≤exp(-α t) [f(α)]^n provided α≤δ
       = exp(-α t) exp(α^2 n/2(1-η)).

Taking α = (1-η)t/n,

    {^1,^2 ≥ t}≤exp(-1/n(1-η)t^2 + 1/2n(1-η)t^2) = exp(-1/2n(1-η)t^2)

as desired. This holds provided α≤δ, i.e. t ≤δ n/(1-η). A symmetric argument with -Π in place of Π holds for the other tail, {^1,^2 ≤ -t}.





§ FORMAL CONSEQUENCES OF THE LOW-DEGREE METHOD


Here we provide the proofs of Theorems <ref> and <ref>, which show that if the LDLR predicts hardness then polynomial thresholding and low-degree spectral methods (respectively) must fail in a particular sense. We first discuss hypercontractivity, the key ingredient in the proofs.



 §.§ Hypercontractivity



The following hypercontractivity result states that the moments of low-degree polynomials of i.i.d. random variables must behave somewhat reasonably. The Rademacher version is the Bonami lemma from <cit.>, and the Gaussian version appears in <cit.> (see Theorem 5.10 and Remark 5.11 of <cit.>). We refer the reader to <cit.> for a general discussion of hypercontractivity.



Let = (x_1,…,x_n) have either i.i.d. (0,1) or i.i.d. Rademacher (uniform ± 1) entries, and let f: ^n → be a polynomial of degree k. Then

    [f(x)^4] ≤ 3^2k [f(x)^2]^2.



We will combine this with the following standard second moment method.



If Z ≥ 0 is a random variable with finite variance, and 0 ≤θ≤ 1, then

    Pr{Z > θ [Z]}≥ (1-θ)^2 [Z]^2/[Z^2].



By combining Propositions <ref> and <ref>, we immediately have the following.


Let = (x_1,…,x_n) have either i.i.d. (0,1) or i.i.d. Rademacher (uniform ± 1) entries, and let f: ^n → be a polynomial of degree k. Then, for 0 ≤θ≤ 1,

    {f(x)^2 > θ [f(x)^2]}≥ (1-θ)^2 [f(x)^2]^2/[f(x)^4]≥(1-θ)^2/3^2k.




One rough interpretation of Corollary <ref> is that if f is degree k, then [f(x)^2] cannot be dominated by an event of probability smaller than roughly 3^-2k.








 §.§ Lower Bound Against Thresholding Polynomials



Using the above tools, we can now prove Theorem <ref>.


Consider the degree-2kd polynomial f^2k. Using Jensen's inequality,

    _[f()^2k] ≥(_[f()])^2k≥ A^2k.

If _[f()^4k] ≤ B^4k, then (<ref>) holds immediately.
Otherwise, let θ B^4k/_[f()^4k] ≤ 1. Then, we have

    δ   ≥(|f()| ≥ B)
       = (f()^4k≥ B^4k)
       = (f()^4k≥θ _[f()^4k])
       ≥(1-θ)^2/3^4kd. by Proposition <ref>

Thus θ≥ 1 - 3^2kd√(δ), implying

    _[f()^4k] = B^4k/θ≤ B^4k(1 - 3^2kd√(δ))^-1.

Using the key variational property of the LDLR (Proposition <ref>),

    L^≤ 2kd≥_[f()^2k]/√(_[f()^4k])≥(A/B)^2k√(1 - 3^2kd√(δ))≥1/2(A/B)^2k

since δ≤1/2· 3^-4kd.






 §.§ Lower Bound Against Spectral Methods



The proof of Theorem <ref> is similar to the above.


Let {λ_i} be the eigenvalues of , with |λ_1| ≥⋯≥ |λ_L|. Consider the degree-2kd polynomial f() (^2k) = ∑_i=1^L λ_i^2k. Using Jensen's inequality,

    _[f()] = _∑_i=1^L λ_i^2k≥_[λ_1^2k] ≥(_|λ_1|)^2k≥ A^2k.

If _[f()^2] ≤ L^2 B^4k, then (<ref>) holds immediately. 
Otherwise, let θ L^2 B^4k/_[f()^2] ≤ 1. Then, we have

    δ   ≥(≥ B)
       = (λ_1^2k≥ B^2k)
       ≥(f() ≥ LB^2k)
       = (f()^2 ≥ L^2 B^4k)
       = (f()^2 ≥θ _[f()^2])
       ≥(1-θ)^2/3^4kd. by Proposition <ref>

Thus θ≥ 1 - 3^2kd√(δ), implying

    _[f()^2] = L^2 B^4k/θ≤ L^2 B^4k(1 - 3^2kd√(δ))^-1.

Using the key variational property of the LDLR (Proposition <ref>),

    L^≤ 2kd≥_[f()]/√(_[f()^2])≥1/L(A/B)^2k√(1 - 3^2kd√(δ))≥1/2L(A/B)^2k

since δ≤1/2· 3^-4kd.



