The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Authors: Afonso S Bandeira
Ahmed El Alaoui
Samuel B. Hopkins
Tselil Schramm
Alexander S Wein
Ilias Zadik
Venue: NeurIPS 2022 Accept (2022)
Keywords: Information-computation gaps
low-degree likelihood ratio
statistical physics
MCMC methods
sparse regression

Abstract: Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physics that are based on free energy landscapes. This paper aims to make a rigorous connection between the seemingly different low-degree and free-energy based approaches. We define a free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal. By leveraging these rigorous connections we are able to: establish that for Gaussian additive models the "algebraic" notion of low-degree hardness implies failure of "geometric" local MCMC algorithms, and provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly. These results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools such as new methods for proving low-degree lower bounds.

The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S. Bandeira Department of Mathematics
Ahmed EI Alaoui
Department of Statistics and Data Science Comelll University
ETH Zürich bandeira@math. ethz.
ae3330cornell. edu
Samuel Hopkins
Tselil Schramm
MIT EECS Cambridge, MA samhop@mit.edds edu
Department of Statistics Stanford University
tselil@stanfor ordtaa edu
Alexander S. Wein Department of Mathematics University of California, Davis asweingucdavis.
Ilias Zadik Department of Mathematics
MIT izadikêmit edu
Abstract
Many high-dimensional statistical inference problems believed possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for such hardness, including lower bounds against restricted models of computation (such as low-degree functions), as well as methods rooted in statistical physies that based free energy landscapes. This paper aims to make rigorous connection between the seemingly different low-degree and free-energy based approaches. We define free-energy based criterion for hardness and formally connect it to the well-established notion of low-degree hardness for a broad class of statistical problems, namely all Gaussian additive models and certain models with a sparse planted signal. By leveraging these rigorous connections we are able to: establish that for Gaussian additive models the "algebraic" notion of low-degree hardness implies failure of "geometric" local MCMC algorithms, and provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly. These results provide both conceptual insights into the connections between different notions of hardness, as well as concrete technical tools such as new methods for proving low-degree lower bounds.
Introduction
Many inference problems in high dimensional statistics appear exhibit inforimation-ccompuaaoon gap, wherein at some values of the signal-to-noise ratio, inference is information information-theorrticaall theoretically possible, but (time-)efficient algorithm is known. Well-known problems that exhibit such gaps include sparse linear regression, sparse principal component analysis (PCA), tensor PCA, planted clique, community detection, graph coloring, and many others (we point the reader the survey references [ZK] 6a, BPW18, RSS19, KWB19, Gam21] and references therein for many examples).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A priori, it is unclear whether such gaps are symptom of the inherent computational intractability of these problems, or whether they instead reflect a limitation of our algorithmic ingenuity. One of the main goals in this field is to provide, and understand, rigorous evidence for the existence of an cebornation-compuatte information -hheoretic lower bounds, and these often sharply characterize the signal-to-noise ratio at which inference is possible. We have relatively fewer tools for establishing computational lower bounds in statistical settings, and the study of such tools is still in its early days. Broadly, there are problems
gap. Indeed, there are several mature tools to establish statistical or
three approaches: (i) establishing computational equivalence between suspected-to-be-he via reductions, (ii) proving lower bounds within restricted models of computation, in other words, ruling out families of known algorithms, and (ii) characterizing geometric properties of the problem that tend to correspond to computational hardness, often by studying corresponding energy or free energy landscape of the posterior distribution of the signal given the data, and establishing the existence of 'large harriers' in this landscape. In some cases it can be rigorously shown that these properties impede the success of certain families of algorithms (notable examples include the work of Jerrum [Jer92] and Gamarnik and Sudan [GS17]; see also references therein for other instances).
These complementary approaches give us a richer understanding of the computational landscape of nigh-dimensional statistical inference. Reductions contribute establishing equivalence classes of (conjectured hard) problems, and lower bounds against restricted models, or characterizations of the problem geometry, give concrete evidence for computational hardness within the current limits of known algorithms. There have been considerable recent advances in this context (see for example [BB20], the surveys [ZK16a, BPW18, 18, RSS19, KWB19, Gam21], and references therein). One particularly exciting direction, which is the topic of this paper, is the pursuit of rigorous connections between different computational lower bound approaches. For instance, recent result shows (under mild assumptions) that lower bounds against statistical query algorithms and low-degree polynomials are essentially equivalent [BBH*20] 20]. Results of this type help to unify our understanding about what makes problems hard. Following the work of [BHK* 19, HKP 17, HS17] in the context of the uum-of-squares hierarchy of algorithms, a conjecture was made that there is a large and casy-to-characteriie universality class of intractable problems [Hop18]: those for which low-degree statistics cannot distinguish data with a planted signal from (suitably defined) random noise. These problems are "hard for the low-degree likelihood ratio" or "low-degree hard," which we will define precisely below. Many problems mentioned above fall into this class precisely in the regime of their informationn-copputtioo gaps.
Another successful approach to understand computational hardness of statistical problems borrows tools from statistical physics: tools such as the cavity method and replica method can be used to make remarkably precise predictions of both statistical and computational thresholds, essentially by studying properties of free energy potentials associated to the problem in question, by studying related iterative algorithms such as belief propagation or approximate message passing (see e.g. [DKMZ11, LKZ15a, LKZ15b, DMK 16]) the type of "free energy barrier" encountered in these potentials that is (heuristically) suggested to lead to computational hardness also often has an appealing interpretation as barrier to algorithms based on Markov chain Monte Carlo methods. However, the physics approaches are not without drawbacks, chief among them (for us) that it is notoriously difficult to pin down with mathematical rigor just what the free energy potentials (certain one-dimensional curves) in question are, or precisely what properties of them are meant to predict computational hardness. Furthermore, it is clear that some versions of the "physics recipe" can make erroneous predictions (for instance, in the case of the tensor PCA problem), and can require seemingly problem- specific modifications to be redeemed [RM14, LML 17, BGJ20, WEM19, BCRT20, GZ19]. This has made it challenging to push any mathematical account of the physics approach to predicting computational hardness beyond a one-problem-at- -tt-ttmmme---- theory.
Main Contributions A tantalizing question and a step towards rigorous free-energy based theory of statistical hardness is whether some free-energy based criterion is actually rigorously connected with low-degree hardness. This paper aims to achieve exactly this: to make a rigorous connection between the low-degree and free-energy based approaches in the setting of statistical inference. (We note that this setting differs from that of random optimization problems with no planted signal, where a connection of this nature has already been established [GJW20, Wei22, BH21J.) Our first contribution is a formal definition of free-energy based criterion for computational hardness, the Franz-Pariae Parisi criterion (Definition 3.2) inspired by the so-called Franz-Parisi potential [FP95]. We formally connect this criterion to low-degree hardness for broad class of statistical problems,
2

---

namely all Gaussian additive models (Theorems 4.3 and 4.4) and certain sparse planted models (e.g. Theorem 6.2). By leveraging these rigorous connections we are able (i) establish that in the context of Gaussian additive models, low-degree hardness implies failure of local MCMC algorithms (Corollary 5.4), and (ii) provide new low-degree lower bounds for sparse linear regression which seem difficult to prove directly (Theorem 6.2). In the supplementary material, we also investigate whether the Prans-Parisi criterion, as we defined it, is accurate beyond Gaussian Additive Models, and find, with counterexamples, that it can make erroneous predictions in simple discrete settings. We thus leave as an exciting future direction the problem of determining its precise domain of applicability, and investigating what other free-energy based criteria may be more suitable in other inference problems.
2 Preliminaries
We will focus problems in which there is signal vector of interest E R", drawn from a prior distribution μ over such signals, and the data observed is a sample from a distribution P,, on RVV that depends the signal u. We focus mainly on hypothesis testing: we given a sample generated either from the "planted" distribution P = Eu P. (a mixture model were the data is drawn from P. μ1) from "null" reference distribution Q representing pure noise, and the goal is
for random to decide whether it is more likely that the sample came from IP or Q. While not our main focus, we note that in the section on MCMC hardness we do also discuss the related task of estimation/recovery:: given a sample from P., with the promise that u ~ μt, the goal is to estimate u (different estimation error targets correspond to different versions of this problem. often referred to weal/approximate recovery or exact recovery). We now begin with the formal definitions.
Problem 2.1 (High Dimensional Inference: Hypothesis Testing). Given positive integers n, N. and distributions ja on IR", and P., on R- for each w E supp(u), the goal is to perform simple hypothesis testing between the Null model Ho Y Q and the Planted model H, Y P Euryy P..
We will be especially interested in asymptotic settings where + and the other parameters scale with n in some prescribed way: N = Nn. f = Pn. P = F.. Q Qn. In this setting, we focus on the following two objectives.
Definition 2.2 (Strong/ Weak Detection). Strong detection is achieved if the sum of type and type errors' tends to 0 as n co. Weak detection is achieved if the sum of type I and type II errors is at most - e for some fixed > (not depending on n.).
Throughout, we will work in the Hilbert space L2(()) of (square integrable) functions R- + R with inner product (f,g) == Er-el((Y)))()) (Y)) and corresponding norm ||fle == (f, f) 1/2 For function f N -> TR and integer D E N, we let f denote the orthogonal (w.r.t. (,, (o) projection of f onto the subspace of polynomials of degree < D. We assume that P., is absolutely dP,
continuous w.r.t. Q for all u E suрр(и), use L,- == ai to denote the likelihood ratio, and assume that L. E (2) for all u E supp(p). ::= de Eu-pla is the likelihood ratio of I and Q.
2.1 (Low-degree) Likelihood Ratio and Computational Complexity of Inference
A key quantity of interest is the (squared) norn of the likelihood ratio, which is related to the chi- squared divergence x²(P1) || Q) as ||| = (P Q) + 1. If this quantity is asymptotically bounded (by O(1) or 1 + o)) there are well-known consequences for information -hirooetittee impossibility of testing (impossibility of strong and weak detection, respectively); see [MRZ15, Lemma 2]. The which recall means the projection of the likelihood ratio onto the subspace of degree-D polynomials, has been studied intensively in recent years as a means to "predict" computational complexity of high-dimensional testing problems (see [Hop18, 18, KWB19]).
low-degree likelihood ratio,
Definition 2.3 (Low- Log-ee Likelihood Ratio). Define the squared norm of the degree- D likelihood ratio (also called the "lowedegree likelihood ratio")) to be the quantity
LD(D) || =
Lm umnj
E u,0~n
[LS
I.P.
1
'Type I error is the probability of outputting "F" when given sample from Q. Type Il error is the probability of outputting "Q"" when given sample from I..
3

---

where the last equality follows from linearity of the projection operator, and where u. are drawn independently from p. For some increasing sequence D D... we say that the hypothesis testing problem above is hard for the degree- D) likelihood or simply low-degree hard if (DD(D) = 0(1)
Heuristically speaking, the interpretation of LD(D) should be thought of as analogous to that of | but for computationalll-bouus -ooundee tests: if LD(D) = (11) (or 1 + o(1)) this suggests computational hardness of strong (or weak, respectively) detection. The parameter D D. should be loosely thought of as a proxy for the runtime allowed for our testing algorithm, where D = O n) corresponds to polynomial time and more generally, larger values of D correspond to runtime ex)(@(D)) where θ hides factors of log n. See supplementary material for further discussion of the relationship between low-degree hardness and hardness against other classes of algorithms.
3 The Franz Parisi criterion
We define a predictor of computational hardness, which we call the Franz-Parisi criterion. It is inspired by well-established ideas rooted in statistical physics, which discuss further below and in the supplement. However, the precise definition we use here has not appeared before (to our knowledge). Throughout this paper we will argue for the significance of this criterion in number of ways: its conceptual link to physics, its provable equivalence to the low-degree criterion for Gaussian additive models, its formal connection to MCMC methods for Gaussian additive models (Section 5), and its usefulness as a tool for proving low-degree lower bounds (Section 6).
Definition 3.1 (Low-Overlap Likelihood Norm). We define the low-overlap likelihood norm at overlap 6 2 0 as
LO(6)
[[ooL))iS (Lus Luii)
where u, u drawn independently from p..
Definition 3.2 Tranz-Pariss Criterion). We define the Franz- Parisi Criterion at D deviations to be the quantity
FP( = TO()), for 8 = 5(D) == sup (a 2 S.t.
Pr (1 e)) 2 8) 2 e D). (3)
For some increasing sequence D = Dz,, problem is FP-hard at D deviations if FP(D) = 0(1)
Heuristically speaking. FD) should be thought of as having a similar interpretation as LD(D): FP(D) = O(1) this suggests hardness of strong detection, and if FP(D) = 1 + o(1) this suggests hardness of weak detection. The parameter D is a proxy for runtime and corresponds to the parameter D in LD(D), as we justify below.
We remark that IDD) and FP(D) can be thought of different ways of "restricting" the quantity
= EE
(LL,,LL))
(4)
which, recall, is related to information-theorete impossibility of testing. For LD, the restriction is low-degree projection on each Lu, while for FP it excludes pairs (u, v) of high overlap. Our results will show that (in some settings) these two restrictions are nearly equivalent.
Relation to statistical physics We defer to supplementary material an extended discussion of the relationship between the Franz-Parisi criterion and ideas from statistical physics. See also [MM09, ZK 16b] for exposition on the well-explored connections between statistical physics and Bayesian inference. Roughly speaking, the logarithm of LO()) is the 'annealed' approximation near = 0 of the Franz-Purisi potential [FP95]; a tool used study the free energy landscape of disordered system locally around a reference configuration at equilibrium. In our statistical context this potential takes the form
f(8) Eu ~r, log Euryy (u.v)= (Y)]
Roughly speaking, f(6) measures the amount of mass that the posterior distribution places on vectors of overlap 5 with the true signal. Jensen's 's inequality leads to the upper bound f()) S fanm (8)
log Bu, [A (a,))= (Ln, Lu) which we call the annealed FP potential, c.f. LO(8), Eq. (2).

