An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
Authors: Siyu Chen
Theodor Misiakiewicz
Ilias Zadik
Peiyuan Zhang
Venue: NeurIPS 2025 oral ()
Keywords: statistical query
Franz-Parisi criterion
computational hardness in statistical inference
Primary area: theory
TL;DR: We propose a refined Franz-Parisi criterion, and show that it is equivalent to Statistical Query lower bounds under a mild, verifiable assumption satisfied by a broad class of statistical models.

Abstract: Bandeira et al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on an annealed version of the celebrated Franz-Parisi potential from statistical physics, was shown to be equivalent to low-degree polynomial (LDP) lower bounds for Gaussian additive models, thereby connecting two distinct approaches to understanding the computational hardness in statistical inference. 
In this paper, we propose a refined FP criterion that aims to better capture the geometric ``overlap" structure of statistical models. Our main result establishes that this optimized FP criterion is equivalent to Statistical Query (SQ) lower bounds---another foundational framework in computational complexity of statistical inference.  Crucially, this equivalence holds under a mild, verifiable assumption satisfied by a broad class of statistical models, including Gaussian additive models, planted sparse models, as well as non-Gaussian component analysis (NGCA), single-index (SI) models, and convex truncation detection settings. For instance, in the case of convex truncation tasks, the assumption is equivalent with the Gaussian correlation inequality (Royen, 2014) from convex geometry. In addition to the above, our equivalence not only unifies and simplifies the derivation of several known SQ lower bounds—such as for the NGCA model (Diakonikolas et al., 2017) and the SI model (Damian et al., 2024)—but also yields new SQ lower bounds of independent interest, including for the computational gaps in mixed sparse linear regression (Arpino et al., 2023) and convex truncation (De et al., 2023).

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
Siyu Chen
Theodor Misiakiewicz
Department of Statistics and Data Science
Department of Statistics and Data Science
Yale University
Yale University
siyu. chen. sc32260yale.cccomoo edu
theodor wwwsiiiiiiiczsyaa...... edu
Ilias Zadik
Peiyuan Zhang
Department of Statistics and Data Science Yale University
Department of Statistics and Data Science
Yale University
ilias. lliiaszaadik@yaee.eee
peiyuan saayyunnzzann@yylle...
Abstract
Bandeira al. (2022) introduced the Franz-Parisi (FP) criterion for characterizing the computational hard phases in statistical detection problems. The FP criterion, based on annealed version of the celebrated Franz-Parisi potential from statisti- cal physics, was shown to be equivalent to low-degree polynomial (LDP) lower bounds for Gaussian additive models, thereby connecting two distinct approaches to understanding the computational hardness in statistical inference. In this paper, we propose refined FP criterion that aims to better capture the geometric "overlap" structure of statistical models. Our main result establishes that this optimized FP criterion is equivalent to Statistical Query (SQ) lower bounds-another founda- tional framework in computational complexity of statistical inference. Crucially, this equivalence holds under mild, verifiable assumption satisfied by broad class of statistical models, including Gaussian additive models, planted sparse models, as well as non-Gaussian component analysis (NGCA), single-index (SI) models, and convex truncation detection settings. For instance, in the case of convex truncation tasks, the assumption equivalent with Gaussian correlation inequality (Royen, 2014) from convex geometry. In addition the above, our equivalence not only unifies and simplifies the derivation of several known SQ lower bounds-such for the NGCA model (Diakonikolas al., 2017) and the SI model (Damian et al., but also yields new SQ lower bounds of independent interest, including for the computational gaps in mixed sparse linear regression (Arpino et al., 2023) and convex truncation (De et al., 2023).
1 Introduction
Over the past decades, central focus in statistical inference has been to understand the transition from computationally easy to hard regimes-thar is, to characterize when a statistical task can be solved by polynomial-timg algorithms. key insight from this line work the emergence of computationallstatiiee tradeoffs: many models, there exist broad parameter regimes where information-theorre theoretic recovery is possible, yet no known polynomial-ting algorithm succeeds.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Evidence for such tradeoffs spans multiple disciplines with varying levels of mathematical rigor. In particular, the statistical physics community has played an instrumental role by leveraging non- rigorous but highly predictive techniques to study average-case hardness. Their approach typically analyzes the geometry of solution spaces and identifies structural properties that correlate with algorithmic intractability (see [40] for survey). Remarkably, for many statistical models, the predictions from statistical physics have been in striking agreement with the performance of the best-known polynomial time algorithms.
Alongside these heuristic predictions, rigorous frameworks from statistics and theoretical computer science have been developed to analyze the limitations of efficient algorithms. While ruling out all polynomial-time algorithms would require resolving P + N/P, substantial progress has been made by studying broad, expressive classes of polynomial-ting algorithms. Two frameworks have emerged as particularly influential: low-degree (LD) polynomial lower bounds [31] and statistical query (SQ) lower bounds [20]. For many "nice enough" detection problems, the lower bounds derived from these frameworks align closely with the performance of the best-known polynomial-iimg algorithms'. This striking consistency has motivated the formulation of the so-called low-degree conjecture by Hopkins [26]. which posits that for sufficiently "symmetric and noisy" models, the failure of degree-O(log)) polynomials is indicative of the failure of all polynomial-time algorithms [31].
Given this context, a natural question arises: can one formally connect these two seemingly distinet approaches? At first glance, the answer appears negative, due a fundamental mismatch in scope. Statistical physics techniques are primarily geared toward estimation problems, where the goal is to recover hidden signal, while the rigorous frameworks discussed above-suu as LD and SQ lower bounds- are focused on detection or hypothesis testing, where the task is to distinguish between the presence or absence of a signal in a noisy environment". Nevertheless, a major step towards bridging this gap was taken by Bandeira et al. (2022) [6]. who introduced the Franz-Parisi (FP) criterion for computational hardness in detection tasks. Inspired by the seminal work of Franz and Parisi in spin glass theory [21], the FP criterion provides a geometric perspective on computational hardness rooted in overlap structures. Crucially, Bandeira et al. showed that for Gaussian additive models, the FP criterion is mathematically equivalent the low-degree (LD) lower bounds, thereby establishing rigorous link between statistical physics heuristics and formal algorithmic barriers.
Specifically, consider the following general detection problem between two distributions and Q supported on a subset of RR,, which in what follows we refer to as "P versus Q" task. Under the planted distribution = E.P u. signal u is drawn from a prior distribution æ supported on ④ C SN and one observes m independent samples Y ...... Ymm Pu- Under the null distribution Q. the samples are drawn independently from Y1, ..,..., Ym Q. The goal in the detection task is to distinguish between these two hypotheses based on the observed data, that is to find test statistics with vanishing Type I and Type II errors, as grows. Note that the computational question then is whether such a successful test statistic exists that also terminates in polynomial-in-mmn time. To characterize the hardness of detection problems from the statistical physics perspective, Bandeira et al. in [6] introduced the following notion of Pranz-Parisi (FP) hardness:
Definition 1 (FP hardness). For D,m m. E N.e > 0, we say that a P versus Q detection task is (g, s)-PP hard if
FP: E [[LO" mm I.T)) 1(Ku, w)1 S 8(4)) 11+ where
5(g) sup > 0: x² (1 b) 2 8) 2 2g
In the definition we denoted as customary L., & u E θ and for f.g E C²()),, the Hilbert ao space (QQ of (square integrable) functions from RD to R. we use (5.9i = (Y)))
1 For exceptions this correspondence, see [39] and discussion therein.
2 "Some recent work has extended low-degree lower bounds to estimation settings, beginning with [38], though this direction remains relatively underdeveloped.
'The associated estimation problem consists in recovering the planted signal from Yi...., Ym ~ Pu.

---

We elaborate in Section A.I on the statistical physics motivations behind this criterion, and only briefly highlight its core intuition here. The left-hand side of the FP condition integrates the function Fann (t) := E [ _ ) ((uu, e) t)], over a (1 q Jtypicall region of the overlap variable 1, corresponding to the constraint (u, u)| S 8(4). This function Fnnn (1) an annealed proxy for the Franz-Parisi potential, a central object statistical physics that has long served as a predictor of algorithmic hardness [40]. Intuitively, the Franz-Parisi potential captures the energy landscape experienced by local algorithms- such as Langevin Glauber dynamics- wwhose performance is constrained by the geometry of the underlying signal space. The overlap (u, e) naturally quantifies a local "geometric" similarity between signals, making it meaningful argument for Faun (t) and explaining its role within the FP criterion.
Returning to the definition of FP hardness, the parameter m corresponds to the sample size, and one should interpret q as a proxy for the required runtime. In this light, Bandeira al. (2022) proved that, for Gaussian additive models, FP-hardness is equivalent to the failure of degree-D D log q polynomials to solve the detection task with samples-ic. roughly the authors of [6] showed that the problem is (g, m, (FP) hard if and only if it is "hard" for degree-log 4 polynomials to solve the detection task'. Hence, based on the current belief in the literature of low-degree lower bounds that a D-degree lower bound implies that the detection task requires at least eD runtime to be solved, c.g., see [18], proving a task is ((mn))(1), m, O(L))-FP hard for a Gaussian additive model provides rigorous evidence for polynomial -omomematemmeeeeee hardness for the task.
Despite this success, the connection between the FP potential and other rigorous notions of algorithmic hardness remains limited. [6] only established a formal equivalence for Gaussian additive models and an one-sided implication for planted sparse models between the FP criterion and "low-degree" lower bounds. They further presented counterexamples where the equivalence fails entirely. In this work, our aim is to extend the Franz-Paris criterion to rigorously characterize hardness beyond Gaussian additive models, and to clarify the scope and limitations of this framework across broader class of statistical models.
1.1 Main Contributions
Our main contribution is to propose slight modification of the FP-hardness criterion from [6], motivated by the observation that sticking the Euclidean geometry assumption (and hence the "overlap" (u, e)) may fail to capture the "true" hardness of some statistical models. We remark that this is an arguably natural modification, as (1) there are many statistical models for which the Euclidean geometry appears unnatural for navigating their parameter space (see Section 5 for a simple such construction), and (2) even in statistical physics settings, the Franz-Parisi potential is often considered under a more general notion of overlap [22]. Motivated by these considerations, we propose optimizing the "overlap" event inside the FP-hardness definition, subject only to a mild symmetry assumption for technical reasons. This leads to the following new criterion of ha-hardness:
Definition 2 (Generalized Franz Parisi (GFP) hardness under symmetry G). Fix q, E N, 0 and a group G of finite order acting on the parameter space of the signal. We say a "P versus Q" problem is (g, m, e)-GPa hard if
GFP
inf Alr (2)21-1
E (I
33m) ILm) ) 1(A)
< s1+
(3)
A i anariaa
As in the original FPP-hardness framework of [6], one should interpret q as proxy for runtime, and therefore ((mn)=(1) m, G(F) hardness should be providing evidence of polynomial-time hardness with samples in this framework. We highlight that the assumption the invariance of the optimizing event under group G is made for technical reasons to enhance the applicability of our hardness criterion. We point the reader to Section 3.1 for further discussion of this assumption.
The main result of this work is that the "optimized" notion of GFP-hardness is fundamentally connected with the well-established framework of Statistical Query (SQ) hardness. The SQ framework
'66 established this equivalence for m 1, but the argument extends directly to general
3

---

was initially proposed by Kearns in [30] to capture the power of poiisettoeerat algorithms. The notion of a statistical dimension proposed by [20] allowed for achieving powerful lower bounds against SQ methods, which we refer to from now on as SQ-hardness results. We employ here a slight
strengthening of the notion of SQ-hardness from [20], introduced [8].
Definition 3 (SQ hardness). Fix q, m E N. We say a "P versus Q" detection problem is (q, m))SQ hard if
SQ:
sup
(L.
E
Lo) 1 1A
(4)
A (A)29
m
Roughly, detection problem is (g. m)-SQ hard if any Statistical Query method succeeding at solving it with samples requires y queries, which should be interpreted as requiring runtime q (see [8, Appendix A] for more details and motivation). Hence, proving a task is ((mm)=(), m)-SQ hard provides evidence for polynomial-time hardness for the task.
Our main result informally described as follows.
Theorem 1. (Informal, GFP and SQ equivalence) Consider any P versus Q detection task which assume (I) it satisfies mild assumption with respect group G of finite order acting on the parameter space (namely Assumption below), and (2) it is information -maattoo-hhoorttiallll impossible to be solved with mir samples. Then the following holds for any samples size m and proxy runtime
q = m (())
If the task is (4,m)-SQ hard, then is also (O()), (())
If the task (q, m, ((1)) GFrdd then it is also (m (mmrr) m (0))) hard.
Note that often in statistical tasks of interest myr = wlog n) (in fact, more often than not Mar- (o)y(n)). Under this condition, Theorem implies that a task is ((mm))(1))mm" - O(1))-GFP hard if and only if is ((mm)u(1) m (ol--(())-SQ hardness, matching the two criteria for hardness.
On top of that, as we mentioned above and discuss in Section 3.1, the required Assumption on the detection task is rather mild. In fact, it turns out that it is satisfied for several models of recent interest in the community, making strong case of how the Generalized Franz- -arisi criterion now correctly predicts the hardness phase for them. Importantly, these models include the Gaussian additive models and also greatly extend beyond them, significantly extending the key message from [6] about connecting the physics-base forms of hardness to more rigorous frameworks. We list now some of the tasks that satisfy Assumption 1.
1. All Gaussian additive models (GAMs), under any symmetric prior, satisfy Assumption I with G 2z that flips the sign of the signal. Moreover, in that case the Generalized Franz Parisi criterion is equivalent to the Franz-Parisi criterion, that is the optimizing event A in (3) is of the form (l(u, e>) S 5(g)}. Hence, Theorem allows us to extend the result of [6] which proved the equivalence of FP-hardness to Low-degree hardness for GAMs, to also proving FP-hardness equivalent with SQ-hardness for these settings*.
2. All Planted Sparse Modely satisfy Assumption for the trivial group G = (id). In particular, using Theorem 1 we can prove that GFP-hardness is equivalent to SQ-hardness for multiple well-studied models such as sparse phase retrieval [5], sparse regression [24, 6). (multi- sample) sparse PCA [7], and Bernoulli group testing [11]. As corollary of this connection, we present straightforward argument to obtain an SQ lower bound for the mixed sparse linear regression problem [5]. We remark that in [6] it has been proven that FP-hardness implies low-degree hardness for all Planted Sparse Models, but no result was presented for the other direction.
3. All any symmetric prior) satisfy Assumption with G = Zz, Therefore, via Theorem GFP. hardness is again equivalent with SQ-hardness for these tasks.
component analysis (NGCA) models and all single-index models (under
We remark that such connection could also be made via the results of [8], since GAMs noise-robust.

---

4. All Gaussian convex truncation models satisfy Assumption 1 for G = fid}. In particular, interestingly Assumption for these models is exactly equivalent to the celebrated Gaussian correlation inequality for convex bodies probability theory, which was a multi-decade open problem posed in 1972 in [25] that was finally proven by Royen in 2014 [37]. Leveraging the equivalence between GFP-hardness and SQ-hardness in Theorem 1, we establish an SQ- lower bound for the convex truncation detection task. This allows us to provide, the best of our knowledge, the first formal evidence that the current state-of aeffthe-art polynomial time detection method for convex truncation proposed in [15] has optimal sample complexity.
We also complement our results, with a simple example satisfying Assumption where FP-hardness does not coincide with GFP-hardness, which we interpret as a model where the Euclidean geometry is not appropriate. We finally conclude the paper with a discussion.
For completeness, we prove Appendix B the equivalence between GFP-hardness and low-degree (LD) polynomial hardness for noise-robust models. This result follows by combining our GFP-SQ equivalence with the equivalence between SQ-hardness and LD- --hardnness under noise robustness shown by Brennan et al. [8]. In particular, our CEPP-hardness results for the examples presented in this paper immediately imply low-degree lower bounds in all those settings. This substantially extends the equivalence established in [6]. For clarity and readers' convenience, we also include succinet proofs of the SQ-to-LD equivalence, adapted from [8].
2 Setting and Definitions
We first recall the definition of a "P versus Q" task mentioned in the Introduction. Under the planted distribution IP = P.. signal is drawn from prior distribution supported on θ C SN-1, and one observes m independent samples Yi...., Ym ~ Pu.. Under the null distribution Q, the samples are drawn independently from Yi,..., Ym ~ Q. The goal in the detection task is the so-called strong detection task to distinguish between these two hypotheses based on the observed data, that is to find a test statistics with vanishing Type and Type errors, as n grows. We will also be interested in the weak detection task, which is that the sum of type and type errors fixed 0 (not depending on n). In other words, strong detection means the test succeeds with high probability, while weak detection means the test has some non-trivial advantage over random guessing.
most
for some
Throughout, we will work the Hilbert space (2) of (square integrable) functions R.V + R with inner product (f.g) g) Ey (X)((())(()))))) and corresponding norm ||íl == (f, 1/2 We will assume that P. is absolutely continuous with respect to Q for all u E supp(r)), use T, == at to denote the likelihood ratio, and assume that L, E (Q) for all supp(T).. The likelihood ratio between P and Q is denoted by := dF = Ru--p Tuu- Observe that for m samples, we denote तप
dp.
by I.m EEw-g the m-sample likelihood ratio. Finally, for a function f V + R and integer D E N, we let fSD denote the orthogonal (w.rt. (,)))) projection of f onto the subspace of polynomials of degree at most D.
An important identity between the (squared) norm of the likelihood ratio with m samples and the chi-squared divergence x² (m (Sm) is
1 = | Lu (P +10++111
This quantity has the following standard implications for information--heorrtiic impossibility of testing, in the asymptotic regime n + cc. The proofs can be found in e.g. [34, Lemma 2].
. If |3 O(1) then strong detection is impossible.
If ||||||3 1 1 o(1) then weak detection is impossible.
'The associated estimation problem consists in recovering the planted signal from Yi,...,
, Ym ~ Pu.
5

---

3 Main Results
In this section, we formally present our equivalence between GFP-hardness and ---rardness.
3.1 The Assumption
As mentioned in the Introduction, all our results operate under a crucial assumption on the "IP versus Q detection task. The assumption is as follows.
Assumption 1. Given any "P versus Q" task, there exists т --preserving finite group G acting on the parameter space θ for all G, g(v) ( for ~ т, such that for any sample size for any u, U E O, the following "correlation" inequality holds for any k E N
1)* 2 0. We first remark that (5) is natural condition even if G is the trivial group, G = {id]. Indeed in that case (5) asks that for all u, v E θ
Eg ((L
(5)
(Luy Lodo 2 1.
(6)
Recall that if one averages over all (u,, v) x 82, we have by standard identities
ELL,, Lu)Q
Eq E. 12
2 1.
Thus, (6) should be understood pointwise condition that is guaranteed to hold in expectation over the product measure x for any P. Q. While this pointwise condition turns out to be vanilla satisfied in many models (such as Planted Sparse Models or Convex Truncation settings), a slight modification of it leading to applies more broadly. Specifically, this modified condition requires (6) to hold for pair u, v only after performing a "small" averaging over the a group orbit that preserves the prior и. For instance, the prior is symmetric around 0 and the group G is Z2, which acts by flipping the sign of the signal u, then for 1, condition (5) reduces to demonstrating that, for all u, v,
(B((Tww: Loie + B(T.-u; L + B(T,,, I_-) + BL
which is significantly less restrictive than the original pointwise condition (6). This averaging approach allows for much greater generality, making it applicable to various settings, including Gaussian additive models, single-index models, and Non-Gaussian component analysis settings.
Remark 3.1. We finally make a trivial remark that will be useful in verifying (5) in our examples in Section 4 with symmetric prior. In all of them by symmetry we have for all u, (Lus L_v)q = (L-u; Le)q and (La, L = (L-u: L- Using that and the trivial fact that for all x, E R, x + y 2 then ² + n² (which will be the case in all examples of Section it suffices check the case in (5), and then it automatically holds for all & E N.
for all & E N, we conclude that is either the trivial group or Zo
Remark 3.2. As mentioned in the previous remark, we highlight that all our examples in Section 4 of our GFP-SQ equivalence theorem below, we either use G be the trivial group Zz. The reason state assumption Assumption for general finite group G is for potential further applications of our work.
3.2 The GFP-SQ equivalence
3.2.1
Simplifying GFP-hardness
We present our equivalence theorem in two steps. First, we identify an approximate optimal "overlap" event in the definition of GFP-hards which simplifies GFP-hardnesss significantly and makes CFP--hrddness easier establish in applications. Then, prove the equivalence between this simplified version and SQ- h-harddees..

---

Given a group G' acting on the parameter space of the signal, it turns out that the approximately optimal "overlap" event A takes the form {pa(u, u) S r for the following notion of "overlap" between u, U,
pa(u, u) - max ((L)) (o)e - 1
3.9'
In particular, focusing only such type of events we define the following version of FP-hardness. Definition 4 (pc-FP hardness). Fix q, m E 0 and finite group G acting the parameter space of the signal. We say "PP versus Q" problem is (q. m. e)-PG-F hard if
PG PC-FP-
E | Lb
L." // (p v) < r())) - 31+ 11 where r(q) sup 7 (pa(u,)) r) }}
(7)
(8)
We prove that GFPachardness is equivalent PG-FP hardness under Assumption 1. Theorem 2. Consider any "IP versus Q" task that satisfies Assumption 1 for group G. Suppose m, E N and >> 0. Then the following statements hold.
1. If the task is (g, m. (...E)---PPP hard, then the task is also (q. m, E)-GFP hard.
2. Assume there exists an
such that x (pG Then, if the task is (q, m, m,m)mm....... GFPG hard, then it is (g. m, [ল (1 + m XP,, Qc)-PFFFP hard. In particular, if mxx (P, Q) = O(1), the task is (q. m. O + P)) hard.
r) 1 q=² and that m is
The proof of this theorem can be found in Appendix C.I.
Remark 3.3. While the first implication is immediate to grasp, the second implication has some additional conditions we now elaborate upon. First, both the requirements the existence of r with the desired probability mass and the parity of m are technical convenience, and both can be easily remove with some tedious work. Second, any potential "blow-up" in the 6-term for PG-FP hard depends only [G], which should be treated constant, and the term m 2 Q), which is easy to compute quantity (usually
and 2P,, Q) is one-dimensional integral). Moreover, it is almost always of order ((1) for detection tasks that are conjecturally hard with m samples. Indeed, the mathematical reason behind this is exactly that it is equal to the squared C²-norm of the projection of the likelihood onto the 1egree-1 polynomial space, i.e., on the span of linear functions. On top of that, if the detection task is (g, m)-SQ hard for any q then holds directly m²² ,, Q) = 0(1) as well. We elaborate more on this Remark in Section B.
3.2.2 The equivalence
As we have already proven an equivalence between GFP-hardness and Pc-FP hardness, it suffices to connect the latter with SQ-hardness. This is the topic of the next theorem.
Theorem 3 (SQ and PG-FP Equivalence). Suppose a "I versus Q" task satisfies Assumption I for a group G.
1. If the task is (q, m)-SQ hard for some q, m with q > 2 then, is also (g' m', elG /mm) Pc FP hard for any integers < q/v2 and m² < m/2.
2. Suppose the task (q, m, FP hard for some q, m integers. Assume that there exists 9 and m even. Then, the model is also (g', m S-SQ hard for any even integer with t s log q/ log and any integer of where
an r r(g) such that =² (pG(u, < <)
m
m'
(1(1 E)/ltt x2 (PS ((orr)) (g')27
In particular, for some sample size mIr, we have
(a) (Bounded x² for mur samples)
(p @@mrr) O(1).
7

---

(b) (Large enough q)
2 m m.
then the model is (morrr O m
- hard for any 8 >
mer(1+e)
The proof of this theorem can be found in Appendix C.2. Similar to Theorem 2, the conditions on r, m of part 2 in Theorem 3 are for technical convenience and can be easily removed. As we discussed in the Introduction the assumption that there exists some sufficiently growing MAT (e.g., growing super-logarihhmicall in n) is natural for multiple commonly studied models. We remark that the condition on the information theory threshold miT to be growing with n is also necessary, by constructing a variant of the planted clique problem which satisfies Assumption 1, it not SQ-hard and is GFP-hard. Lastly, we also note that our introduced Assumption 1 is also necessary for the equivalence. In Section A, we discuss counterexample satisfying Assumption 1 that is GFP-hard, but not SQ-hard.
Remark 3.4. We note that while our bounds in the equivalence of Theorem 2 deteriorate when | becomes large, a slightly more general equivalence between GFP and SQ, using a variant of pa, can also be proven for infinite groups under an "hypercontractiitty" assumption on (Lus Leta with respect the pair (u, We omit this generalization as all relevant examples this work a small group action using either the trivial or 2-cyclic group suffices.
Examples
In this section, we discuss two popular classes of detection tasks that satisfy Assumption 1 and hence fall under our GFP-SQ equivalence. Further examples are deferred Appendix D.
4.1 Gaussian Additive Models
A P versus task is Gaussian additive model (GAM) if it satisfies:
1. Under the null model, Q = =O Ln).
2. Under the planted model P,, (for u E 5m-1), for some signal-to-noise ratio (SNR) > 0 we set
Y= Au + Z, for some Z ~ Q-
GAMs includes multiple well-studied models in the literature, with the predominant examples being (multisample variants) of tensor PCA [36] and sparse PCA [2]. For such models, it can be straightforwardly checked (see [6, Proposition 2.3]) that for all u, v,
(Lus Loyo = (((,)))
So for instance, in the case of non-negative sparse PCA where u, are binary k-sparse vectors in (see e.g.. [4, 10J) we always have (u, v) 2 O, and therefore Assumption is always satisfied for the trivial group G. On top of that, Assumption remains true for any prior which symmetric around O; this time Assumption
also always satisfied by choosing the action of = Z2 which flips the sign of We remark that symmetric priors encompass most commonly used priors for GAMs, e.g., for tensor PCA where
ree(x=r), Unif(Sd
Lemma 1. Consider any GAM with symmetric i.e., v. = -V, π. For any u, v E support(T).
1 1 ((L,, Lo)a + (L- Loya + (Lus L-vie + (L-a, L)) 2 1.
Moreover, any GAM satisfies Assumption 1 for = Ze acting by flipiigg the sign of u.
Proof. Notice
1 1 (o), Lu)g (bw, L L- (exp (2² v)) texp (-X2(u, u))) 2 1.
Hence, given Remark 3.1, the conclusion follows.

---

Given the above lemma, we conclude the (almost) equivalence between GFP- GFP-hardness and SQ- hardness from Theorem 3.
Remark 4.1. We remark that in the symmetric prior case for GAM and G 22 acting by flipping the sign of u, Pc(u, v) exp (A2) u is an increasing function of (u, e)). Hence, for such GAMs conclude via Theorem 2 that FP-hardness is equivalent to GFP-hardness, and therefore also to SQ-hardness, This is in agreement with the results of [6] establishing that FP- FP-hardness is equivalent to LD-hardness; in fact, our approach can offer an alternative proof of their result via the LD-SQ equivalence [8] and the noise robustness of GAMs (see Theorem Theorem 6).
4.2 Planted Sparse Models
In [6], the authors introduced the family of planted sparse models (PSM) and proved that FP-hardness for a PSM implies it's also low-degree hard. We start with the definition.
A P versus task is planted sparse model (PSM) if it satisfies:
1. Under the null model, the one sample is given by Y = (Yi...... Yn) ~ Q. where each entry Yi, i = 1....,77 n2 drawn independently from some distribution Q;, i 1,..., on TR.
2. Under the planted model P... we associate u with set of planted entries 4,, C. [nx]. Then on sample is generated follows. For the entries Q... we draw Y; independently from Q: (which is identical in the Q measure). For the entries in D. we draw from arbitrary joint distribution Pule. with the following symmetry condition: for any subset $ C P., the marginal distribution Pu &.. (S) does not depend on u but only S, i.e. Pals = Ps.
Multiple well-known detection models satisfy this definition, such as, well studied model of sparse regression [24, 6], Bernoulli group testing [1, 11], sparse phase retrieval [5], well multi-sample variants [8] of planted clique [29] and sparse (Wigner) PCA [2].
Satisfyingly, all planted sparse models directly satisfy Assumption for the trivial group. In fact this result has already been established for a different use in [6, Proposition 3.6], proving that any u, v we have (Tru Lo)q 2 We state here for completeness.
Lemma 2. Consider any PSM. For any u, v support(T), (Lus Lo) 2 1. This is to say, any PSM satisfies Assumption I for the trivial group.
The proof follows from [6, Proposition 3.6] for D 0. Using this, one can apply our main equivalence Theorem multiple interesting planted sparse models and obtain old and new SQ- hardness results in rather streamlined fashion. As an instantiation of this, in Appendix D.1 we prove the GFP-hardness for the mixed sparse linear regression setting studied in [5] in its conjecturally hard regime. We then use our equivalence theorem to translate it into an SQ-hardness result in the same regime. Our results complement the existing low-degree lower bound [5], providing further evidence for the hard phase of the problem.
4.2.1 Other examples
Due to space constraint, we defer the following examples to Appendix D:
Gon-Gaussian Component Analysis (NGCA): Assumption holds with G = Σg for any symmetric prior. We recover the SQ-hardness result of [16] for the uniform prior via its equivalence with GFP-hardness, and establish a new SQ lower bound under a sparse prior.
Single-Index Models (SIM): Again, Assumption holds with G = Ez. We rederive the SQ-hardness result of [12] for the uniform prior through the GFP-hardness equivalence, and prove a new SQ lower bound for sparse priors.
Convex truncation detection: Here Assumption holds with the trivial group. In fact this assumption is precisely equivalent to the celebrated Gaussian Correlation Inequality on convex bodies [37, 32). Using the GFP-hardness correspondence, derive new SQ lower bound that matches the current saate-of-the-s polynomial-time algorithm of [15].

---

5 GFP-hardness is not always equal to FP-hardness
Recall that by definition, FP-hardness implies GFP-hardness. In this section, we show that the con- verse does not necessarily hold: we construct IP versus Q detection task that satisfies Assumption 1 and is easy under the FP criterion but hard under the GFP criterion. In particular, by using Theorem and Theorem the problem is also SQ-hard. Thus, while the FP criterion fails to capture the SQ-hardness in this case, our optimized GFP criterion correctly predicts it. As our initial departure from FP-hardness was that in many models the Euclidean overlap (u, v) might not be the "correct" choice, our example is carefully creating a model where the natural "overlap" pa(u, v) (based on Theorem 3) is not a function of the Euclidean dot product.
The P versus Q problem is defined as follows. The null model is Q Rad (1) 8(++1) i.e., each coordinate is an independent Rademacher random variable. For signal u E {0, 13,1,, the sample I ~ P. is generated by drawing each coordinate independently according to
w.p. 2 + r. 2 1-(1-a)-u
I3
w.p. 3 1-(1-a)-us
(9)
where a, r E (0, 1) are fixed constants to chosen later. The following holds.
Lemma 3. Let u, {0, 1]m+1, For any u, v E (0,1)=t1, (In,, Lo)Q = I[ (1 + p² auitti).
Notice that our construction importantly ensures that the likelihood ratio inner product (Imu, Trr) is not solely a function of (u, v), but instead has a more intricate dependence on u and v. is exactly this reason that leads to the discrepancy between GFP and FP hardness stated below.
Theorem 4. There exist two-point prior and D n., where E >> O is any small constant, the following hold. The m-sample hypothesis testing problem Pum versus Q2om is P/2 m, ((n=)))-GH GGPP hard but not (n m, exp (9(nf))) hard. Moreover, via our equivalence theorem the model is (en .n (e)-((e))-Se S-Q hard.
such that, for 1/2 2, 1+22, m n
The proof of this Theorem and the above Lemma can be found in Appendix E.
6 Conclusion
In this work, we generalize the Franz-Parisi (FP) criterion introduced by [6], motivated by the obser- vation that the Euclidean dot product may not be the most natural geometry for all statistical task-a point partially illustrated by our example in Section 5. Our main result shows that optimizing the overlap event in the FP definition of [6] leads to a Generalized Franz-Parisi (GFP) hardness criterion, which is equivalent SQ-hardness for models satisfying the mild Assumption 1. This assumption holds in a broad range of well-studied problems, including Gaussian additive models, planted sparse models, single-index models, and convex truncation. Our work significantly strengthens the theo- retical foundation behind the (annealed) FP potential's predictions from statistical physics, but also opens several questions:
(Algorithmic implications) Does the optimal overlap function Pa(u, v) as characterized in Theorem 2-yyeld meaningful algorithmic insights, particularly for local search or geometric methods?
2. (The annealed potential) Can similar equivalences be established for the original (also known as quenched) FP potential, i the choice of the annealed version fundamental?
3. (Interpretation of FP Area) Why does the area under the FP curve appear to govern detection hardness? Is there some physical/algorithmi interpretation of this phenomenon?
4. (Generalization to estimation) Can our techniques be extended from detection to estimation tasks, for which the Franz-Parisi potential was originally introduced?
We believe these questions point toward promising future directions, with the potential to unify different approaches on the computational complexity of statistical inference.
10

---

References
[1] Matthew Aldridge, Oliver Johnson, Jonathan Scarlett, et al. Group testing: an information theory perspective. Foundations and Trends@ in Communications and Information Theory, 15(3-4):196-3 2019.
[2] Arash A Amini and Martin J Wainwright. High-dimensional analysis of semidefinite relaxations for sparse principal components. In 2008 IEFE international symposium on information theory, pages 2454-24444 2458. IEEE, 2008.
[3] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Algorithmic thresholds for tensor pea. The Annals of Probability, 48(2))2052-2087 2020.
[4] Gérard Ben Arous, Alexander S Wein, and Ilias Zadik. Free energy wells and overlap gap property in sparse pea. Communications on Pure and Applied Mathematics, 2023.
24733,
[5] Gabriel Arpino and Ramji Venkataramanan, Statistical-compuattonn tradeoff's in mixed sparse linear regression. In The Thirty Sixth Annual Conference on Learning Theory, pages 921-986. PMLR, 2023.
[6] Afonso S Bandcira, Ahmed EI Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. The franz-parisi criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems, 35:33831-33888 2022.
[7] Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. In Conference Learning Theory, pages 417-468. PMLR, 2019.
[8] Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, and Tselil Schramm. Statistical query algorithms and low degree tests are almost equivalent. In Conference on Learning Theory, pages 774-774. PMLR, 2021.
[9] Siyu Chen, Beining Wu, Miao Lu, Zhuoran Yang, and Tianhao Wang. Can neural networks achieve optimal computationallstatissiin tradeoff? analysis single-index model. In The Thirteenth International Conference on Learning Representations.
[10] Zongchen Chen, Conor Sheehan, and Ilias Zadik. On the low-temperature meme thresh- old: the cases of sparse tensor pea, sparse regression, and a geometric rule. arXiv preprint arXi::2408.007400 2024.
[11] Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander $ Wein, and Ilias Zadik. Statistical and computational phase transitions in group testing. In Conference Learning Theory, pages 4764 4781. PMLR, 2022.
[12] Alex Damian, Loucas Pillaud-Vivien, Jason Lee, and Joan Bruna. Computationallstatiiiio gaps in gaussian single-index models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1262-1262. PMLR, 2024.
[13] Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Ef- ficient statistics, in high dimensions. from truncated samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 639.649, IEEE, 2018.
[14] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Com- putationally and statistically efficient truncated regression. In Conference learning theory, pages 955-960. PMLR, 2019,
[15] Anindya De, Shivam Nadimpalli, and Roceo Servedio. Testing convex truncation. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4050-4082, SIAM, 2023.

---

[16] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high -igh-iimensinnal gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73 84. IEEE, 2017.
[17] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithmss, pages 2745- SIAM, 2019.
[18] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Subexponential-tine algorithms for sparse pea. Foundations of Computational Mathematics, 24(3):865-914, 2024.
[19] Jianqing Fan, Han Liu, Zhaoran Wang, and Zhuoran Yang. Curse of heterogeneity: Computa- tional barriers in sparse mixture models and phase retrieval. arXiv preprint 2018.
0699,,
[20] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1-37, 2017.
[21] Silvio Franz and Giorgio Parisi. Recipes for metastable states in spin glasses. Journal de Physique 1, 5111::144011144 1995.
[22] Silvio Franz and Giorgio Parisi. Effective potential in glassy systems: theory and simulations. Physica A: Statistical Mechanics and its Applications, 261(3-4):317-33, 1998.
[23] Francis Galton. An examination into the registered speeds of american trotting horses, with remarks on their value as hereditary data. Proceedings of the Royal Society of London, 62(379- 387):310-315, 1898.
[24] David Gamarnik and Ilias Zadik. Sparse high- digh-dimensionl linear regression. estimating squared error and phase transition. The Annals of Statistics, 50(2):880-903, 2022.
[25) S Das Gupta, Morris L. Eaton, Ingram Olkin, Michael Perlman, Leonard J Savage, and Milton Sobel. Inequalities on the probability content of convex regions for elliptically contoured distributions. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), volume 2, pages 241-265, 1972.
[26] Samuel Hopkins. Statistical Inference and the Sum of Squares Method. PhD thesis, Cornell University, 2018.
[27] Daniel J Hsu, Clayton H Sanford, Rocco Servedio, and Emmanouil Vasilcios Vlatakis- Gkaragkounis. Near-optimal statistical query lower bounds for agnostically learning inter- sections of halfspaces with gaussian marginals. In Conference on Learning Theory, pages 283-312. PMLR, 2022.
[28] Hidehiko Ichimura. Semiparametric least squares (sls) and weighted sls estimation of single- index models. Journal of econometrics, 58(1-2):71-120,, 1993.
[29] Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347-35,, 1992.
[30] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))983-1006, 1998.
[31] Dmitrly Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1-50. Springer, 2019.
12

---

[32] Rafal Latala and Dariusz Matlak. Royen's 's proof of the gaussian correlation inequality. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2014-2016, pages 265-275. Springer, 2017.
[33] Peter McCullagh. Generalized linear models. Routledge, 2019.
[34] Andrea Montanari, Daniel Reichman, and Ofer Zeitouni. On the limitation of spectral meth- ods: From the gaussian hidden clique problem rank-one perturbations of gaussian tensors. Advances in Neural Information Processing Systems, 28, 2015.
[35] Karl Pearson, On the systematic fitting of curves to observations and measurements. Biometrika, 1(3):265-303 1902.
[36] Emile Richard and Andrea Montanari. A statistical model for tensor pea. Advances in neural information processing systems, 27, 2014.
[37] Thomas Royen. A simple proof of the gaussian correlation conjecture extended to multivariate gamma distributions. arXiv preprint arXiv:1408.1025, 2014.
[38] Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 50(3):1833-18588 2022.
[39] Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna. Lattice-based methods surpass sum-of-squares in clustering. In Conference on Learning Theory, pages 1247-1248. PMLR,
2022.
[40] Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 6555):553555,, 2016.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], , [No], or [NA]
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked the checklist one of the factors in their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable to answer "I "[oo] provided proper justification is given (c.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in a binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write a justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the abstract and introduction make accurate claims about the paper's contributions and scope. We describe our results accurately.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
14

---

2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss sufficiently the limitations of our results and provide clear assump- tions under which they apply.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We write clearly all the assumptions that are required for our results hold. The proofs are all provided in the appendices.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
15

---

4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: There experimental results, this is theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
There are no experimental results, as this is theory paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c//
for more details.
16

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /tips.cc/ppuli http:/cccpppccccccccccceccccclct hwwuublicgguudss../ee Sttpe//oooSSSeiiiieeeeeeee sewonoolicyyyyoooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: There are no experimental results, this is theory paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: There are no experimental results, as this is a theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula. call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2- 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
17

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: There are no experimental results, as this is theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: :
cc/ httpppllic/ttiihcccudeeeeee..eee
Answer: [Yes]
Justification: We have conducted research and presented our work in accordance with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There are no direct societal impact of our work that we are aware of.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There are no such risks that we are aware of.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Yes, we cite all the relevant works be acknowledged to establish our results.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets
19

---

has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: As this is theory paper with no such crowdsourcing involved on human related subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: As this is a theory paper with no such crowdsourcing involved on human related subjects.
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
This paper does not involve the use of LLMs for our scientific methodologies.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: hattps://neuripe: for what should or should not be described.
http://rrippp..ccaeeeeeeeeeeeeee wcCConferences///0000 /LLM)
21

---

Contents
Introduction
Main Contributions
2 Setting and Definitions
3
Main Results
3.1
The Assumption
3.2
The GFP-SQ equivalence
3.2.1
Simplifying GFP-hardness
3.2.2
The equivalence
Examples
4.1
Gaussian Additive Models
8
4.2
Planted Sparse Models
4.2.1
Other examples
GFP-hardness is not always equal to FP-hardness
10
Conclusion
10
A Discussions FP criterion and assumptions
23
A.I Connection of the FP criterion with statistical physics
23
A.2 Necessity of assumptions in main theorem
24
A.2.1 Necessacity of Assumption 1
24
A.2.2 Necessity of non-trivial information- threshold
25
Equivalence between LD, SQ, and GFP
27
B.1
Low-Degree lower bounds definitions
27
B.1.1
Low-Degree Lower Bounds
27
B.1.2 Low Samplewise Degree Lower Bounds
................................
B.2 Unconditional SQ hardness
28
B.3 Noise-robust models and SQ-LD equivalence
29
B.4 Equivalence of GFP, SQ, and L.D hardness for noise-robust models
30
Proofs of main theorems
32
C.I Proof of Theorem 2
32
C.2 Proof of Theorem 3
34
Details of examples and proofs
36
22

---

D.1
Symmetric mixed sparse linear regression
36
D.1.1 Proofs for mSLR
37
D.2
Non-Gaussian component analysis
39
D.2.1 Proofs for Non-Gaussian Component Analysis
40
D.3
Single-index Models
42
D.4 Truncated statisties: convex truncation
42
D.4.1 A new SQ lower bound
43
D.4.2 Proofs for Convex Truncation
43
Details the GFP-hardness and FP-hardness separation
45
A
Discussions on FP criterion and assumptions
In this Section, we provide additional discussions on the Franz-Parisi criterion and its connection with Statistical physics, well as, on the necessity of our assumptions our main theorem (Theorem 3).
A.1 Connection of the criterion with statistical physics
We begin by discussing the connection between the Franz-Parisi (FP) criterion and statistical physies methods. For more detailed overview and additional references, refer the reader to [6, Section 1.3].
natural algorithm for solving the estimation problem of recovering u from = (Yi,..., Ym) ~ P. to run some "local" dynamics (e.g., Langevin or Glauber dynamics) to sample from the posterior
m
P(u Y) x (U))P(Y))) = m()) II PY.) E
where Y = (Y,,..., Yn). In statistical physics, a powerful heuristic exists for predicting the success of local dynamics in sampling from random distributions of the form py (v)u(v), v E θ where v is a a "disorder". The heuristic approach is to check the monotonicity of
reference measure and Y the so-called Tranz-Pariss potential defined
F(t) = Eu-eeY~ Ev- [pr (d(e, u) = ()], [0,
where d(-,-) is some notion of (normalized) distance between the states u, in agreement with the operations of the local dynamics on the state space. The prediction, introduced by Franz and Parisi in [21], is that local dynamics can efficiently sample from the distribution if and only if the potential is monotonic, i.e., it lacks "bad" local minima. Remarkably, this prediction has been empirically validated across a range problems in statistical physics, often yielding accurate forecasts of algorithmic tractability. For instance, when d the Euclidean distance, this criterion has proven effective in the study of spin glasses [21]. Other, more intricate distance functions have also been used successfully in non-spin glass settings, such as binary fluids [22].
Now, returning to statistical estimation settings, researchers in statistical physics have applied this rule for Py (v) == P(Y|v) I[ IP (Y,) and v = π to arrive at a prediction of success for "local" algorithms based on the geometry defined by the distance The prediction [40] is then based on the monotonicity of the curve
F(t) = En Y-F. logg E (P(Y)e)1 [d(v, u) t]], t [0.1],
or equivalently for
m
(Yi) ((+))
x) -1) 11) )] , [0, 1],
F(1) Eusz,Yar, log Evnar
πI
(d(v,u)= (d(v, u)
(10)
23

---

Interestingly, when -(..-) is the Euclidean distance, recent mathematical works have indeed produced one-sided results linking the potential to the performance of local methods for estimation tasks in the context of the so-called Gaussian additive models (e.g.. [3, 4, 6]). This connection with the choice of the Euclidean distance can be perhaps cast as natural by a well-known analogy between spin glasses and GAMs, where GAMs often take the form of "spiked" spin glass models. Now, given the above successes, both heuristic and rigorous, it is natural to conjecture a potential link between general algorithmic hardness and the monotonicity of Ft)). However, this connection remains unproven in general, and known counterexamples exist. For instance, in sparse tensor PCA [10], there are regimes where the FP potential is non-monotun non-monotonic (suggesting hardness), but some polynomial methods do succeed.
Despite the above issue, [6] used the Franz-Parisi potential to arrive at a different criterion, but now for algorithmic hardness of detection. Following an application of Jensen's inequality described in [6, Section 1.3] one get the following "annealed" upped bound for any t [0, 1] F(t) I log F(t) for,
F(t) L. L [d(e, u) f]], t E [0. 1].
(11)
Then by focusing on the Fuclidean distance d (or equivalently the Fuclidean dot product (u, u)) they suggested the Franz-Parisi (FP) criterion Definition restated here. Definition (FP hardness). We say a problem is (q, (a,mm,e-FF E)-FP hard if
FP: E [ @m L -1Kku, w) = ((4)) s si+e, where
(12)
8(q) sup(ó (uu b) 2 8) 2 ).
(13)
Notice that the FP criterion says that to check for "hardness" " of detection one should integrate the annealed FP curve is an (1 (1-o q -tyypiiaall overlap t-region. Moreover, as we elaborated in the Introduction, one should understand q in the above definition as a proxy for run-time. In that light, [6] roughly proved that for any GAMs is a (q, m, ((P))-FP hard if and only if D = log qedegree polynomials fail detect between TP and Q with m samples. We remark that, albeit this is an equivalence for detection, this is a first-of-a-kind result for GAMs as it is mathematical connection between the FP curve and rigorous form of hardness. However, [6] also presented counterexamples where this equivalence breaks down when we move away from GAMs.
The central idea of this work is to optimize over the integration region in the FP criterion, rather than fixating on the Euclidean dot product. This leads us to propose the Generalized Pranz-Parisi (GFP) criterion (see Definition 2). Our motivation arises from the observation that while the Euclidean distance is natural for GAMs (and spin glass models), it may be inappropriate in other statistical settings (see Section 5). This echoes insights from statistical physics, where non-Euclidean distances are used in models beyond spin glasses [22]. Satisfyingly, this generalization enables a broad equivalence with statistical query (SQ) lower bounds, as shown in Theorem 3.
A.2 Necessity of assumptions in main theorem
In this section, we comment on the necessity of our assumptions for the GFP-hardness and SQ- hardness equivalence.
A.2.1 Necessacity of Assumption 1
We first show that there is a strong separation between GFP-hardness and SQ-hardness unless some
non trivial lower bound on ming, (Ln,, L is assumed, providing support for our Assumption 1. Indeed, we present here a (very) simple counterexample when one allows for min (Ieu, L.) = 0.
Let us define a variant of the following model from [6, Section 4.2.] (assume for simplicity n is multiple of 10 in what follows):
Under P. first sample U {-1,1}" Σx, 8n/10)). Then under P.
each sample always equals to u, i.e., P., is the Dirac measure on u.
24

---

Under Q for each sample, we sample ~ Unif({-1,11) and output u.
It is easy to see that for all u, fz 1-1.11" : = 8n/10),
(Lus - 22 v).
We first prove that the task is not even (1, 1)-5Q hard. Indeed (1, 1)-QQ hard implies El] L 1|] < 1, but
LL L0)Q
11] 2 1( Lu²Q - [1 = =0)
(14)
= (2" - 1) (9//10) = w(1.
n
(15)
On the contrary, we now show that the task is (c 00, ((F)))GFP--aaa more specifically we prove that it is (m, q, (()))-GFP-harr for any sample size m and q (on/10) 1/2 ex
o(1) Indeed,
we have m # v) -2 and therefore to prove (m, 4)PG hardness it suffices
L L 10 (u v) 0
But in fact it even holds Bl( m 1 # v)] 0 completing this proof.
A.2.2 Necessity of non-trivial information-theon, threshold
The second assumption that our equivalence operates under is that myr is non-trivial. We now claim that some non-trivial lower bound on mrr is also necessary for the connection between the notions of GFP-hardness and SQ-hardness, even under Assumption 1.
Indeed, consider the following multisample problem over graphs. Let n E N, = 1 1 11/4 and = n 1/3+o(1)
Under P we choose a u being a k-clique in Kn, chosen uniformly at random (we see as a k-vertex set). Then under P, one sample consists the union a G(n,p) with the k-clique on u.
Under Q one sample a sample from G(n,p)) p).
We note this a multi-sample variant of the classic planted clique model [29], but on the (very) dense regime, which has been recently used establish circuit lower bounds for the model [? ].
Now, even for always a k-clique, while under Q there is no k-clique with probability 1 -(1), and brute force method can distinguish the two cases. Indeed, by a union bound the probability there is a k-clique under Q is at most
the problem is information- theorrticllr solvable; indeed, under IP there is
n² - 2143(() S exp (n/23 log n 0(12/3-1/4) exp (-0(13/22) o(1)
Moreover, the model satisfies Assumption 1. One can see this because the model PSM and Lemma 2. Alternatively,
just directly observe that for any u, have L, (G)
1(u is k-clique in G)p (t). Hence, for any u,
(In, Lo)g = (1-2")) (1 -1-1) n1-n 111/--14(( (120) 2 1.
Now, we prove that this PSM is not SQ-hard even for m = 1 and 1, but it is GFP-hard even for m = n. (() -amples.
We first prove that the task is not (1, 15-SS-hhard... Notice that (1, 1)-SQ hardness equivalent with
the condition (T] T 1]] < 1. But in this context
Bl| L 0 1 2 (L., Lu)g 1/ v)
25

---

(1 n 1111/11833) n1
k)
exp (0(k2n 1/4) - @klog)))
exp (0 = w(1)
On contrary, the task (en .n2//8 u, क,, the overlap follows an (n, k. k) Hypergeometric. Hence by [6, Lemma 6.6.] for any 0 if 8 log( 2 0 it holds
Fix m samples. Notice that for i.i.d.
( 8) S k(k2/n))) S =
Hence, to prove GFP-hardness it suffices to prove that El(Lur Lo) (lunel s 6)] = O(1).
Therefore for q exp (n for some a > 0, and = n218+0(11,
bb Lo) 1 - 6)] s [B((1 n 1
m 1(lunel 5 6)]
< (1 - n (1-m=1/44-mm{
= (1 - n 1/4 -n-11))-0(m((o((xm)))
S exp
((lo((((
n (-11/822 =()),
exp
where the last equality hold say for any 0 < < 1/16. Hence, choosing say 2/ the proof.
concludes
26

---

B Equivalence between LD, SQ, and GFP
In this Appendix, we discuss the equivalence between GFP and low-degree (LD) polynomial hardness. This result is obtained by combining the GFP-SQ equivalence from Section 3 with the equivalence between SQ and I.D hardness under noise robustness proved by Brennan et al. [8]. We recall and provide succinct proof of Brennan et al.'s result for completeness.
B.1 Low-Degree lower bounds definitions
We start by recalling the definition of low-degree lower bound. The definition based on the low-degree likelihood ratio L, where recall that L denotes the projection of the likelihood ratio onto the subspace of degree-at-most-D) polynomials.
B.1.1 Low-Degree Lower Bounds
The following is the standard definition of Low-Degree hardness as originally stated, for example, in [26].
Definition (Low-Degree Likelihood Ratio). For m samples, define the squared norm of the degree- D likelihood ratio (also called the "low-degree likelihood ratio") to be the quantity
LD(D) = : 1 = (Bunn Lam) 1 Eu,ont ((
SD (L s))]
(16)
For some increasing sequence D Dn we say that the hypothesis testing problem above is hard for the degree-D D likelihood simply D-degree hard if LD(D) (()).
While direct the reader to [6, Section 1.2] the performance of low-degree algorithms we highlight some key conjectures in the community.
relation between the Low-degree likelihood ratio and
We expect the class of degree- polynomials to be as powerful as all exp (Ō(D) -time tests (which is the runtime needed to naively evaluate the polynomial term-by-term). Thus, if LD(D)= O(1) (or o(1)), take this evidence that strong (or weak, respectively) detection requires runtime (D(P) see Hypothesis 2.5.5 of [26].
On a finer scale, we expect the class of degree-O r)) polynomials to be at least as powerful as all polynomial-ting tests. Thus, if LD(D) = O(1) (or 1 + o(1) for some (log n),, we take this as evidence that strong (or weak, respectively) detection cannot be achieved in polynomial time; see Conjecture 2.2.4 of [26].
We emphasize that the above statements are not true in general (see for instance [39] for some discussion of counterexamples) and depend the choice of P and Q yet remarkably often appear to hold up for broad class of distributions arising in high-dimensional statistics.
B.1.2 Low Samplewise Degree Lower Bounds
In multisample settings like ours, similar notion of "samplewise" low degree lower bounds have been considered in [8].
Definition For d, k E N {2o) function f (Ra)@m - E has samplewise degree (d, if can be written linear combination of functions which have degree most d in each x; and non-zero degree in most k of the 's (ifd oc the function is therefore polynomial).
Let's state the hardness criterion associated with this samplewise low degree polynomials:
Definition 8 (Low Degree (LD) Hardness). We say "P versus Q" detection problem is (m, d, k, E)- LD hard if
LD: E (L (L@m)sdk)) s $1+..
(17)
27

---

Notice that this notion of (d, klwlow degree hardness is the natural generalization to (16). As point of comparison, dk-degree polynomials contain all (d, k) -degree polynomials and (d, d) deggree polynomials contain all d-degree polynomial.
Remark B.1 (Explaining Remark 3.3), A nice property of the low samplewise-degree degree projection is that it is easy to relate it to d-degree projections. Indeed, using a binomial expansion argument (see [8, Claim 3.
|| |
113 Eur ((I " ( s((d,) (
(((A)))()))))))
= =Σ 1=
m E BR,DNT [((1
1g500 1)r_]
In particular, if l 1, oo, since Eug [( Lp) = (P, Q we have
[0,,)00 11 = + mix+mxxx (P,())
In particular, notice that the condition m Q) (1) discussed in Theorem 2 and Remark 3.3 is equivalent with samplewise (oo, deegree lower bound for the task, i.e., lower bound against function that are linear combination of functions of one sample at a time. In [8] the authors prove that SQ lower bounds are (almost) equivalent with sample-wise degree lower bounds, therefore is perhaps no surprise that the condition (P, Q) = (1) can be also explained as a (very) weak consequence of any SQ lower bounds against m samples. Indeed, assume P versus Q detection have that problem is (q, m)- hard for any q (even g 1). Then setting support(T)) must hold m.,. now LK Loke 1]] < and therefore
mx² (P, Q uww Kh Lote 1] 1.
B.2 Unconditional SQ hardness
Before stating the equivalence between the above LDDhardness criterion and SQ-hardness, we define an Unconditional Statistical Query (USQ) hardness criterion, which equivalent to SQ and often appears convenient intermediate step in proofs. This hardness measure appeared, often implicitly, in several prior work (e.g.. [8]):
Definition 9 (Unconditional SQ hardness), We say "P versus Q" detection problem is (m, unconditional SQ hard for some even i if
t)-
USQ: E [xQ(FP,, S m-
(18)
The USQ criterion removes the conditioning event A from the SQ criterion, which makes it much easier to manipulate. USQ hardness is essentially equivalent to SQ hardness stated in the next proposition:
Proposition 1 (Equivalence USQ and SQ hardness).
(i) Ifa model is (m, I)-USQ hard, then it is (g, /tt/ hard for all integers 1. (ii) If model is (q, f --t hard for all integers q 2 then it is (')-S')UUSQ hard for all t' < t and m² < m 1/ (t))tt
For simplicity, fort 2 4, can set t' t/2 and m' m in Proposition 1.ii). Proposition was proven in [8]. We provide succinct proof for completeness.
Proof of Proposition I. USQ hardness implies SQ hardness. By Hölder's inequality,
E [[<,,, Lule - 11 |A] < (E [1(L Lu)a - 1/0 (E [1[(u, v) A]])
(A)
=(BlK
E [B Tool 119)
1/2
x2(A)
28

---

Assuming that we have (m, t)-USQ hardness, this implies that for any 2 1,
E [1(Lu Loda - -11 |A| S g2/t
sup
A: (A)29-
which establishes the (q, ///2//1-S0 hardness.
SQ hardness implies USQ hardness. For convenience, introduce the random variable X (Lurde)) 1| with (u, v) ~ n². Assume that we have (g. m//2/t)-SS hardness for all g 2 In particular, for all A, we have
B[X]A] S x (²(A)
Using [8, Fact 4.3], we have for every > t' 0,
E[X"1 $ 22sup x (A) E[X[A|]) 8/t
t
2
S
6- t'
me t - t¹
which establishes (t', m - hardness for any t' < t and m' m 2 3-1/((6 t.
B.3
Noise-robust models and SQ-LD equivalence
An advantage of USQ that it is directly related to Low Degree lower bounds: USQ hardness is equivalent to LD hardness with d = oo, that is, with no degree-constraint on each sample in the projection.
Proposition 2 (Equivalence between USQ and hardness with d = oc).
(i) If model is (m, oc, k.k,,e) LLDD hard, then it (m' k)-USQ hard with m' (kekk///)) (ii) If a model is (m, -UUUSQ hard, (m, oo, k, - 1)-LD hard. More generally, it will be (m', oo, k, eml /m)-LD hard for all m! m
Proof of Proposition 2. We follow the proof in [8]. Assume that the model is (m, co, k. E)-LD hard. Then
Σ m
|E |E. (som) 118
Eu (P..
and in particular, for A: even,
( Soc. 1 (Lm 111 =
m En, L P.) S
This implies that Ey (o, S E/ (Tt) S ck /m On the other hand, (m, k--USQQ hardness implies that
m s!
E., (L
-11 <
E (xo(bu bo) S (e 1).
More generally, we will have for m' < m
[(L Soo, ( 11
b
(m')*
Bu (xo L.
1
m'
m'
s!
s!
m
m
which concludes the proof.
Combining this equivalence USQ and LD(d = xc) with the equivalence between USQ and SQ in Proposition 1, we can directly state an (unconditional) equivalence between SQ and LDddd co) hardness. In order transfer this equivalence LD with d < cc, one can assume that the model with d and d < close to each other: this assumption is equivalent to being noise-robust (in some sense, see discussions in [8]).
29

---

Assumption 2 (Noise robustness). We say "P versus Q detection problem is (d, k, 8) ---ose robust
if
[
(L,2 10 12 I 6.
(19)
Under this assumption, one can state equivalence between LD and USQ: Proposition 3 (Equivalence between LD and USQ Hardness).
(i) If the model is (m, tU-SSQ hard, then the model is also (m', d, , ,em' /m))-Dm hard for all m' & m, k' S t and d 2 1.
(ii) the model is (m, d, k, E hard and we further assume that it is (d, k. -n-iise robust, then the model is (m', k--USQ hard with
m
m m61/k + kg
Proof of Proposition 3. Part (i) is directly implied by Proposition 2.(i).. For part (ii), following the same argument as the proof Proposition 2.(i). we get
Ast
BI Ed L. - 1141 s
m
Then using [8, Lemma 3.4), we obtain
Bl| Lu) 11/11/k < (L L.a) 1//
EE (L
S 1/k k
ke
m81/k
+ 8
m
which concludes the proof.
Then, the equivalence between LD and SQ hardness in [8] is obtained by combining Proposition and Proposition 1. We state below for completeness: Theorem (Equivalence between LD and SQ hardness).
(i) If the model is (g. m//2/t)-QQ hard for all q 2 1 (with 2 4, for simplicity), then is (m', d, W, em' /m)-LID hard for all m' m, ke S 1/2. and d > 1.
(ii) If the model (m, d, k, ELDD hard and we further assume that it is (d, kt 8)-noise robust, then the model is (g, m (/SQ hard for all q 2 with
m m81/k + k/
B.4 Equivalence of GFP, SQ, and LD hardness for noise-robust models
Based on the SQ-LD equivalence stated in the previous section (Theorem 5) and the equivalence between GFP and SQ (Theorem 3), we can state an equivalence between GFP and LD hardness for noise-robust models.
Theorem (L.D and PG-FP Equivalence). Suppose a "P versus Q" task sutisfies Assumption for group
(i) If the model (m, d, d,,ke)) EDD hard and we further assume that it is (d, 8)-noise robust, then the model is (g', m', -mq /mi)--a--P hard for any integers q 1, q' 9/v2. and m' m/2 with
m
m
mgl/k + kg1/k
30

---

(ii) If a task is (q, m, PP--PP hard for some q, m integers. Assume that there exists an and m is even. Then, for all even integer 4 S t S log(g)/ / (m), the model is also (m' d, W eml m hard for all m' S i and S 1/2, and d 2 1, where
T = r(g) > such that n² (pG (u, v) < =
m 1(1 + E) (P Q04)
Note that the implication of GFP hardness to LD hardness is unconditional. LD hardness with d = oo implies GFP hardness, while for d < co, this implication holds under the noise robustness assumption.
31

---

C Proofs of main theorems
C.1 Proof of Theorem
Proof of Theorem 2. It is clear that (g, m, PPG--PPPPPPP hard implies m4) hard as for the event
A = {oa v) r(g)}:
clearly holds (A) 2 1 q=2 and, since a group, (A) Hence,
inf Ass (A)211- (1))m))
E (
m0 I (AA) s B [1L ,
_o") ) 10po < $ +
implying the desired result.
We now focus on the other direction. By decomposing the likelihood ratio inner product, we obtain
m
(L Lo 1e0m) 12
Lo) (o)-
((Lus Lota - 1)r
(20)
Taking expectation over the prior 82 conditioned on any event A satisfying (82 = and (A) = q 2 we have
m E B[((Lu: Lo)a - 1) [A]
E ( 8m L a IA
L
1=0
m (
(Bg-umitico E ((Lg(u)) Lo(i)e - -1)" +
lm/2
m
(R[Bey-unittcc ((To(u)s T - -1)241 (A]) + 1.
2t
where in the second equality, we used that G a n-preserving transformation, and for the inequality use Assumption
Clearly for all t 2 O,
Un--Uit ((og(u), Lo(s)) - 1) 2 2GI pc(u, 2)2.
(21)
Therefore, we further conclude that
Lm/2]
B[(L @m L. L 11A] G
m
E E[po(u, w) [A].
(22)
21
Recall that r(g) satisfies
x (2, v) pa(u, S r())) (A) -2
Hence, by definition of r(q) we have
1m/2 /
Lm/2]
m
m
|G|-1
E (p
2)2
2 GG
E [(cc(,, ( v) r(g)]
t=1 2t
(23)
1m/2]
|G
m
E E[ Lu)g 1121 I v) s r(4)
2t
(24)
32

---

In addition, we notice that for each even order 2t+ with t 1...., [m/2] - 1, it holds by Lemma
that
|(L L 1| 1
2r
2r+
S
2.
22
(Lus L
1| (2142)
|(Lu Lu)g
21+2
(m) 21
m (2++2)
Therefore, using the inequality ab + b for a, 0, we obtain
21 11 Consequently, the right-hand-side of (24) can be further lower bounded by
[4 Lo)a
1| <
m
21 (Lus Lo)o - 1| + 21 21
|<b Lu1g - -1/2t2
Lm/2]
|G|
11
m
Lole 1120 I 2) $ r(4) [[
E
(25)
G|
m
EE
(Las L010 11" palu, v) rr())]
(26)
2=2
G
Σ
m
18
(((( Loke 1) p (u, 0) s rr()).
(27)
Combining (22), (24), and (27), with the condition of (g, m, .FFG hardness, we obtain
E (L., ( Lo0o 1)' (u, v) S (r()) < 3| (L (m L 12 1|A]. (28)
1=2
Again, by the definition of r(AA) it follows that
m
Σ
m
[[((Tr): Tu0l - 1) 1 (pa(U, v) S r(a))] s 33 ((r " - -1)()-1))(A)))
[=2
and therefore by (20)
E E[ @m L q () r(())]
$ 3 L. L - 1))( + mB[((Luu Lo)o - 1) ( v) S r())))
Next, we aim to upper bound the first order term, namely E[((Lur Le) 1) 1(pa(u, v) s r())). Note that A' == ((,,v) : (u & r(4)) is also Gn2-invarian.. Hence, employing also Assumption we also have
B[[(Lm, L.) - 1) ((c v) r()))
Lg( [[[[EE B[( (gg))) 1)) 1(po(u,)) S r(a)))
S BI (B (L Lg()) 1))]
B[((Lur L.) 1)]
= (PP, Q).
Therefore,
E [[((L ( - (p v) S r())) s 3/GG 8m 1 - 1)1(A)) + + Q).
from which the result follows.
Lemma 4, For any t E 2,,2.... n n- 1} and n 2 3, we have
(1) < 4
(29)
Proof. Note that by the successive ratio between binomial coefficients, we have
t(n t) < 1 + 1 n
+
2 < 4.
(30)
(411
n-1
1
This completes the proof.
33

---

C.2
Proof of Theorem 3
Proof of Theorem 3. SQ implies PG-FP. We have that
sup E [KiTu: Lod - 11 [|] s
(31)
Asa (A)24
Now as G is π r--preeervin that easily implies that for any such that 2 (*2 = A, that
G m
sup E (u v) [|] S [G] (A)201
sup (A)2(0)
E [Bg-Unit(C) (T T(((o)) 1 A S
Hence for any > 0 if we set A, = {po(u, v) 2 r) since ( = A we conclude that (Ar) 2 q-2 implies r S |G//m. Recall that r(g) > 0 satisfies n² (Arig) 2 q- In particular,
r(g) S Gl/m, and therefore for any m' S m/2,
E
(L@
L le 1(polu, S r(a))]
E
((Tnu Toog 1 + 1)th 1(polu v) s r(()))
< E (po(u, v) + 1ym² ((pa(u, S r(())]
(32)
S (r(g) + 1)th v ([Gl/m + 1)m² S mm
(33)
This concludes the (g, m', e|Gmm' /m hardness.
PG-FP hardness implies SQ-hardness. Suppose we have (q, (.mm))-PGFFP hardness
E (0mm
(
Lo ) ((p(u, <r(g))) s1+5, where ()po(u,)) 2 r(1)) -²
By definition 4, we have that
1 1+22
L E [(L
@m
Le -0-1) 1). ((po(u < <r()))]
((Lm. L,ke - 1)a ( u) < r(a))
E
E pnn-uiitcc mo)) - 1)9 (po(u,)) < rraa]
m
E
where the first inequality holds by the definition of the PG-FP hardness and the second equality holds by using the elementary (L L 1 ((Lu: Levo 1+ 1+11"* 1)Th. The last equality holds by using
that G is m-masurre preserving. As crucially E Eg-CCii(c)) LooD) 1)'1 2 0 for all integers
t 2 0, we have
E
m
Loco)) - 1)'1 ((p((u,)) < r(a))
E
Σ
(m)
m
Bggu Lo(v)) 1)'1. I(po(u,v) <r()))
(
(m))
((Tuy Lu)o 1)¹ 1(p((u))) r()))
max E
+
Hence, combining the two for all even i, with S S m,
max E Liin Love 1)¹ ( v) <r(i)) <
1+e
(34)
(m))
34

---

Therefore, we have for any even t with t S m that
B[((bur Lo) 1) [[(Lbu Lo) 1)a (pc(u, v) < <r(x))] + 18 [((Lon Lo) - 1) (po(u, 2 r()))
1+ + EE ((Lur Lod - 1)2111/2 1/2 a-
(7)
x2 (PeNe ( t(1 =(
9!/1
m
where in the first inequality, we use the that (pG u) 2 r(g)) S q². In the second term, we use the elementary (?r) 2 (m/t)².
inequality for the second term and the fact
Now focusing on & S log // log m we further have
((1++)
(F Q&a1
[[(L Lo) - 1)'1 =
(35)
m
Hence the model is xx1+))=/+xx((PP Quarj US-USQ hard. By Proposition we conclude for any
> 0 that the model is (4' +x (1 (qony >-QQ hard. The second part follows by setting
mlg')
t = (log m) and g' = m)++1
35

---

D Details of examples and proofs
D.1 Symmetric mixed sparse linear regression
The symmetric mixed sparse linear regression (mSLR) setting, a IP versus Q detection task defined as follows. Given k n E N with
and o² O, have:
Under the planted model, we first sample
x uniformly from set u {0,1)" with
| k. Then, the sample (Itz, yt) ~ Pa is generated by
y/ (k o) [z @ (ar, u) (1 2) @ (Pt--u) wil,
for independent w; ~ (N o²), Ui ~ NN In) and 2, ~ Bern(1/2). Following [5] we also denote SNR k/o²
Under the null model, the sample (ys, ~ Q generated by y: ~ N((, 1) and indepen- dently 2; ~ NO,, I..).
To that mSLR is PSM, set for any u, P. suppport(u) U {n + 1j. that the coordinates of ((=)))) and of yi- Then it is easy to confirm that for any subset C Qu. the marginal distribution Puls.. (S) does not depend u but only S; the choice of suppport(u) \ S does not alter this distribution.
is known that the information theory sample size threshold of the problem is
MSTATS = è
log(
SNR 2SNK+I
see e.g., [19]. Also in [5] was proven that in the similar mSLR setting where u's coordinates can take values in {-1, 0, 13,
(SNR 1)2 SNR²
m S MALG =
122
then the problem is Ollog n.) degree hard. Here we prove that with sample size m S (MALG))-a()) 1-o(1) the problem also GFP-hard, and hence via Theorem 3 also SQ-hard. Our result holds under very mild assumption on SNR being not exponential in k. Interestingly, the proof is relatively short.
The first step calculate the inner product (L Lem") which accounts calculation over the Gaussian measure.
Lemma 5. For any sample size m and any u, binary k-sparse vector, the following holds for the mSLR model:
(1
(u, 2/ A: + o²
m(u, v)² (k: + 02)2 (n, v)
(L%
S exp
Using Lemma one can prove the GFP-hardness, and therefore the SQ-hardness.
Theorem 7. R(1) = k o() then for any m =
k logí aNDZ +1)
holds
x2 pm @mm) o(1).
Moreover, for any constant T > 1, for any
1S (lgg(log and q @((logn))) the mSLR task is (g, m, ((1))-GFP hard. In particular, iNR S c for some a >> 0, then for any T 1 the mSLR task is ((logn)))") (1NNR+1) 1) hard.
o
The proof of this Theorem can be found in Appendix D.
36

---

D.1.1 Proofs for mSLR
Proof of Lemma 5. Let X vk/o²+1 +1 and since (Le Le (1L - focus on the case m = 1.
Let Y = Y X1. By definition and Bayes' rule,
Lu = LxX,)) X(
Q(Y)
Under Q we have AoY ~ ~O(0)A002) while under I' conditional on (X,, u) we have
AoY = Vk+ u) 1 (x(
and so
L, P(
Q(Y)
20 (AoY -0, ux, + 2X202 (orr2))
2 Aexp
(-1
+ texp
(NOY + +X,, x)) + 21202 (Nor)))
(M
20
m
X2
y +
Y(X, u) 2 (x,
ux2 u/²
exp
2
2
20
12
y2 > Y u) 202 (X, u// (x, }.
1
+ exp
2
Now standard integration argument using the MGF of the x² distribution (see e.g., the proof of [6, Proposition 6.8.] for an almost identical argument) gives for any u, binary k-sparse vectors,
2²
(Lu, Lo)a 2(2x² 1)1/2 Eexo
202(2X2 1) (1_ u)² + (X, 22 2A²(X, (X, (X, (X,,)
(36)
(x,,)))- 2X 2002 - 1) [11 (11 (3X, (xxx))
(x,, (37)
+ exp
Now of course the pair ((X, u), (X, u)) follows bivariate Gaussian law with variances equals and covariance (u, v). Hence, some standard manipulations (see again the proof of [6, Proposition 6.8.] for almost identical argument) allow us to derive that for Z R 1x3 with i..d. (0 1) entries and
t:= 20² - 1)
(38)
20 +1)
4k + 20
holds
22m
(Lu, LuiQ=
2(212 - 12 Ez Exxp (t(M1, z Z)) + exp (t(M2, ZT ZTZ))
(39)
where for l = (u,,))
28
Vi(k-
)
Mj M2(1)== = Ve(k - E)
(1 - x²) - 9)
2² - 6)
Ve(k: - E)
2² - 1
(1- 22) - E)
and
2(1 - 2X20e
(1 - 2x2) E(k -0
(1 - (1-2X2) / ((k-)) ->2(k- -0)
)
M2 M2(1)=
(1 (1-) Llkk -
(1 X3) 8)
(1-2 (2222))((( Ve(k -f)
X2 8)
(1- x2) 1)
37

---

The eigendecomppoitionn of MI, M2 of the form Ei= X
u.u." ||u, are, first for M1;
"1 (0) -1
1 = (1 2x - E)
W2 (vk E Vt VB)
A =
(40)
03 = (2VE vk- & vk (
A = h + l.
and for M2,
4 (0 1 -1
A1 k-6
32 (vk-1 - Vt Vt)
A = 0
(41)
"3 = (2V2 vk vk ()
A = (1 - 2x²) +2-
As t < 1/(4k) we have 2t max [|-M1llopp [| < (l: + f) S 1. Hence, using [6, Lemma
A.5.] for B(U)= = Raxm we have
X
(Iw, Loto 2(2X² - 1)1/2 (det(Ts - 21 1/2 + det(Ts - 2tM2))-1/2
(42)
Using (38) and (40), (41) the eigenvalues of the matrices - 1..M,,,1 13 21.M2 are
3: + l
{1, - 21(k + - 1- 2(1)) = 1,
+
02(2X² 1)
and
11,1-211 -2((k -0., f), 1- - 20( = (
{1,
k -
1+ k k+
r2 - 1)
Since X² = =k/o² + 1 we have
221²_ det(T3 - 21M 1/2 X2 ( 22
x²
11
h k+L
) (1 (+ -- ]
11/2
(43)
0²
$ +1
(44)
1 1+ E
(45)
k: + 002 σ²
and by symmetry,
2²
1 t -1
)
det(Is 2t.22 =
(46)
22
k + 02
Combining the above,
(Le, Lol
= - (/(11-
E
-1
+
1
(47)
4: + o²
k + 02
-1
t
1
(48)
k + o²
m2²
S exp
(49)
(k: + 02)2 82
where for the last inequality we used that log x 2 1 1/x, for x > 0.
Proof of Theorem 7. We have from the first part of Lemma 5,
x² (p8m @@m) - 1 = Eujent (L L ) I Eu,onr (1-
032 (Ks 02)2
m
(50)
38

---

But, in this setting (u, v) follows an Hypergeometric distribution with parameters n, k k. Hence, by [6, Lemma 6.6].
h22
x (pom, Qam
15
Σ
(51)
(I:
0213
n
k
8=
|k/2|
ml?
k
exp
(k: + 02)2 - 8z
6
log
xxtt))))) +
(1
(k: 02)
6 - log( x27)))
t=
[/21
(52)
12/2|
(²) )2
fm/ -elog( "x²") + R-
+ 1)
0(klog((")))
(53)
2 0a2 +1
where for the last inequality we used log x 2 1 1/2 for x > Since k² = o(n). m of
) J,SNR = k// we have for large enough
aNR- logt 29N1T+
k1 2
+1)e Ils - )) 0(k log( ( o(1)
0²
Moreover, since 2.2 o(n), o(k) we have for large enough n,
[k/2]
[2/2]
[4/2] eogg //2 1+ o(1).
tm/ (m/(kke))(logg log( (pt)
2tm/k- log
Now, fix any T > 1. Notice (Ln, L is an increasing function of (u,,), u). Hence, for any q > there exists do (q) > such that {pra(u, v) 2 r(g)} = {(u v) z 60(4)). Moreover, from the tail of (u, v) which is an (n, k.)) Hypergeometric distribution, there exists some q qr ((logn)))) for which there exists rT) with T ((Pia(u, v) 2 r(T))) = =-
Let us then fix Q = Qr. Notice that if we choose 8 == log(ky large enough n, by [6, Lemma 6.6] ( v) 2 6) < ki ) S 12-5 5 = 1/02. Hence, ón S 8. Combining the above with the second part of Lemma 5,
O(logn) T+1), then we have for
m(u, w)2
Eu,vor (ooor(((L (LL I. 1. (2ln)))(((u) v) S 5o)) exp
(k 02)2 (u, u)2 1(u,, v) 50)
mo²
exp
(I+ + 2202 82
(log n) )2(+++))
) 0(1),
cxpp
k2(1 SNR 112))))
SNR
for any m = O ((L+SNR 1)2). ). Hence, the model is (g = qr, m = O ((L+SNRR 2)2 ). (1))) Pia- (log (logn)8(--1
(log [ogg))(7+1]]
hard. Using now Theorem 3 for mrr (logn) which is permissible to use using our x² bound
and that SNR < ch--a for some a >> O, we conclude for all T > 1, the (c -1 (k2 SNR- S-QQ hardness. The result follows.
D.2 Non-Gaussian component analysis
The following model was introduced in [16] to capture the complexity of learning Gaussian mixtures. Definition 10 (Non-Gaussian component analysis model). A "IP versus Q" detection problem is a Non-Gaussien component (NGCA) model if:
There exists μ E P(R) such that, under the planted hypothesis Pu with Sa-1, we sample x ~ (0, In) and replace the component (z, u) by where z ~ y independently;
39

---

Under the null model, we sample x ~ NO, In)
In other words, an NGCA model is an isotropic Gaussian distribution with a non Gaussamn marginal in direction u. The SQ-hardness for NGCA models established also in [16] has been of big importance in proving many recent SQ-hardness for learning tasks, such as for robust estimation of Gaussians [17] and robust linear regression [17] among others.
Interestingly, we can also connect all NGCA models with GFP-hardness for G = Zz. By direct Hermite expansion, we can decompose the likelihood function (in (Q))
Lu(z)= Σ vuhi(u,,)))
14 = (e.
where h; the (normalized) degree-i Hermite polynomial. Here we denoted 8" the first non-zero coefficient V/2 * that the smallest moment of p that disagrees with NN 10 moments (we call s* the generative exponent of the NGCA model). The inner-product of the likelihood ratios is given for all u, 8 by
(Luy LT) =1 Σ vg u(,,
(54)
where we used that E[h, he ((,,)))] = (u, w)". Similar to GAMs, using again the group G = Z, acting on flipping the sign of each parameter, we get
Uuifn (Lg())) (w) 1) Σ
v. ((u, u)) 2 0,
$= even
concluding that NGCA satisfy Assumption with G G Zz. Hence, based on our equivalence, for any NGCA model the SQ-hardness is equivalent with the GFP-hardness for any symmetric prior (that (-- = π (u)). We illustrate this equivalence for two standard priors: the uniform prior Unif(S and the k-sparse prior π Unif( (u E + + (0, 1)" ||u][o= k+)).
Theorem 8 (GFP-hardness of NGCA, uniform prior). Consider NGCA model with generative exponent s" and the uniform prior æ = Unif(( For any E (0, 1/2), the NGCA model is (exp (O(n))) ,, ,m, ((1))-GF hard with
n1 (2)
m
Moreover, via our equivalence theorem, the model is (exp (n (())) .mm -(s))-SQ hard.
Theorem 9 (GFP-hardness of NGCA, sparse prior). Consider a NGCA model with generative exponent s" and the k-sparse prior Unif( (u E vi (0,1)" ||u]lo- = k)). For any E (0, 1/2) so that l: = n M()), the NGCA model (exp (e((())())))))))))))) )), O(1))-GFP hard with /2-0(s) /2- ke n -(6)).
m min(n"
Moreover, via our equivalence theorem, the model is (exp (n (())) m 1 -SS))-SQ hard.
The SQ lower bound in Theorem 8 was proven in [16] by direct argument: here, we prove this SQ-hardness via equivalence to GFP-hardnest The sparse prior not considered previously and we include it to illustrate the broad applicability of our equivalence.
D.2.1 Proofs for Non-Gaussian Component Analysis
Proof of Theorem 8. Let prove that the model is p2, P2,-FP -FP hard and conclude using the implication in Theorem 2.1. Note that pz, (u, v) (Lu, (u,,))) 1, that is
0c
Pz. (u, Σ (u, w)1".
8=
40

---

and Pzz (2, u) is an increasing function of (u, e)). Thus, P2, -FP hardness is equivalent to FP hardness.
Using that (u, v) under the uniform prior is distributed as the first coordinate of ~ Unif & ) we get
π (( w) 2 x) S 2exp (-enx²),
for some universal constant > O. For simplicity denote = 1(1, 1)}- Using that u < for any s E N by Jensen's 's inequality, we can write
E 0 1p' U (12 (2++--))
(Io Loo) 1 Σ 12p00 S u2 + pp
$2
82
so that for p (1) and n large enough, (Lus Lu) - S 2v p² We deduce that for A = n 1/22e,
we have
m
E [ L 1ST))q
< <x]
s1+
Σ
E [(LL,) 1)- 1(Ku, u)1 <x)]
j=1
11+
Σ
(2mvz k:
1=1
Thus we deduce that the problem is (exp (0(n)) m, (()))-GFP hard with m - n2 12- 12- /1g. To the equivalence with SQ, need compute the x2 diverggne, that is
4t j
EK Lo) 41 El Lo) 41 ( 11 Σ
EE[ (L Lo) -1y1.
Let us bound
(Tr, Lup) - 11}} = B[[(ITr. Inp) - 133 1(1p) S k)] + E[((Tur Lu) - 173 1 > k)]
S (2 g+ x²² + MMexp (-cn²*),
where we denoted M = || 12 = O(exp ( Thus
4t
[[[(Lng Ln) 131 = 1 + Σ (Stv?, k") pp + e4tM)epp (-en?)) = =01),
where we used that t log(t) = 222 by assumption. We can therefore apply Theorem 3 with o' = exp (2 and = 52 (so that / < log(g)/ loom//og(mmm))) = ô(nf)). The model is (d' m')-SQ hard with
m' (111 t6) + (2 (011)){722 = (mm/l) = m m-(e()))
m
which concludes the proof.
Proof of Theorem 9. The proof proceeds similarly as the proof of Theorem 8. The main difference the new tail bound (u, v) given in Lemma 6. We now set K. n² max(n 11/2 k-)), so that
(((u, e\| 2 x) S 2exp (-enf).
With this modification, the rest of the proof is identical and we omit it.
Lemma 6 (Tail bound for sparse prior). Let u, v be independently sampled from the prior π = Unifl(u {u E + vI 10,1)" ||u]|o = kt). Then for any t 2 0, we have
2²((1, v) 2 1) < exp (-emin(nl?, kt))
(55)
for some universal constant > 0.
41

---

D.3
Single-index Models
Another extremely popular class of models in statistics dating back to the 80s [33, 28] are the so-called single-index models.
Definition 11 (Single-index model). "PP versus Q" detection problem is a Single-index model if:
There exists a distribution E P(R x R.) such that, under the planted hypothesis Pu. we sample a ~ NO, In) and y ~ pl-lzu), where =u = (xr, u);
Under the null model, we sample a ~ NOO, In) and ~ My where By is the marginal distribution of p.
Also, all single index models satisfy Assumption 1 for G Zz. Indeed, s* the generative exponent of the model [12], following [12] we know that an Hermite expansion gives for some s* (s" called the generative exponent) that for all u, Sn-
(bu, Lo)= 11
Σ X o(), $=8"
:= 1==10
((v) :- (1)all)
From this point on, the argument is identical as in the case of NGCA, including the nonnegativity with G = Σe as well as the examples of GFP-hardness with uniform and sparse priors. For completeness, we state separate theorems for single-inde inglle models:
Theorem 10 (GFP-hardness of SI models, uniform prior). Consider a SI model with generative exponent 8" and the uniform prior a = Uni For any E (0, 1/2), the SI model is (O(x)) m,
,,, ((1))-GFP hard with
n 12-B(())
Moreover, via our equivalence theorem, the model is (exp (n (())
.m (01- hard.
Theorem 11 (GFP-hardness of SI models, sparse prior). Consider SI model with generative exponent s" and the k-sparse prior x = Unifl {u E + vI 1)" ||ullo = k}). For any e E (0, 1/2) so that k = ((), the SI model is (O(p)) m, O(1))-GFP hard with
m / (2))(e) kst -())).
Moreover, via our equivalence theorem, the model is (exp (n (()) .mm (-e(c)))S hard.
The SQ lower bounds Theorem and Theorem were proven in [12] and [9] via direct argument.
Here, we obtain these bounds via the equivalence of the SQ-hardness and GFP-hardness.
D.4 Truncated statistics: convex truncation
Learning from truncated data has been a topic of interest since the late 1800s and the pioneering works Galton [23] and Pearson [35]. Interestingly, there has been some recent line of works on truncated statistics tasks that seeks revisit these old questions from computational viewpoint, see e.g., [13], [14] and references therein. In this line of recent work, the problem of detecting convex truncation in Gaussian noise has been proposed.
Definition 12. Fix a (0, hypothesis testing "IP versus Q" problem called an a- e-Coovex Truncation model if it satisfies:
1. Under the null hypothesis Q N(., (n).
2. Under the planted hypothesis IP PK. NO, K where K a symmetric conver body with Gaussian volume most
42

---

Interestingly, also all a- e-Convex Truncation models satisfy Assumption for the trivial group G. Perhaps this fact is even more interesting because it turns out Assumption is exactly equivalent with the celebrated Gaussian Correlation Inequality on convex bodies [37, 32].
Lemma 7. Consider an a-convex truncated model in Definition 12. For any K; K' two symmetric
convex bodies of Gaussian volume 1- a, it holds (Lx, L 2 1. This to say, and a- a-Convex Truncated Model satisfies Assumption 1 for the trivial group.
Proof. For any K, it holds Lx(x)= 1(x E K)/Q(K), E R.. Hence,
(LK, LK) Q(K (KK
Q(K)((K))
But the so-called Gaussian correlation inequality for symmetric convex bodies in convex geometry [37] states exactly that for any symmetric convex bodies K, K' it holds Q(K n K') 2 Q(K)Q(K)) yielding the result.
Now, for the a-Convex truncation models, the state-of-the-arl polynomial-tin timme algorithms require ((n/a²) samples [15], and the best known information- -theoratio--hhoorttii lower bound is 12(n/a) samples [15]. Using the GFP-hardness to SQ-hardness framework we prove that for some prior K, is SQ-hard distinguish with ö(n/a²) samples, providing evidence that the polynomial-timg method from [15] cannot be improved.
D.4.1 A new SQ lower bound
To apply framework, we focus on the following prior on K, variant of which has been studied in [15] to prove their cetemmatioo-thhorette lower bound of (((/aa) samples. To define it we let
K K, (a E Rd. KI, sx),
Here, we choose k x(a, d) is such that the Gaussian measure of each K2 is 1 a. Then our prior is uniform among Ku, U Unil([-1/Vd, M/V)))) We refer to the a-convex truncation setting with this prior the "a-Slice Convex Truncation" model.
for any v E Unff((11/V..//ay))
We first point out that for any m = w(naa), detection with m samples is always possible in the a-Slice Convex Truncation model from a time-inefficient method. Indeed, one can brute-force search for some e E (-1/Vd, 1/Vdjd for which it holds: for all i = 1. m, (2,, e>| S K. Under P. there always exists such vector v and hence the brute force search algorithm will find it with probability 1. Under Q though a direct union bund gives that such e exists only with probability most (1 az) mh o11) for any
wd/a). Hence, the algorithm can detect with probability 1 -1). In that context, we prove the following result.
Theorem 12 (pIa-FP- and SQ harddaddeess of Convex Truncation). Let n E N growing and arbitrary On E 1). There exists universal constani C > 0 and prior on the convex bodies K of Gaussian volume 1 a such that for any q E N with eolam), the a- a--onvex Truncation model under æ is (q, az log() 30)33/1oog --ta------aaa FP-hard.
Cn
In particular, for any constant T > 0 if w( (logn) is (e (()og)))))
then the o-Convex Truncation model under
( a (1))) ma ) hard.
Satisfyingly the proof of this result is also relatively short. The proof of this Theorem can be found in Appendix D.
D.4.2 Proofs for Convex Truncation
Proof of Theorem 12. Observe that for Lu := Lx., we have via standard Hermite expansion (identi- cal to the argument in [15, Line (32), proof of Claim 24)),
(Lu, Lu)e = Q(K,, (k)) 1 + (1 - ax) (u, 0)
Σ
oc:
Sa w)
(56)
(1 a1=
43

---

where f; is the i-th Hermite weight of 1(r E [-x, x)), 2 E R for such that ((k) = 1 a/2 where is the CDF of a standard Gaussian.
Now, conveniently, the authors [27] have already studied the Hermite mass of indicators of symmetric intervals around 0. Indeed, applying [27, Lemma 27] for 2, k imply that
f (1<((K))),
where ó is the PDF of a standard Gaussian. But observe that by standard tail bounds k /lo/(//a)))))))) and from the Mill's ratio bound ((x) = @((1 (x:))t. Combining the above we conclude
$ = 0 (a log(1/a)3/2
Parseval's identity gives Eiso l? = a(1 - a) S a, and hence for some constant C
(Iu LulQ 1 C (11 3 (u, u)² (a² log(1/)))))) + (u, 1) o)
Now, notice that from (56). (Ln, L is increasing function of (u, 0)2. Hence, for any 0
there exists do(g) > 0 such that {Pia u, v) 2 r(g)} {(u, u}² 2 6o(4)) }. From Hoeffding's
inequality we have that for some constant C" 0f = C² lor then x ((u, v) 2 6) S 9- Hence
50(g) 8 C" log
Combining the above we have that for any q co(an),
[L Lo)0 ((u, ()² s do)l s
C
(1 - log(/a)) + 60a))]
a1- logg (a log (1g(1/)) + + log a)
)
$
1 + C
<
1 20
C'' log
n1 a) (a log 1/a)8/2)
O(1)
as long as m ((d((a²))))) log(1 (1/a)3/2 Pid -ard for any q caa))
3/2 log q)). So we conclude the (q, ((n((a² log(1/a)3/2 log q)))-
Now via an identical proof to [15, Theorem 23] we have for any m o(n/a) that
x² (pom ?8Th O().
In particular, for any constant T 0,
x² (p (llgg))) = 0(1).
Finally, notice that again since (Lu, L is strictly increasing function of (u, v) and (u, v) is sum of iid Rademacher random variables we conclude via standard Central Limit Theorem arguments that for any T > 0 there exists q q(T) Ollng ") T+1) for which for some r' (T),), r(T') > 0 it holds that x² ((u, 2)² 2 n" (pia v) 2 2r' -
Hence, for any > we can apply our equivalence Theorem for mir = (log = q + 1) (so logg = @(log n) )+))), and appropriate t (((logn)T) to conclude the (((OR))))) (
(log SSQ hardness of the task.
44

---

E
Details on the GFP-hardness and FP-hardness separation
Below, we provide details on the counterexample described in Section 5.
Proof of Lemma 3. By definition, for any u E {0, 10
[a(x) = II (1( 1(x = =) 1/2 + r. 1-(1-a)
"
1/2 + +1(1; = 1/2 - r.
1/2-r-
1-(1-o)mp
-1)
1/2
i=0
II (1 ræ; [1 (1 a) usl).
i=0
For any u, v E 10,1)=+1 the inner product (Lus Lud satisfies
(oo) = B
II
(1 + rz; [1 (1 - a.) uil) (1 + rr, [1 (1 - a) wil)
1=
E (1d(1
r1 [1- (1 a) u.l) roa [ (1 a) v/l)
1=0
(1 + 2 (1 (1 a) u;)(1 (1 a) v4))
Denote d; + 2 (1 - (1 a) u1 - (1 a) vz). When u; = 0; = 0, we have 0; 1 r2: when U, 02 1. a; 1 1 ,2 a²: when there is exactly one and one 0 in ug Us we get
a; 1 12 a. We deduce that a; 1 + 2 a 44 and the lemma follows.
Let us consider the m-sample version of the hypothesis testing problem. The null hypothesis is then Q8m and the alternative hypothesis is Pow where is sampled from the following two-point prior n:
(1.0.... .t.O,....0), 0). w.p. P.
u
(57)
10.1... 1). w.p. 1 - p.
We abbreviate these vectors as 41 (1,0, ...,....,))) 0) and U2 = (0, 1, 1,.....]] 1) for convenience. Using Lemma 3, it holds that
(L mm
II 1=0
(1 + r2 a m
(58)
Let's next show that this problem is GFP hard but FP easy. Note that Lc) 2 for all u, v and therefore the model verifies Assumption 1 for the trivial group.
Theorem 13. For the two-point prior in (58) with p exp exp (2n and and n 1426
ni-= and D n', where 0 is any small constant, the following hold. The m-sample hypothesis testing problem P@ versus @'0m is (e m, ((n-"))-GFP hard but not (n-1 m. exp (O(n))))-FP hard. Moreover, via our equivalence theorem the model is (en oie) .nl-@(E)) hard.
Proof of Theorem 13. Let us first show is FP easy. Define d = 11/2) the supremum over ò such that x² ((u, v) 2 8) 2 1 1/n. We observe when * v, then must have (u, u) 0 < 8 by the choice of the two points prior with (u1, u2) 0. Therefore,
n >2 + v) 2p(1 p) < 2e n n! x" (() 8).
(59)
We deduce the following lower bound
Eu,v (L _ 1(uu, v) < 6)] > (L L Lom) 1(u + v)
45

---

= T + t] -E, (La Lam Leme) l + v|
When conditioned u o v, we get
Eu, L .L m Iu * u| (1 + ar 2) ((+t)m
by applying Eq. (58), with u, + vi = for all S S n. Inserting the parameters stated in the lemma, we obtain
En (L L.m) 1((u, < <6] 2 2p(1 - pp) - (1 + ar 3)(++t)
2 eepp (- (1 + n 2222 2 (n+1)a
= -1 exp (- f eepp (n²) 2 Q(1) exp (fn²).
This shows that under our parameter choice, the task is (n (n-1/2 1/2 m. exp ()) easy.
Let us now show that this model is GFP hard. We will prove that the model is pta pta-FP hard and conclude using the implication Theorem 2.1. Under the trivial group, we have Pia (u. 2) Lo)q 1. From Eq. (58), the m-sample inner product of likelihood ratio is given for
u1 by
mm I. &mm ) = (1 + a², (1 + 2)mm
(60)
Us
and for u = 0 = U2 by
(L Lam = (1 + 222
(1 + p2)m.
(61)
Because a < 1, it is not hard to notice
(La LS)) _m )
sm Lmm)
(62)
From the definition of n, it holds that
(fu = ū2 u= u-
=1
21-9
(63)
using that we set q = exp (D/2). Combining with Eq. (62), we conclude that the event {p(u,
v) S
r(4) C (u- = U2, r= = w2) U {u # v). This allows us to estimate the upper bound as
[ 8m L 1(r S r())) S E '
I 1( = u2 u2) } U fu v))]
(64)
S (1 + a² 2²)2) nm (1 + p2)m
Inserting our choice of parameters, we obtain
[T 8m T 1(r S rr()))] S (1 + n 3
n² (1 + n (1+n-1)ut
(65)
S exp (n 143c + n=) 1 + 2n
Thus, the model is (cn/2,m, m. (nn PLa hard, and therefore P/2 m, (nn-))))Gr GFF hard.
Finally, 1et us the SQ-GFP equivalence in Theorem 3 to show that the model is also SQ hard, with parameters g' = c and n²/² (where indeed S log(())/ loo/m//mmmmmmm -((n))) )) To apply the theorem, we need compute the x diveeregee Denoting X = (L 1 with n²/2.
x² (peet @84) + = x 2 u1 v= = u1) B|X|u= = #1, e = u1] + n 2 v) E E|X|u + w]
+ x (u U2, u = u2) E[X -= = 02 u = u2]
= (1 - p1-p) (1 + a2) r1+ + p² (1+ (1+0212)41 (1 + 22)ant
+2p - p) - (1+ aaaz)22)(xt
< (1 + 3+40m itc
(1 + n 1ym
+ - a1+n-3t4gm (1 n 2yn'te/2 + == (1 + n -2+3e)2n
< 1 + 4n -1+e.
Thus, we obtain
m'
(1(1 + 8)1/ + (P@ || (Q)2) m m-()(
and we deduce the model is P/2 m mmmmm11pp m0(e)) J-QQ hard.
)-QQ
46


Reviews:
[{"review_id": "6e5imsFy2q", "reviewer": "Reviewer_Nb5E", "summary": "The authors propose a refinement of the Franz Parisi criterion for the detection of planted signals and the understanding of statistical to computational thresholds introduced by Bandeira et al. in 2022. They show that this optimized criterion is equivalent to Statistical Query lower bounds (which according to the authors can be considered as a representative approach which closely aligns with best known algorithms, together with the low degree polynomial lower bounds)", "questions": "Section 1\n\n- lines 51 - 62, you should give an example of a detection problem (even the simple rank one detection problem) illustrating the meaning of P, Q u and v. \n- lines 52-56 are not very clear. Why not give an example. Isn’t the planted distrbution the same as the null distribution except that the parameters are updated. E.g. In the additive model with Gaussian noise, if I’m not wrong, the addition of a planted signal corresponds to changing the mean and variance of the original distribution doesn’t it?\n- line 58: what are vanishing type I or type II errors ?\n- line 63 - 65, in definition 1, from what I understand, the expectation is taken with respect to u and v? I would explicitly indicate this.  \n- Definition 1 again. From what I understand, you only look at levels of overlap that can be demonstrated for a sufficiently large number of solutions. But then you average over solutions that are more different than the level of overlap delta  \n- Lines 65-67, The likelihood ratio (dP_u/dQ) should be properly introduced. I strongly encourage a complete introduction such as in e.g. Kunisky et al. “Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio” (Definition 1.7). I also encourage mentioning the annealed upper bound (and its connection to the FP potential) in the main paper. \n- Again on the likelihood ratio, I really recommend moving (11) from appendix A.2 to section 1 and properly introduce the notation L_u^{\\times m} in relation to the independence of the Y_i\n- The definition of the Franz Paris potential that you give in appendix A2, line 945, is also quite vague.  What does the Potential represent? There is no intuition given. Moreover several explanations are missing. E.g. why do you need the Franz Parisi criterion to be less than 1+epsilon. You should explain somewhere that an O(1) FP criterion corresponds to a regime in which string detection is impossible and that a 1+o(1) FP criterion corresponds to a regime in which weak detection is impossible. Perhaps also indicate that FP is always larger than 1. Perhaps just indicate that the smaller the FP criterion, the harder the problem. I.e. Honestly I think you should at least add part of Bandeira et al 2022, section 1.1. (the reminders on the likelihood ratio and the importance of the squared norm of this ratio)\n- it seems that in Equation (1) the inner product should be <L_u, L_v >_Q\n- line 68: I really think that appendix A.2. should be moved to section 1 or that you should at least give a better introduction to the notations in Definitions 1 and 2. The notations L_u, L_v really come out of the blue which makes the understanding quite difficult.  \n- lines 70-73, if you want to provide an additional explanation for (1)-(2) it is good. But your explanation should bring more information. What you do here is you merely describe the formulation. In fact you could do more simple: The left-hand side … corresponding to the constraint. —> this is just a description of what’s already given in (1)-(2). Now if you really want to add a sentence make it simpler: “”we integrate over the region <u,v><=\\delta. \n- To me, lines 68 to 77 do not bring a lot more information. Except for the sentence on the landscape. \n- line 89: “and an one-sided” —> “and a one-sided”?\n\nSection 1.1.\n\n- line 95: “Our main contribution of this work” —> “The main contribution of this work” or “Our main contribution” ?\n- lines 98 - 100, you use arguably twice, perhaps replace of the occurrences by another word?\n- In (3) it is not clear what \\pi represents. \\pi seems to be a distribution over u and v? so that \\pi^{\\otimes 2} is the distribution over independent (u,v). This should be clarified\n- In Definition 3, again, no intuition is given. \n- Informal statement of Theorem 1: “which we assume (1) it satisfies … and (2) it is…” —> “which we assume (1) satisfies.. and (2) is” ?\n- line 135 : “On top that ” —> “On top of that”\n- lines 142 - 161, you list examples of tasks that satisfy your assumption before introducing those models. You mention the models in section 1.1 but the reader has to wait for section 3 for those models to be clearly defined. I strongly recommend moving lines 142 to 166 to section 3. \n\nSection 2\n\n- Equation (5), what is the meaning of Unif(G) ?\n- line 187: “over the a group” —> “over a group orbit that…”?\n- line 189: Isn’t the expecation already applied through the 1/4 and the average over the group? I.e shouldn’t the equation read as 1/4(<L_u, L_v> +<L_{-u}, L_v> + ….) ?\n- line 191 : “This averaging approach allows for much greater generality” —> why ? this is not clear to me. Expand or remove.\n- line 193 - 194 : “in our examples Section 3” —> “In our examples in section 3”?\n- Generally speaking, I would recommend moving Remark 2.1. to section 3 as it does not improves readability of section 2.\n- lines 203 - 204 : “Given a group G … it turns out that ..” —> why ? again this it not rigorous.\n- lines 217 - 219: “First both the requirement of the parity…” this should go. Either you do it or don’t. But if you don’t, mentioning it reduces readability and should be considered as noise. \n- The dependence on the cardinality of the group G is quite interesting and to my opinion would deserve some additional comments. \n\nSection 3\n\n- lines 257 - 258, I would recall 189 - 190 to improve readability ?\n- line 272 : “and obtain internet new hardness results” —> Here I’m not sure what you mean\n- lines 280 - 283: your definition of the non Gaussian Analysis model is not clear/self contained. In particular what is meant by “replace the component <x, u> \\cdot u” by z\\cdot u. Is z\\cdo u an inner product ? then why not write <z, u> and if it is not, then why not write zu ? also where should one replace the component <x, u> u by zu? The model is not clearly defined. In fact, here again I would advocate less details to gain clarity on the reduced information you provide. By wanting to show more, you lose the readers on everything you want to explain. Is it really necessary to detail all the models in section 3? I would focus on one or two (and perhaps briefly indicate that it works in the other settings as well, without entering into the details)\n\nBibliography and Appendices\n\n- It is a detail but it would be convenient to add hyperlinks to the bibliographic references. \n- The references of the supplementary material do not match the references in the abbreviated paper.  \n\nAppendix A.2.\n\n- line 941. Why do you add variable v in the definition of the posterior, why not keeing u as the only variable for the planted signal?\n- line 947 : “of the loca dynamics” —> “of the local dynamics”?\n- line 971 : “one get” —> “one getS”\n- line 977: “as we elaborated in the Introduction ” —> “as we elaborated in the introduction”\n- line 980 “it is mathematical connection” —> “it is A mathematical connection”?\n- In appendix A.2. lines 937 to 973, if feel there is some confusion with the distributions. In 945 - 946 u has distribution p and v has distribution \\nu. In 957 -958, u has distribution p and v has distribution \\pi. Finally in 971-972 both u and v have distribution p.", "limitations": "see above", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- The paper engages with a subject that is particularly relevant in the current context but at this point, it lacks sufficient clarity and organization. I believe it would be more reasonable to take some time to carefully organize it and consider submitting to a journal which favors longer expositions. The main focus of the paper is the Franz Parisi criterion but this criterion is not properly introduced. The idea is great and the paper demonstrates a wide scientific culture but in order for the full depth and implications of this idea to be thoroughly understood, the foundations have to be more clear. In short, the idea is very interesting but it must be reworked (with the objective for the paper to be self contained which is currently not the case). New results are often messy and such messiness should not be a criterion for how novel and influential an idea is. That being said, communication also matters and at this point my feeling is that the structure of the paper does not facilitate a clear understanding of the idea.\nMost of the text at this point barely consists of descriptions of the formulas. Central to the generalized Franz Parisi criterion is the notion of group. But the intuition behind this novelty is never fully discussed. Another important notion which is not clearly introduced is the product <L_u, L_v>. Most of the definitions involve tuples of parameters (e.g. the Generalized Franz Paris criterion is defined with respect to a triple (q, m, epsilon)) I think it would be good to recall the meaning of those parameters from time to time in the text. E.g. In lines 107 - 109, the authors give an intuition for q.\n\n- I find it surprising that the Generalized Franz Parisi criterion is group dependent. I feel that this should be further addressed. For example in section 3 you indicate that GAM are FP hard with respect to the group Z_2. Then you say that planted sparse models satisfy assumption 1 w.r.t. the trivial group.. Perhaps I’m missing something but shouldn’t there be a relation. I.e. if a problem is hard with respect to a group, shouldn’t it be hard with respect to the other groups as well ? and if it is not the case, why?\n\n\n- I think the paper should be reorganized around a practical example such as the Gaussian additive model. At each step, one could then illustrate the different concepts based on this model. It is a bit disappointing given how important the result is and given that the main assumption of the Theorem is satisfied for those models, to not have a clear illustration with more intuition.  \n\n- The theoretical definitions 2 and 3 are interesting but better intuition should be provided", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments on the novelty of our ideas and the interdisciplinary nature of the work, and for the detailed feedback. We commit to correcting all found minor and typographic mistakes.\n\n**[1]** Several reviewers raised questions about clarity and organization. *In the revision, we will make a serious effort to reorganize the main text and the appendix, with the goal to include more details in the main text.* In particular, (1) we will move more details on the examples from the appendix to the main text, (2) we will ensure that all key assumptions and concepts are properly introduced and in a timely manner in the main body of the paper, and (3) we will also more clearly highlight our contributions compared to Bandeira et al.\n\n\nBelow are our response to reviewer’s comments and questions:\n\n\n* **``....take some time to carefully organize it and consider submitting to a journal which favors longer expositions.''** \n\nWe respectfully disagree with the reviewer’s suggestion that our work is better suited for a journal. The primary aim of our paper is to introduce a novel criterion of hardness, which is inherently speculative and exploratory in nature, to uncover a perhaps surprising equivalence of this criterion with SQ lower bounds, and to explore the implications of this connection. Our intention is to stimulate discussions within the community and to highlight the deep interconnections among different schools of thought on computational hardness in statistics and machine learning. We believe that such conceptual and thought-provoking contributions are more appropriately presented at a conference, which traditionally encourages innovative and forward-looking work, rather than in the often more formal and conclusive setting of a journal.\n\n\n* **“The main focus of the paper is the Franz Parisi criterion but this criterion is not properly introduced.”**\n\nThe Franz-Parisi criterion is introduced in Definition 1 in page 2 of our submission. We are not sure what the reviewer means with this comment.\n\n\n* **“with the objective for the paper to be self contained which is currently not the case”**\n\nIn our original submission, we made a significant effort to ensure the paper is self-contained by defining all necessary concepts and even including a clean proof of the previously established LD-SQ equivalence from Brennan et al. in Appendix B. That said, we are fully committed to carefully revisiting and rereading the manuscript, with the goal of improving the clarity of our presentation, and of adding any missing elements to further enhance its self-contained nature.\n\n\n* **“Most of the text at this point barely consists of descriptions of the formulas. Central to the generalized Franz Parisi criterion is the notion of group. But the intuition behind this novelty is never fully discussed.Another important notion which is not clearly introduced is the product $\\langle L_u, L_v\\rangle$ “** **“I find it surprising that the Generalized Franz Parisi criterion is group dependent. I feel that this should be further addressed. “**\n\nWe thank the reviewer for requesting clarification on our use of group structure in Assumption 1. To begin, we note that Assumption 1 is a deliberate relaxation: rather than requiring that $\\langle L_u, L_v\\rangle \\geq 1$ for all pairs $u, v$, it only asks that this condition holds on average over the group orbits of $u$ and $v$ (see Section 2.1 for more details).\n\nWe introduced the group-orbit version of this assumption primarily as a technical convenience in our proofs. This formulation enabled us to extend the GFP-SQ equivalence to a broader class of models. Initially, by assuming $\\langle L_u, L_v\\rangle \\geq 1$ for all $u, v$, our equivalence applied to planted sparse models and convex truncation settings. However, we later observed that using the $Z_2$-symmetric  version still allowed the proof to go through, and crucially, extended its applicability to generalized additive models (GAMs), single-index models, and non-Gaussian component analysis (NGCA) models.\n\nTo the best of our knowledge, the introduction of group symmetry in Assumption 1 currently serves as a technical tool to broaden the scope of our proof. That said, it appears to play a deep role in bridging the GFP and SQ frameworks. We therefore find this connection intriguing and believe it opens up an exciting direction for future research to understand why that is the case.\n\n\n* **\"Another important notion which is not clearly introduced is the product $\\langle L_u, L_v\\rangle$ \"**\n\nBelow Definition 1, page 2 of the paper, both the inner product between functions in $L^2(Q)$ is defined and the likelihood function $ L_u$. We had a typo in Definition 1, which we will correct in the camera-ready version of our work: by writing $\\langle L_u, L_v\\rangle$, we meant to write $\\langle L_u, L_v\\rangle_Q$. Please let us know if you need any further clarification on this.\n\n\n* **“Most of the definitions involve tuples of parameters (e.g. the Generalized Franz Paris criterion is defined with respect to a triple (q, m, epsilon)) I think it would be good to recall the meaning of those parameters from time to time in the text. E.g. In lines 107 - 109, the authors give an intuition for q”**\n\nWe mention the interpretation of the parameters multiple times in the paper (e.g., lines 78-86, 107-109, 120-123 in the first four pages). We will carefully read the paper and add any further remarks on this topic that we can in our camera-ready version of the paper.\n\n\n\n* **“I think the paper should be reorganized around a practical example such as the Gaussian additive model.”**\n\nWe thank the reviewer for this suggestion.\n\nIn our examples section, we begin with generalized additive models (GAMs) because they are among the simplest cases and have already been carefully analyzed in the prior work on the FP-criterion, particularly by Bandeira et al. (2022). There, we include an explanation of why our GFP-SQ equivalence applies in the setting of all GAMs, which reduces to a straightforward calculation, meaning that for whichever GAM one knows the SQ-hardness prediction, the GFP-hardness prediction is (essentially) the same. For added pedagogical clarity, we are happy to incorporate an earlier remark in the paper referencing a specific GAM example—such as tensor PCA—and explicitly illustrating how the GFP, FP, and SQ criteria align in their hardness predictions for that model.\n\nThat said, we respectfully disagree with the suggestion to reorganize the paper entirely around such an example. Several prior works (e.g., Kunisky et al. (2019), Brennan et al. (2021), Bandeira et al. (2022)) have already provided detailed calculations of how the LD-, SQ-, and FP-criteria apply to many of these models, including GAMs. Given the space constraints of a 9-page main paper, we believe our focus should remain on the GFP criterion itself—its precise formulation, novel contributions, and broad applicability.\n\n\n* **“The theoretical definitions 2 and 3 are interesting but better intuition should be provided”**\n\nDefinition 3 corresponds to the classical SDA hardness criterion, as introduced in Feldman et al. (2017) and further developed in Brennan et al. (2021). Moreover, our Definition 2 of GFP-hardness represents the main contribution of this work. We devote significant discussion to this new criterion, establish its equivalence with the SQ framework, and provide an example that highlights its separation from the FP definition proposed by Bandeira et al. (2022). Let us know if you need us to provide more details.\n\n\n* **Lines 65-67, The likelihood ratio should be properly introduced. I strongly encourage a complete introduction such as in e.g. Kunisky et al. ... I also encourage mentioning the annealed upper bound (and its connection to the FP potential) in the main paper.**\n\nWe are happy to include more details of $L_u$ and its definition in the appendix of the paper. However, we respectfully disagree with the reviewer that these standard arguments---such as those thoroughly covered in the survey by Kunisky et al., or the annealed bound already explained in Bandeira et al. (2022)---belong in the main body of our paper, given the strict 9-page limit of the conference format.\n\n\n* **\"The dependence on the cardinality of the group G is quite interesting and to my opinion would deserve some additional comments.\"**\n\nThis arises as a technical consequence of certain Hölder inequality bounds used in our proofs. While we don’t think the group $G$ should be present in an optimized version of our equivalence results, notice that it is rather benign in all our applications, as in all examples $|G|$ is either $1$ or $2$."}, {"review_id": "awa0RfoYSg", "reviewer": "Reviewer_NyN2", "summary": "The paper studies information-computation tradeoffs in the context of SQ lower bounds and the Franz-Parisi (FP) criterion. According to the FP criterion (inspired by work from statistical physics) a hypothesis testing problem of distinguishing between a null hypothesis and another distribution family ${P_v}$ parameterized by a (random according to some prior) vector is called FP-hard (with parameters $m,q,\\epsilon$) if the average inner product of m-sample likelihood ratios between two members $P_u,P_v$ of the alternative distribution family, where the average is over the a \"typical\" region for the inner product of $u$ and $v$ is upper bounded by $1+\\epsilon$. Prior work (e.g., Bandeira et al. 2022) showed that FP-hardness captures SQ-hardness (in both directions) for Gaussian additive models, and partially for sparse planted models, but also gave counterexamples where the equivalence fails. The present paper proposes a Generalized Franz-Parisi (GFP) criterion. The modification, provided in Definition 2 consists of relaxing the notion of \"typical\" event to use a more general condition instead of the standard inner product. The paper shows that this is now is equivalent to bound on the Statistical Query dimension. The result relies on an assumption (Assumption 1) which is a correlation condition  required to hold over a group that preserves the prior distribution.\n\nThe main equivalence theorem comes in two steps where the authors first show that the \"typical\" event in the GFP criterion takes a specific form, and then show that the resulting simplified form of the GFP criterion is equivalent to bound on the SQ dimension bound. The combination yields the main result in Theorem 3. The final result also requires the hypothesis problem to be have information-theoretic optimal sample complexity that is lower bounded. A convenient simplified version of the theorem is that if the problem requires $m = \\omega(\\log n)$ samples information-theoretically, then super-polynomial SQ lower bounds are equivalent to GFP hardness with $q$ (the proxy for runtime) being super-polynomial.\n\nFinally, the paper demonstrates that several well-studied statistical models satisfy the correlation assumption, hence the equivalence applies. These include:\n\n- Gaussian additive models\n- Planted sparse models (which includes Gaussian sparse regression, sparse phase retrieval  and sparse PCA) for which the authors show new SQ and GFP-hardness results.\n- Non-Gaussian component analysis to which many statistical problems like GMMs estimation and robust mean/regression are reducible to\n- Single index models\n- Gaussian convex truncation models, for which the paper shows a connection to the correlation inequality for convex bodies in probability theory", "questions": "Is there any intuition for understanding the role of $k$ in Assumption 1?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n- There’s significant ongoing interest in characterizing computational-statistical tradeoffs, and this paper builds meaningfully on that direction.\n- The generality of the main result is a positive aspect of the paper. Also the paper includes several applications and examples/counter examples to demonstrate why assumptions are needed.\n\nWeaknesses:\n\n- All of the technical work is deferred to the appendix, which makes the main body feel light and the appendix a bit dense.\n\nOverall, I do not have any major concerns about the paper and I would recommend acceptance.", "was_revised": true, "final_justification": "The authors have provided clear explanations to my points. After reviewing the other rebuttals and discussions my view of the paper remains positive, I thus keep my original score.", "rebuttal": "We thank the reviewer for their time in reviewing our work and overall positive feedback.\n\n\n* **All of the technical work is deferred to the appendix, which makes the main body feel light and the appendix a bit dense.**\n\nWe will reorganize the paper a bit and make an effort to include more details in the main text. See comment **[1]** in response to Reviewer Nb5E.\n\n\n* **Is there any intuition for understanding the role of $k$ in Assumption 1?**\n\nThe reason is highly technical. In short, the proof of the equivalence proceeds by an appropriate Taylor expansion of functions of $\\langle L_u,L_v \\rangle$ and hence boils down to controlling all moments of $\\langle L_u,L_v \\rangle$. Assumption 1 allows us to work around a critical such bound. Note that in our applications, $G$ is either the trivial group or $Z_2$ and it is sufficient to check this inequality for $k=1$, as explained in Remark 2.1."}, {"review_id": "LiqqS6qR3M", "reviewer": "Reviewer_sUVK", "summary": "The paper explores the computational hardness of statistical inference problems. The paper extends the Franz--Parisi criterion to rigorously characterize hardness beyond the class of Gaussian additive models which was the focus of the existing work. The paper defines a generalized notion of the Franz--Parisi criterion that classifies SQ hardness in a broad class of models beyond the Gaussian additive models.", "questions": "1. Is there some intuition why the annealed Franz--Parisi potential is the right object to look instead of the quenched one? It seems possible that in the regimes of parameters than you can show or disprove hardness might coincide with the regimes that quenched and annealed quantities are the same. \n\n2. In what sense is the generalized notion of the GFP hardness optimal? Is it true that if GFP hardness fails, then we also get the absence of SQ hardness? A nice example of the failure of FP criterion to detect SQ hardness is explained in section 4. Is a similar example known if GFP hardness fails to detect hardness in a problem. \n\n3. Is there a simple explanation on how the two notions of hardness in Theorem 2 and Theorem 3 equivalent. Namely the second point makes it a bit hard to parse how the second notion of hardness implies the first due to the extra conditions that appear in the second point. \n\n4. How important is the criterion that $u$ is supported on the sphere on line 55? Is it because if we weakened this condition, then the overlap is not the only quantity we care about, but also the norm of both $u$ and $v$? If that is the case, can we get similar results if we consider the normalized overlap $\\frac{\\langle u, v \\rangle}{\\|u\\| \\|v\\|}$ in FP/GFP hardness?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The main body of this paper provides a nice preview and overview of the original Franz--Parisi criterion and its generalization. However, the nature of the paper is quite technical and much of the proofs are deferred to the appendices. The paper does a adequate job motivating the results and the intuition behind the assumptions, but the constraint on page limit means that the explanations are brief. The appendices are referenced several times in the main body, and perhaps a precise pointer to the relevant section of the appendices to help readers jump to the relevant section. \n\nThe connection to detection problems is quite remarkable, as typically from the statistical physics point of view this involves an understanding of the fluctuations. The link with the Franz--Parisi potentials and detection is not obvious at all. The original paper by Bandeira et al is of great importance and this follow-up paper is a strong continuation of this line of work. So although this connection is not new and was established in the earlier work, the extension to statistical query is new and quite interesting as well. The generalization beyond Gaussian additive models is also very powerful.", "was_revised": true, "final_justification": "I believe this work is a nice improvement over the original paper that introduced Franz--Parisi hardness criterion. The paper is a bit dense and a lot of the technical results and explanations are deferred to the appendices. I keep my rating as is.", "rebuttal": "We are grateful to the reviewer for the positive and encouraging feedback on our work.\n\n* **Is there some intuition why the annealed Franz-Parisi potential is the right object to look instead of the quenched one? It seems possible that in the regimes of parameters than you can show or disprove hardness might coincide with the regimes that quenched and annealed quantities are the same.**\n\n​​We thank the reviewer for this insightful question. Unfortunately, for both the FP criterion and our newly introduced GFP criterion, we are not aware of any alternative explanation for why the annealed FP criterion agrees with the LD/SQ lower bounds, beyond going through the proof itself. We believe that establishing a connection to a criterion based on the *quenched* FP potential is a highly intriguing direction for future research, which we are actively investigating. For this reason, we highlight it as one of the main open questions in the conclusion of our paper.\n\n\n* **In what sense is the generalized notion of the GFP hardness optimal? Is it true that if GFP hardness fails, then we also get the absence of SQ hardness? A nice example of the failure of FP criterion to detect SQ hardness is explained in section 4. Is a similar example known if GFP hardness fails to detect hardness in a problem.**\n\nOur main result shows that, under Assumption 1 and assuming the model of interest has a non-trivial information-theoretic threshold, the SQ and GFP hardness criteria are equivalent. If either of these assumptions is removed, we provide counterexamples in Appendix A3, which (if we understand the question of the reviewer correctly) also provide the requested examples for the reviewer. Specifically, when the problem has a trivial samplewise information-theoretic threshold (e.g., planted clique), the SQ criterion is folklore known to fail to predict hardness correctly, while the GFP criterion gives the correct prediction of hardness (see Appendix A.3.1. for details of such an example). Conversely, if Assumption 1 does not hold, we construct an example where the SQ criterion gives the correct prediction of hardness but the GFP criterion does not (see Appendix A.3.2. for details). Let us know if you need further details on this. We will elaborate more on this in the camera-ready version of our work.\n\n\n* **Is there a simple explanation on how the two notions of hardness in Theorem 2 and Theorem 3 equivalent. Namely the second point makes it a bit hard to parse how the second notion of hardness implies the first due to the extra conditions that appear in the second point.**\n\nWe are not entirely certain what the reviewer's question refers to specifically, but we will do our best to further elaborate on Theorems 2 and 3 and their roles. Please let us know if this does not fully address your concerns.\n\nTo clarify, Theorems 2 and 3 are intermediate steps in establishing the equivalence between GFP-hardness and SQ-hardness. Specifically:\n1. *Theorem 2* shows that GFP-hardness is equivalent to a specialized version of GFP-hardness defined with respect to a particular type of event $A$.\n2. *Theorem 3* then proves that this specialized version is, in turn, equivalent to SQ-hardness.\n\nThat said, both theorems rely on a set of technical assumptions that must be satisfied for the total equivalence to hold. We suspect that the number and nature of these assumptions may have caused some confusion, so we summarize and clarify them below, along with why they are reasonable in practice:\n1. *CDF Condition and Parity of m:* We assume that  $1 - q^{-2}$ lies in the image of the CDF of $\\pi^2$, and impose a condition on the parity of $m$. Both are purely technical, and we expect that our results can be generalized to remove them — see Remark 2.2 for further discussion.\n2. *Bounded Group Size and 1-sample Chi-Squared Divergence:* We assume that  $|G| = O(1)$ and $m \\cdot \\chi^2(P, Q) = O(1)$. These conditions are satisfied in all natural examples we consider — see again Remark 2.2.\n3. *Bounded Chi-Squared Divergence with $m_{IT}$ Samples:* We assume that  $\\chi^2$ remains $O(1)$ when using $m_{\\text{IT}}$ samples. As discussed below Theorem 2, one should think of  $m_{\\text{IT}} \\sim \\log n$, which holds for all examples presented in our paper. Moreover, Appendix A.3.1 shows that this condition is *necessary* for the equivalence, based on a counterexample using the planted clique model.\n4. *Large Enough $q$:* We assume $q > m^{m_{IT}}$ . In our context,  $q$ corresponds to a “runtime” bound, which is typically taken to be exponential in $n$. Since $m_{IT} \\sim \\log n$, this condition is typically satisfied in all our examples.   \n\n\n\n* **How important is the criterion that  is supported on the sphere on line 55? Is it because if we weakened this condition, then the overlap is not the only quantity we care about, but also the norm of both $u$  and $v$? If that is the case, can we get similar results if we consider the normalized overlap $\\langle u,v\\rangle /|u| |v|$  in FP/GFP hardness?**\n\nIndeed, we adopted the assumption that the parameter lies on the sphere primarily to simplify notation when comparing our GFP-hardness criterion to FP-hardness; it is not required for the GFP-to-SQ hardness equivalence. However, for FP-hardness, the assumption does play a role. In fact, Bandeira et al. (2022) assume that the parameter has a bounded norm in their proof of the FP-to-LD hardness equivalence, where this assumption is essential for their proof of equivalence to work. We will clarify this point and add a corresponding remark in the revised version of the paper."}, {"review_id": "iEatz9p6lE", "reviewer": "Reviewer_MCz7", "summary": "This manuscript refines the Franz–Parisi (FP) geometric criterion for average-case computational hardness in high-dimensional inference. The authors introduce a Generalized FP (GFP) criterion that optimizes the choice of “overlap” event and prove an equivalence between GFP-hardness and Statistical-Query (SQ) lower bounds under a mild symmetry assumption . The equivalence is shown to hold for a broad family of detection problems.", "questions": "* Title and scope. Will the authors consider adding “Detection” to the title and a short paragraph contrasting annealed FP (detection) with quenched FP (estimation)?\n\n* Clarifying the leap beyond Bandeira et al. Can the authors provide an explicit toy model (in addition to the Section 4 construction) where overlap-based FP passes but GFP detects hardness, and explain the geometric intuition? ALso, in all the exampel provided, can they explain if Bandeira et al applied or fail?. Beyond the Section 4 Rademacher-product example, are there natural models (e.g. permutation-invariant priors) where |〈u,v〉| is irrelevant yet Assumption 1 holds? Including one would strengthen claims of generality.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Conceptual advance. Optimizing the overlap event yields a unified hardness criterion that aligns with SQ lower bounds across many canonical detection tasks; this is theoretically neat and practically useful for researchers who favour the SQ framework and unite it with the low degree approach\n- Broad theoretical applicability. The mild group-symmetry assumption is verified for several popular models (GAMs, sparse PCA, NGCA, single-index, convex truncation), demonstrating real scope.\n- Illustrative counter-example. Section 4 convincingly shows that GFP can succeed where the classical FP criterion misfires, underlining that the refinement is substantive.\n\nWeaknesses\n\nEssentially, the paper is not easy not read, and a lot can be done to enhance clarity:\n\n- Detection vs Estimation not foregrounded. The work targets detection tasks, whereas the original Franz–Parisi potential in physics predicts hardness of estimation. Although this is stated in the abstract, the title and early sections still refer generically to “Franz–Parisi” and \"Hardness\" which risks confusion. I suggest amending the title (e.g. “An Optimized Franz–Parisi Criterion for Detection”) and maybeadding a short subsection that contrasts annealed FP (used here) with the quenched/estimation version (used in physics and in AMP)?\n\n- Relation to Bandeira et al. (2022) under-explained. Section 4 asserts that GFP and FP diverge, but the presentation is terse and the reader is left unsure why Bandeira’s overlap-based criterion fails in the constructed model. A crisper comparison—perhaps tabulating the two notions side-by-side and walking through a minimal counter-example—would better highlight the novelty. It weould be really a plus in the paper to have more concrete, worked-out examples. The paper claims GFP handles cases where “overlap” is meaningless, yet only one synthetic example is detailed. Additional, simpler examples (even toy 1-D priors) illustrating how the optimized event departs from |〈u,v〉| ≤ ε would help readers grasp the intuition and appreciate originality beyond a minor improvement of Bandeira.\n\nSide note: Additional related-work gap (single-index models).\nIn discussing the single-index model, the authors cite only Ref. [11] for the characterization of the easy (GE = 1) and hard (GE = 2) phases. Yet these phase diagrams were established several years earlier in two independent lines of work:\n• J. Barbier, F. Krzakala, N. Macris, L. Miolane & L. Zdeborová, Optimal errors and phase transitions in high-dimensional generalized linear models, PNAS 116 (2019): 5451 – 5460.\n• M. Mondelli & A. Montanari, Fundamental limits of weak recovery with applications to phase retrieval, 2018.", "was_revised": true, "final_justification": "This paper introduces a refined Franz–Parisi criterion that, by optimizing the overlap event, aligns with SQ hardness and corrects cases where the classical FP criterion fails. The rebuttal clarified the relation to Bandeira et al. (2022), addressed the detection vs. estimation scope, and committed to adding missing references and improving clarity. While additional examples would further enhance intuition, the conceptual advance and broadened applicability are clear. Overall, I find the contribution solid, original, and impactful, and I recommend acceptance.", "rebuttal": "We thank the reviewer for their positive comments on the conceptual value and the broad applicability of our work.\n\n\n* **“Essentially, the paper is not easy not read, and a lot can be done to enhance clarity: Detection vs Estimation not foregrounded. The work targets detection tasks, whereas the original Franz–Parisi potential in physics predicts hardness of estimation. Although this is stated in the abstract, the title and early sections still refer generically to “Franz–Parisi” and \"Hardness\" which risks confusion. I suggest amending the title (e.g. “An Optimized Franz–Parisi Criterion for Detection”) and maybe adding a short subsection that contrasts annealed FP (used here) with the quenched/estimation version (used in physics and in AMP)?”**\n\nWe commit to revising the paper to improve as possible its readability and ensure that the scope and significance of our results are clearly stated. (See comment **[1]** in the response to Reviewer Nb5E)\n\n*Detection vs Estimation:* We respectfully disagree that the “estimation versus detection” discrepancy between the classical use of the FP potential for estimation and the detection settings we study is not foregrounded. Very early in the introduction, we comment exactly on this (Lines 40 to 51): *``Given this context, a natural question arises: can one formally connect these two seemingly distinct approaches? At first glance, the answer appears negative, due to a fundamental mismatch in scope. Statistical physics techniques are primarily geared toward estimation problems, where the goal is to recover a hidden signal, while the rigorous frameworks discussed above—such as LD and SQ lower bounds—are focused on detection or hypothesis testing.’’*\nWe also highlight that this distinction is a central theme already extensively discussed allso in the work of Bandeira et al. (as we mention on lines 46- 47). \n\n\n*Quenched vs Annealed:* Now, we would also like to note that we discuss in detail the distinction between annealed and quenched version of the FP potential, along with their connection to statistical physics in our Appendix A.2. Yet, this material is not novel as it is already almost identically discussed in Bandeira et al ‘2022 – for this reason it was placed in the appendix primarily because of limited space. That said, we agree that the distinction should be more visible in the main body of the paper and will revise the introduction to include a clearer reference to this appendix—beyond the current brief mention on Lines 61–62—along with a concise summary of the annealed vs. quenched distinction.\n\n\n*Title:* Regarding the title: while the Franz-Parisi potential has traditionally been used in the context of estimation, the “Franz-Parisi criterion” is already formulated only for detection problems in Bandeira et al (2022). For this reason, we do not believe it is necessary to further specify “detection” in the title, which is already quite long. Throughout the paper, we make a careful distinction between the Franz-Parisi criterion and the Franz-Parisi potential, and we define our hardness notion through our generalized FP criterion. We will double-check the manuscript to ensure this distinction is clearly and consistently maintained.\n\n\n* **Relation to Bandeira et al. (2022) under-explained. Section 4 asserts that GFP and FP diverge, but the presentation is terse and the reader is left unsure why Bandeira’s overlap-based criterion fails in the constructed model. A crisper comparison—perhaps tabulating the two notions side-by-side and walking through a minimal counter-example—would better highlight the novelty. It weould be really a plus in the paper to have more concrete, worked-out examples. The paper claims GFP handles cases where “overlap” is meaningless, yet only one synthetic example is detailed. Additional, simpler examples (even toy 1-D priors) illustrating how the optimized event departs from $|\\langle u , v \\rangle | \\leq \\varepsilon$ would help readers grasp the intuition and appreciate originality beyond a minor improvement of Bandeira.**\n\n\nThe reason our counterexample in Section 4 works to separate the GFP-hardness versus FP-hardness is because the GFP-optimal overlap $\\langle L_u,L_v \\rangle$ (per Theorem 2) in this model is *not* a function of the overlap $\\langle u,v \\rangle$. It is this property that causes the FP criterion to fail in this setting, as we explain in the first paragraph of Section 4. We agree that an even simpler separation would be even better, but this was the simplest counterexample we could construct, as most “easy” or lower-dimensional examples (such as 1-d) end up with the overlap $\\langle L_u,L_v \\rangle$ being a function of $\\langle u,v \\rangle$.\n\nThat being said, we strongly disagree with the reviewer deeming our work a minor improvement of Bandeira et al (2022) from multiple viewpoints. Besides that optimizing the event is an important conceptual advancement to the FP-criterion, which provably corrects it in some cases (such as the model in Section 4), our approach has value when seen also purely as a proof technique as well (independently if FP- and GFP-hardness disagree or not). Specifically it is only under introducing this optimization step that the resulting GFP-hardness can be proven to be equivalent to SQ-hardness for models going well beyond the GAMs that Bandeira et al argued about: including single-index models, NGCA models, planted sparse models and more. This step therefore, greatly expands the scope of this connection between physics-based notions of hardness and TCS notions of hardness.\n\n\n* **Side note: Additional related-work gap (single-index models). In discussing the single-index model, the authors cite only Ref. [11] for the characterization of the easy (GE = 1) and hard (GE = 2) phases. Yet these phase diagrams were established several years earlier in two independent lines of work: • J. Barbier, F. Krzakala, N. Macris, L. Miolane & L. Zdeborová, Optimal errors and phase transitions in high-dimensional generalized linear models, PNAS 116 (2019): 5451 – 5460. • M. Mondelli & A. Montanari, Fundamental limits of weak recovery with applications to phase retrieval, 2018.**\n\n\nWe thank the reviewer for providing this reference. We will further add additional references for each model. Note that to the best of our knowledge, reference [11] is the paper that defined the generative exponent for single index models (as the first non-zero coefficient in the Hermite expansion of the likelihood ratio).\n\n\n\n* **Clarifying the leap beyond Bandeira et al. Can the authors provide an explicit toy model (in addition to the Section 4 construction) where overlap-based FP passes but GFP detects hardness, and explain the geometric intuition? ALso, in all the exampel provided, can they explain if Bandeira et al applied or fail?. Beyond the Section 4 Rademacher-product example, are there natural models (e.g. permutation-invariant priors) where $| \\langle u,v \\rangle |$ is irrelevant yet Assumption 1 holds? Including one would strengthen claims of generality.**\n\n\n\nBandeira et al showed equivalence between FP-hard and LD-hard for GAMs, and an one-sided implication for Planted Sparse Models where FP-hard implies LD-hard. By equivalence of LD-hard and SQ-hard for noise-robust models, this can be shown to imply equivalence between FP-hard and LD-hard for GAMs, and that FP-hard implies SQ-hard for some noise robust Planted Sparse Models.\n\nIn contrast, here, we show equivalence of GFP-hard with SQ-hard for GAMs (by a direct proof),  all Planted Sparse Models (here equivalence instead of one-sided implication), all NGCA, all Single-Index models, and all Gaussian convex truncation models. We believe that our results extend well beyond these examples and that this equivalence can be applied to a wide variety of other problems as well.\n\nAbout the request of the reviewer for more natural examples compared to Section 4’s counterexample, we do not yet have such an example. Yet, we want to point out that many planted signal models exhibit geometric structures that differ substantially from simple Euclidean overlap $\\langle u,v \\rangle$, hence, we strongly believe that many such natural examples should exist. For example, in multi-index models, the signal u is an orthogonal matrix. The natural notion of overlap in this case is the Gram matrix $u^T v$, and not for example, their scalar Frobenius inner product. We are actively working on extending our results (and specifically Assumption 1) to apply also for such examples and hope to include additional such applications in the camera-ready version."}, {"review_id": "bOtspoDcf3", "reviewer": "Reviewer_g7yN", "summary": "This work takes a significant step toward unifying methods for predicting computational hardness in high-dimensional hypothesis testing. The basic setting is as follows. the goal is to distinguish between a family of planted distributions $\\mathcal{P} = \\\\{P_u^{\\otimes m} \\mid u \\in \\Theta_n\\\\}$ and $\\mathcal{Q} = Q^\\{\\otimes m\\}$, where m denotes the number of samples and we implicitly consider a sequence of hypothesis testing problems indexed by the data dimension (or instance size) parameter $n$. Note that by assuming a prior $\\pi$ over the parameter space $\\Theta_n$, the testing effectively becomes a (high-dimensional) simple vs simple testing problem for which likelihood ratio traditionally plays a central role.\n\nThere has been a growing recognition that many techniques for predicting computational hardness are closely related, as they rely on common intermediate quantities derived from the likelihood ratios $L_u = P_u/Q$. However, formal connections between these approaches have only recently begun to be established, with the first such unification appearing in the work of Brennan et al. (2021).\n\nThis work represents the latest coordinated effort toward unification, this time building connections between the Franz-Parisi potential heuristic from statistical physics and statistical query (SQ) lower bounds from learning theory. In particular, the authors introduce the generalized Franz-Parisi (GFP) criterion and establish its equivalence to a notion of statistical dimension for SQ algorithms, which provides a sufficient (though not necessary) condition for SQ hardness. The criterion is \"generalized\" because the authors demonstrate that the original FP criterion, introduced in previous work, is overly conservative in its predictions of computational hardness.\n\nThe established equivalence also enables a straightforward proof of a new SQ lower bound for the convex truncation problem.", "questions": "1. What should one conclude if Assumption 1 does not hold and the GFP and SQ criteria give different predictions of hardness? Which one is a more reliable indicator of computational hardness when equivalence breaks down?\n2. The example illustrating the necessity of Assumption 1 in Section A.3.2 appears to be missing some important details. In particular, is there a constraint on the parameters for the planted distributions $P_u$ that ensures the example works as intended?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. **Building bridges between fields that speak different technical languages.** This work situates the GFP criterion within its historical context in statistical physics. By establishing the GFP-SQ equivalence, it connects statistical physics and learning theory, fostering the cross-pollination of intuitions and ideas between these fields.\n2. **Simplicity and elegance of the GFP criterion.** The GFP criterion introduced by the authors is a simple, elegant quantity that formalizes a hunch shared by many experts: that existing notions of computational lower bounds, while technically defined differently, largely feel similar in spirit and appear to be different shades of the same \"hardness core.\" By formally establishing the equivalence between GFP and SQ, the work provides a satisfying justification for these intuitions.\n3. **Clear and well-organized exposition.** The clear and well-structured exposition makes the main results accessible and allows readers from diverse backgrounds to follow the technical developments.\n\n### Weaknesses\n\n1. **Statistical dimension does not characterize SQ hardness.** The statistical dimension-based criterion is conservative and often predicts problems as \"not hard\" even when they are, in fact, hard for SQ algorithms. In other words, statistical dimension (Definition 3) provides is a sufficient but not necessary condition for SQ hardness, as noted in [Brennan et al., 2021, Appendix B]:\n    \n    > *However, since SDA is **not** a characterization for VSTAT …*\n    > \n    \n    Hence, referring to Definition 3 as \"SQ hardness\" can be misleading, especially for readers who may not be aware of this subtlety.\n    \n    I suspect that exponentially thin Gaussian pancakes may provide yet another example of the aforementioned gap between statistical dimension and SQ hardness. Notably, Diakonikolas et al. (2024) demonstrated that even pancakes with zero thickness remain SQ-hard.\n    \n2. **The role of GFP in the equivalence.** The $\\rho_G$-FP criterion appears to be the main workhorse in establishing the equivalence to SQ. Is there reason to believe that GFP is a more fundamental quantity? I agree that the $\\rho_G$ criterion seems somewhat ad hoc, as multiple symmetry groups $G$ can correspond to the same high-dimensional testing problem $(\\mathcal{P}, \\mathcal{Q})$, each giving rise to a different notion of the \"overlap potential\" $\\rho_G$.\n\n**References**\n\n- Ilias Diakonikolas, Daniel Kane, Lisheng Ren, Yuxin Sun. SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions. *NeurIPS* 2024.", "was_revised": true, "final_justification": "Rating remains the same. Reasons are provided in my response to the authors' rebuttal.", "rebuttal": "We thank the reviewer for the positive comments on the unification character of our work and our exposition.\n\n\n* **Statistical dimension does not characterize SQ hardness. The statistical dimension-based criterion is conservative and often predicts problems as \"not hard\" even when they are, in fact, hard for SQ algorithms. In other words, statistical dimension (Definition 3) provides is a su!cient but not necessary condition for SQ hardness, as noted in [Brennan et al., 2021, Appendix B]: However, since SDA is not a characterization for VSTAT … Hence, referring to Definition 3 as \"SQ hardness\" can be misleading, especially for readers who may not be aware of this subtlety. I suspect that exponentially thin Gaussian pancakes may provide yet another example of the aforementioned gap between statistical dimension and SQ hardness. Notably, Diakonikolas et al. (2024) demonstrated that even pancakes with zero thickness remain SQ-hard.**\n\nThis is indeed an important point, and we will make sure to clarify and add comments at multiple places in the text. We will make sure to consistently use the term “SQ-hardness criterion” when referring to the SDA dimension bounds. Of course, the reviewer is correct that an SDA bound is a sufficient condition for SQ-hardness, but not necessary, in the same way the LD-hardness criterion (i.e., LDR bound) criterion is a sufficient but not necessary condition for the failure of low-degree polynomials to achieve strong separation. \n\n\n\n* **The role of GFP in the equivalence. The $\\rho$-FP criterion appears to be the main workhorse in establishing the equivalence to SQ. Is there reason to believe that GFP is a more fundamentalquantity? I agree that the criterion seems somewhat ad hoc, as multiple symmetry groups can correspond to the same high-dimensional testing problem , each giving rise to a different notion of the \"overlap potential\" .**\n\nThis is a valuable point. First, we note that the two formulations are equivalent under Theorem 2. We chose to emphasize the optimization-based viewpoint because it more clearly illustrates how our generalized GFP-hardness extends the FP-hardness criterion of Bandeira et al. into a variational framework. This formulation also makes the conceptual advancement more explicit.\n\nMoreover, at least at present, the overlap quantity $\\rho_G$ lacks a clear algorithmic interpretation (as we also mention in the Conclusion), and, as the reviewer noted, it may appear somewhat ad hoc. For this reason, we currently prefer to treat $\\rho_G$-FP​ as a technical intermediate step rather than the central definition of our framework.\n\nThat said, we agree it would be exciting to further explore whether $\\rho_G$ carries meaningful algorithmic implications—particularly in relation to local search, landscape geometry, or other structural properties of the underlying models. We see this as a promising direction for future work and that is why we ask it as one of our main questions in the conclusion of the paper."}]

Author rebuttal:

Meta-review: This paper introduces a generalized Franz–Parisi criterion and proves its equivalence with Statistical Query lower bounds under mild assumptions. This provides a rigorous bridge between physics-inspired heuristics and formal complexity theory, clarifying the computational limits of a wide class of planted models. Reviewers praised the work as a substantial conceptual advance, technically strong and broadly relevant, with several noting its originality and potential to influence both statistical physics and theoretical machine learning.

Some reviewers found the exposition dense and the positioning with respect to prior work insufficiently sharp. In rebuttal the authors committed to significant reorganization, more intuitive examples, and clarification of technical points. Reviewers acknowledged these efforts, and the consensus remained strongly positive.

Given the combination of conceptual depth, breadth of applicability, and clear relevance across communities, I view this as an outstanding contribution. Despite its demanding presentation, the work stands out in both originality and impact, and I recommend acceptance as an oral.

[SAC edit]
This is indeed a very strong contribution that tackles a relevant problem and establishes an important bridge between two methods belonging to two different domains (and communities). It is thus of wide interest (amongst the theory community) and with potential high impact. Oral presentation is recommended.
Decision: Accept (oral)