Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper works in a computational model where various architectures of energy-based-models are viewed as computational models for accepting languages. EBM's assign a weight to each string. The sum of weights is called the partition function and this needs to be computed (or at best approximated) if the energy is to be thought of as a probability measure. The paper shows that expressive EBM's are turning complete, and uses that to show that the partition function may be uncomputable. And that is even in the case the energy of a sequence could be computed in poly-time. The paper then shows some corollaries and variations of this result, showing that model selection is undecidable as well. The paper concludes by suggesting scenarios where the partition function is computable but this naturally comes at the expense of the expressivity of the model.
main_review: The paper is generally well written with a good exposition. One glaring exception (for me) is the 2nd paragraph of Section 2.4 where the reduction from neural sequence to formal languages is presented. This is crucial for understanding the paper, yet it is done quickly and I found it hard to follow. It may also be a good place to draw clear distinction from the work of Perez et al (2021). This (and Theorem 1) are key, after all, theorem 2 (for instance) is quite straightforward once the setup is established.

It would be nice to connect the 'recommendations' of Section 7 to actual EBM's used in practice. 
summary_of_the_review: The paper is clear and interesting, but suffers from two major weaknesses:
1. It seems to me the big 'insight' is Turing completeness of the model, but this is (mostly) done in previous papers. Once this is established the remaining reductions are much less surprising.
2. I'm not sure the paper is a good fit for ICLR. It is mainly a complexity/computability paper where the models are related to ML. I'm skeptical that its insights are interesting for most of the ICLR audience  (If I'm wrong I'm  happy to be corrected).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This theoretical work highlights uncomputability issues arising with energy-based sequence models. It is shown that an EC-complete family (a certain computational model capturing neural networks and transformers that is essentially equivalent to weighted Turing machines) cannot approximate the partition function of energy-based sequence models (EBMs) even given an unlimited amount of time and space. A consequence is the impossibility of model selection for EBMs. This paper also rules out popular estimators such as rejection and important sampling. This work concludes with a discussion of restricted EBMs that avoid such uncomputability issues. 
main_review: **Strengths:**

- This paper rigorously explores the computational barriers of calculating the partition function and model selection, both of which are fundamental machine learning tasks

- A specific EBM is exhibited whose partition function is uncomputable (even unprovable) assuming the consistency of ZFC -- to my knowledge this is a new connection between logic and machine learning.

- Sections 7 and 9 point to more interesting work to be done

**Concerns:**

- The uncomputability of the partition function is not necessarily a barrier to using EBMs in practice if the task at hand does not require sampling or model selection

- The uncomputability of the partition function seems to be known. See the "Remark on computability" in Lin et al '21. Also the proof of Lin et al's Theorem 5 uses a very similar construction to the paper under the review, and this should be mentioned.

- As this paper admits, the EBMs studied are pathological and not necessarily an obstruction to practice. There is also a lack of discussion on polynomial-time computation of partition functions in less pathological situations (see [1,2,3] below) 

- Only rather specific asymptotic estimates of the partition function are ruled out. Perhaps this deserves further study.

**Comments**

- pg 4: I had trouble understanding the phrase "many estimation procedures are anytime algorithms". Can you explain this a bit more? It seemed that asymptotic estimates defined here capture the idea of the sample size going to infinity, but I am unclear on the details.

- pg 6, Theorem 4: Is it possible to simplify the proof of Theorem 4 as follows? Given a randomized estimate $\hat Z_\epsilon$, one can compute $\mathbb{E}[\hat Z_\epsilon]$ by derandomization. If $\varepsilon^{-1} Z \leq \mathbb{E}[\hat Z_\epsilon] \leq \varepsilon Z$ holds, then the exact estimate $\mathbb{E}[\hat Z_\epsilon]$ satisfies Equation (2) from Lemma 1 with probability $1$. But this is impossible by Lemma 1. 

- pg 7, Theorem 7: In most applications, it is not necessary to verify identifiability with an algorithm. Perhaps it is worth only mentioning the model selection result in the main text and using the identifiability as a proof tool in the Appendix.

- pg 9, Conclusion: Lin et al '21 are aware of computability issues arising from EBMs. To my understanding, the work under review continues the conversation about uncomputability and says some interesting new things about it. And again, just because the partition function is uncomputable, it doesn't mean that EBMs are useless for all applications. I think the conclusion should be rephrased to acknowledge these points.

- pg 20: Table C.1 is interesting and could be cited in the main text.

**Minor issues**

- pg2, Table 1: This table is hard to understand without knowing the definitions. The phrase "suspected to be useless in general" is too informal.

- pg 5, Theorem 3: Please describe what $\tilde b$ is around here.

- pg 5: "The weighted language... by simulating $x$ on $M$." Please describe this more  formally. Lin et al's proof of Theorem 5 uses convenient notation for this.

- pg 5: "We discuss this in further detail in Section 2.5" This is a backward reference; is it a typo?

- pg 6: A brief definition of rejection sampling would be helpful at the beginning of Section 5.1.

- pg 8: $\Psi_{\vert x \vert}$ is not defined when describing FGGs. 

- pg 19: "for any halting trace $x'$ of $M_b$" seems to be a typo.

**References**

[1] M. Luby and E. Vigoda, “Fast convergence of the glauber dynamics for sampling independent sets,” Random Structures and Algorithms, vol. 15, no. 3-4, pp. 229–241, 1999.

[2] A. Galanis, D. Stefankovic, and E. Vigoda, “Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models,” arXiv preprint arXiv:1203.2226, 2012.

[3] M. Jerrum and A. Sinclair, “Polynomial-time approximation algorithms for the Ising model,”
SIAM Journal on computing, vol. 22, no. 5, pp. 1087–1116, 1993
summary_of_the_review: This paper develops an interesting point of view on machine learning and computability. The proofs seem to be correct. I support accepting this paper once it is revised to take into account concerns raised above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies "efficiently computable (EC) energy-based sequence models (EBMs)" which are simply sets of strings equipped with nonnegative weights that can be computed by a poly-time Turing machine (upon normalization, the weights induce a probability distribution over the strings). In practice, it is common for these weights to be computed by neural networks. In fact, certain neural sequence model families like RNNs and Transformers are expressive enough to be Turing-complete. In this paper, the authors find that the expressivity of such sequence model families, so-called "EC-complete parametric families", comes at a significant cost in terms of *computability/decidability* of various primitives for inference. For instance, they show that if one could actually take in any vector of parameters specifying a model in such a family and output the corresponding partition function (sum of the weights of all strings) even approximately in expectation, then would be able to decide the halting problem (Theorem 2, 4). They also exhibit a single efficiently computable EBM for which proving (within ZFC) that the partition function is one of two possible values would either disprove Godel's second incompleteness theorem or disprove consistency of ZFC (Theorem 3); this can be extended to show that *asymptotic* estimates like rejection sampling and importance sampling will also fail (Theorems 5, 6). Along similar lines, they can reduce from the halting problem to other tasks like deciding whether two given parameter vectors give rise to the same EBM ("parameter identifiability", Theorem 7), or deciding which of two given parameter vectors gives rise to an EBM which is distributionally closer to some other given EBM ("model selection", Theorem 8).

In terms of techniques, the reductions from the halting problem are all based on a simple weight function that is tiny unless if the string corresponds to a valid accepting trace of an input-free Turing machine M. The point is that the weight for any string x can be computed by M simply by simulating M on x, but the partition function is large iff M halts. The ZFC results follow by taking M which enumerates all provable propositions under ZF and halts iff it proves 1 = 0.
main_review: The main strength of this submission is its cohesive conceptual message. This work studies the viability of EBMs from an unconventional angle: whereas one's initial reaction to the complexity of computing the partition function for an EBM might be to point out that it is obviously computationally expensive, the findings in this paper show that in fact this task isn't even computable. A related strength is that the paper systematically pursues this idea from a variety of perspectives, e.g. exact/approximate/asymptotic + deterministic/randomized estimation, failure of off-the-shelf techniques like rejection/importance sampling, related tasks like identifiability and model selection.