---

For inference problems which are information-theorrtccall theoretically solvable, most of the mass of the posterior distribution of YY, when Y Fa is concentrated on those with large (u, v). But to predict computational complexity, the Franz-Parisi criterion stipulates that it is the contributions of v with Ku, e) I 5 for small values of which matter: when such e contribute noticeably, (,0(5) is large and hence so is FP(D).
The FP criterion, Definition 3.2, is whether FP(D) stays bounded or diverges as + oo for some choice of an increasing sequence D = Dn- A heuristic justification of this criterion is as follows: We should first note that since Lu 2 O, we have FP(D) z |_,|.- Thus if |_lle
oo but (D) (1), then the divergence of Llla must be due to contributions to the sum Eq. (4) with high overlap values: Ku, w) >> 6(D). Suppose now there is a free energy barrier separating small overlaps (u,, v)) ((D) from larger ones (u, u)| >> 8(2). For instance, suppose (u,
is a local maximum of the potential, separated by a barrier from a global maximum located at (u, u) > 8(D (see Fig. I, Panel (b)), then one needs much more than co(D) samples to guess an overlap value on the other side of the barrier and land in the basin of attraction of the global maximum. This suggests that tests distinguishing IP and Q cannot be constructed in time eo(D), One of our main results (see Section 4) is an equivalence relation between the (P) criterion and the LDD))) criterion for Gaussian models, where D' = (D). therefore grounding this heuristic in a rigorous statement.
Example: The spiked Wigner model As a concrete example, let us consider the spiked Wigner model with sparse Rademacher prior: The signal vector has i.i.d. entries drawn from a three-point prior f40 = 1/+1 to (1 $5-1/ vi- and for 1 S í S j S n we let Yi₃ X - Uruy + Zig. where Z is drawn from the Gaussian Orthogonal Ensemble: Zaj ~ NO0 1) for j and Z (N, 2). The null distribution is pure Gaussian noise: Y= 7. In this case, known efficient algorithms succeed at detecting/estimating the signal if and only if X >> 1 [BGN11, LM19, CL19]. Furthermore, the threshold ÂAL = 1 is coormatioon-thorettcce than a known absolute constant). On the other hand if p is small enough, then detection becomes information-theorre theoreticallly possible for some X < 1 but no known polynomial-tmne algorithm succeeds in the regime [BMV+ 17, PWBM18, AKJ20J. Let us check that the behavior of the annealed potential is qualitatively consistent with these facts. A small computation (see Section 4) leads to the expression
tight when p = 1 (or more generally, if is larger
(>a 2n
Lo)a = cxp
(u.
and the annealed FP potential is
22k2
yann (k/p) log Pr
= (),,)>=///) +
2np²
Letting & = [nz]. and using Stirling's s formula, we obtain a variational formula for the annealed FP potential: famm ([ [[nx]/p) n²(x)) + onn) where
X2x²
((x) = max (b(p) + (1 - (o) log(o? 222) + +ro pog(111 /²)} + P
2p²² E [-1,1
(5)
The max is over probability vectors p = (p-1.Po,71 PI) satisfying Pl - p- = I, and h(()) =
-p-1 logp p_ po log - Pi log It is not difficult to check that 6(0) 0'(0) = 0. and (²(0) = (X² 1)/p². Hence when À- < AALLG = 1, fann is negative for all |a| S E for some = p) (Fig 1, Panels (a), (b)). This indicates that FP(D) is bounded for D < c(E)n. On the other hand, if X > 1, fanm > 0 over [- for some E > O. which indicates that FP(D) + do for slowly (Panel (c)). One can also look at the global behavior of fann, which we plot in Figure 1. Panel (b) represents a scenario where x = 0 is a local maximum separated from the two symmetric global maxima by barrier, while in panels (a) and (c), no such barrier exists.
D D,
Differences to prior physical hardness criteria Our FP criterion is conceptually similar to ideas that have appeared before in statistical physics, but there are a few key differences. While free energy barriers are typically thought of as an obstruction to algorithmic recovery, our criterion-due to its connection with | instead designed for the detection problem. As such, we do not expect the annealed FP to make sharp predictions about estimation error (e.g. MMSE) like approaches based on approximate message passing (AMP), e.g. [DMM09, LKZ15a, LKZ15b, DMK 16]. (For instance,
5

---

0.9.9.
A= 0.9, 0.4
1.3.pp
0.373
0.05
0.359
-0.13
0.04
0.125
0.07
-0.23
0.333
-0.39
1.00
3.00
0.21 3.0
130 075
100 075 550 nin nirs sip 1/50
0.309
150 0.7
022 625
035 1.52
[3]
(b)
(2)
Figure 1: The annealed FP potential, Eq. (5), for various value of X and p. Panel (a): A global maximum at æ = 0. Panel (b): Local maximum at x = separated from two global maxima by 'barrier'. Panel (c): A local minimum at 0.
Figure 1, Panel (b) wrongly predicts that estimation is 'possible but hard' for À - 0.9, p 0.4, when impossible [LM19].) On the other hand, one advantage of our
is in fact information-theoretieee criterion is that, by virtue of its connection LD in Section 4, it predicts the correct computational threshold for tensor PCA (matching the best known poly-time algorithms), whereas existing methods based AMP or free energy barriers capture different threshold [RM14, LML+ 17, BGJ20] (see also [WEM19, BCRT20) for other ways to "redeem" the physics approach).
One-sidedness of hardness criteria Finally, we note that the quantities || LD(D), FP(D) should be thought of primarily as lower bounds that imply/suggest impossibility hardness. If one of these quantities does not remain bounded as n - oc, it does not necessarily mean the problem is possible/tractable. We will revisit this issue again in Section 6, where conditional low-degree calculation will be used to prove hardness even though the standard LD blows up (akin to the conditional versions of |T that commonly used to prove e.g. [BMNN16, BMY+ 17, PWB16, PWBM18)..
lower bounds,
4 The Gaussian Additive Model
We will for now focus on particular class of estimation models, the called Gaussian additive models. The distribution P., describes an observation of the form
Y Xu
where A 2 the iggnal-tonoiie ratio, u ~ l is the signal interest drawn from some distribution on R.V. and 7 (0, IN) ) is standard Gaussian noise (independent from u). In recovery, the goal is to recover u, or more precisely to compute an estimator ((Y) that correlates with u. We note that in principle, could be absorbed into the norm of u, but it will be convenient for us to keep À explicit because some of our results will involve perturbing slightly. We focus on the hypothesis testing version of this question, where the goal is to distinguish a sample (6) from standard Gaussian vector.
Definition 4.1 (Gaussian Additive Model: Hypothesis Testing). Given N a positive integer, À 2 O, and μ distribution on R with all moments finite, let Z ~ NO Z) and testing in the Gaussian additive model consists of performing a simple hypothesis test between
μú, then hypothesis
Ho
Q : Y Z and
H1
Y Au + Z.
We are interested in understanding, as N = N, + oc, for which prior distributions SNR levels X = X,, is possible to computationally efficiently distinguish sample from IP from sample from Q (in the sense of strong or weak detection; see Definition 2.2). As in Section 2 use Pu to denote the distribution N ((u,, I), and write L., dF,.
μ., and
number of classical inference tasks are captured by the Gaussian additive model, and bounds on LD(D) are known for many of them [HKP* 17, KWB19, DKWB19, BBK BBK+ including matrix and tensor PCA.
Example 4.2 (Matrix and Tensor PCA). In the matrix PCA case, we take N = n² and u = x2 where x for instance drawn with i.i.d. coordinates from some prior poo In the tensor case, take N n² and tr Sp, with J drawn uniformly from the sphere Sn-1
The detection and recovery thresholds the same in this

---

FP-LD Equivalence The following two theorems show that in the Gaussian additive model, FP and LD are equivalent up to logarithmic factors in D and + E factors in Recall the notation (D) and FP(D) from (1) and (3), here also with a dependency on the SNR X.
Theorem 4.3 (FP-hard implies LD-hard), Assume the Gaussian additive model (Definition 4. and suppose |uu|2 s M for all E supp(u). for some M 0. Then for any X 2 0 and any odd integer
D21, 1, LD(D, A) & FP) + +e D, where D == D (2 + log + X))
We give the proof in the supplement. We are primarily interested in the regime D = (1), where we have shown that LD can only exceed FP by an additive o(1) term. We have lost logarithmic factors in passing from D to D. For many applications, these log factors are not issue because (in the "hard" regime) FP is bounded for some D) = NZ((1 while X, M are polynomial in N.
Theorem 4.4 (LD-hard implies FP-hard). Assume the Gaussian additive model (Definition 4.1). For all E (0, there exists Do = Do(e)= > O such that for any X 2 0 and any even integer D 2 Do. if
LD(D, (1 E)A) (1+ ((eD) (eD))
then
FP(D,A) S LD(D, (1+))
(7)
The proof, together with proofs for various corollaries, can be found in the supplementary material. In the asymptotic regime of primary interest, we have the following consequence.
Corollary 4.5. Fix any constant e' > and suppose D = Da = An N Nn. and p Un are such that D is an even integer, D = (1),, and LD(D, (1 + e'AA) = 0(). Then FP(D, A) S
LD(D, (1 + =)) + (1).
Remark 4.6. Above, we have taken the liberty to assume D has particular parity for convenience.
Since FP and LD are both monotone in D, one can readily deduce similar results for all integers D.
5 FP-Hard Implies MCMC-Hard
In this section we show that in the Gaussian additive model, if FP is uniformly bounded then a natural class of local Markov chain Monte Carlo (MCMC) methods fail recover the planted signal. Combining this with the results of the previous section, we also find that low-degree hardness, an impossibility result for polynomial ("algebraic") methods, implies MCMC-hardness, which is the failure of "geometric" methods. To the best of our knowledge this is the first time such a direct implication is established for any planted model. Note also that such a result is interesting as low- degree hardness is in principle an impossibility result for detection, while UCMCChardnesd is failure of some MCMC methods to perform estimation. We remark that the result of this section is similar in spirit to [BAJ18], which relates version of annealed FP to the spectral gap for Langevin dynamics (albeit in a setting with no planted solution).
We again restrict our attention to the additive Gaussian model, now with the additional assumption that the prior μ is uniform some finite set S C R. with transitive symmetry, defined as follows.
Definition 5.1. We say S C N has transitive symmetry if for any u, v E S there exists an orthogonal matrix R E O(N) such that Ru and RS = S.
The assumption that S finite not too restrictive because one can approximate any continuous prior to arbitrary accuracy by a discrete set (see the supplementary material for more details on that). Note that transitive symmetry implies that every u E S has the same 2-norm. Without loss of generality we will assume this 2-norm is I, i.e., S is a subset of the unit sphere S.V
Given an observation Y = Au + Z from the Gaussian additive model (with uniform finite, vranstive-symmett set 5 C N --N-),, -1), consider the associated Gibbs measure Va on S defined by
Za exp(-3H(())
(8)
where B 2 0 an inverse-temperature parameter (i.e., 1/3 is the Cmmperatur)).H(1) = ( Y) the Hamiltonian, and Z3 Eves exp(-3X (v)) is the partition function. When (the "Bayesian temperature"), ") the Gibbs measure Vg3 is precisely the posterior distribution for the signal given the observation Y Au + Z.
We consider an arbitrary Markov chain Xo, X1, X2,... on state space S with stationary distribution Vg (for some 8), i.c., if X, ~ Vg then X Vg. We will assume worst-case initial state, which
7

---

may depend adversarially on Y. We are interested in hitting time lower bounds, showing that such a Markov chain will take many steps before finding a "good" state that is close the true signal u.
The core idea of our argument to establish a free energy barrier, that is, subset B C S of small Gibbs mass that separates the initial state from the "good" states. Such barrier is well-known to imply a lower bound for the hitting time of the "good" states using conductance; see e-g. [LP17, Theorem 7.4]. This is formalized in the proposition below.
Proposition 5.2 (Free Energy Barrier Implies Hitting Time Lower Bound). Suppose Xo: X1, X is a Markov chain on a finite state space S, with some stationary distribution Let A and B be two disjoint subsets of S and define the hitting time TB == inf't E N. X, E B}. If the initial state Xo is drawn from the conditional distribution v A, then any t E N, Pr(Tn 1 S t. v(B) In particular.
v(A)
for any 1 N there exists U E A S.J. if Xn v deterministically then Pr(Tn () S L. r(B)
v(A).
We will need to impose some "locality" on our Markov chain so that it cannot jump from A to good state without first visiting B. We say Markov chain on a finite state space S _ S is A-local if for every possible transition v - v' we have ||v r'Il2 S A. We note that the use of local Markov chains well motivated and preferred in theory and practice for the, in principle, low computation time for implementing single step. For this reason, in most (discrete-state) cases the locality parameter A > 0 tuned so that the A neiighoordooo of each point at most of polynomial size; see e.g. [Jer92, BWZ20, GZ19, CMZ22].
We now state the core result of this section, followed by various corollaries. (See the supplementary material for a slightly more general result and for the proof). The proof is based on an free energy barrier argument used in [BGJ20] which relies on rotational invariance of the Gaussian distribution.
Theorem 5.3 (FP-Hard Implies Free Energy Barrier). Let μ be the uniform measure on S, where S C S.N-3 is finite, transitive-symmetre set. The following holds for any E (0, 1/2), D 2 2, 2 O, and 3 2 0. Fix a ground-trute signal u E S and let Y = Au + Z with Z ~ NO, IN). Define (u,, v)] S 8) and B = {u E S : (u, u) E (6, (1 } over Z, the Gibbs measure (8) associated to Y satisfies that
8 = 8(D) as in (3). Let A {o E S
With probability at least - e c
PB(B)
(2 (2- FP + log 2g 2))
1-2s
e= where x = V 2+c
S 2 25(A)
As mentioned above, one particularly natural choice of 3 is the Bayesian temperature À (which corresponds to sampling from the posterior distribution). By combining Proposition 5.2 and Theo- rem 5.3 we conclude that FP-hard implies that the hitting time grows exponential with D, which we simply refer to as "MCMC-hard", Combinining now this result with the FP and LD equivalence part described in Corollary 4.5, we conclude also that LD-hard implies MCMC-hard.
Corollary 5.4 (FP-Hard (and LD-hard) Implies Hitting Time Lower Bound). In the setting of Theorem 5.3, suppose Xo, X1, 1, X2,... ....... a Allocal Markov chain with state space S and stationary distribution Va. for some A < e6. Define the hitting time 7 == inf{t E N : X,) > 8). With probabiliiyy at least D over Z., there exists a state v E A such that for the initialization Xo = v, with probability at least 1 =DD2 over the Markov chain.
D/2
T
+ Pogg+ A)) 1-2
2 (2
If furthermore D Dn is sequence with D w(1 such that D + log is an even integer LD(D + log (1 e) S B for a constant B O, then there is a constant C C(B, c) > 0 for
which T 2 E
We note that Corollary 5.4 applies for all A < =D()). For various models of interest, we note that the range A < cD(D) for the locality parameter A contains the "reasonable" range of values where the A d-neighborhoods are of polynomial size. For example, let us focus on the stulest tensor PCA setting with a Rademacher signal and even tensor power, that is S = {u = 2 x e (-n=",n=>)")) Then for any D > 0 and any E > 0, we have c5(D) = a(n -P) and therefore the E5( -eighbbooooo of any point u 022p E 5, contains all (1) points u = y E S where y has any Hamming distance of /n) from x. Remark 5.5. We note that the original work of [BGJ20], on which the proof of Theorem 5.3 is based, showed failure of MCMC methods in strictly larger (by a power of n) range of X than the
8

---

low-degree- regime for the tensor PCA problem. In contrast, our MCMC lower bound uses the same argument but matches the low-degree threshold (at the Bayesian temperature). This is because [BGJ20] only considers temperatures that are well above the Bayesian one: in their notation, their result is for constant / whereas the Bayesian grows with n.
6 Sparse Linear Regression
In this section we prove sharp low-degree lower bounds for the hypothesis testing version of a classical inference problem: sparse linear regression. This is significant for number of reasons: (i) we uncover a new computational phase transition in sparse regression, (ii) our proof involves upper-bounding L.D in terms of FP, illustrating that FP-to-LD connection be achieved outside the Gaussian additive model, and (iii) the proof requires a first-of-its-kine conditional low-degree calculation which seems difficult to carry out directly without using FP, illustrating that FP can be powerful tool for proving low-degree lower bounds. We consider the following detection task.
Definition 6.1 (Sparse Linear Regression: Hypothesis Testing). Given a sample size m E N, feature size E N. sparsity level k E N with & S and noise level > O, we consider hypothesis testing between the following two distributions over (X, Y) E [Rmx* x X I!"..
T generates a pair (X, where both X and Y have i..dd N( 1) entries.
P generates a pair (_,, Y) as follows. First X is drawn with i.i.d (0, 1) entries. Then, for planted signal {0, 1)" drawn uniformly from all binary vectors of sparsity exactly k, and independent noise W ~ ~N(00, o Im), set Y (k + od) 1 + W). This normalization ensures !o,.
In the following result, we provide rigorous "low-degree evidence" (and a matching upper bound) for the precise threshold separating the "easy" and "hard" regimes.
Theorem 6.2. For 0 E (0, 1), define
(L)(O) 2(--0)
1+v0 110 < 0 + 0 $
(9)
Consider sparse linear regression (Definition 1) the following scaling regime: for fixed constants 0 E (0, 1) and R > 0, take + 00 with k = n 90(1) 0² =ok),, and m = (1 o()) log(n/k) kk).
o(k),
(a) (Hard regime) If R < RL)(() then no (kgree-o(k) polynomial f [mm(x+1) + achieves the following notion of " strong separation".
maxx [aaolf Vare[fl} o (|Eel EglfIl).
(10)
(b) (Easy regime) If R (L) then there is polynomial-time algorithm for strong detection between P and Q (see Definition 2.2).
In line with existing low-degree lower bounds in the literature, the notion of strong separation ruled out in part (a) is natural notion of success for polynomial-basee tests: by Chebyshev's inequality, (10) implies that strong detection is possible by thresholding f. Part (a) is interpreted as evidence that when R RLD (0), strong detection requires runtime exp($2(k)). This is tight, matching the runtime of a brute-force search algorithm, which succeeds for any constants 0 E (0, 1) and R >>> 0 (i.e., the caammmaiioonthoretiicaaee possible our regime) [RX721]]
problem is always
The algorithm that gives the matching upper bound in part (b) is fairly simple but somewhat subtle: letting X, denote the jth column of X, the idea is to count the number of indices [r|] for which (X,, / ||z exceeds a particular (carefully chosen) threshold, and then threshold this count.
We note that prior work has also considered the related task of recovering u, given (X,Y) ~ (e.g. [Wai09, DT10, GZ22, RXZ19, RXZ21J). Our result gives evidence that the existing algorithms for recovery cannot be improved in the regime 0 J O. See the supplement for further discussion.
Proof techniques and beyond sparse regression Proving the sharp low-degree lower bound in the regime < 1/4 requires a conditional low-degree calculation: instead of bounding LDD for testing P versus Q. we bound LD for testing the conditional distribution PIA versus Q for some

---

Highh-robbbbilig event A. This is necessary because the standard LD blows up at a sub-optimal threshold due rare "bad" event under I.. Conditioning arguments of this type are common for information-theoreti lower bounds (see e.g. [BMNN16, BMV+ 17, PWB16, PWBM18J). but this (to our knowledge) the first instance where conditioning has been needed for a low-degree lower bound. We note that [Arp21] gave low-degree lower bounds for sparse regression by analyzing the standard (non-conditioned) LD, and our result improves the threshold when 0 < 1/4 via conditioning.
The standard approach bounding LD involves direct moment calculations (see e.g. Section 2.4 of 18), but it seems difficult to carry out our conditional low-degree calculation by this approach. Instead, we prove that the conditional LD can be upper-bounded by the corresponding conditional FP, which is more tractable to bound directly. This illustrates that FP can be powerful tool for proving low-degree lower bounds that may otherwise be out of reach. As we discuss the supplement, the FP-to-LD connection we establish here holds for a broad class of problems with planted sparse signals, including planted clique, planted dense subgraph, and any sparse generalized linear model.
7 Conclusion
We have introduced the Franz-Parisi criterion and have shown that it implies lower bounds against local MCMC algorithms and is equivalent low-degree hardness in Gaussian additive models. We have also used the FP criterion as a tool to prove new low-degree lower bounds for sparse regression. This is first step in relating notions of computational intractability based on free energy potentials to lower bounds within restricted models of computation, such as the sum-of- squares hierarchy. A clear question in the wake of our work is whether similar connections can be drawn for broader class of planted models. In the supplementary material, we demonstrate that this cannot be done in a straightforward way, by building counterexamples (namely, certain simple mixtures over Boolean product measures) where the Franz-Parisi criterion is not consistent with computational intractability. Nonetheless, given the impressive track-record of accuracy of free-energy based computational threshold predictions, we believe this to be a shortcoming of our specific criterion, and the development of one for a more general class of problems is a fascinating direction for future research.
Acknowledgments and Disclosure of Funding
AEA: Part of this work was done while this author was supported by the Richard M. Karp Fellowship at the Simons Institute for the Theory of Computing (Program on Probability. Geometry and Compu- tation in High Dimensions). This author is grateful Florent Krzakala for introducing him to the work of Franz and Parisi.
SBH: Parts of this work were done while this author was supported by Microsoft Research PhD Fellowship, by Miller Postdoctoral Fellowship, and by the Microsoft Fellowship the Simons Institute for the Theory of Computing.
ASW: Part of this work was done at Georgia Tech supported by NSF grants CCF-2007443 and CCF-2106444. Part of this work was done while visiting the Simons Institute for the Theory of Computing. Part of this work was done while with the Courant Institute at NYU, partially supported by NSF grant DMS-1712730 and by the Simons Collaboration
Algorithms and Geometry.
IZ: Supported by the Simons-NSt grant DMS-2031 18833 on the Theoretical Foundations of Deep Learning and the Vannevar Bush Faculty Fellowship ONR-N00014-20- 1-2826. Part of this work was done while visiting the Simons Institute for the Theory of Computing. Part of this work was done while with the Center for Data Science at NYU, supported by a Moore-Sloan CDS postdoctoral fellowship.
The authors thank Cris Moore and the Santa Fe Institute for hosting the 2018 "Santa Fe Workshop on Limits to Inference in Networks and Noisy Data," where the initial ideas in this paper were formulated. The authors thank Aukosh Jagannath and anonymous reviewers for helpful comments on an earlier version of this work.
References
[AKJ20] Ahmed El Alaoui, Florent Krzakala, and Michael Jordan. Fundamental limits of detection in the spiked wigner model. The Annals of Statistics, 48(2):863-885, 2020.
10

---

[Arp21] Gabriel Arpino. Computational hardness of sparse high-dimensional linear regression. MSc Thesis, ETH Zürich, 2021.
[BAJ18] Gérard Ben Arous and Aukosh Jagannath. Spectral gap estimates in mean field spin glasses. Communications in Mathematical Physics, (61(1): 2018.
[BB20] Matthew Brennan and Guy Bresler. Reducibility and statistical cnnisticalcompuuaaiionnlll gaps from secret leakage. In Conference on Learning Theory, pages 648-847. PMLR, 2020.
[BBH+20] Matthew Brennan, Guy Bresler, Samuel B Hopkins, Jerry Li, and Tselil Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint NeKi:2009.06100. 2020.
[BBK*21] Afonso Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alexander Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities random graphs. In Conference on Learning Theory, pages $10-473. PMLR, 2021.
[BCRT20] Giulio Biroli, Chiara Cammarota, and Federico Ricci-Tersenghi How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA. Journal of Physics A: Mathematical and Theoretical, 53(17):174003, 2020.
[BGJ20] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor PCA. The Annals of Probability, 48(4):2052 2020.
[BGNII] Florent Senaych-Georges and Raj Rao Nadakuditi. The eigenvalues and cigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics, 227(():494 521, 2011.
[BH21] Guy Bresler and Brice Huang. The algorithmic phase transition of random k-SAT for low degree polynomials. In 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 298-309 IEEE, 2021.
(BHK+19) Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2):687-735, 2019.
[BMNN66] Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli. Information- theoretic thresholds for community detection in sparse networks. In Conference Learning Theory, pages 383-416. PMLR, 2016.
[MV++1 17] Jess Banks, Cristopher Moore, Roman Vershynin, Nicolas Verzelen, and Jiaming Xu. informationnthhoreet bounds and phase transitions in clustering, sparse PCA, and submatrix localization. In IEEE International Symposium on Information Theory (ISIT), pages 1131-1141. IEEE, 2017.
[BPW18] Afonso S Bandeira, Amelia Perry, and Alexander S Wein. Notes on computational- to-statistical gaps: predictions using statistical physies. Portugaliae Mathematica, 75(2):159-186, 2018.
[BWZ20] Gérard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse PCA. In Conference on Learning Theory, pages 479-482. PMLR, 2020.
[CL19] Hye Won Chung and Ji Oon Lee. Weak detection of signal in the spiked wigner model. In International Conference on Machine Learning, pages 1233-1241. PMLR, 2019. PM...
(CM7222 Zongchen Chen, Elchanan Mossel, and Ilias Zadik. Almost-linear planted cliques elude the metropolis process. arXiv preprint arXiv:2204.01911, 2022.
[DKMZ.11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymp- totic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066100 106, 2011.
11

---

[DKWB19] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Subexponential time algorithms for sparse PCA. arXiv preprint 13X.v.190..11635 2019.
[DMK*16] Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, Lenka Zdeborová, et al. Mutual information for symmetric rank-one matrix estimation: proof of the replica formula. Advances in Neural Information Processing Systems, 29, 2016.
[DMM09] David L Donoho, Arian Maleki, and Andrea Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914- 18919, 2009.
[DT10] David Donoho and Jared Tanner. Counting the faces of caadoomlyprrjectedd hypercuhes and orthants, with applications. Discrete & computational geometry, 43(3):522-555 2010.
[FP95] Silvio Franz and Giorgio Parisi. Recipes for metastable states in spin glasses. Journal 1995.
de Physique I,
[Gam21] David Gamamik. The overlap gap property: A topological barrier optimizing random structures. Proceedings of the National Academy of Sciences, 118(41), 2021.
[GJW20] David Gamarnik, Aukosh Jagannath, and Alexander S Wein. Low-degree hardness of random optimization problems. In 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 131-140. IEEE, 2020.
[GS17] David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. Annals of Probability, 45(4):2333 2017.
[GZ19] David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property, 2019.
[G722] David Gamarnik and Ilias Zadik. Sparse high-dimensional linear regression. Estimating squared error and a phase transition. The Annals of Statistics, 50(2):880-903, 2022.
[HKP* 17] Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 730-731. IEEE, 2017.
[Hop18] Samuel Hopkins. Statistical Inference and the Sum of Squares Method. PhD thesis, Cornell University, 2018.
[HS17] Samuel B Hopkins and David Steurer. Bayesian estimation from few samples: commu- nity detection and related problems. arXiv preprint 1710:0000000264 2017.
[Jer92] Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347-359, 1992.
[KWB19] Dmitriy Kunisky, Alexander Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv: 2019.
[LKZ15a] Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. MMSE of probabilistic low- rank matrix estimation: Universality with respect the output channel. In 2015 53rd Anmual Allerton Conference on Communication, Control, and Computing (Allerton), pages 680-687. IEEE, 2015.
[LKZ15b] Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Phase transitions in sparse PCA. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 1635-1639. IEEE, 2015.
[LM199] Mare Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation. Probability Theory and Related Fields, 173(3):859-99 9299999999000 2019.
12

---

[LML* 17] Thibault Lesieur, Léo Miolane, Mare Lelarge, Florent Krzakala, and Lenka Zdeborová. Statistical and computational phase transitions in spiked tensor estimation. 2017 IEEE International Symposium on Information Theory (ISIT), pages 51 1-515. IEEE, 2017.
[LP17] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[MM09] Marc Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
[MRZ15] Andrea Montanari, Daniel Reichman, and Ofer Zeitouni. On the limitation of spectral methods: From the gaussian hidden clique problem to rank-one perturbations of gaussian tensors. Advances in Neural Information Processing Systems, 28, 2015.
[PWB16] Amelia Perry, Alexander Wein, and Afonso Bandeira. Statistical limits of spiked tensor models. arXiv preprint arXiv: 1612.07728, 2016.
[PWBM18] Amelia Perry, Alexander Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub-optimality of PCA I: Spiked random matrix models. The Annals of Statistics, 46(5):2416-245 2451, 2018.
[RM14] Emile Richard and Andrea Montanari. A statistical model for tensor PCA. In Z. Ghahra- mani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[RSS19] Prasad Raghavendra, Tselil Schramm, and David Steurer. High-dimensional estimation via aum-of-squares proofs. ICM 2018, 2019.
[RXZ199] Galen Reeves, Jiaming Xu, and Ilias Zadik. All-or-nothing phenomena: From single- letter to high dimensions. In 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 654-658. IEEE, 2019.
[RX721] Galen Reeves, Jiaming Xu, and Ilias 7adik. The all-or-nothing phenomenon in sparse linear regression. Mathematical Statistics and Learning, 3(3):259-3133 2021.
[Wai09] Martin J Wainwright. Information-theerriicc limits on sparsity recovery in the high- dimensional and noisy setting. IEEE transactions on information theory, 55(12):5728- 5741, 2009.
[Wei22] Alexander S Wein. Optimal low-degree hardness of maximum independent set. Mathe- matical Statistics and Learning, 4(3):221-251, 2022.
[WEM19] Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi hierarchy and tensor PCA. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1446-1468. IEEE, 2019.
[ZK16a] L. Zdeborová and F. Krzakala. Statistical physics of inference: Thresholds and algo- rithms. Advances in Phyisics, 65(5), 2016.
[ZK16b] Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5):453 552, 2016.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [N/A] Our work
is purely theoretical and has no socictal impacts.
13

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes] In the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yG1bMBH2jXa", "reviewer": "Reviewer_sVoz", "summary": "The authors consider the computational hardness of hypothesis testing in planted models.\nConsider a \"null\" probability distribution and a \"planted\" distribution, i.e. a distribution depending on a hidden random signal with a given prior distribution.\nGiven a sample from one of the two distributions, how computationally hard is it to decide from which distribution it comes from?\n\nThe authors introduce a novel criterion, the Franz-Parisi (FP) criterion, that depends on local geometric properties of the planted/null distributions, and they define a related notion of FP hardness.\nThey show that FP hardness is related to an already established kind of computational hardness, namely low-degree (LD) hardness, in Gaussian additive models and some planted sparse models.\nIn particular, in the former class of models they prove that FP hardness is equivalent (up to technical hypothesis) to low-degree hardness, while in the latter they prove that FP hardness implies LD hardness.\nThus, they establish a link between geometrical properties of the planted/null distributions and computational hardness.\n\nIn Gaussian additive models, the authors prove that FP-hardness implies failure of local MCMC algorithms, in the sense that FP-hardness implies the existence of large free-energy barriers in the landscape explored by MCMC. \nThese prevent MCMC from fully exploring the configuration space in polynomial time.\nTogether with the LD-FP equivalence, this implies that low-degree hardness implies failure of local MCMC algorithms.\n\nThe authors then focus on the sparse linear regression model, where they provide new low-degree computational lower bounds using a proof technique that crucially relies on the new FP criterion.", "questions": "I am curious on how the FP hardness criterion relates to overlap gap properties and their consequences: do the authors have some intuition that could be added to the manuscript?\n\nIn the manuscript the authors hint at some relationship between the hypothesis testing setting they study and the (to me) more common estimation (retrieval of the planted signal) setting: is there some more precise relationship between computational and theoretical thresholds of the two settings? \n", "limitations": "The authors clearly assess the limitations of their results in the supplementary materials, where they provide counterexamples that suggest that their results do not point towards a complete equivalence between low-degree hardness and FP hardness.\nThese limitations do not undermine the validity or significance of their results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\n\nThe papers contains several novel results: the definition of the FP criterion, the study of the relationship of FP hardness with LD hardness and MCMC hardness in different models and new bounds for sparse linear regression.\nMoreover, the proof of the bounds relies on the FP criterion, which has to be considered not only as a conceptual item, but also as a practical tool for proofs.\nThe authors clearly and convincingly state the relationship of their results with existing literature in many remarks both in the main text and in the supplementary materials.\n\nI am not familiar with the literature enough to assess whether all relevant work has been adequately cited.\n\n### Quality\n\nThe authors clearly state the assumptions underlying their results, and provide seemingly correct proofs.\nI did not check the details of the proofs.\n\n### Clarity\n\nThe manuscript is overall clearly and nicely written, and together with the extensive supplementary material provides enough information for the expert reader to be able to fully assess correctness and to reproduce the proofs.\n\n### Significance\n\nI believe that the results presented in this manuscript related to FP-hardness are significant. \nLinking algorithmic hardness with statistical-physics-like properties of computational problems is a long-standing research effort. As far as my knowledge goes, it is still not completely clear how geometric properties of free-energy landscapes, such as replica symmetry breaking, relate to computational hardness, and this seems a promising step.\n\nI am not qualified enough to properly assess the significance of the results on sparse regression, and on the novel proof technique based on the FP-criterion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "izEILp_j2iZ", "reviewer": "Reviewer_UuKm", "summary": "The author(s) introduce a new \"Franz-Parisi criterion\" for predicting computational hardness in certain types of hypothesis testing problems, where the goal is to distinguish a mixture model with a random planted signal u from a null reference distribution. The criterion is, on one hand, a restriction of the second moment of the likelihood-ratio statistic to pairs of planted signals u,v having \"typical\" overlap under their prior. On the other hand, it is way of quantifying the growth/decay behavior of an annealed approximation to the Franz-Parisi potential locally around the overlap delta = 0. The authors posit that if this FP-criterion, when restricted to a range of overlaps (-delta,delta) having probability 1-e^{-D_n} for D_n growing slowly with n, is O(1) or 1+o(1), then this provides evidence for computational hardness of strong detection or weak detection respectively in the testing problem.\n\nTo support this claim, a number of interesting results are shown rigorously about this criterion:\n(1) In a Gaussian additive model which includes spiked matrix and spiked tensor problems with Gaussian noise, it is shown that the FP criterion may be upper and lower bounded by the low-degree likelihood-ratio, up to the degree D_n modulo logarithmic factors. In certain relevant asymptotic regimes, this implies that FP's indication of hardness is equivalent to the low-degree method (which is believed to characterize the sharp threshold for hardness in many of these problems), and it establishes a new connection between the low-degree method and more geometric notions of overlap.\n(2) Under an additional symmetry assumption for the Gaussian additive model, it is shown that FP-hardness formally implies a free energy barrier in the posterior distribution of the planted signal, which in turn implies a hitting time lower bound for MCMC algorithms having sufficiently \"local\" moves. Coupled with the above result, this provides a new method for showing hardness results for local MCMC algorithms using the low-degree approach.\n(3) One direction of the above equivalence, that FP-hardness implies low-degree hardness, is shown also for a different class of planted sparse models satisfying a certain symmetry of the planted distribution. This implication is used to establish low-degree-hardness of detection in a sparse linear regression model, up to an sparsity-undersampling threshold curve that appears to be sharp in the studied regime, by bounding a conditional low-degree second-moment via the corresponding conditional FP-criterion.\n\nOutside of the above settings, a discussion of some insightful counterexamples is also provided, where the FP criterion (or overlap-gap-based criteria in general) does not seem to accurately predict hardness of the testing problem.", "questions": "I might suggest to the author(s) to include some more of the discussion in Section 1.3 of the supplement (on the Franz-Parisi potential) into the main text, if this is possible. Currently I find Remark 3.3 a bit hard to understand (i.e. what is the relation between the FP potential and a restriction of the partition function?). Without this, it's hard to grasp the intuition behind the main Definition 3.2, as well as how the local/global properties of Figure 1 should be interpreted in the discussions on page 5.\n\nA few typos:\np2 l86, \"its precisely domain\"\np3 l121, \"computational\" is repeated\np5 l189, \"local minimum separated from\", minimum -> maximum", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find the paper to be very interesting, and am strongly supportive of its publication in NeurIPS. Some of the insights are:\n\n(1) An annealed approximation to the Franz-Parisi free energy admits a second-moment type interpretation, and connects to the classical second-moment method in testing.\n(2) A formal connection can be shown between restricting the geometric overlap and restricting the polynomial degree in the second-moment method. This seems to be particularly surprising in the planted sparse model setting of Section 3 where there is no explicit form for the low-degree likelihood ratio in terms of the overlap, and where the implication is shown from a symmetry condition alone.\n(3) The connection can be used in both directions, to provide geometric approaches to analyzing the (conditional) low-degree likelihood ratio statistic, and to provide algebraic methods of analyzing the overlap landscape. It's helpful to have these connections elucidated at the level of generality of this current work, even if versions of these implications were used implicitly before in more specific models.\n\nI guess the main weakness seems to be that it's unclear whether this FP-criterion fully captures the \"physics intuition\" for hardness in these types of problems, as (a) it is defined in terms of an annealed potential, and it's a bit unclear (at least to me) when this should have the same behavior as the replica-symmetric potential or the true quenched potential, and (b) it pertains to the properties of this potential only locally near 0, rather than to the entire overlap landscape. But I think these issues are adequately discussed in Section 4, and in my opinion they provide food for thought and do not detract much from the strengths of the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YhoYDLaSsd", "reviewer": "Reviewer_AiU6", "summary": "## Summary of paper:\n\nThis work deals with proving algorithmic hardness of a class of statistical problems against local MCMC algorithms. To do this, they introduce a new algebraic quantity called the Franz-Parisi criterion (FP) and study it. For many learning problems, there is a phenomenon called the information-computation tradeoff where there is a gap between the information-theoretic sample complexity and the minimum sample complexity needed for polynomial time algorithms, e.g., in Sparse PCA, there is almost a quadratic gap. There have been many works trying to characterize this phenomenon by showing lower bounds against efficient algorithms. Techniques include reductions from conjectured hard problems (such as planted clique from graph theory), showing that the geometry landscape of the solution space have barriers in them (borrowing ideas from statistical physics), or showing hardness against powerful families of algorithms (such as the Sum-of-Squares hierarchy). In this work, they show that for the Gaussian additive noise model, under a strong symmetry assumptions, the so-called low-degree hardness (used before in the literature) implies failure of local MCMC algorithms. Their proof goes via this new FP criterion they introduce. They also show another usecase of this criterion, namely in obtaining tradeoffs for sparse regression. They finally study limitations of the FP criterion and show that it fails to predict the right threshold for simple mixtures of boolean distributions.\n\n## Technical summary:\n\nConsider the problem of hypothesis testing of Gaussian additive models, where null distribution is iid Gaussian and the alternative distribution has a planted spike sampled from a prior, e.g. tensor PCA. In this setting, this work shows that two hardness approaches are related. In particular, they show that a hardness hypothesis called low-degree hardness implies hardness of local MCMC algorithms.\n- Low-degree hardness (LD) (definition 2.3) is a notion of hardness against hypothesis testing algorithms that utilize low-degree polynomials. Stemming from the analysis of the Sum of Squares family of algorithms, it is a simple and very effective technique to predict computational tradeoffs, however they do not say much about hardness of the Sum of Squares algorithms themselves. The hypothesis basically says that, under favorable conditions such as symmetry and noise robustness, if the projection of the likelihood ratio test (from the Neyman-Pearson lemma) to low-degree polynomials is bounded, then the problem is hard.\n- Borrowing ideas from statistical physics, hardness of local algorithms can be obtained by exhibiting free-energy barriers in the solution landscape by approximating the free energy of a posterior distribution when we restrict the overlap with the ground truth. The relevant quantity they borrow inspiration from here is the Franz-Parisi potential, which when massaged appropriately via the Jensen's inequality, gives rise to a new quantity that's called the annealed potential. This is further modified to a notion this work introduces and terms the \"Franz-Parisi criterion\" (definition 3.2). This work shows that for additive Gaussian models, to show hardness of local alogorithms, it's enough to bound the FP criterion.\n\nBoth these approaches can be thought of as trying to bound the (computationally-bounded) Neyman-Pearson likelihood ratio and use it to predict computational barriers. This intuition is made formal in this work for Gaussian additive models. Main assumptions are:\n- The null distribution has iid Gaussian entries\n- The prior on the signal has sufficient symmetry, which necessiates among other things, thht every signal has the same L2-norm\n\nUnder these assumptions, LD hardness implies FP hardness (theorem 4.4, converse is also true) which in turn implies a free-energy barrier (theorem 5.3) and this in turn implies hardness against local MCMC algorithms (variants known in the literature before). As the authors point out, both assumptions seem crucial and not easy to be relaxed.\n\nAs another application of their criterion, the authors obtain computational phase transitions for certain specific parameter regimes of the sparse regression problem. In this setting, they found that their new criterion is easier to analyze than the low-degree ratio. However, it's still quite nontrivial and requires conditioning on a high-probability good event (definition 6.3 in the appendix) amidst tedious calculations.\n\nLimits of this criterion are also explored, the authors show that it fails in several aspects. For example, it doesn't predict sharp thresholds for the estimation/recovery problem (compared to hypothesis testing). Moreover, it fails in boolean settings (as the authors point out, the issue is not booleanness, but something more inherent) and it also fails for the planted subgraph problem, where the LD criterion works instead. Therefore, this criterion should be considered as a means to an end in this research direction.", "questions": "A few questions were raised above.\n\n## Other questions/comments:\n\n1. Just to clarify, can the sample size in theorem 6.2, i.e. m = (1 + o(1))Rk log(n/k), be replaced by m <= (1 + o(1))Rk log(n/k)? It seems a bit unusual to set the sample size to be something specific\n\n2. L86: \"precisely\" -> \"precise\"\n\n3. L166: the partition function is not defined, I believe the first place it's defined is L271.\n\n4. In the last paragraph of page 7 of the appendix, \"says bounded\" -> \"stays bounded\"", "limitations": "This is primarily a theoretical paper. Limitations of the results are sufficiently addressed, including the various assumptions and conceptual limitations (section 4 of the appendix). Negative societal impacts are not discussed, but I do not think there is any.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Summary of evaluation:\n\nI was not able to verify the math in this timeframe. However, the results seem plausible, since the tradeoffs obtained here for various problems are expected to be true. The contributions in this work are conceptually interesting and raise potential directions for further research. However, the actual results obtained seem a bit weak since they require a lot of assumptions. Also, they are not readily applicable to other problems due to the difficulty of the calculations involved. Moreover, the proofs are highly technical and will take quite a bit of time to absorb for even experts in either statistical physics or statistics, let alone the average NeurIPS reader, which leads to concerns regarding the fit.\n\n## Strengths:\n\n1. Lower bounds against computational methods have long been studied from different perspectives, especially for average-case problems where NP-hardness results are not known. Recently, researchers have been trying to build bridges between different perspectives, e.g. Brennan et al. 2021 show that SQ algorithms and low-degree tests are equal power under some assumptions. Likewise, this work attempts to bridge the gap between statistical physics approaches and low degree tests.\n\n2. Although the LD test became useful for its ease-of-use in predicting computational thresholds, the authors state that it's hard to apply it to certain parameter regimes of sparse regression. They overcome this with their new FP criterion.\n\n3. The FP criterion recovers predicted thresholds for the spiked Wigner model of PCA. The example worked out is very helpful to understand it.\n\n4. Formalizing all of the intuition this work brings about is nontrivial. The technical mastery in this work is commendable.\n\n## Weaknesses:\n\n1. The main weakness is that even if the FP criterion is a potentially useful criterion, it still seems quite hard to use it for other problems of interest. For example, even for the application to planted sparse models, the authors have to spend significant effort to bound the FP criterion, such as conditioning on a high probability event (definition 6.3). So, the usefulness of this criterion itself for other problems seems rather limited and technically tedious even for experts.\n\n2. Based on my understanding, the transitive symmetry property seems to break when we consider sparse PCA where the sparsity is *at most* k, instead of *exactly* k. Therefore, the results here do not apply for this simple variant of sparse PCA since transitive symmetry seems to be a rather strong assumption. Could the authors clarify this?\n\n3. Although the results are intriguing, my main concern is regarding the fit of this paper for this conference. Due to its length and non-triviality, It may be better suited for a journal or a more theory-focused conference.\n\n4. For someone more from an ML background and not from a statistical physics background, it can be hard/impossible to follow section 1.3 in the appendix. Despite this, I understand that it is not easy to have a self-contained intro to the statistical physics terms used here. I'd suggest that a good reference should be cited to learn these better for the interested reader.\n\n5. In the end of page 14 of the appendix, it's stated that very few tools are available to prove the success of MCMC methods for inference. If that's the case, then why are hardness against MCMC methods a good proxy for computational hardness?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept