Learning High-Degree Parities: The Crucial Role of the Initialization

We thank the reviewer for constructive comments and for appreciating our work.

• Phrasing in the abstract and introduction, Positive result for almost full parities.

We thank the reviewer for pointing our some confusion in our presentation. We refer to our general response for an extension of our positive result to include almost-full parities.

• Breaking down Theorem 4, consistency of format between positive and negative sections.

We thank the reviewer for the suggestions. We will implement the changes in a revised version of the paper.

We thank the reviewer for the constructive comments and for a summary of the big picture for parities.

• What’s the emerging picture around parities and complex function learning, and what are the broader takeaway? What does this paper add to it?

At the theory level, the paper indicates that deep learning with regular networks is not related to Statistical-Query (SQ) learning under “stability” assumptions, where `stability' refers to small changes in the training parameters (as the initialization). Namely, several papers (such as https://arxiv.org/pdf/2108.04190) have asked whether the paradigm of learning with regular networks trained by SGD would be PAC or SQ or something smaller. It is known that PAC cannot be reached with batches that are too large compared to the precision available. One consequence of our negative result is that SQ itself is not achievable if we do not initialize the network carefully, since the full parity is SQ learnable. From a more practical point of view, it raises the point that discrete initializations may be useful in settings where high-degree functions are expected to be learned. While expecting Rademacher initialization to be broadly useful is perhaps too optimistic, there can be other surprising cases where well chosen discrete initialization might be advantageous.

The GAL concept builds on previous work including cross-predictability [Abbe-Sandon,'20] and initial alignment [Abbe et al.,'22]. Indeed, it subsumes those in the sense that we believe that their main results can be restated in terms of GAL. We further refer to the response to reviewer oGKm for comments on our notion of GAL with respect to other measures defined, e.g. the Label-Gradient Alignment (LGA).

Finally, perhaps one more general lesson is a cautionary one. It seems there is a sense in which the full parity function is hard to learn for GD on a neural network, however such results can be stated only in a limited way. Even assuming the symmetry of initialization up to sign changes is not sufficient, as the Rademacher initialization has this property. Therefore, care is needed in stating and interpreting GD lower bounds.

• Difference in the proof techniques compared to [Abbe, Boix,’22, Abbe et al.,’22]

The key distinction between the negative results in this paper and [Abbe, Boix ’22; Abbe et al., ’22] lies in the nature of our proof, which does not rely on symmetries or the hardness of the orbit class of the target function under permutations. Instead, our approach involves directly bounding the gradient alignment along the junk flow—a challenge that previous works addressed through the cross-predictability of the orbit class. Furthermore, we introduce the concept of initial gradient alignment as a more appropriate complexity measure, which captures both the influence of initialization and the inherent difficulty of learning some functions that are hard despite having learnable orbit classes, such as the full parity.

• How can Theorem 7 be used in practice? Should we estimate the GAL at initialization (from labeled examples) and abandon if it is small?

Yes, in practice one can estimate the GAL and abandon learning if it is small, since a small GAL corresponds to a long time needed to achieve weak learning. Moreover, the actual value (and scaling) of the GAL seems to characterize the complexity of escaping the initial saddle, and not just whether it is poly or super-poly small, as in the case of sparse k-parities and single-index models (see response to reviewer sB62). One should notice that a large GAL does not imply a successful strong learning of the target in a short time, since the dynamic can get stuck in other saddles that are not visible at initialization.

• Define Gaussian perturbation as $A+ \sqrt{Var(A)} H_\sigma.$

Indeed, our technique requires that we establish that GAL is small not just for the perturbed initialization, but also for its further smoothing. In our proofs for parity, it is easy to conclude that further smoothing can only decrease the GAL. We considered variations of the definition of perturbed initialization, including the one suggested by the reviewer, but we do not believe it would significantly change the presentation of our results.

Thank you for your engagement. We do like our results, though we prefer to err on the side of not overstating them.

• This seems almost a little too good to be true. Can the authors give an honest assessment of whether there is a catch here? What assumptions are required for this to go through, and when might they fail to hold in practice?

Currently Theorem 6 applies only to the correlation loss. The general upper bound in (76) applies for a general loss function, but it requires a small GAL at every time step t. In the simpler case of the correlation loss, we can show some connection between GAL at initialisation and at later times (Theorem 6, Corollaries 3 and 4). It is in fact tempting to conjecture such a connection for other losses and we have some empirical validation, see Figure 8 in the revision. However, we do not have a theoretical justification nor counterexamples (which would be interesting in their own right too).

More generally, we view Theorem 6 as a guarantee for challenging cases, i.e. scenarios where the dynamics remain stuck near initialisation for a significant time (hardness of weak-learning). We expect this behaviour to happen for targets presenting symmetries and requiring some level of `logical reasoning’ (e.g. arithmetic, graphs, syllogisms), for which parities are a simple model. We do not expect such stagnation to happen e.g. for datasets like CIFAR or MNIST, but we do believe that the GAL may be useful for these other settings.

