An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds

We thank the reviewer for their positive comments on the conceptual value and the broad applicability of our work.

• “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)?”

We 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)

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.’’ We 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).

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.

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.

• 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.

The 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$.

That 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.

• 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.

We 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).

• 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.

Bandeira 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.

In 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.

About 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.

We thank the reviewer for the positive comments on the unification character of our work and our exposition.

• 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.

This 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.

• 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" .

This 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.

Moreover, 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.

That 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.

We thank the reviewer for their time in reviewing our work and overall positive feedback.

• All of the technical work is deferred to the appendix, which makes the main body feel light and the appendix a bit dense.

We 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.

• Is there any intuition for understanding the role of $k$ in Assumption 1?

The 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.

We are grateful to the reviewer for the positive and encouraging feedback on our work.

• 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.

​​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.

• 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.

Our 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.

• 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.

We 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.

To clarify, Theorems 2 and 3 are intermediate steps in establishing the equivalence between GFP-hardness and SQ-hardness. Specifically:

1. 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$.
2. Theorem 3 then proves that this specialized version is, in turn, equivalent to SQ-hardness.

That 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:

1. 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.
2. 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.
3. 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.
4. 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.

• 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?

Indeed, 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.

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.

[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.

Below are our response to reviewer’s comments and questions:

• ``....take some time to carefully organize it and consider submitting to a journal which favors longer expositions.''

We 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.

• “The main focus of the paper is the Franz Parisi criterion but this criterion is not properly introduced.”

The 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.

• “with the objective for the paper to be self contained which is currently not the case”

In 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.

• “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. “

We 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).

We 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.

To 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.

• "Another important notion which is not clearly introduced is the product $\langle L_u, L_v\rangle$ "

Below 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.

• “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”

We 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.

• “I think the paper should be reorganized around a practical example such as the Gaussian additive model.”

We thank the reviewer for this suggestion.

In 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.

That 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.

• “The theoretical definitions 2 and 3 are interesting but better intuition should be provided”

Definition 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.

• 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.

We 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.

• "The dependence on the cardinality of the group G is quite interesting and to my opinion would deserve some additional comments."

This 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$.