Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper mainly focuses on learning logical function with GD and investigates generalization error under matched and mismatched setting. For GD generalization error under matched setting, the authors prove a lower-bound related especially to noise-stability, supporting a formal conjecture. Under the canonical holdout, the generalization error is close to Boolean influence for relevant architecture, which puts forward an interesting ‘low-degree implicit bias hypothesis’. 
strengths_and_weaknesses: Overall, the compact structure explains points clearly and logically. Introduction part basically and vividly explains the main contributions of this article, providing several instances for easy-understanding(e.g. illustration of low-degree bias hypothesis). After that, matched and mismatched setting are separately illustrated. Then, several experiments on MLPs, Transformers and linear models provided effectively support the formal points and hypothesis. 
The idea that introducing PVR benchmark to understand the limits of deep learning on tasks  and investigating ‘memorization and reasoning’ trade-off is practical and can be used in many domains. The ‘canonical’ holdout that a single feature/bit is frozen at training is also an important case. This paper exactly considers the two settings, proving a lower-bound and a tightness, which other papers haven't investigated. 

questions: Experiments conducted are under the distribution shift setting. Is it necessary to carry out experiments verifying the generalization error lower bound under the matched setting and observe difference by changing noise stability?
limitations: Three architectures, MLPs, Transformers and linear models, are considered for experiments. It is worthy to consider an extension to other architectures and prove the Boolean influence tightness, as mentioned in the future pursuits.
Unseen Data, appeared in the title, is not mentioned except in the future pursuits. Maybe there should be more explanations about it.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper presents some iinteresting results on the properties of NNs on boolean function learning, that are supported by experimental evaluation,
strengths_and_weaknesses: I liked the paper, but I had  to overcome two initial problems:
Title is really misleading, why is this about learning to reason?
Structure: I found sec 1 jumps everywhere, namely   1,,2 present results (boolean influence) wIthout a def, (see 3.1 for more details?). 
def 2 is only used in sec 2?
Why: 1.3 Further related literature, further?

Finally the exp design must be in the main text. Especially when your results are impressive, the strength of this paper is in the match between theory and results.

questions: Why use a quadractic error measure?

You use 3 architectures. Please explain why these three.

Fig 3 results seem to be designed to explain the mixer results? Maybe explain that from the start.

how would the classifiers work if there is no noise?

What is  " the empirical claim made in [ZRKB21]." ?
limitations: The authors discuss some extensions to their setting, but that is mostly done n the Appendixes, and shhow some clear research diretcions in the Conclusions.
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 paper develops a combination of empirical and theoretical analyses for the recently introduced pointer value retrieval (PVR) benchmark, proposed to measure how a neural network reasons about a logical task. The paper has two main results which connects generalization error of a learner performing gradient descent on l2-norm loss in a (pseudo) Boolean logical task to two measures in Boolean optimization under settings where a shift between the distribution of training and test sets exists or can be avoided:

In order to learn general logical functions (Boolean and pseudo-Boolean functions) using gradient descent, it is theoretically proven that the learner incurs a generalization error which is lower-bounded by the noise stability of the target function (i.e., how much the output of the function changes on average as the result of Boolean perturbations). The analysis is distinct from the prior theoretical work in that it uses a measure that poses a property over the target function rather than the function class to be learned (or an alignment between the two).

In the distribution shift setting (and focusing on a particular shift called canonical holdout which fixes a binary coordinate in the training set), the generalization error of the learner with gradient descent follows an intuitive measure called Boolean influence. The study further establishes the existence of a bias in neural networks towards learning low-degree polynomials (low frequencies). This result is theoretically proven for the linear models and empirically justified for some neural networks such as MLP and Transformers.

strengths_and_weaknesses: Overall the paper investigates a new and timely problem of reasoning in neural networks from a theoretical perspective with clear results and contributions which help advance both machine learning research and Boolean optimization—an intersection with growing research problems. Connecting generalization performance of logical functions to Boolean measures is novel, intuitive, and interesting. It also opens up new research questions to be addressed in learning Boolean functions. I have a few questions and suggestions for the authors mostly to improve the paper.
questions: Implication of the theoretical results to the problem of reasoning in neural networks under PVR. The paper is motivated by the PVR benchmark and puts forward a theoretical analysis for that under distribution shift. Discussing the implications of these theoretical results to the reasoning problem (under PVR) can further strengthen the paper. In a high level (if I am correct) the paper seems to  suggest that for the Boolean problems the neural network choses a solution (logical function) which has a bias towards low-degree polynomials (natural given that the known empirical biases of neural networks towards low-frequencies components in other domains). While this bias seems to be beneficial in several cases in terms of generalization (e.g., when there is no distribution shift), the bias does not seem to be the desired one in general (e.g., when there is a distribution shift) especially in the logical tasks involved in the Boolean-PVR benchmark. A symmetry-compensation bias, however, which is either explicitly-imposed via regularization or implicitly-imposed via a new architecture, seems to be what is required (as alluded in the future work). Does this imply that learning gradient descent on the l2 norm loss over MLP and Transformers lack such symmetries and are thus not well-equipped for reasoning tasks such as the one in PVR? 

