Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The author(s) introduce a new "Franz-Parisi criterion" for predicting computational hardness in certain types of hypothesis testing problems, where the goal is to distinguish a mixture model with a random planted signal u from a null reference distribution. The criterion is, on one hand, a restriction of the second moment of the likelihood-ratio statistic to pairs of planted signals u,v having "typical" overlap under their prior. On the other hand, it is way of quantifying the growth/decay behavior of an annealed approximation to the Franz-Parisi potential locally around the overlap delta = 0. The authors posit that if this FP-criterion, when restricted to a range of overlaps (-delta,delta) having probability 1-e^{-D_n} for D_n growing slowly with n, is O(1) or 1+o(1), then this provides evidence for computational hardness of strong detection or weak detection respectively in the testing problem.

To support this claim, a number of interesting results are shown rigorously about this criterion:
(1) In a Gaussian additive model which includes spiked matrix and spiked tensor problems with Gaussian noise, it is shown that the FP criterion may be upper and lower bounded by the low-degree likelihood-ratio, up to the degree D_n modulo logarithmic factors. In certain relevant asymptotic regimes, this implies that FP's indication of hardness is equivalent to the low-degree method (which is believed to characterize the sharp threshold for hardness in many of these problems), and it establishes a new connection between the low-degree method and more geometric notions of overlap.
(2) Under an additional symmetry assumption for the Gaussian additive model, it is shown that FP-hardness formally implies a free energy barrier in the posterior distribution of the planted signal, which in turn implies a hitting time lower bound for MCMC algorithms having sufficiently "local" moves. Coupled with the above result, this provides a new method for showing hardness results for local MCMC algorithms using the low-degree approach.
(3) One direction of the above equivalence, that FP-hardness implies low-degree hardness, is shown also for a different class of planted sparse models satisfying a certain symmetry of the planted distribution. This implication is used to establish low-degree-hardness of detection in a sparse linear regression model, up to an sparsity-undersampling threshold curve that appears to be sharp in the studied regime, by bounding a conditional low-degree second-moment via the corresponding conditional FP-criterion.

Outside of the above settings, a discussion of some insightful counterexamples is also provided, where the FP criterion (or overlap-gap-based criteria in general) does not seem to accurately predict hardness of the testing problem.
strengths_and_weaknesses: I find the paper to be very interesting, and am strongly supportive of its publication in NeurIPS. Some of the insights are:

(1) An annealed approximation to the Franz-Parisi free energy admits a second-moment type interpretation, and connects to the classical second-moment method in testing.
(2) A formal connection can be shown between restricting the geometric overlap and restricting the polynomial degree in the second-moment method. This seems to be particularly surprising in the planted sparse model setting of Section 3 where there is no explicit form for the low-degree likelihood ratio in terms of the overlap, and where the implication is shown from a symmetry condition alone.
(3) The connection can be used in both directions, to provide geometric approaches to analyzing the (conditional) low-degree likelihood ratio statistic, and to provide algebraic methods of analyzing the overlap landscape. It's helpful to have these connections elucidated at the level of generality of this current work, even if versions of these implications were used implicitly before in more specific models.

I guess the main weakness seems to be that it's unclear whether this FP-criterion fully captures the "physics intuition" for hardness in these types of problems, as (a) it is defined in terms of an annealed potential, and it's a bit unclear (at least to me) when this should have the same behavior as the replica-symmetric potential or the true quenched potential, and (b) it pertains to the properties of this potential only locally near 0, rather than to the entire overlap landscape. But I think these issues are adequately discussed in Section 4, and in my opinion they provide food for thought and do not detract much from the strengths of the work.
questions: I might suggest to the author(s) to include some more of the discussion in Section 1.3 of the supplement (on the Franz-Parisi potential) into the main text, if this is possible. Currently I find Remark 3.3 a bit hard to understand (i.e. what is the relation between the FP potential and a restriction of the partition function?). Without this, it's hard to grasp the intuition behind the main Definition 3.2, as well as how the local/global properties of Figure 1 should be interpreted in the discussions on page 5.

A few typos:
p2 l86, "its precisely domain"
p3 l121, "computational" is repeated
p5 l189, "local minimum separated from", minimum -> maximum
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: ## Summary of paper:

This work deals with proving algorithmic hardness of a class of statistical problems against local MCMC algorithms. To do this, they introduce a new algebraic quantity called the Franz-Parisi criterion (FP) and study it. For many learning problems, there is a phenomenon called the information-computation tradeoff where there is a gap between the information-theoretic sample complexity and the minimum sample complexity needed for polynomial time algorithms, e.g., in Sparse PCA, there is almost a quadratic gap. There have been many works trying to characterize this phenomenon by showing lower bounds against efficient algorithms. Techniques include reductions from conjectured hard problems (such as planted clique from graph theory), showing that the geometry landscape of the solution space have barriers in them (borrowing ideas from statistical physics), or showing hardness against powerful families of algorithms (such as the Sum-of-Squares hierarchy). In this work, they show that for the Gaussian additive noise model, under a strong symmetry assumptions, the so-called low-degree hardness (used before in the literature) implies failure of local MCMC algorithms. Their proof goes via this new FP criterion they introduce. They also show another usecase of this criterion, namely in obtaining tradeoffs for sparse regression. They finally study limitations of the FP criterion and show that it fails to predict the right threshold for simple mixtures of boolean distributions.

## Technical summary:

Consider the problem of hypothesis testing of Gaussian additive models, where null distribution is iid Gaussian and the alternative distribution has a planted spike sampled from a prior, e.g. tensor PCA. In this setting, this work shows that two hardness approaches are related. In particular, they show that a hardness hypothesis called low-degree hardness implies hardness of local MCMC algorithms.
- Low-degree hardness (LD) (definition 2.3) is a notion of hardness against hypothesis testing algorithms that utilize low-degree polynomials. Stemming from the analysis of the Sum of Squares family of algorithms, it is a simple and very effective technique to predict computational tradeoffs, however they do not say much about hardness of the Sum of Squares algorithms themselves. The hypothesis basically says that, under favorable conditions such as symmetry and noise robustness, if the projection of the likelihood ratio test (from the Neyman-Pearson lemma) to low-degree polynomials is bounded, then the problem is hard.
- Borrowing ideas from statistical physics, hardness of local algorithms can be obtained by exhibiting free-energy barriers in the solution landscape by approximating the free energy of a posterior distribution when we restrict the overlap with the ground truth. The relevant quantity they borrow inspiration from here is the Franz-Parisi potential, which when massaged appropriately via the Jensen's inequality, gives rise to a new quantity that's called the annealed potential. This is further modified to a notion this work introduces and terms the "Franz-Parisi criterion" (definition 3.2). This work shows that for additive Gaussian models, to show hardness of local alogorithms, it's enough to bound the FP criterion.

Both these approaches can be thought of as trying to bound the (computationally-bounded) Neyman-Pearson likelihood ratio and use it to predict computational barriers. This intuition is made formal in this work for Gaussian additive models. Main assumptions are:
- The null distribution has iid Gaussian entries
- The prior on the signal has sufficient symmetry, which necessiates among other things, thht every signal has the same L2-norm

Under these assumptions, LD hardness implies FP hardness (theorem 4.4, converse is also true) which in turn implies a free-energy barrier (theorem 5.3) and this in turn implies hardness against local MCMC algorithms (variants known in the literature before). As the authors point out, both assumptions seem crucial and not easy to be relaxed.

As another application of their criterion, the authors obtain computational phase transitions for certain specific parameter regimes of the sparse regression problem. In this setting, they found that their new criterion is easier to analyze than the low-degree ratio. However, it's still quite nontrivial and requires conditioning on a high-probability good event (definition 6.3 in the appendix) amidst tedious calculations.

Limits of this criterion are also explored, the authors show that it fails in several aspects. For example, it doesn't predict sharp thresholds for the estimation/recovery problem (compared to hypothesis testing). Moreover, it fails in boolean settings (as the authors point out, the issue is not booleanness, but something more inherent) and it also fails for the planted subgraph problem, where the LD criterion works instead. Therefore, this criterion should be considered as a means to an end in this research direction.
strengths_and_weaknesses: ## Summary of evaluation:

I was not able to verify the math in this timeframe. However, the results seem plausible, since the tradeoffs obtained here for various problems are expected to be true. The contributions in this work are conceptually interesting and raise potential directions for further research. However, the actual results obtained seem a bit weak since they require a lot of assumptions. Also, they are not readily applicable to other problems due to the difficulty of the calculations involved. Moreover, the proofs are highly technical and will take quite a bit of time to absorb for even experts in either statistical physics or statistics, let alone the average NeurIPS reader, which leads to concerns regarding the fit.

## Strengths:

1. Lower bounds against computational methods have long been studied from different perspectives, especially for average-case problems where NP-hardness results are not known. Recently, researchers have been trying to build bridges between different perspectives, e.g. Brennan et al. 2021 show that SQ algorithms and low-degree tests are equal power under some assumptions. Likewise, this work attempts to bridge the gap between statistical physics approaches and low degree tests.

2. Although the LD test became useful for its ease-of-use in predicting computational thresholds, the authors state that it's hard to apply it to certain parameter regimes of sparse regression. They overcome this with their new FP criterion.

3. The FP criterion recovers predicted thresholds for the spiked Wigner model of PCA. The example worked out is very helpful to understand it.

4. Formalizing all of the intuition this work brings about is nontrivial. The technical mastery in this work is commendable.

## Weaknesses:

1. The main weakness is that even if the FP criterion is a potentially useful criterion, it still seems quite hard to use it for other problems of interest. For example, even for the application to planted sparse models, the authors have to spend significant effort to bound the FP criterion, such as conditioning on a high probability event (definition 6.3). So, the usefulness of this criterion itself for other problems seems rather limited and technically tedious even for experts.

2. Based on my understanding, the transitive symmetry property seems to break when we consider sparse PCA where the sparsity is *at most* k, instead of *exactly* k. Therefore, the results here do not apply for this simple variant of sparse PCA since transitive symmetry seems to be a rather strong assumption. Could the authors clarify this?

3. Although the results are intriguing, my main concern is regarding the fit of this paper for this conference. Due to its length and non-triviality, It may be better suited for a journal or a more theory-focused conference.

4. For someone more from an ML background and not from a statistical physics background, it can be hard/impossible to follow section 1.3 in the appendix. Despite this, I understand that it is not easy to have a self-contained intro to the statistical physics terms used here. I'd suggest that a good reference should be cited to learn these better for the interested reader.

5. In the end of page 14 of the appendix, it's stated that very few tools are available to prove the success of MCMC methods for inference. If that's the case, then why are hardness against MCMC methods a good proxy for computational hardness?
questions: A few questions were raised above.

## Other questions/comments:

1. Just to clarify, can the sample size in theorem 6.2, i.e. m = (1 + o(1))Rk log(n/k), be replaced by m <= (1 + o(1))Rk log(n/k)? It seems a bit unusual to set the sample size to be something specific

2. L86: "precisely" -> "precise"

3. L166: the partition function is not defined, I believe the first place it's defined is L271.

4. In the last paragraph of page 7 of the appendix, "says bounded" -> "stays bounded"
limitations: This is primarily a theoretical paper. Limitations of the results are sufficiently addressed, including the various assumptions and conceptual limitations (section 4 of the appendix). Negative societal impacts are not discussed, but I do not think there is any.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the computational hardness of hypothesis testing in planted models.
Consider a "null" probability distribution and a "planted" distribution, i.e. a distribution depending on a hidden random signal with a given prior distribution.
Given a sample from one of the two distributions, how computationally hard is it to decide from which distribution it comes from?

The authors introduce a novel criterion, the Franz-Parisi (FP) criterion, that depends on local geometric properties of the planted/null distributions, and they define a related notion of FP hardness.
They show that FP hardness is related to an already established kind of computational hardness, namely low-degree (LD) hardness, in Gaussian additive models and some planted sparse models.
In particular, in the former class of models they prove that FP hardness is equivalent (up to technical hypothesis) to low-degree hardness, while in the latter they prove that FP hardness implies LD hardness.
Thus, they establish a link between geometrical properties of the planted/null distributions and computational hardness.

In Gaussian additive models, the authors prove that FP-hardness implies failure of local MCMC algorithms, in the sense that FP-hardness implies the existence of large free-energy barriers in the landscape explored by MCMC. 
These prevent MCMC from fully exploring the configuration space in polynomial time.
Together with the LD-FP equivalence, this implies that low-degree hardness implies failure of local MCMC algorithms.

The authors then focus on the sparse linear regression model, where they provide new low-degree computational lower bounds using a proof technique that crucially relies on the new FP criterion.
strengths_and_weaknesses: ### Originality

The papers contains several novel results: the definition of the FP criterion, the study of the relationship of FP hardness with LD hardness and MCMC hardness in different models and new bounds for sparse linear regression.
Moreover, the proof of the bounds relies on the FP criterion, which has to be considered not only as a conceptual item, but also as a practical tool for proofs.
The authors clearly and convincingly state the relationship of their results with existing literature in many remarks both in the main text and in the supplementary materials.

I am not familiar with the literature enough to assess whether all relevant work has been adequately cited.

### Quality

The authors clearly state the assumptions underlying their results, and provide seemingly correct proofs.
I did not check the details of the proofs.

### Clarity

The manuscript is overall clearly and nicely written, and together with the extensive supplementary material provides enough information for the expert reader to be able to fully assess correctness and to reproduce the proofs.

### Significance

I believe that the results presented in this manuscript related to FP-hardness are significant. 
Linking algorithmic hardness with statistical-physics-like properties of computational problems is a long-standing research effort. As far as my knowledge goes, it is still not completely clear how geometric properties of free-energy landscapes, such as replica symmetry breaking, relate to computational hardness, and this seems a promising step.

I am not qualified enough to properly assess the significance of the results on sparse regression, and on the novel proof technique based on the FP-criterion.
questions: I am curious on how the FP hardness criterion relates to overlap gap properties and their consequences: do the authors have some intuition that could be added to the manuscript?

In the manuscript the authors hint at some relationship between the hypothesis testing setting they study and the (to me) more common estimation (retrieval of the planted signal) setting: is there some more precise relationship between computational and theoretical thresholds of the two settings? 

limitations: The authors clearly assess the limitations of their results in the supplementary materials, where they provide counterexamples that suggest that their results do not point towards a complete equivalence between low-degree hardness and FP hardness.
These limitations do not undermine the validity or significance of their results.
review_title: null

Meta-review: metareview: The paper establishes new bridges between two fundamental notions for the study of average case hardness of hypothesis testing problems: low-degree functions and the Franz-Parisi free energy, and also connect them to MCMC hardness. The paper has been very well received by the reviewers, who have done a great job. I agree with the reviewers on the quality of the paper. I also think that despite NeurIPS not being the most obvious avenue to submit such a paper, there indeed is an active sub-community of NeurIPS readers very much enthusiastic about such results, connections with statistical physics, etc. All issues raised seems to have been properly answered by the authors, so this is a clear accept for a high-quality paper full of rich notions and new fundamental connections.
confidence: Certain
Decision: Accept