As for weaknesses, the actual technical content isn't particularly involved and arguably not that surprising given that families like Transformers are known to be Turing-complete, though perhaps this is an unfair criticism given that the contribution of this work is primarily conceptual. Regarding the writing, I did feel that the important preliminaries were introduced in a rushed fashion; for instance, even though they figure in a majority of the theorems in this submission, their definition of "EC-complete parametric families" was extremely difficult to parse, in part because their definition of seq-to-seq models was similarly difficult to understand. That said, the formalism doesn't figure that heavily in the proofs as the arguments are ultimately primarily about Turing machines anyways.
summary_of_the_review: I am not an expert in this area so I'm not sure to what extent the field was already aware of issues of computability. Superficially the connection between EC and the halting problem does seem quite straightforward, but if this was not observed or studied in any depth previously in the EBMs literature, I think the submission is a worthy conceptual contribution that should be accepted.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the trade-off between expressiveness and computability (of the partition function) for energy-based sequence models. The theoretical results show that the high expressively of unrestricted energy based models comes at the cost of un-computability and in-approximability of the partition function. These negative results further show that rejection and importance sampling are not a panacea either.
main_review: This paper tackles the important question of what we loose in theoretical guarantees if we remove all restrictions on the energy-based model. As such, this paper provides an important answer to conjectures raised in (Lin et al. 2021).
The paper is technically sound and well written to the degree that the arguments are also comprehensible for non-experts; I honestly enjoyed reading the paper.
One might argue that the findings are somewhat abstract as they only hold for energy-based models without any restrictions on the model expressively. The theoretical properties (e.g., regarding randomized algorithms) are intriguing at first, but less so considering that we implicitly assume that $\tilde{p}$ has infinite support. Granted, the authors are quite open about the -- lack of -- assumptions and discuss the implications of typical model restrictions in depth in Sec. 7. Nonetheless, I would have preferred a brief discussion about the practical relevance of EC-complete parametric families in Sec. 2.4. (and in the introduction) and to what degree certain model restrictions lead to non-complete families. That is if the authors would state the scope of the current work more blatantly.

I have a couple of further remarks and questions:
* I cannot follow the logic from Prop. 1 that infinite-length sequences have zero mass; that is, I do not understand why $\epsilon$ must go to zero for $n \rightarrow \infty$.
* In Sec. 4 it is stated that no estimate exists with a bias within a multiplicative factor. If I understand Lm. 1 correctly, such an estimate does exist, however; although only with probability < 1/3. Can you explain this discrepancy?
* Most arguments hinge on the undecidability of the HALT problem. I think that it would help the reader if that was stated explicitly in the text.
* Thm. 5 states that rejection sampling does not work for EC-complete families. I get the argument, but I was left wondering whether it might be possible to quantify the approximation error one introduces when relying on randomized methods nonetheless.
summary_of_the_review: The paper considers an important problem, is technically sound (at least from what I can tell), and well-written. Although the practical implications are not immediately clear, I am convinced that it is actually relevant to understand the theoretical limitation of considering energy-based models with ever-increasing expressiveness.
review_title: null

Meta-review: This is a deep theoretical paper with results that I consider very interesting. I have *not* had time to check them myself, but I have background in these theoretical matters and the results seem reasonable to me - the hardness of even checking the quality of a solution is well known for partition functions (as well as hardness of any reasonable approximation), but the undecidability seems new - I assume it comes naturally and it is a very interesting result - I have seen similar decidability issues for #P: general probabilistic polynomial time Turing machines (it is unclear if a connection was sought here). Reviewers are all positive about the content, and authors have acknowledge some points for improvement.
Decision: Accept (Spotlight)