Noise stability analysis of the PVR task. To complete the exposition, is it straightforward to find the \delta-noise stability term for the logical PVR function considered as a function of the problem dimension n and the window size w analytically? Is it a monotone function of w?

Analysis of distribution shift for the nonlinear case. The analysis of the distribution shift with canonical holdout is done for the linear case. What are the challenges to do the analysis for the nonlinear case? Can the authors elaborate more on Remark 3—is the suggested analysis trivial?

MLP-Mix. More insights on why there is no bias towards low-degree solutions in the MLP-Mix case would be beneficial.  Also more details on how the architecture is adapted to the Boolean problem (given that MLP-Mix is developed for images) helps the reader better contrast the three architectures (MLP, MLP-Mix, and Transformers) employed in the work and understand the differences in their behaviors on the PVR benchmark.

Background on low-degree bias. While the analysis for the bias of neural networks towards low-degree polynomials is novel from the theoretical perspective the empirical evidences are observed in prior works in applied machine learning domains involving Boolean objects (e.g., analysis of fitness functions in biology) which might be worth mentioning, e.g. see "Epistatic Net allows the sparse spectral regularization of deep neural networks for inferring fitness functions." Nature communications 12.1 (2021): 1-10.

Uniform assumption. Throughout the paper the assumption on the non-hold-out indices is a Bernouli distribution. In practice this might be too restrictive; it is common that the training data is concentrated around a point in the hamming space in many learning scenarios. While it is fairly natural for the theoretical analysis to assume uniformity, from a practical point of view do the authors expect the results to hold under a non-uniform distribution case? 
limitations: Discussed before.
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 paper uses the Pointer Value Retrieval (PVR) benchmark to study the problem of reasoning with DNNs. In the PVR problem, MNIST digits in the string format are provided as input (say restricted to 0,1 digits) and the task is to perform some logical operation over these to find the final label. The paper focuses on the string version of the problem (rather than matrices).  The benchmark helps study the tradeoff between memorization and reasoning by acting with a distribution shift at testing. This paper focuses on the logical/Boolean learning component of the challenge. 
strengths_and_weaknesses: 
+ The paper addresses an important challenge of reasoning with DNNs and studies the problem using a variant of PVR benchmark. 

+ The paper shows that if the target function is highly noise unstable - stability decreases faster than any inverse polynomial in n, then gradient descent will not learn the 2n extension of the function in polynomial time and with a polynomially sized NN. So, noise stability gives a proxy to generalization error. 

+ The theoretical result is complemented with empirical evaluation over architectures such as MLPs and transformers. 

- Boolean function learning has been extensively studied in formal methods and AI. The O'D14 reference from the paper is an excellent background, and there have been some practical algorithms for special classes of Boolean function that might be of interest to the authors such as https://ieeexplore.ieee.org/abstract/document/8849233, https://link.springer.com/article/10.1007/s10817-018-9499-8, https://eprint.iacr.org/2021/1099 Discussion of this larger literature on Boolean function learning would be useful. 
questions:  The presentation starts with a more general problem of reasoning over DNN before narrowing to PVR. It then further narrows to PVR over string. It then narrows to the Boolean learning component. It finally narrows to canonical holdout. This is a very odd presentation choice and makes the reader assume the breadth of the paper's contribution to be initially much larger.  Is there anyway, the initial presentation (first 2.5 pages) can be rewritten to better reflect the key contributions of the paper?
limitations: There are no potential negative societal impact of this work to the best of this reviewer's understanding.
review_title: null

Meta-review: metareview: The paper addresses in a formal and solid way a specific learning task with the intent to assess the limitations of different neural networks architectures. The addressed task requires some degree of reasoning for the architecture to learn it in a satisfactory way. Although the authors eventually restrict the scope of their work, personally I think the paper gives insights about some aspects of learning bias in specific architectures that are not so evident at first sight, in fact contributing to the creation of a different perspective for the pursuit of a better understanding of deep learning models. In their rebuttal authors have clarified some issues raised by the reviewers, and no specific negative concerns have been raised on the presented work, except for the relatively limited scope of the theoretical analysis and range of applicability to other architectures not covered in the paper. Overall I think the paper contains interesting material and concepts that can be of interest for NeurIPS audience, and harbingers of future developments.
confidence: Certain
Decision: Accept