• And if it is indeed true (even with qualifications), this seems like a far stronger general result than the particular application to full parities, and hence worth emphasising more. Is there a reason that GAL isn't pitched as the chief contribution of the paper?

The relationship between small initial alignment and the impossibility of weak learning was explored in [ACHM22], where the authors define the initial alignment (INAL) as the average maximum correlation between neurons in the network and the target. As the authors show, this notion subsumes the cross-predictability of [AS20] but their approach relies on an input extension to guarantee the hardness of the orbit class, which prevents proving the hardness of functions with a learnable orbit, such as almost-full parity functions.

Our work diverges from [ACHM22] in the following ways (see also the related work section):

1. Our notion of alignment (GAL) is based on the gradient norm, which is arguably easier to estimate than INAL, as it does not require finding the maximum correlation between all neurons and the target.

2. Crucially, we introduce a novel proof technique that establishes hardness of learning directly in terms of the GAL, without relying on input extensions or orbit classes. This is a critical improvement both in terms of theory and potential practical relevance. However, this approach is currently limited to the correlation loss. We believe that this technique, and the bound in (76), may have broader applications and agree with the reviewer for the practical appeal.

To clarify our motivations for not positioning GAL upfront as our main contribution:

1. The connection between small initial alignment and no learning with more practical implementations were already put forward in [ACHM22] and in this paper we improve and strengthen this approach. So we focused more on this improvement but we agree with the reviewer in hindsight that we should also bring back some of the more general motivations.

2. It remains open to investigate whether GAL can serve as a guarantee for strong learning.

We thank the reviewer for suggesting greater emphasis on GAL. In the revised manuscript, we will highlight its relevance and provide a more detailed discussion of our contributions relative to [ACHM22]

• References:

[AS20]: Abbe, Sandon, On the universality of deep learning, 2020.

[ACHM22]: Abbe, Cornacchia, Hazla, Marquis, An initial alignment between neural network and target is needed for gradient descent to learn, 2022.

We thank the reviewer for the constructive comments. We address the questions in the list below.

• Negative result for deterministic gradient descent (without additional noise).

Please, see the general reply.

• Positive result: width of the network. What happens for narrower networks?

The reviewer is correct that our positive proofs require a certain minimum poly$(d)$ network width. We do not know how to remove this limitation. Empirically, decreasing the network width results in worse learning time and test accuracy. However, this worsening seems to occur in a continuous manner.

• How does the choice of the loss function affect the results?

For the theoretical results, the choice of the loss function affects the distribution of the junk flow, i.e. the dynamics of a network that is trained on random labels (see Definition 6). Lemma 3 holds regardless of the loss function. However, the value of gradient alignment (see (49)) has to be bounded separately for a new loss function (this is inconvenient, but related to the fact that our techniques are sensitive enough to distinguish Rademacher and Gaussian initialization). Bounding GAL for different losses is more challenging, especially for later time steps. In the case of correlation loss it is easier to relate values of GAL at initialization and at later times. Empirically, both positive and negative results seem to hold for other losses, including cross-entropy and hinge loss. For example, Figure 2 shows the values of GAL at different times for the hinge loss seemingly decaying exponentially with input dimension $d$.

• Intuitively, what is the role of the gradient alignment at initialization? How does it affect the learning process?

The gradient alignment at initialization measures the strength of the target function's signal in the initial gradient. Specifically, it reflects how the model's gradient deviates from that of a network with random labels, which points in a random direction. This metric determines (at least in the negative sense) the time complexity of escaping initialization to achieve non-trivial learning. Our theorem shows that if the initial gradient alignment is small, it will take a long time to grow and escape the initialization.

• In other common settings (e.g. single/multi-index models) what is the typical value of the gradient alignment at initialization?

For single/multi-index models and for squared or correlation loss, the gradient alignment is related to the Hermite expansion of the target link-function, and to the information exponent (i.e. the smallest non-zero Hermite coefficient, as defined in https://arxiv.org/pdf/2003.10409, https://arxiv.org/pdf/2210.15651). For , for a single-index model, we have data $x \sim N(0,I_d)$, $y = f(w^Tx)$, where $w \in R^d$ such that $|| w ||_2 =1$ and $f:R \to R$ has information exponent $s <<d$. Assuming a two-layer neural network with Gaussian initialization and with activation $\sigma$ with non-zero s-th and (s-1)-th Hermite coefficient, one can show that the GAL at initialization is of order $\theta ( Pd^{-(s-1)/2} )$, where P is the total number of weights in the network. Thus, it correctly captures the complexity of escaping the initial saddle for target link function with high information exponent.

• In the sparse parity case, what’s the role of gradient alignment at initialization?

For sparse k-parities, the GAL is related to the size of the support, k. For a parity of degree $k<<d$ and for a two-layer ReLU network with Gaussian initialization , the GAL is of order $\theta(P d^{-k} )$, where $P$ is again the total number of weights in the network. Similarly to the single-index case, also for sparse parities, the initial GAL captures the complexity needed to identify the parity support, which corresponds to the complexity of achieving weak learning.

We thank the reviewer for the constructive comments. We address the questions in the list below.

• Noisy-SGD vs. SGD without additional noise.

We refer to the general response for a discussion on the gradient noise.

• Training of the input layer in the negative result

Yes, our negative result holds for joint training, thus proving that if the initial GAL is small, feature learning does not occur.

• Sample complexity of the positive result: tightness and improvements in case of joint training.

Our positive result for hinge loss holds also for training hidden weights (this is stated in Section 4.2). However, we do not get any theoretical advantage out of training the hidden weights and the same result would hold training output weights only. We included this analysis only for hinge loss for the sake of simplicity. We do not think our sample complexity and network width are tight. Empirically, training both layers results in faster convergence and better accuracy. It would be interesting to understand it theoretically, but we do not address it in the paper.

• Comparison between GAL and previously defined measures (particularly LGA).

Our definition of GAL is loss-dependent. For square loss or correlation loss, the GAL at initialization aligns with the Label-Gradient-Alignment (LGA) proposed in prior work. Our approach improves on previous work in two ways:

1. Our loss-dependent GAL can capture important differences between losses. As an example, in the revision (Appendix E.2, Figure 8) we added an experiment with the following Boolean function: $f(x) = \frac 18 x_1x_2x_3 + \frac 3 8 x_1x_2x_4 + \frac 14 x_1x_3x_4 + \frac 14 x_2x_3x_4$. In https://arxiv.org/pdf/2407.05622, the authors show that this function is learned more efficiently by SGD with L1-loss than with L2-loss. Our experiment show that such difference is captured by our GAL, while it cannot be captured by LGA since it is not loss-dependent. Although a full comparison of our GAL with prior metrics across various tasks is beyond the scope of this paper, which focuses on high-degree parities, we are hopeful that our GAL can reveal interactions among initialization, loss, and target in a broader context.
2. To the best of our knowledge, previous works do not provide theoretical bounds on learning complexity based on initial alignment. Our work offers a theoretical lower bound that depends directly on the GAL.

We thank the reviewer for the constructive comments. We address the questions in the list below.

• Positive result for almost full parities and high-lighting of main contributions.

Please, see the general response for an extension of our positive result to almost full parities. We thank the reviewer for the feedback on our presentation. We will include a positive result for almost full parity and correct the flow accordingly. We will also highlight the negative result as our main contributions in the revision.

• Sample complexity for positive result.

For learning the full parity with a 2-layer ReLU network using SGD with Rademacher initialization and correlation loss, we demonstrate that $\tilde O(d^7)$ samples are sufficient (Theorem 4, part 3). We can further improve such sample complexity if we instead use a clipped-ReLU activation and obtain an upper bound of $\tilde O(d^3)$ samples (Remark 1). We remark that previous results on full parity learning concerned only weak learning and noisy full-batch gradient descent ([Abbe,Boix,’22]), thus with no bound on the sample complexity.

• Negative result: main techniques and difficulties.

To upper bound the success probability in terms of gradient alignment, our approach consists of the following key steps:

1. Defining the "junk flow": This represents the training dynamics of a network trained on random noise.

2. Coupling the GD dynamics with the junk flow: We show that if the Gradient Alignment (GAL) remains small along the junk flow, then the noisy-GD dynamics stay close to the junk flow in total variation (TV) distance, meaning that the network does not learn (Lemma 3).

3. Proving that GAL is small along the junk flow: For correlation loss, we demonstrate that the GAL remains small along the junk flow. In particular, under certain conditions (Corollaries 2 and 3), if the GAL is initially small, it continues to stay small throughout the junk flow.

4. Almost-full parities: For almost-full parities, perturbed initializations, and 2-layer ReLU networks and correlation loss, we show that the GAL along the junk flow remains small.

Notably, steps (1) and (2) apply to any architecture with a linear output layer, symmetric initialization, and any loss function. However, step (3) is currently limited to the correlation loss, as tracking junk flow dynamics for other losses is more complex. Empirically, we also observe that the GAL remains small for the hinge loss (Figure 2, left). Extending step (3) to other losses would require new techniques to analyse the junk flow dynamics, and it is an interesting direction for future work. Bounding the initial GAL for step (4) involves precise calculations, which we limit in this paper to 2-layer ReLU networks. Extending this to deeper networks would establish a negative result for learning almost-full parities in deeper architectures, though we do not expect such an extension to be technically easy. In the revision, we will move the junk flow definition to the main text, outline the main techniques and challenges, and, if space permits, include a proof outline for Theorem 7.

• Intuition on why initial alignment is large for Rad. init and poor for Gaussian perturbation.

1. GAL large for Rademacher init: Under Rademacher initialization the gradient of each hidden neuron i is related to the correlation of the full parity with the Boolean majority function ${\rm Maj}(x)= {\rm sgn}(\sum_{i=1}^d x_i)$ on a uniform input in $\{\pm 1\}^d$. (see e.g., [O’Donnel,'14]). This correlation (at least for odd d) is of the order $1/ \sqrt(d)$. Extension of the proof to almost-full parities is related to the fact that the majority also can have 1/poly(d) correlation with almost-full parities.

2. GAL small for Gaussian init: For Gaussian initialization, the continuity of the distribution allows us to use a series expansion. Using such expansion, we find that low order terms cancel out due to the properties of the parity function, and high order terms are exponentially small.

3. Perturbed initialization: For a perturbed initialization $r+\sigma g$, with $r$ Rademacher and $g$ Gaussian, roughly, for $\sigma$ sufficiently small, $r$ is the dominant term, while for $\sigma$ sufficiently large, the Gaussian part becomes dominant. It seems interesting to determine the behaviour also in the intermediate range of $\sigma.$

• Typos and suggestions.

We thank the reviewer for pointing out a typo in line 237 and for suggesting improvements to the presentation, which we will include in the revision.

Thank you for your detailed response!

1. Could you help me further see the argument for high GAL for Rademacher init? I am familiar with the claim from O'Donnell. Also, it would be good to add this in the main text.
2. What is $d$ in Figure 7? As far as I found it, only Fig 7 is the experiment with 2-layer MLP, correct? The rest (Fig 5 and the main paper experiments) are with 4-layer MLPs.
3. Width: What width have you used in Fig 7? Also, what width have you used for Fig 5 for different $d$ s? Is it the same as (512,512,64) for the hidden layers?
4. It seems that for $d=150,200$, it did not succeed in strong learning. Should I view Fig 7 as a success or failure? I am slightly confused here. Overall, it would be good to conduct experiments with just correlation loss with an appropriate width on a 2-layer MLP and demonstrate success with higher $d$ s, to at least verify the theoretical results as they are.
5. Also, is the sample complexity in experiments really that sensitive to the activation used (as you mentioned in theory)? Also, how real is the dependence on width and iteration complexity derived in the formal results? In experiments, do you see similar blow-ups in the complexities when (a) going from full to almost full parties and (b) changing activations?

Overall, I am still confused with the experiments, and perhaps the addition of more comprehensive experiments in the final version would be nice. The main thing is, besides the initialization, how sensitive is the effect of the activation and loss on the required width and sample complexity? Also, as stated, I request the authors to at least add

1. One convincing experiment in which we succeed in learning with higher $d$ s, ideally using the same settings as in the theoretical results.
2. the intuitive explanation behind low and high GAL for Gaussiand and Rad initialization respectively, in the main text in an easily accessible subsection/paragraph.

The paper has an important contribution. Hoping the authors will improve their presentation further, I raise my score to 6 and support acceptance.

PS: for Fig 8, where the function output is non-binary, is the null/ junk label distribution to measure GAL still Rad(1/2), as used in the GAL definition eq 2?

Thank you for your engagement and for increasing the score. Regarding your further questions:

1. Further details about the argument for high GAL for Rademacher initialization.

Let us give the following simplified argument for the GAL of the first (hidden) layer. The gradient of the first layer’s weights can be written as: $\partial_{w_{ji}} L = - a_i E_x [ f(x) x_j 1(w_i x+b_i)],$ where $f(x) = \prod_{i=1}^d x_i$ is the full parity function. For simplicity assume that $b_i=0$, and let us drop the subscript $i$ for clarity. Then $1(wx+b) = \frac 12 + \frac 12 {\rm Maj} (w \odot x)$, where $x \odot w$ denotes the Boolean vector with j-th entry $w_j x_j$, and ${\rm Maj}(w \odot x) : = {\rm sgn}(\sum_{k=1}^d w_k x_k)$ is the majority function. Now, consider the Fourier-Walsh expansion of ${\rm Maj}$ as ${\rm Maj} (w \odot x) : = \sum_{S \subseteq [d]} \hat {\rm Maj} (S) \prod_{k \in S} x_k w_k$, where $\hat {\rm Maj} (S)$ are the Fourier-Walsh coefficients. Replacing this in the formula above, and using the orthogonality of the Fourier basis elements, we obtain: $\partial_{w_{j}} L = - a_i \prod_{k\ne j} w_k \hat {\rm Maj} ([d] \setminus j ) ,$ and accordingly $\partial_{w_{j}} L^2=a_i^2 \hat {\rm Maj} ([d] \setminus j )^2$. If $d$ is even, the majority coefficient of $[d]\setminus j$ has magnitude $1/\mathrm{poly}(d)$ (using similar calculations as in Chapter 5 of [O’Donnell,'14]) and the GAL lower bound follows for this coordinate of the gradient. For the second layer weights, analogous calculations can be made using ReLU instead of the threshold.

Please note that in the paper we do not compute the GAL for Rademacher initialization. By our negative result, sufficiently high GAL is necessary for strong learning, but in general it is not sufficient. Rather, our positive proof proceeds by direct analysis of the (S)GD process. An important element of the positive proof is the quantity (4), which shows up in the gradient computation in (20). Estimating (4) involves binomial coefficients, which can be seen in the proofs in appendix A.3, e.g., Lemma 1. We can add the GAL computation for Rademacher as outlined above in a later revision if you think it would be informative.

2. What is d in Figure 7? As far as I found it, only Fig 7 is the experiment with 2-layer MLP, correct? The rest (Fig 5 and the main paper experiments) are with 4-layer MLPs.

In figure 7, d=50. We added it in the caption in the revision, thanks for pointing this omission out. Yes, Figure 7 (and now Figure 9) uses 2-layer MLPs, while the rest use 4-layer MLPs.

3. What widths were used in Fig. 7 and Fig. 5 for different d’s? Is it the same as (512,512,64) for the hidden layers?

Yes, in Figure 5 (and 7) the widths of the hidden layers are kept constant, and only the input layer’s dimension is changed.

4. It seems that for d=150, 200, it did not succeed in strong learning. Should I view Fig 7 as a success or failure?

We assume you meant Figure 5, please let us know if we are mistaken. We added Figure 5 as a negative result for weak learning with perturbed initialization. In particular, while with $d=50$ (figure 1) a perturbation of e.g. $\sigma=0.1$ allows to achieve performance close to Rademacher, for larger $d$, the performances seem to deviate, and for $d=200$, only with Rademacher initialization the network seems to pick signal in the first iterations. To achieve strong learning with Rademacher initialization for larger $d$ we have to increase the width of the hidden layers, see new plot (Figure 9).

5. Overall, it would be good to conduct experiments with just correlation loss with an appropriate width on a 2-layer MLP and demonstrate success with higher d’s, to at least verify the theoretical results as they are.

We thank the reviewer for the suggestion. We added a preliminary plot for this, see Figure 9 in the Appendix of the revision. We show that a 2-layer network with clipped-ReLU activation and $d^2$ hidden neurons, with only the output layer trained by SGD with the correlation loss can achieve accuracy 1 for $d = 50, 100, 150, 200$. We will run more experiments and reorganize the order of the figures in the final version of the paper.

6. Also, is the sample complexity in experiments really that sensitive to the activation used (as you mentioned in theory)? Also, how real is the dependence on width and iteration complexity derived in the formal results? In experiments, do you see similar blow-ups in the complexities when (a) going from full to almost full parties and (b) changing activations?

We tried training the same 2-layer network with $d^2$ hidden neurons as in the previous point, using the same setting (SGD with the correlation loss trained on the output layer only), while replacing the clipped-ReLU activation with ReLU activation. We observed that the network does not achieve accuracy 1: from our preliminary experiments it achieves accuracy around 0.55 for d=200, suggesting that the activation does play a role in the complexity of learning, in particular that in our setting ReLU requires more hidden neurons than clipped-ReLU.

From preliminary experiments it is also apparent that almost-full parities require more resources than full parities. We intend to investigate further and add our findings to a later revision.

These findings are subject to some caveats:

• We do not make theoretical claims that our bounds are tight.
• We are somewhat confident that our empirical positive findings are qualitatively robust. In particular, we managed to obtain good accuracies for full parity for various numbers of layers, with or without training hidden weights, and different losses (square, cross-entropy, hinge). The main necessary factor seems to be the Rademacher initialization (also a piecewise linear activation might play a role). However, the particulars can change when the architecture is changed. For example, the difference between clipped-ReLU and ReLU might be empirically validated in the exact setting of our theorem, but disappear (or even reverse) for other losses and architectures.

7a. I request the authors to at least add: One convincing experiment in which we succeed in learning with higher d’s, ideally using the same settings as in the theoretical results.

We added a preliminary plot in Figure 9. Please, let us know if you have any further comment about it.

7b. the intuitive explanation behind low and high GAL for Gaussiand and Rad initialization respectively, in the main text in an easily accessible subsection/paragraph.

We thank the reviewer for this suggestion, which will improve the presentation of our paper. We will add a paragraph with such an explanation in the informal contribution section.

8. For Fig 8, where the function output is non-binary, is the null/ junk label distribution to measure GAL still Rad(1/2), as used in the GAL definition eq 2?

We thank the reviewer for the question. Yes, in the current plot, we used the same definition. We remark that with the squared loss any junk label distribution such that E[y_junk] = 0 gives the same gradients. We will run experiments replacing the junk flow Rad(1/2) with the marginal distribution of f.

We thank the reviewer for the constructive comments. We address the questions in the list below.

• Relevance for feature learning.

Indeed, our positive result does not address feature learning, as it depends only on training the second layer (in the case of the hinge loss the positive result holds also when training the first layer, but it is not necessary). In contrast, our negative result demonstrates that, even when both layers are trained using perturbed or Gaussian initialization and with the correlation loss, feature learning does not occur. Therefore, our negative result is relevant for highlighting the limitations of feature learning under these conditions.

• Relevance for real-world problems.

High-degree parity functions are simple yet challenging targets because learning them requires capturing global associations among the inputs. These functions cannot be meaningfully approximated using low-degree representations, making them a clear and well-defined benchmark for evaluating learning algorithms. As a result, they have become a key focus in recent deep learning research, particularly in studies involving global relationships. In relation to “real-world” problems, beyond offering a simple test for “global reasoning”, they relate to more recent logic and reasoning benchmarks, such as related to arithmetic, coding, genomics, algorithms or networks applications.

• Extension of positive result to d-k parity.

We refer to the general response for a discussion on the extension of the positive result to d-k parities. We additionally note that indeed almost full d-k parities seem learnable with d^\Theta(k) complexity under Rademacher initialization. This is the case even though feature learning is not involved.

We uploaded a new revision of the paper. In this revision:

• We added an additional experiment (Figure 8, Appendix E) for a specific target function, showing that our GAL can capture differences in the loss function used for training.
• We clarified the language in the abstract and the introduction regarding the positive results.
• We added a positive result for ReLU activation and correlation loss for almost full parities $d=k-1$ and $d=k-2$, see Corollary 2 in Section 4.1.
• We added a more precise calculation for a bounded ReLU variant, where $\Omega(d^2)$ hidden neurons are sufficient for learning of the full parity function. See Corollary 1 in Section 4.1
• We made changes aiming to improve the presentation of positive results in Section 4.