Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures
Authors: Emmanuel Abbe
Samy Bengio
Elisabetta Cornacchia
Jon Kleinberg
Aryo Lotfi
Maithra Raghu
Chiyuan Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: generalization
implicit bias
reasoning
distribution shift
Boolean influence
noise sensitivity
deep learning

Abstract: This paper considers the Pointer Value Retrieval (PVR) benchmark introduced in [ZRKB21], where a `reasoning' function acts on a string of digits to produce the label. More generally, the paper considers the learning of logical functions with gradient descent (GD) on neural networks. It is first shown that in order to learn logical functions with gradient descent on symmetric neural networks, the generalization error can be lower-bounded in terms of the noise-stability of the target function, supporting a conjecture made in [ZRKB21]. It is then shown that in the distribution shift setting, when the data withholding corresponds to freezing a single feature (referred to as canonical holdout), the generalization error of gradient descent admits a tight characterization in terms of the Boolean influence for several relevant architectures. This is shown on linear models and supported experimentally on other models such as MLPs and Transformers. In particular, this puts forward the hypothesis that for such architectures and for learning logical functions such as PVR functions, GD tends to have an implicit bias towards low-degree representations, which in turn gives the Boolean influence for the generalization error under quadratic loss.

Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures
Emmanuel Abbe" EPFL
Samy Bengio Apple
Elisabetta Cornacchia EPFL
Jon Kleinberg Cornell University
Aryo Lotfi
Maithra Raghu
Chiyuan Zhang
EPFL
Google Research
Google Research
Abstract
This paper considers the Pointer Value Retrieval (PVR) benchmark introduced in [ZRKB21], where 'reasoning' function acts on a string of digits to produce the label. More generally, the paper considers the learning of logical functions with gradient descent (GD) on neural networks. It is first shown that in order to learn logical functions with gradient descent on symmetric neural networks, the generalization error can be lower-bounded in terms of the noise-stability of the target function, supporting a conjecture made in [ZRKB21]. It is then shown that in the distribution shift setting, when the data withholding corresponds freezing a single feature (referred to as canonical holdout), the generalization error of gradient descent admits tight characterization in terms of the Boolean influence for several relevant architectures. This is shown on linear models and supported experimentally
other models such MLPs and Transformers. In particular, this puts forward the hypothesis that for such architectures and for learning logical functions such as PVR functions, GD tends have implicit bias towards low-degree representations, which in turn gives the Boolean influence for the generalization error under quadratic loss.
Introduction
Recently [ZRKB21] introduced the pointer value retrieval (PVR) benchmark. This benchmark consists of a supervised learning task on MNIST [L.B10] digits with a 'logical' or "reasoning' component in the label generation. More specifically, the functions be learned defined on MNIST digits organized either sequentially or on grid, and the label is generated by applying some 'reasoning' on these digits, with specific digit acting as a pointer on subset of other digits from which logical/Boolean function is computed to generate the label.
For instance, consider the PVR setting for binary digits in the string format, where string of MNIST digits is used as input. Consider in particular the case where only 0 and digits are used, such as in the example of Figure 1. The label of this string defined as follows: the first bits 101 define the pointer binary expansion, and the pointer points to a window a given length, say in this example. Specifically, the pointer points at the first bit of the window. To generate the label, one has
Authors in alphabetical order.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Aggregaation
Pointer
Window
Output
function
Figure I: An example of a PVR function with a window size of The first 3 bits are the pointer, which points to window in the subsequent bits. Specifically, the number indicated by the pointer bits in binary expansion gives the position of the first bit of the window. The label is then produced by applying some fixed aggregation function to the window bits (e.g.. parity, majority-vote, etc.).
to thus look the 6th window? of length 2 given by 11, and there the label is produced by applying some fixed function, such as the parity (so the label would be 0 in this example). In [ZRKB21], the PVR benchmark also defined for matrices of digits rather than strings; we focus here on the string version that captures all the purposes of the PVR study. This benchmark is introduced to understand the limits of deep learning on tasks that go beyond classical image recognition, investigating in particular the trade-off between memorization and reasoning by acting with a particular distribution shift at testing (see further details below).
In order to learn such PVR functions, one has to first learn the digit identification and then the logical component these digits. Handling both tasks successfully at once naturally more demanding than succeeding at the latter assuming the first successful. Here, we focus on the 'logical component' as necessary component to learn, and this corresponds learning a Boolean function. The overall function that maps the pixels of an image to its label in the PVR is of course also a Boolean function (like any computer-encoded function), but the structural properties of such meta-functions are more challenging to describe, and left for future work. In any case, to understand the limits of deep learning on such benchmarks, we focus on investigating first the limits of deep learning on the logical/Boolean component.
We next re-state formally one of the PVR benchmarks from [ZRKB21], focusing on binary digits for simplicity. We will use the alphabet [0, 1} to describe the benchmark to connect to the MNIST dataset, but will later switch to the alphabet [+1, 11} for the problem of learning Boolean functions with neural networks. Recall for d N, F2 = {0, 1)".
Definition 1 (Boolean PVR with sliding windows), The input consists of n bits and the label is generated as
f(a Fn)
(1)
where p is the number of bits in the pointer, w is the window size, g : Fy + R. is the aggregation function, P: F2 + 1p++1 n)] is the pointer map, 2, denotes the bit in position j and x" = [Z1..... ........ xp) denotes the pointer bits. We often set = p 2", and hence the last window starts at the last digit.
In words, the first p bits give a pointer to the beginning of a window of w consecutive bits, and the label is produced by applying a Boolean function on these bits.
Remark 1. If w 1, for some values of the pointer, P(œ²) + w would exceed the dimension of input n. This issue can be solved by using cyclic indices or by using non-overlapping windows as defined in Appendix D. However, in the experiments of this paper, mainly truncate windows (if necessary) in order to capture the underlying asymmetries (e.g., the last windows have smaller sizes).
In this paper we consider the problem of learning in the holdout setting, i.e., when some data are withheld (or 'unseen') during training. We focus specific type of holdout setting, that we call 'canonical holdout', which we define here. Extensions to other types of holdout are also of interest, and left for future work.
Definition 2 (Canonical holdout). Let F be the class of Boolean functions n bits and let be a specific function in that class. For lo E [n], consider the problem of learning F from samples (X-k, f (X-x)), where the X-k 's are independently drawn from the distribution that freezes com- ponent k to and that draws the other components i..d. Bernoull( Let f-x be the function
2 'pointer 000 points at the first window, pointer 001 at the second window, and so on. Thus pointer 101, that equal to 5 in binary expansion, points the 6th window.

---

learned under this training distribution. We are interested in the generalization error with square loss when the k-th bit is not frozen at testing, i.e.,
-xx s (f -
ge
(2)
where by X ~U F2 we mean that X is chosen uniformly at random from E2. and similarty for f ~u F. We denote by f the function learned in the case where the k-th component is not frozen at training, i.e. when the train and test distributions both uniform the Boolean hypercube, and use the following notation for the corresponding generalization error:
gen [, f)
2 Ex -E f(x))
(3)
The 'canonical' holdout is thus a special case of holdout where single feature/bit is frozen training. In [ZRKB21], different types of holdout are allowed where a given string is absent from the windows rather than given bit as in the canonical version. We believe that the canonical holdout still captures the essence of the PVR benchmark: other windows will get to see the strings that are withheld due to the bit freezing, and thus the goal is still investigate whether neural networks trained by GD will manage to patch together the different pieces.
Finally, we will often consider neural network architectures that have invariances on the input, such as permutation invariance. In the PVR setting, this means that we do not assume that the learner has knowledge of which bits are in the window. In such cases, instead of learning class of function F, one can equivalently talk about learning a single function f (with the implicit F defined as the orbit of f through the permutation group), and define
1 gen(J. f)) = 1 Ex (f(X) - fx((x))² and g) =x (x(x) f(x))-
1.1 Contributions of this paper
The contributions of this paper are:
1. In the matched setting (i.e., train and test distributions are matching), we prove a lower- bound (Theorem on the generalization error for gradient descent' (GD), that degrades for functions having large noise-sensitivity (or low noise-stability), supporting thereby with a formal result a conjecture put forward in [ZRKB21].
2. In the mismatched setting, specifically in the canonical holdout where single feature is frozen at training and released to be uniformly distributed at testing, we hypothesize that (SJGD on the square loss and on certain network architectures such as MLPs and Transformers has an implicit bias towards low-degree representations when learning logical functions such as Boolean PVR functions. This gives new insight into the implicit bias study of GD on neural networks for the case of logical functions.
We then show (Lemma 1) that under this hypothesis, the generalization error in the canonical holdout setting is given by the Boolean influence, central notion in Boolean Fourier analysis.
3. We provide experiments supporting this hypothesis for various target functions and architec- tures such as MLPs and the Transformers [VSP+ 17] in Section 3.2 and Appendix F. These rely on mini-batch stochastic gradient descent (see Section 3.2 for more details).
4. We establish formally the hypothesis for GD and linear regression models in Section 3.3, and conduct experiments to support on multi-layer neural networks of large depths and small initialization scales in Section 3.3 (with further arguments in Appendix G).
1.2 The low-degree bias hypothesis: illustration
We now discuss the hypothesis put forward in this paper that "GD on certain architectures such as MLPs and Transformers has an implicit bias towards lower-degree representations when learning
This part relies on population gradients with polynomial gradient precision as in [AS20, AKM*21]
Wee do not expect the square loss be critical, but it makes the connection to the influence more explicit.
3

---

PVR and, more generally, logical functions." Before starting our illustration let recall some basic notions from Boolean analysis (we refer to [O'D14] for details). Any Boolean function f: [ + R can be written in terms of its Fourier-Walle transform: f(z) = f(T)xx where XT = IlieT 2; and f(T) = 2 Ex (())x(()) are respectively the basis elements and the coefficients of the Fourier- Walsh transform of f.
Definition 3 (Boolean influence [O'D14]) Let f: {+1}" + R be Boolean function and les f be its Fourier-Waie transform. The Boolean influence of variable E [m] on f is defined by Inf, (f) ==
Σ frg In particular, if {=1}" + {+1}. Inf = P(f(X) # f(X + tx))), where X + BK corresponds to the vector obtained by flipping the k-th component of X.
Consider the following example of PVR function with a I-bit pointer, 2 overlapping windows of length 2, and parity for the aggregation function. We consider f {=1}" + {=1} (i.e., with #1 variables instead of 0, 1, to simplify the expressions), with f given by
f 22, Z3, 24) 1+ 21
1-
12 +
23T44
(4)
2
We can rewrite f in terms of its Fourier- Walsh expansion (i.e., pulling out all the multivariate monomials appearing in the function, see Section 3.1 for more details), which gives
1 12 D2, I3, x2a) 22 +
1 2 13T4
1 2 2222223 2123244
1
(5)
Consider now training a neural network such as a Transformer as in Section 3.2 on this function, with quadratic loss, and a canonical holdout corresponding to freezing 22 = training. Under this holdout, and under the 'low-degree implicit bias' hypothesis, the low-degree monomials are learned first (see experiments in Section 3.2), resulting the following function being learned training:
f-2(21, F2, F3, .T) = 23 + 2 23 + 211s 2 212322 = 1 21
1
1
1
F1 Z3
F3
(6)
2
2
2
Thus, according to Lemma proved in Appendix C, the generalization error is given by
P((())))(()))))))))) f(x+
which is the probability that flipping the frozen coordinate changes the value of the target function, i.e. the Boolean influence (where we denoted by X + e2 the vector obtained by flipping the second entry in X). As shown in this paper, neural networks tend to follow this trend quite closely, and we can prove this hypothesis on simple linear models. Notice that an ERM-mininizing function could have taken more general form than a degree minimizing function, i.e.
ERM (x) == 1+ 02 f2(()) + 1-
1 1- x22 r(x)
(8)
2
2
for any choice of r (=1)+ {+1). In the special case of r FRRM corresponds f-2 (the low-degree representation). For instance, among such ERM-mininizees, one can check that the minimum 2n-norm interpolating solution would be given by
1 (x) = 1 (r3+ + + ( (11 (a0 - 1 -xx +11 (9) 4
This gives a generalization error of 1 - 4(2)² 1. i.c., half the error of f-2- yet still bounded away from 0.
In order improve on this, under the same canonical holdout with 22 1, one would like rely on a type of minimum description length bias, since describing ff may be more efficient than f-2 due to the stronger symmetries of f. Namely, f corresponds to taking the parity on the middle two bits I1 = 1, and on the last two bits otherwise. On the other hand, f-2 requires changing the function depending on #
or ii = 1, since once the function xi and once the function T3344. So an implicit bias that would exploit such symmetries, featuring in PVR tasks, would give different solution than the low-degree implicit bias, and could result in lower generalization error. We leave to future work to investigate this 'symmetry compensation' procedure.

---

1.3 Related literature
GD lower bounds. Several works have investigated the difficulties of learning class of functions with descent algorithms and identified measures for the complexity in this setting. In particu- lar, [BFJ+94, Kea98] prove that the larger the statistical dimension of a function class is, the more difficult it is for statistical query (SQ) algorithm to learn. We refer to [AKM DGKPI9] for further references on SQ-like lower bounds. For GD with mini-batch and polynomial gradient precision. [AS20] uses the
Predictability (CP) of class of functions to show that classes sufficienlly small CP and large batch-size are not efficiently learnable. This is further generalized in [AKM*21] 21] to broader range of batch size and gradient precision. In [AGNZ18], the noise-stability for deep neural networks is defined as the stability of each layer's computation to noise injected at lower layers, and is used to show correctness of compression framework. However, the generalization error of GD depending on the noise stability of the target function is derived in this work. The noise-stability, the statistical dimension and the cross- poos-predictabiliit are measures for some given function or function class. One can obtain measures that are defined for a dataset and a network architecture. For that purpose, [ACHM22] introduced the "Initial Alignment" (INAL) between the target function and the neural network at initialization and proves that for fully connected networks with Gaussian i.i.d. initialization, if the INAL is negligible, then GD will not learn efficiently. We remark that the problem of approximating and learning Boolean functions appear in other areas as well. For instance, [HPV19] considered the problem of approximating Boolean functions, using functions coming from restricted classes (namely k-juntas and linear Boolean functions); [JSR+ 19] proposes two algorithms to learn sparse Boolean formulae; and [Udo21] proposes techniques for modeling Boolean functions by mixed-integer linear inequalities.
bounds on
Implicit bias. The implicit bias of neural networks trained with gradient descent has been ex- tensively studied in recent years [NTS14, NBMS17, MGW+ JT19, GLSSI8a]. In particular, [SHN+17 17] proved that gradient descent on linearly binary classification problems con- verges to the maximum fn-margin direction. Several subsequent works studied the implicit bias in classification tasks on various networks architectures, e-g.. homogeneous networks [LL19], two layers networks in the mean field regime [CB20], linear and ReLU fully connected networks [VSS21], and convolutional linear networks [GLSS18b]. Among regression tasks, the problem of implicit bias has been analysed for matrix factorization tasks [GWB+17, RC20, ACHL19], and also gradient flow on diagonal networks [PPVF21]. However, all these works consider functions with real inputs, instead of logical functions which are the focus of this work. On the other hand, as discussed in Section 1.2, the Boolean influence generalization characterization reflects the implicit bias of GD on neural networks to learn low-degree representations. Similar types of phenomena can implicitly be found in [XZX18, XZL+ + 19, RBA+ 19], in particular as the "spectral bias" in the context of real valued functions decomposed in the classical Fourier basis (where the notion of lower degree is replaced by low frequencies). In [ABAB* 21, ABAM22], the case of Boolean functions is considered as in this paper, and it is established that for various 'regular' architectures (having some symmetry in their layers), gradient descent can learn target functions that satisfy a certain 'staircase' property. However, these papers do not investigate lower-bounds in terms of noise stability, neither distribution shift as in the canonical holdout. We note that, in the context of Boolcan functions, the problem of regularizing a learning algorithm to avoid overfitting appears in other areas of research, e.g., in the analysis of fitness functions in biology [ANO*21] 21].
Distribution shift. Many works were aimed at characterizing when classifier trained on a training distribution (also called the "source" distribution) performs well on a different test domain (also called the "target" distribution) [QCSSL09]. On the thcoretical side, [BDBC+ 10] obtains bound of the target error of a general empirical risk minimization algorithm in terms of the source error and the divergence between the source and target distribution, in a setting where the algorithm has access to a large dataset from the source distribution and few samples from the target distribution. We refer to [SQZY17] for further result similar setting. Instead, in this work we focus on gradient descent on neural networks in the setting where no data from the target distribution is accessible. On the empirical level, several benchmarks have been proposed to evaluate performance for a wide range of models and distribution shifts [WGS+22 22, M 2KL+ Despite this significant body of works on distribution shift, we did not find works that related the generalization error under holdout shift in terms of the Boolean influence.
5

---

2 Matched setting: formal lower-bound on noise stability and generalization
Our first result provides a lower bound on the generalization error in the setting where the training and test distributions of the inputs are both uniform on the Boolean hypercube, i.e., the "matched setting". We directly relate the generalization error achieved by GD, or SGD with large batch-size, to the complexity of the task, providing theoretical support to the empirical claim in [ZRKB21], that complex tasks are more difficult to learn for GD/SGD on neural networks. The latter work used the noise sensitivity as a dual measure of the target function complexity, whereas we use here the noise stability (Stabs (f).
Definition (Noise stability). Let f: (= + R and ó E 1/21 Let X be uniformly distributed on the Boolean n-dimensional hypercube, and let Y be formed X by flipping each bit indepen- dently with probability 5. We define the 5-noise stability of f by Stabs [f] == Exxx))((X) f(Y)).
Intuitively, Stabs [f] measures how stable the output of f is to a perturbation that flips each input bit with probability 6, independently. The noise stability can be easily related to the noise sensitivity NS; [f used in [ZRKB21].
The generalization enror depends as well on the complexity of the network, which is quantified in terms of the number of edges the network, the number of time steps, and gradients precision the gradient descent algorithm. We give one more definition before stating our result.
Definition 5 (N-Extension). For a function ʃ =R - R and N >> nI, we define its N-extension f: F R as f(x1, .... In.
I2., .N) f2,, In).
Theorem 1. Consider a fully connected neural network of size E with initialization that is target
agnostic in the sense that it is invariant under permutations of the input". Let f: {=1}" > {+1}
be a balanced target function. Let f be the 2n-extension of f as defined in Definition 5. Let SNN be the output of noisy- GD with gradient range A, batch-size b. learning rate n and noise scale o (see Def. 8) after time steps. Then. for ó small enough? and for b large enough", the generalization error satisfies
ptt)
gen (I.J 2 1/2 MVEA
StabssJ]1/4
(10)
Theorem states a lower bound for learning in the extended imputtspace We use the input doubling to guarantee that the hypothesis class F resulting from the orbit of f, i.e., orb(f) (s o π S2n)) is not degenerate to a single function, as this could then be learned using a proper choice of the initialization (i.e., one can simply set the weights of the neural network at initialization represent the unique function, if the network has enough expressivity). Instead, the input doubling prohibits such representation shortcut and ensures that the structural properties of the function what creates the difficulty of learning, irrespective of the choice of the initialization. For instance, consider the full parity function on all of the input bits. The orbit of this function contains only that specific function, and one can learn that function by choosing a proper initialization on neural net of depth 2. However, with an input doubling, this function becomes hard to learn no matter what the initialization is [Kea98, AS20]. One can remove this input doubling requirement by assuming that non-extremal (i.e., no terms of degree ((n) in the Fourier basis) and non-dense (i.e., poly -n)-si Fourier spectrum), see Appendix B.
The proof of Theorem I uses [AS20] which obtains a lower-bound in terms of the prods-predictabiliiy (CP) (instead of the noise stability). The CP is a complexity measure of a class of functions, rather than a single function. For the orbit of f. the CP is defined as CProrb(f) = Ex Szn. [xx0r [f() f o T [. We give a more general definition of CP in Appendix A (we believe that the CP also extends to other invariances than permutations and non i.i.d. distributions).
'Specifically, for binary-valued functions, NS = ] 1 Stabs[f].
2
'One could consider other groups of invariances than the full permutation group: this is left for future work.
2 'Generally, this holds for any 8 such that CP(rrb(J)) I Stabx in particular, this holds for d < 1/4 under input doubling or for some > O under non-extremal and non-dense assumptions.
'This holds for b 2 I/CP()rbbf))

---

Theorem 1 states that if the target function is highly noise unstable, specifically if there exists 5 < 1/4 such that Stabs[]] decreases faster than any inverse polynomial in n, then GD will not learn the 2n-extension of (or f itself if it is non-extremal/dense) in polynomial time and with polynomially sized neural network initialized at random. So in that sense, the noise-stability gives a proxy to generalization error, as observed in [ZRKB2I]. More specifically, this result is about failure of the weakest form of learning no matter what the architecture is. One could also consider 'regular' architectures (such as with isotropic layers) and stronger learning requirements; for this is known that the 'Fourier leap' from [ABAB* 21] is relevant complexity measure, and we leave investigations of regular architectures to future work. More details of the proof of Theorem are in Appendix A. In Appendix D, we explain how the noise stability of PVR functions can be computed, and the implications to the result of Theorem
Mismatched setting
In this section, we focus on the generalization error under the distribution shift setting, more specifi- cally the canonical holdout setting defined in Definition 2. Namely, assume that at training component k is frozen to 1, and assume it to be released to }ni testing. Our experiments show that in this setting. for some relevant architectures, the generalization error is close to the value a standard measure in Boolean analysis, namely the Boolean influence of variable on f-
3.1 Boolean influence and generalization
To explain the connection between generalization error and Boolean influence, we start with simple lemma relating the Boolean influence to the f2-distance between the true target function and the function obtained by freezing component i: (which we call the "frozen function").
Lemma 1. Let f [+1]" - TR be a Boolean function and let k be defined as f=a(x) == (<--)) where x (1) = 1 i = k and x (i) = arii) otherwise. Then, (Xx (f))
The proof of Lemma 1 can be found in Appendix C. In Section 3.2, present experiments that demonstrate the relation between the Boolean influence and the generalization error for different architectures. In Section 3.3, we focus on linear models, namely, linear regression and linear networks.
3.2 Experiments
We consider three architectures for our experiments: multi-layer perceptron (MLP) with 4 hidden layers, the Transformer [VSP+ 17], and MLP-Mixer T11. For each architecture, freeze different coordinates separately and evaluate our models. In other words, we train the model while freezing coordinate 1, then coordinate 2 and on, until coordinate n. and compare the generalization error with the Boolean influence of the corresponding coordinates of the target function. We train models using & loss and mini-batch SGD with momentum and batch-size of 64 as the optimizer. Moreover, we have repeated each experiment 40 times and averaged the results. Furthermore, note that for the MLP model, we pass the Boolean vector directly to the model. However, for the Transformer and MLP-Mixer, we first encode +1 and - tokens into 256-dimensional vectors using shared embedding layer, and then we pass the embedded input the models. More details on training procedure as well as further experiments are presented in Appendix F.9
Influence vs. canonical holdout generalization. In this section, we consider a Boolean PVR function (as in Def. 1) with 3 pointer bits to be learned by the neural networks. For this function we set window size
and use majority-vote (defined as g(11, .......... xx)) = sign(x; + +.... + x,)). outputting -1, 1. O, or 1) as the aggregation function on the windows. The generalization error of the models on this PVR function and its comparison with the Boolean influence are presented in Figure 2. The x x-axis corresponds to the index of the frozen coordinate, that is from 4 to 11 (we do not freeze the pointer bits). On the y-axis, for each frozen coordinate we report the generalization error obtained in the corresponding holdout setting for MI.P, the Transformer, and MI.--Mxer, together with the value of the Boolean influence of the frozen coordinate on the target function. can be seen that the generalization error of MLP and the Transformer can be well approximated by the Boolean influence.
CCode: https: https://githute cemm/aryol/BolleanPP"
7

---

Generalization error for PVR function
Generalization error
0.25
0.20
0.15
Error
0.10
Error of Transformer
Error of MLP-Mixer
10
11
Index of the frozen bit
Figure 2: Comparison between the generalization loss in the canonical distribution shift setting and the Boolean influence for a PVR function with 3 pointer bits, window size and majority-vote aggregation function. See Appendix F for further experiments.
Whereas, the generalization error of MLP-Mixer follows the trend of the Boolean influence with an offset. We remark that in Figure the value of the Boolean influence (and gen. error) in the PVR task varies across different indices due to boundary effects and the use of truncated windows (see Def. I). We refer Appendix F for further experiments on other target functions.
Implicit bias towards low-degree representation. Consider the problem of learning a function f in the canonical holdout setting freezing 2 = Denote the Fourier coefficients of the frozen function f-* (as defined in Lemma 1), by f-+(S), for all S S [n] == (1,..., n) (recall, f-&(S) (X))s For S such that k & S, the neural network can learn coefficient (-) using either (x) or æx xs(x)= = Xsu(k} (i) (since these are indistinguishable at training). The low-degree implicit bias states that neural networks have preference for the lower degree monomial
Xs- More precisely, Xs learned faster than Xs_(k} and thus the term (Sx in the Fourier expansion of f-k, is mostly learned by the lower degree monomial. Consequently, according to Lemma the generalization eтror will be close the Boolean influence. Figure 3 shows this bias empirically for the above mentioned PVR function and for frozen coordinate t = 6. Figure (left) shows that the MI.P model has strong preference for low-degree monomials, Similarly, Figure (bottom) shows that the Transformer also captures the monomials in the original function using monomials that exclude the frozen index. Therefore the generalization errors of the MIP and Transformer are very close to the Boolean influence seen in Figure 2. Whereas, Figure 3 (right) shows that the MLP-Mixer model has weaker preference for lower degree monomials (e.g., it learns 1 and to the same extent) and hence, its generalization error follows the trend of Boolean influence with an offset, which also presented in Figure 2. We refer to Appendix for additional experiments.
3.3 Linear Models
In this section, we will focus on linear functions and linear models. First, we state a theorem for linear regression models. Furthermore, show experiments the generalization neural networks and its relation with the depth and initialization of the model.
of linear
Theorem Let f {=1}" + E. be a linear function, i.e., f(x1,... ,x) = "ini.....,,n">"""
f()+
f((i))a (
Consider the canonical holdout where the k-th component is frozen at training for linear regression model where weights and biases are initialized independently with the same mean and variance o², Also assume the frozen function is unbiased, i.e. [x)] O. In this case, the expected generalization error (over different initializations) of the function learned by GD after time steps given by Eeg fg ((2) = Inf o,- (1) + O(e-ct, where e is a constant dependent on the [eo[gen(,f.
learning rate. Moreover, the frozen function biased, the expected generalization error is equal to
Eg Eoo[gen(f f (f(0)- f(()))) + oga O

---

Coefficient monomials by
Coefficient monomials leamndd by MLP-Mixer
0.15
0.15
Fourier Coefrcient
0.10
X6
Fourier coeffrcient
X
XgKiAs
X176
0.00
0.09
1000
XyXoAs
X3Xı44
X
XiXs
-0.10
-0.10
0.15
-0.15
Epach
Epach
Coefficient monomials learned by Transformer
0.15
Fourler coafiictet
6.10
0.05
Kg
X:86
0.00
XyX22
Xy8g
-0.0
-0.15
Epoch
The coefficients of a selected group of monomials learned by the MLP (left). MLP. Mixer (right) and the Transformer (bottom) when learning the aforementioned PVR function, with Jg = 1 frozen during the training. The coefficient of these monomials in the original function are f((6)) 0.1875, f({3, 6, 7,8)) 0.0625, f(16, 7, 7,8}) -0.0625, and f((1,6)) One can observe that the monomials of the lowest degree are indeed picked up first during the training of the MLP and Transformer, which explains the tight approximation of the Boolean influence for the generalization error in these cases. contrast, the MLP-Mixer also picks up some contribution from the higher degree monomials including the frozen bit Ø6.
Figure 3:
-0.1875.
Remark 2 (Kernel regression). Our result would still hold if, instead of linear regression, we per- formed kernel regression with a kernel that is invertible under the training distribution, i.e., such that Ex,x'=44 (XX,XX (X,X')) is invertible. Furthermore, one could try to remove the invertibility assumption by adding a regularization term.
Remark 3 (Staircase learning). An attempt to extend the above result to non-linear function consists of considering staircase functions [ABAB++11 ABAM22), and extending [ABAM22] to a setting with bias in order to show that SGD learns the lowest-degree representation under proper mean-field initialization of depth-2 neural networks.
The proof of Theorem 2 is presented in Appendix C. In the rest of this section, we empirically show that the condition of zero bias stated in Theorem 2 is no longer necessary linear neural networks of large enough depth small enough initialization are used. In fact, the generalization error linear neural networks makes a transition from value proved Theorem to the Boolean influence as deeper models or smaller scales of initialization
used. We take f IZ D2..... .I11)
11210 + 12x11 as the function that we want to learn. We consider linear neural networks with hidden layers of size 256. Figure 4 (left) shows the effect of depth: initialize weights and biases independently using the uniform distribution 4d VN.. vV=)) where
1+ 20; - 3z2 + 4z3
Nin is the input dimension of the respective layer. We plot the generalization error in the holdout setting with respect to corresponding frozen coordinate training, together with the value the Boolean influence of each coordinate. We observe that with the increase of depth, the generalization error tends to the Boolean influence. Figure 4 (right) show the role of initialization: we take linear neural network with 3 layers and initialize weights and biases using the uniform distribution

---

Effect the Depth
Effect of the Initialization
190
Boolean influence
150
Boolean influence
Linear regression model
Linear regression model
Depth
0,5
Gemeralization etrer
120
Depth
120
1.0
*
Depth 12
a 1.5
Generalization
2.5
90
80
40-
40
0-
11
11
Index of the
Index
Figure Effect of depth (left) and initialization scale (right) on the out-of-distribution generalization error of linear neural networks. Generalization error tends to the Boolean influence as depth increases (left) or as the initialization scale decreases (right).
u(-N N,aa with taking value in (0.5, 1,5, 2, can be seen that as the initialization scale decreases, the generalization error tends to the Boolean influence.
Conclusion
This paper first establishes formal result that supports conjecture made in [ZRKB21], relating the noise sensitivity of a target function to the generalization error. This gives a first connection between central measure in Boolean analysis, the soisi-vensitivity, and the generalization error when learning Boolean functions with GD. The paper then investigates the generalization emrrr under the canonical holdout. The 'low-degree implicit bias hypothesis' is put forward and supported both experimentally and theoretically for certain architectures. This gives a new insight on the implicit bias of GD when training neural networks, that is specifie to Boolean functions such the Boolean PVR, and that relates to the fact that certain networks tend to greedily learn monomials by incrementing their degree. In particular, this allows to characterize the generalization error in terms of the Boolean influence, second central notion in Boolean Fourier analysis. Boolean measures thus seem to have role to play in understanding generalization when learning of 'reasoning' or 'logical' functions. There are now many directions to pursue such as: (I) extending the realm of architectures/modee for which we can prove formally the Boolean influence tightness. (2) considering more general holdout or distribution shift models, (3) investigate how the picture changes when the bits/digits are given by MNIST images, (4) better understanding when the low-degree implicit bias taking place or not, within and beyond PVR, since the Boolean influence is not always tight in our experiments (e.g., MLX-Mixers seem to have worse performance than the Boolean influence on PVR; see also Appendix F for other functions), (5) investigating how to 'revert' the implicit bias towards low-degree when taking place, to compensate for unseen data; this will require justifying and engineering why certain symmetries are favorable in the learned function.
Acknowledgments and Disclosure of Funding
We thank Raphaël Berthier (EPFL) and Jan Hęzla (EPFL) for useful discussions.
References
[ABAB+21] Emmanuel Abbe, Enric Boix-Adsera, Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning, NeurIPS, 2021. 5,
10

---

[ABAM22] Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-stairease property: a necessary and nearly suffiiient condition for sgd learning of sparse functions on two-layer neural networks, 2022. 28
[ACHL19] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization, 2019. 5
[ACHM22]
Emmanuel Abbe, Elisabetta Cornacchia, Jan Hązla, and Christopher Marquis. An initial alignment between neural network and target is needed for gradient descent to learn 2022. 5, 22, 23
[AGNZI8] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach, 2018. 5
[AKM+21] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus PAC and SQ learning. In Advances in Neural Information Processing Systems, volume 34, 2021. 3, 16
[ANO*21] Amirali Aghazadeh, Hunter Nisonoff, Orhan Ocal, David H. Brookes, Yijie Huang, O. Ozan Koyluoglu, Jennifer Listgarten, and Kannan Ramchandran. Epistatic net allows the sparse spectral regularization of deep neural networks for inferring fitness functions. Nature Communicutions, 12(1):5225, 2021.
[AS20] Emmanuel Abbe and Colin Sandon.
the universality of deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20061 200722 Curran Associates, Inc., 2020. 3, 6, 15, 16, 17
[BDBC+10] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Vaughan. theory of learning from different domains. Machine Learning. 79:151-175, 2010.
94] Avrim Blum. Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Symposium on Theory of Computing (STOC), pages 253-262, 1994.
[CB20] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. 2020.
[DBK+20] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold. Syl- vain Gelly, et al. An image is worth 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 1929, 2020. 24
[DGKP19] Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy. On the learnability of deep random networks, 2019.
[GLSS18a] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry, 2018.
[GLSS18b] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks, 2018.
[GWB+17] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization, 2017. 5
[HPV19] Mohsen Heidari, S. Sandeep Pradhan, and Ramji Venkataramanan. Boolean functions with biased inputs: Approximation and noise sensitivity. In 2019 IEEE International Symposium Information Theory (ISIT), pages 1192-1196, 2019. 5

---

[1S Susmit Jha, Tuhin Sahai, Vasumathi Raman, Alessandro Pinto, and Michael Francis. Explaining ai decisions using efficient methods for learning sparse boolean formulae. J. Autom. Reason., 63(4):1055-1075, dec 2019.
[JT19] Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via a primal-dual analysis, 2019.
[KB14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
2014. 25
[Kea98] Michael Kearns, Efficient noise-toleramt learning from statistical queries. Journal of the ACM, 45(6):983-1066, 1998. 5, 6
[LCB10] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yannllecmn.. lecwn.com/exd///miisy 2, 2010.
[LL19] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks, 2019. 5
[MGW+20] Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D. Lee, Nathan Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy, 2020. 5
[MTR+21] John Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the line: On the strong correlation between out-of-distribution and in-distribution generalization, 2021.
[NBMS17] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. Exploring generalization in deep learning, 2017. 5
[NTS14] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning, 2014. 5
[O'D14] Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
16, 21, 23
19GM+19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019. 25
[PPVF21] Scott Pesme, Loucas Pillad-Viviers and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity, 2021. 5
[QCSSL09] Joaquin Quionero-Candele Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence. Dataset Shift in Machine Learning. The MIT Press, 2009. 5
[RBA+19] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Ham- precht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5310. PMLR, 2019.
[RC20] Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms, 2020. 5
195 Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv: /00. 2019. 24
[SHN+17] Daniel Soudry, Flad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data, 2017. 5
12

---

[SKI,+21]
Shiori Sagawa, Pang Wei Koh, Tony Lee, Irena Gao, Sang Michael Xie, Kendrick Shen, Ananya Kumar, Weihua Hu, Michihiro Yasunaga, Henrik Marklund, Sara Beery, Eti- enne David, Ian Stavness, Wei Guo, Jure Leskovec, Kate Saenko, Tatsunori Hashimoto, Sergey Levine, Chelsea Finn, and Percy Liang. Extending the wilds benchmark for unsupervised adaptation, 2021.
[SQZY17] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation, 2017. 5
[THK+ Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung. Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, al. Mip-mixer: An all-mlp architecture for vision. Advances Neural Information Processing Systems, 34, 2021. 7, 24
[Udo21] Aleksei Udovenko. Milp modeling of boolean functions by minimum number of inequalities. Cryptology ePrint Archive, Paper 2021/1099, 2021. https: //printt///i..... iacr. wwtoor////// 20tg//2021099....
[VSP+17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, Advances in neural information processing systems, 30, 2017. 3, 7, 24
[VSS21] Gal Vardi, Ohad Shamir, and Nathan Srebro. On margin maximization in linear and relu networks, 2021. 5
[WGS+22] Olivia Wiles, Sven Gowal, Florian Stimberg, Sylvestre-Alvise Rebuffi, Ira Ktena, Krishnamurthy Dj Dvijotham, and Ali Taylan Cemgil. A fine-grained analysis on distribution shift. In International Conference on Learning Representations, 2022. 5
[9] Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks, 2019. 5
[XZX18] Zhi-Qin John Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior of deep neural network in frequency domain, 2018. 5
[ZRKB21] Chiyuan Zhang, Maithra Raghu, Jon M. Kleinberg, and Samy Bengio. Pointer value re- trieval: A new benchmark for understanding the limits of neural network generalization. ArXiv, 0tbs/2107.12580) 2021. 1, 2, 3, 6, 7, 10, 23
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We believe there are no potential negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] Link to the GitHub repository is provided.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 3.2 and Appendix experiment details.
13

---

(c) Did you report bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The 95% confidence interval reported if relevant.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix on experiment details
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "s8ZYM-DroNt", "reviewer": "Reviewer_mpbM", "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:\n\nIn 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).\n\nIn 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.\n", "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? \n\nNoise 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?\n\nAnalysis 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?\n\nMLP-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.\n\nBackground 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.\n\nUniform 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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hetyKIHztwG", "reviewer": "Reviewer_Mz9k", "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’. ", "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.\nUnseen Data, appeared in the title, is not mentioned except in the future pursuits. Maybe there should be more explanations about it.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \nThe 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UVGG_Vm5ut9", "reviewer": "Reviewer_PXDA", "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. ", "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. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n+ The paper addresses an important challenge of reasoning with DNNs and studies the problem using a variant of PVR benchmark. \n\n+ 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. \n\n+ The theoretical result is complemented with empirical evaluation over architectures such as MLPs and transformers. \n\n- 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IvBTUnI2Irq", "reviewer": "Reviewer_g1sx", "summary": "The paper presents some iinteresting results on the properties of NNs on boolean function learning, that are supported by experimental evaluation,", "questions": "Why use a quadractic error measure?\n\nYou use 3 architectures. Please explain why these three.\n\nFig 3 results seem to be designed to explain the mixer results? Maybe explain that from the start.\n\nhow would the classifiers work if there is no noise?\n\nWhat 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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I liked the paper, but I had  to overcome two initial problems:\nTitle is really misleading, why is this about learning to reason?\nStructure: I found sec 1 jumps everywhere, namely   1,,2 present results (boolean influence) wIthout a def, (see 3.1 for more details?). \ndef 2 is only used in sec 2?\nWhy: 1.3 Further related literature, further?\n\nFinally 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept