Learning High-Degree Parities: The Crucial Role of the Initialization
Authors: Emmanuel Abbe
Elisabetta Cornacchia
Jan Hązła
Donald Kougang-Yombi
Venue: ICLR 2025 Poster (2025)
Keywords: initialization
neural networks
gradient descent
parity functions
complexity
initial alignment
Primary area: learning theory

Abstract: Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degree $k$ parities on uniform inputs for constant $k$, but fail to do so when $k$ and $d-k$ grow with $d$ (here $d$ is the ambient dimension). However, the case where $k=d-O_d(1)$, including the degree $d$ parity (the full parity), has remained unsettled. This paper shows that for gradient descent on regular neural networks, learnability depends on the initial weight distribution. On one hand, the discrete Rademacher initialization enables efficient learning of almost-full parities, while on the other hand, its Gaussian perturbation with large enough constant standard deviation $\sigma$ prevents it. The positive result for almost-full parities is shown to hold up to $\sigma=O(d^{-1})$, pointing to questions about a sharper threshold phenomenon. Unlike statistical query (SQ) learning, where a singleton function class like the full parity is  trivially learnable, our negative result applies to a fixed function and relies on an initial gradient alignment}measure of potential broader relevance to neural networks learning.

Published as a conference paper at ICLR 2025
LEARNING HIGH-DEGREE PARITIES: THE CRUCIAL ROLE OF THE INITIALIZATION
Emmanuel Abbe Ecole Polytechnique Fédérale de Lausanne (EPFL)
Elisabetta Cornacchia
INRIA Paris, DI ENS, PSL
Massachusetts Institute of Technology (MIT)
Jan Hązla & Donald Hougang-YYobly
African Institute for Mathematical Sciences (AIMS), Kigali, Rwanda
ABSTRACT
Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degree k parities on uniform inputs for constant A; but fail to do when k and d-k k grow with d (here d is the ambient dimension). However, the case where
Oa()), including the degree d parity (the full parity), has remained unsettled. This paper shows that for gradient descent on regular neural networks, learnability depends on the initial weight distribution. Rademacher initialization enables efficient learning of almost-full parities, while on the other hand, its Gaussian perturbation with large enough constant standard deviation prevents it. The positive result for almost-full parities is shown to hold up to o = O(d pointing to questions about a sharper threshold phenomenon. Unlike statistical query (SQ) learning, where singleton function class like the full parity is trivially learnable, our negative result applies to a fixed function and relies initial gradient alignment measure of potential broader relevance neural networks learning.
one hand, the discrete
INTRODUCTION
Initialization plays crucial role in the performance of neural network training algorithms. It has been shown that a proper initialization can help avoiding issues such as vanishing or exploding gradients, or set the foundation for efficient convergence and improved generalization (He et al. (2015); Glorot & Bengio (2010); [Sutskever et al. (2013); Kumar (2017)). In this work, we show that the choice of initialization be critical when learning complex functions, such as high-degree parities.
Parity functions are well-known class of challenging problems for differentiable learning models, where the task is to determine the parity of bits belonging to an unknown subset of input coordinates. Due to their inherent non-linearity and extreme sensitivity to small input changes, parity functions often serve as a challenging benchmark for evaluating and comparing learning algorithms, including gradient descent instance, they have been used for showing the advantages of using convolutional architectures over fully connected ones (Malach & Shalev-Shwartz/ (2020)), the superiority of differentiable models compared to kernel methods (Abbe et al. (2021)), and the efficacy of curriculum learning in contrast standard training (Abbe et al. (2024b): Cornacchia & Mossel 2023)
neural networks (Abbe & Sandon (2020); Daniely & Malach (2020)). For
Previous research has mainly focused on the family of sparse parities, also known as k-parities, where the size of the support of the target parity, k, is bounded, i.e., it does not grow with input dimension d. It has been shown that on uniform inputs, k-parities can be learned by gradient descent algorithms (GD/SGD) on standard architectures, such as 2-layer fully connected (Barak al. (002);
Email: emmanuel awbe@eppf..cc..m.. .ch, donald yombii @ai ms. ac. Tw.
a @inria. www.rraaaan...... (jan.hazla,

---

Published as a conference paper at ICLR 2025
Abbe & Boix- (2022) Glasgow (2023); Kou et al. (2024) ) with sample complexity of O(d "oais-""Kooo Kou et al. (2024).
In contrast, for dense parities, where the support of the target parity is unbounded (A: = (1), the picture is less clear. It has been shown that when both & and d - k are unbounded, stochastic gradient descent (SGD) with large batch size and limited gradient precision on fully connected architectures cannot learn dense parities with any initializatton (Abbe & Sandon (2020)) The difficulty in learning parities stems from their orthogonality on uniform inputs, leading to a low cross- cross-predictability (CP) (Abbe & Sandon (2200). However, this only occurs if given class of k-parities is sufficiently large. Since the cardinality of this class is (i) (a=x). this hardness result does not extend to almost-full parities, where d- (d)(),,, including the special case of the single d- d-parity (the full parity).
In fact, it is known that the full parity, as symmetric function, is learnable by gradient descent methods with specific initialization (Nachum & Yehudayoff (2020)), such as setting all first layer weights to 1. For random and symmetric initializations, Abbee & Boix-Adseral (2022) showed that almost-full parities are Sankly-learnableDbb by gradient descent on a two-layer fully connected net- work with discrete Rademacher initialization.
In this paper, we focus on almost-full parity functions and provide a deeper understanding of how the initialization impacts their learning. First, we show that SGD on a two-layer fully connected ReLU network with Rademacher initialization can achieve perfect accuracy for l = d - Oa(1), thus going beyond weak learning. Next, we investigate the robustness of this positive result and argue that it is special case. In particular, we prove that with Gaussian initialization GD with limited gradient precision with the correlation loss cannot learn high degree parities on two layer ReLU networks. We then introduce an intermediate case of where the weights are initialized from mixture of two Gaussian distributions with means +1 and -1 and standard deviation of a. In the case of full parity we prove that when the positive result still holds, while if a is a large enough constant, learning does not occur. We leave the analysis for the remaining range of a and the investigation of potential threshold to future work. While our theoretical analysis focuses on Gaussian perturbations, our experiments also explore other perturbations, both discrete and continuous, supporting our claim that the success of the Rademacher initialization is special case. In our experiments, we also explore other settings beyond our theoretical analysis in order to justify the robustness of our findings.
initialization,
O(d-)),
Crucially, the proof technique for our negative result does not rely on constructing an orbit class or using measures for function classes (as in the cross- prodicrreiittyiliity case). Instead, it introduces a new approach centered on novel measure, the initial gradient alignment, which may be relevant for evaluating the suitability of an initialization for a target distribution beyond the specific parity setting discussed in this paper.
2 RELATED WORK
Learning parities on uniform inputs is easy with specialized techniques like Gaussian elimination over two-element fields or through emulation networks trained with Stochastic Gradient Descent (SGD) using small batch sizes (Abbe & (2020))20200). However, in the statistical query (SQ) setting (Kearns ( (198)) and with gradient descent methods that have limited gradient precision (Abbe & Sandon 2020). learning parities presents computational barriers. Recent works have focused on sparse parities, or k-parities (where = 0,(1)) as a classical benchmark for evaluating learning algorithms (Suzuki et al. (2024); [Eelmma et al. 2023); Barak et al. (2022)
Learning Parities.
Daniely & Malach (2020); Malach et al. (2021)) Abbe & Boix-Adsers (2022) y Malach & Shalev-
Shwartz 2020); Abbe et al. (oomacciaa & ( Wei et al. (2019))) & Telgarsky (201 In particular, in the special case of k = 2 (i.e. the XOR problem), Glasgow (2023) proved a sample complexity upper bound of Ö(d) on a 2-layer network of logarithmic width, while for general k. Kou et al. (2024) proved sample complexity of O(d--1), matching the SQ lower bounds in both cases. For dense parities, has been established that if both k and d & grow with d, SGD
Where Ô(d") O(d" poly log(d)), for E RR
2 Asssuming the initialization is invariant to permutation of the input neurons.
i.c. an inverse polynomial edge over the trivial estimator is achieved with constant probability.
2

---

Published as a conference paper at ICLR 2025
with large batch sizes fail at learning in polynomial time (Abbe & Sandon (0200). We build on
top of Abbbe & Boix-Adsers (2022), which showed that almost-full parities are weakly-learnable by gradient descent two-layer fully connected network with Rademacher initialization. We provide a more complete picture on the role of the initialization for learning the full parity, and we argue that
the Rademacher initialization is in some sense special case.
The Role of the Initialization. Several studies have shown that initialization is crucial for optimiz- ing neural networks. preventing vanishing or exploding gradients (Glorot & Bengio (2010)) speed- ing up convergence (He et al. (2013)) ensuring informative gradient flow in early layers (Sutskever et al. (2033), and enabling learning challenging targets (Zhang et al.] (2019); |Hanin & Rolnick (2018). ) While these works focus on improving learning through tailored initializations, our paper addresses the more fundamental question of what can gradient descent learn with standard initial- izations. Thus, our work aligns more closely with (Abbe & Boix-Adsera (2022); AAbbe & Sandon (2200), which characterize functions learnable by gradient descent on shallow networks, but with- out exploring initialization. Another work (Edelman et al. (202))) shows that sparse initialization aids in learning sparse parities. However, the main challenge their case is identifying the sup- port of the sparse parity. In contrast, when learning the full parity, sparsifying the Rademacher initialization does not aid in learning the full parity (see Figure 3 Section 6p.
Complexity Measures. Previous works have studied the sample and time complexity of learning with SGD on neural networks. proposing various measures, such as: the noise sensitivity (O'Donned)
20hang et al. (202T): Abbe et al. (2022b); Hahn & Rofin (2044), which applies mostly to settings with i.i.d. inputs and is related to the degree of the functions, is known to be loose for strong learning (Abbe et al. (2022a 2023)); the globality degree (Abbe et al. (2024a)), which general- izes the degree and sensitivity notions to non-i.idd settings but remains focused
(2014); /Zhan
weak rather than strong learning: the statistical query (SQ) dimension (Kears (1998); ); Feldman (0116)) and the cross- predictability (Abbe & Sandon 2020)), which are usually defined for a class of fargets/distributioo rather than a single distribution (in particular the full parity is efficiently SQ learnable since there is a single function); the neural tangent kernel (NTK) alignment (Jacot et al. g Cortes et al. (2012)
:
that are limited to the NTK framework; the information exponent (Arous et al. (2021)) Bruna el al. 2023), ). generative exponent (Damian et al. (2024); Dandi al. (2024)) leap (Abbe al. (2023)
and Approximate Message Passing (AMP) complexity (Troiani et al. (2024) ), which measure when fully connected neural networks can strongly learn target functions on i.idd. or isotropic input distri- butions and sparse or single/multi-indee functions. In particular, few works studied measures based on the alignment between the networks initialization and the target distribution, as this paper. (Mok et al. (2022); Ortiz-Jiménez et al. (202I)) studied the label-gradient-alee taligmentt (LGA), de- fined as the norm of the target function in the RKHS induced by the NTK (Jacot et al. (2018) at initialization, showing its empirical relevance for predicting network performance. In contrast, focus on a theoretical analysis, with our measure of initial gradient alignment being loss-dependen Abbe et al. (2022c) defined the initial alignment (INAL) the maximum average correlation of any neuron with the target, providing a lower bound for functions with small INAL, though their result relies on input embedding and orbit hardness, which does not apply almost-full parities.
3 SETTING AND INFORMAL CONTRIBUTIONS
We consider learning with a neural network of P parameters, NN 0). 0 E R.,, initialized as @² ~ DD" for some distribution D and trained using noisy stochastic gradient descent (noisy-SGD, see Def. We assume that the network has access to data samples (z, f()). where x ~ D, for D being distribution in Rd and Rd (=1} is unknown target function. We focus learning parity functions on uniform inputs (D = Unif + 1))). ). A parity function over a subset 5 of the input
coordinates [d] = (1,2,..., d} is function Xs {+1]d (+1), defined as xs(x)) == II Ti, where S C [d]. We will focus on the case where S [d] (full parity) or |S| d - Oa(1) (almost full parity). Let us define our notion of perturbed initialization.
Definition 1 (Perturbed Initialization). Consider neural network with parameters 8 R.P and two independent random vectors A, Ha E R with independent coordinates where A is arbitrary and H has independent entries (Ha), -N a² Tp). We say that a neural network NN(x:; 0)
3

---

Published as a conference paper at ICLR 2025
has (A, ppertured initialization with noise level if its parameters are initialized 89 Ap + (,
We will mostly consider the case where A scenario, we refer to the initialization as o-perturbed Rademacher.
[ni (Rademacher initialization). In this
Theorem 1 (Informal, Positive Almost-Full Parities). Let f(x) = Xs(x), with S S (d.. |S|= = d-Oa(1)- A two-layer ReLU network with some poly(d) (d) hidden units and o-perturbed Rademacher initialization with o = O(d-1) trained by GD or SGD with any batch-size with the correlation or the hinge loss, will learn f to perfect accuracy poly(d) steps.
For our negative result, we introduce the following notion of Gradient Alignment.
Definition (Gradient Alignment). For a neural network (N 0), an input distribution D, target function f R + E, and loss function L E x R + R, we denote the population gradient as
I ( = Ez VoL 0), f()))
If 0 is a random inttialization then we define the gradient alignment of 0 as
G == E (0)0)
(2)
where r-((0)= :- -z.g Lo (x; 0), y)r y ~ ( and independent of x. That is, (0) is the gradient of a random classification task.
We remark that for the squared and the correlation loss, the Gradient Alignment at initialization corresponds to the Label-Gradiens -radieet-Allggneenn Aligmment (LGA) of Ortiz-Jiménzz et al. (202I); Mok et al. 2002), thus our GAL generalizes L.A to other losses.
We first prove that, under some conditions, if the Gradient Alignment at initialization is small, the network does not learn. We remark that this result holds for general input distributions (beyond Boolean and uniform) and for all networks with linear output layer (see Section 5.1 for details).
Theorem 2 (Informal, Negative General). Let f R& + {+1} be larget function, and let NN 0) be a neural network with a linear output layer, trained by noisy-GD with noise level t and the correlation loss. Assume either: 1) Gaussian initialization of the weights and homogeneous ac- tivation, or 2) (A, σ) -perturbe initialization,, polynomially bounded gradients, and small enough (see details in Corollary 3). If (6%) exp( -S(d)), then after poly (d) training steps, the network will achieve accuracy of at most 2 + ((xxp(-Q(d)))
We then apply this result to the case of almost-full parities uniform inputs.
Theorem 3 (Informal, Negative Almost-Full Parities). Let f(x) xs(z), for S S [d]] such that [S] 2 d/2. Noisy-GD with correlation loss and any noise level t = pol/poly(d)) on any two- layer connected ReLU network of poly(d) size, initialized with Gaussian initialization will not achieve accuracy better than random guessing in poly(d) training steps.
We expect Theorem 3 to hold also in case of o-perturbed Rademacher initialization for > a² for some fixed o²
To that end in Section 5.2.2 we prove the gradient alignment bound for the hidden layer weights in the perturbed case. Together with similar bound for the output layer weights (which we omit from this version the paper) that would give the statement of Theorem also for the o-perturbed initialization, with o > o".
Full versions of Theorems separation between Rademacher and Gaussian initializations: Noisy-GI for correlation loss, when applied to a two-layer fully connected ReLUU network with some poly(d) hidden neurons, can learn the full parity function in poly(d) steps if the network is initialized with Rademacher weights. However, using Gaussian initialization while leaving all other aspects of the algorithm unchanged requires exponential time to learn. Furthermore, the negative result is robust to details like changing hyperparameters, and as discussed above, both positive and negative results are also valid for some ranges of o-perturbed Rademacher initializations.
in the following sections provide the following rigorous
*The correlation loss defined Tecore (v. 1) -----
4

---

Published as a conference paper at ICLR 2025
4 POSITIVE RESULT FOR RADEMACHER INITIALIZATION
In both positive and negative results we will be working with the noisy SGD and GD algorithm specified below:
Definition (Noisy-(S)GD). Consider neural network (N) with initializatton of the weights 00 Let J X + IR. be larget function defined on an input space X. Assume we are given fresh samples xt DD for some input distribution 'D defined on X. Given a weakly differentiable loss function L. the updates of the voisy-SGD. algorithm with learning rate are defined by
0++1 = 0 -
V oe (() -% )
(3)
B
where for all t E fo....." and they are independent from other variables, and B is the batch size. If the average over the batch size B. Eomi VoLLNNN(""; f(x))) is replaced by the population mean EzED (Vo 0"), [(r)), we refer to the algorithm as (full batch) noisy-GD.
1}. Zt are i..d (O, for some noise level т,
In this section we consider two layer neural networks with Rademacher initialization for the hidden layer weights. Our results imply that with large enough poly(d) number of hidden neurons, the hidden layer embedding induced by the Rademacher distribution makes the almost-full parities for k - Oa(1) linearly separable. Then:
1. When trained with the correlation loss on the uniform input distribution, the network achieves perfect accuracy in one step of full GD or poly(d) steps of SGD.
2. When trained with the hinge loss any input distribution, the neural network achieves classification error e in poly(d)/e / steps of SGD. (For simplicity we restrict this result to full parity.)
As mentioned, our positive result for the full parity holds also for a perturbed Rademacher initial- ization with deviation up to C/d for some constant C. > O. We demonstrate this for hinge loss, see Section
4.1 GD AND SGD WITH CORRELATION LOSS
We consider fully connected network (xx) = E 1:0 (W; + bi), where is arbitrary activation function. In the corollaries we will take o to be either ReLU or its clipped version. The network is trained with correlation loss L(y. 9) -y where only the output layer weights trained. This is in contrast to the hinge loss result in Section [42 where we allow training of both layers. The gradient of output weights on input x {+1)d is given by V. faa()) + b), where W is an n x matrix with rows Wi...., Wn, and (x) = I. H; is the almost full parity function. During training, the inputs are sampled from the uniform distribution on {=1]".
The hidden layer weights w, are initialized as i.i.d. Rademacher and the output weights n2 0. The biases are i.i.d. according to some distribution b, ~ B. Our result depends on the following quantity:
Σ 23 + b )
d
A A = (=-(= (-1)ld-a-E)z1 as)
(4)
2 = A2 and lo(w x + b)1 S R, where both 2
In the following, 1et us assume that Es- and R vary with d. Furthermore, such that for every b in the support of B it holds Ad.b < CA. (The last assumption is satisfied for any distribution B with a support of constant size. The distributions we consider in the corollaries have this property.)
assume that there exists constant C not depending on d
2 (dd then, except with probability at most 2 2exp(-1x over the choice of initialization, we have sign(N' (z)) = fa(x) for every x E {+1]á, where (') denotes the output of the network at time t. This conclusion holds also in the presence of GD noise of magnitude up ( RRR).
Theorem 4. Consider a network as above trained for one step with the GD algorithm.
5

---

Published as a conference paper at ICLR 2025
Theorem 5. Consider the above network trained with SGD of any batch size. Let M(d Rt Then, except with probability 3 exp(-d), after T 2 Q A (d + logn)) steps, the network predicts correctly sign(N (NT (z)) fa(x) for every E [+1]d in the presence of GD noise of magnitude up to 0 TT2 R
(3).
We present an application of Theorem 4 to specific setting. By estimating A, we prove corollary for the full parity function for ReLU activation and its bounded variant, i.e., clipped ReLU. For clipped ReLU, order of de neurons are sufficient for learning with high probability. We also provide a result for the almost full (d ---paiities for ReLU activation and any = O(1):
Corollary 1. In case of the full parity a = 0 and = ReLU, let b; = 0 if is even or b, = - if odd. Then, we have 2 (1/dd) and R d+I1 1. Hence, 2(d²) hidden neurons are sufficient for strong learning in one step of GD. In the case of clipped ReLU o(x) max(0, min(x, 5)) it holds A = =(1/d) and 5, hence ((d))) hidden neurons are sufficient.
Corollary 2. Let a E N. Take b ~ B such that b; a 2 with probability 1/2 and b; = = with probability 1/2. Then, for a = ReLU it holds A 2 ((d-1-2[a/2) Accordingly, n 2 (d o/21 hidden neurons are sufficient for strong learning in one GD step.
In the corollaries above, we have chosen convenient bias values for simplicity, but the precise values are not crucial except for "unlucky" choices where A can become too small. In particular learning should hold for random biases for most reasonable distributions. For the clipped ReLU activation, we expect (but do not prove) that the bound on the number of neurons in Corollary [ could be improved to n 2 ((d2+1a//21 using a similar modification in Corollary |
4.2 SGD ANALYSIS FOR HINGE LOSS
One of the implications of Theorem is that under Rademacher initialization, with high probability the hidden layer embeddings of the parity function are linearly separable. We use known techniques (in particular, we borrow parts of the analysis Nachum & Yehudayoff (2020) to show that this implies learning for SGD under the hinge loss. For simplicity in this section we restrict ourselves to the ReLU activation and full parity. We refer to Appendix A.5 for details.
5 NEGATIVE RESULTS
5.1 NEGATIVE RESULTS FOR GENERAL TARGETS
In this section we prove negative result that holds for all neural networks with linear output layer: Definition 4 (Linear Output Layer). We say that a neural network NN(x; 0) has linear output layer its output can be written as NN(x; 0) = Ei= ts NN,(x; v), where 0 = (v, v)) are the trainable weights of the network, and n denotes the number of neurons in the last hidden layer.
In the context of binary classification, the network's s +1 label prediction is given by sign (NN(a;; 0))- Let us state our main negative result.
Theorem 6 (Negative Result for General Targets). Let NN(x; 0) be network with a linear oulput layer. Let the weights @ be initialized according to an (A, a)) --perturbed initialization (Def. 7). for A E "R with independent coordinates with distributions symmetric around O. Assume the network is given samples (x, fx)) where x ~ D, for D being a distribution on Rdd Let NN(x; 8r¹) ) be the output of the noisy-GD algorithm with noise level T and learning rate 7 after T steps of training with the correlation loss. Assume that there exists some bound > such that for every 0 & X2 < TT??7 we have
GBL (BL S +
(5)
TVE where H ~ N(O,Tr). Then, P P[sign(NN((r) 0T)) f(x) S 2 27
In words, this theorem states that if IqquationShoolae for E which is small compared to the noise level then noisy gradient descent will require large number of training steps achieve performance better than random guessing. Therefore, even the weakest form of learning is impossible. We provide here brief outline of the proof, and refer to Appendix B for the full proof.

---

Published as a conference paper at ICLR 2025
Proof Outline of Theorem Our proof is composed of three steps: 1) We define the 'junk-flow', ie. the training dynamics of a network trained on random noise (Definition 66: 2) We show that if the 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 5 3) For correlation loss, demonstrate that if equation holds, then the GAL remains small along the junk flow. Notably, steps (I) and (2) apply to any architecture with a linear output layer, symmetric initialization, and any loss function. However, step (3) is currently limited the correlation loss, as tracking junk-flow dynamics for other losses is more complex.
Let us make few remarks.
Remark 1. For simplicity, we present Theorem 6 in the context of full batch noisy-GD. However, we note that the proof can be extended to noisy-SGD with sufficiently large batch size, by leveraging the concentration of the effective gradient around the population mean, similarly to e.g. (Abbe & Sandon (2220) Theorem 3). Remark 2. We propose using GAL. as a measure for hardness of learning. However, the condition in equation requires verifying that GAL, remains small for all Gaussian perturbations of the initialization, with variance within the specified range. In Corollaries
we demonstrate that, in some settings, the condition in equation 3 can be simplified and expressed uniquely terms of GAL, ((0).
Remark 3. We emphasize that Theorem 6 applies to any binary classification task and network architecture with a linear oulput layer, unlike, for example, Abbe et al. (2022c). which is specific to Boolean functions and product measures. Importantly, our result is restricted to the correlation loss, as the proof relies on coupling the gradient descent dynamics with the 'junk flow', as mentioned in the proof outline. We empirically observe that also for hinge loss, the GAL, remains small along the junk flow over time (see Figure[i in Section 0
As first corollary, we show that when the GD noise level is small compared to the variances in the initial Ha, the distributions of H, and H, + XH are similar. As a result, equation 5 can be expressed in terms of GAL,((").
Corollary 3. Let f Rd - {=1} be target function under given input distribution D. Let NN(x;0) be network with linear output layer, with weights initialized according to an (A. perturbed initialization, for O-symmetric independent A R.. Assume that VEz/VNN(ar 0)1
R for all OFLer Let (N(x; 8T) be the output of the noisy-GD algorithm with noise level t and learning rate 7 such that 72 o² min, Var
after T steps with the correlation loss. Then,
PT
P(NN(,; 0-) = ((x)) 5 T
(6)
2T
The proof of Corollary is deferred Appendix B.3
While the above corollary applies to gen- eral perturbed initializations, it relies on the assumption that the GD noise level 7 is sufficiently small. However, we also show that in the specific case of Gaussian initialization and assuming a homogeneous architecture, this assumption can be removed.
to
Gaussian Initialization. Let us restrict ourselves to the special case of Gaussian initialization, i.c. when A = Op. We assume that the activation h satisfies the following homogeneity property. Definition 5 (H--Wakll Homogeneous.). Let h IR IR be an activation function. We say that h is H f--weally homogeneous if for all x E IR and C' 2 0, h(Cxx) = hzx).
For example, ReLU(x) max (0, 2) is 1-weakly homogeneous. z6 is k-weakly homogeneous, for all k E N. We prove the following result.
Corollary 4. Let NN(x; 0) be fully connected network of depth L, with H-weakly homogeneous activation and with weights initialized as 0% ~ (O, of, where lp denotes the layer of parameter 8g. for p [P]. Let Rd + {+1} be a balanced target function. Let NN(x; 8T) be the output of the noisy-Gi fidy--DDeee algorithm with noise-level t, after T steps of training with the correlation loss. Then,
T
L
TT272 of
H
P(NN(x; = f())) 2 + 2r
II
1+
(89
(7)
[=1
This always holds if assume gradient clipping.
7

---

Published as a conference paper at ICLR 2025
5.2
NEGATIVE RESULTS FOR HIGH-DEGREE PARITIES
5.2. SMALL ALIGNMENT FOR GAUSSIAN INITIALIZATION
In this section we state rigorous lower bound for learning of large degree parities with pure Gaus- sian initialization. This is in the setting of two layer ReLU neural networks. Then we will discuss extending this result to perturbed Rademacher initialization for a large enough constant perturba- tion.
Theorem 7. Let 0 = (w, b, for W E Rexd b RR, U E R" and (N; 0) = 1/ (wL bz). Let a a(d) d/2 and [a(x) I Hy. Consider the i..d initialization w N (o, Idnxd), b~ (N0 Id,) for any 0² 0(1), N n Id,).
Then, for any number of hidden neurons exp(o(d)), any number of time sleps T = explo(d)). any learning rate S I exp(o(d)), any noise level of the noisy GD algorithm with correlation loss,
$ T exp(o(d)), after T steps
1 exp(-S(()) 2
Pr [sign(NN' (æ; 0)) fa(x)]
Theorem 7 follows from Theorem 6 and the following bound on the gradient alignment:
Proposition 1. Let a neural network be as in Theorem 7 Then, for every où > 0, there exists C,C² > 0 such that for any network with o² S oū we have gradient alignment bound
GAL (0) S PC' where = ndd 2n is the total number of parameters.
5.2.2 SMALL ALIGNMENT FOR PERTURBED INITIALIZATION
Consider the perturbed Rademacher initialization + (r + 9) for g (O, o²) for some constant Va O. In order prove a rigorous lower bound like Theorem for this initialization, we need to establish the alignment bound for GA + g). Once this bound is proved, the remaining steps of the proof are similar as for Theorem
Theorem 8. There exists do 0 such that for all a = a(d) such that og so S exp(old)) the following holds:
Let 0 = (w, v) for Raxd, v E R and NN(x;; Ei= us ReLU(w,.) Let f(x) II Nz. Ja(r 9) where Rad(1 (nd(1/2), 9 NO0,0²) with all N Id...
Consider the i.i.d. initialization
coordinates independent,
Then, for any number of hidden neurons n = exp(o(d)), any number of time steps T = exp(o(d)), any learning rate S S exp(o(d) any noise level exp(-o(d) S r I exp(o(d)), after T steps of the noisy GD algorithm with correlation loss,
Pr [siii (I; = f(x)] S 5 exx((-
(10)
Proposition There exists oo. C,C" O such that the following holds: Let the setting be as in For any network with perturbed initialization with Jo have gradient alignment Theorem & bound
(0)
exp(-Cd)
(1I)
where P == nd + n is the total nunber of parameters.
The proofs for this section can be found in Appendices C and
6 EXPERIMENTS
In this section, we show empirical results on the impact of the initialization learning the full parity. As our model, we use multi-layer perceptron (MLP) with 3 hidden layers of neurons sizes 512, 512 and 64 with ReLU activation, and we train with SGD with batch size 64 on the hinge loss, training all layers simultaneously. Each experiment is repeated for 7 random seeds and report the 95% confidence intervals. In Appendix we report further experiment details, as well as additional experiments.
8

---

Published as a conference paper at ICLR 2025
Test Accuccayyyy
0.0
Accuracy
0.80
0.0
0.2
0.70
02
0.4
gouss:
0.60
0.4
0.55
gauss.
25000 50000 75000
100000100001100000000000000
10000
50000
90000
130000
Epochs
Train Size
Figure 1: Learning the full parity with o-perturbed initialization by SGD with the hinge loss on 4-layer MLP, with d = 50, with online fresh samples (left) and with an offline fixed dataset (right).
10
10-4
rad. Init,, t-0, exact
Rigma-8.1
5igma=0.3
GAL
10-4
R.6
10-4
Sigma=0.8
8gm9a6..9
10-1
init, (=0, exact
0-0.3
gauss. init, t-2
0.04
10-3
init. t=5
10
3x
4x100
input dim. (odd)
input dim.
Figure 2: Computing numerically the alignment GAly with the hinge loss (left) and the correlation loss (right), for one-neuron network.
o-Perturbed Initialization. We first consider learning the full parity function with o-perturbed initializations and investigate the effect of varying a (Figure[). To make different initializations comparable, we normalize them such that the variance entering each neuron is (see Appendix for details). We observe that the accuracy after training decreases as increases. This pattern is seen in both the online setting (left plot), where fresh batches are sampled at each iteration, and the offline setting (right plot), where the network is trained on fixed dataset until the training loss decreases to 10-2, and evaluated on a separate test set. For input dimension d = 50, as in Figure | some learning occurs for a {0.1, 0.2). However, the Appendix, we report experiments with larger input dimensions, where learning does not occur for these values of (Figure5).
we find that
Gradient Alignment. In Figure 2 compute the gradient alignment for one-neuron ReLU network under different initializations and losses, which are not covered by our theoretical results. The left plot shows the GALy initialization for the hinge loss with Rademacher. o-perturbed Rademacher and Gaussian initializations, across input dimensions up to d 40. We observe that GAL, seems decrease an inverse-polynomial rate for Rademacher, but super-polynomially fast for Gaussian and o-perturbed initializations for large (e.g.
{0.8, 0.99)). The case of smaller {0.1, 0.3) less conclusive. We also estimate, with Montecarlo, the GAL after training the neuron for a few steps (! = 2 and / 5) on random labels (dots). We observe that training on random labels does not increase the GAT.y- theoretical understanding of this observation would allow extend our negative result to the hinge loss.
In the right plot, we estimate numerically the initial GAL, for the correlation loss for a single threshold neuron. We consider o-eerturbed initializations with small contrasting Theorem 8 and Proposition which apply only for large a. For small a, GAL, deviates from the Rademacher case, suggesting that it could be super-polynomially small for all constants 0. Further investigation for small a is left for future work, and Appendix E shows that GAL, remains super-polyy polynomalll small for larger values of a, confirming our theory.

---

Published as a conference paper at ICLR 2025
0.9
Red. +Unit, c:0.1
0.85
Test Accuracy
Unlt+ 0:1.0
Accuracy
0.80
Rad. Unif,
Rad.
Radi+Unif, 0:1.0
sparse Rad., s:1/3
0.70
sparse 5:1/2
sparse 5:15
Sparse Rad, c1/3
0.6
Uniff -2. 1.2)
sparse Rad., s:1/5
0.00
Unif(-2, - 1,1
0.5
0.55
20000
40000
60000
80000
100000
10000
50000
90000
130000
Epochs
Train
Figure 3: Learning the full parity with perturbations of the Rad. initialization by SGD with the hinge loss on a 4-layer MLP, with d = 50, with online fresh samples (left) and with an offline dataset (right).
Other Perturbed Initializations. We next explore perturbations beyond mixtures of Gaussians. In Figure 3 we consider three types: 1) a mixture of two continuous uniform distributions with means +1 and 1,, and standard deviations
(0.1, 2) sparsified Rademacher initialization, where a fraction E {1/2, 1/3, 1/5} of the weights are set to O, and the rest follow Rad(1/2) distribution; and symmetric discrete initialization, where the weights are randomly chosen from (1,,-1,1,2) We find that the mixture of continuous uniforms behaves similarly to the mixture of Gaussians: for 0.1 and input dimension d 50, the network successfully learns, but learning is prevented at larger Additionally, we observe that all other discrete initializations fail to enable learning, suggesting that the Rademacher initialization a special case.
7 CONCLUSION
In this paper, we advance the understanding of whether high degree parities can be learned using noisy-GD standard neural networks with i.i.d. initializations. Specifically, we show that while the full parity is easily learnable with Rademacher initialization, becomes challenging when Gaussian perturbations with large variance are introduced. This constitutes separation between SQ algo- rithms and gradient descent on neural networks: the full parity is an example of a function that trivially learnable in the statistical query (SQ) framework but difficult for noisy-GD neural networks with most typical initializations, with the Rademacher being a special case. It raises inter- esting questions about threshold where learning behavior changes based the perturbation level a. result, e.g., to hinge loss and/or deeper architectures.
Additionally, we propose novel, loss-dependent measure for assessing alignment between the ini- tialization and the target distribution, and prove a negative result for the correlation loss that applies general input distributions, beyond the specific case of full parity and Boolean inputs. We leave to future work investigating if this technique can be applied more generally, especially in other scenarios where the dynamics remain stuck near initialization for a significant time (hardness of weak-learning). For example, such behavior is plausible for targets presenting symmetries and re- quiring some level of 'logical reasoning' (e.g. arithmetic, graphs, syllogisms), for which parities are simple model. Similarly, we leave open strengthening of the negative result, e.g., to hinge loss and/or deeper architectures.
8 ACKNOWLEDGMENTS
The authors thank Nati Srebro for a useful discussion and Ryan O'Donnell for helpful communi- cation regarding binomial coefficients. Part of this work was done while EC was visiting the African Institute for Mathematical Sciences (AIMS), Rwanda. JH and DKY were supported by the Alexan- der von Humboldt Foundation German research chair funding and the associated DAAD project No. 57610033. EC was partly supported by the NSF DMS 201 1883 and the Bush Faculty Fellowship ONR-N00014-20-11220
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Mathoverflow.
oeu.ssaarrccceentttaaioooooooao 2020.
Emmanuel Abbe and Enric Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. arXiv preprint arXiv:2208.031 10t::2208.031/3 03113, 2022.
Emmanuel Abbe and Colin Sandon, On the universality of deep learning. In Advances in Neural Information Processing Systems, volume 33, pp. 20061-20072, 2020.
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 Process- ing Systems, volume 34, 2021.
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pp. 4782-4887. PMLR, 2022a.
Emmanuel Abbe, Samy Bengio, Elisabetta Comncchha,, Jon Kleinberg, Aryo Lotfi, Maithra Raghu, and Chiyuan Zhang. Learning to reason with neural networks: Generalization, unseen data and boolean measures. Advances in Neural Information Processing Systems, 35:2709-2722, 2022b.
Emmanuel Abbe, Elisabetta Comaachiaa, Jan Hazla, and Christopher Marquis. An initial alignment between neural network and target is needed for gradient descent to learn. In International Con- ference on Machine Leurning, pp. 33-52. PMLR, 2022c.
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: leap complexity and saddle-to-sadeee -o-dddle dynamics. In The Thirty Sixth Annual Conference on Learn- ing Theory, pp. 2552-2623, PMLR, 2023.
Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can trans- formers reason? the locality barrier and inductive scratchpad. arXiv preprint (.XXi::40600644000 2024a.
Emmanuel Abbe, Elisabetta Cornacchia, and Aryo Lotfi. Provable advantage of curriculum learning parity targets with mixed inputs. Advances in Neural Information Processing Systems, 36, 2024b.
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from high-dimensiona inference. Journal of Machine Learning Research, 22 (106):1-51, 2021.
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hid- den progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 15:21750-21764 2022.
Stanford Bonan and Dean Clark. Estimates the hermite and the freud polynomials. Journal of Approximation Theory, 63(2):210-27) 224,, 1990.
Joan Bruna, Loucas Pillaud-Vivien, and Aaron Zweig. On single index models beyond gaussian data. arXiv preprint arXiv:2307. 15804, 2023.
Elisabetta Cornacchia and Elchanan Mossel. A mathematical model for curriculum learning for parities. In International Conference Machine Learning, pp. 6400 6423. PMLR, 2023.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kemels based on centered alignment. J. Mach. Learn. Res., 13(1):795-88) 828, mar 2012. ISSN 1532-4435.
Alex Damian, Loucas Pillaud-Vivien, Jason Lee, and Joan Bruna. The computational complexity of learning gaussian single-index models. arXiv preprint arXiv:2403.0552) 2024.
Yatin Dandi, Emanuele Troiani, Luca Amaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krza- kala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv:2402.03220, 2024.

---

Published as a conference paper at ICLR 2025
Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Infor- mation Processing Systems, 09220356-20366 2020.
Benjamin L Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Pareto frontiers in neural feature learning: Data, compute, width, and luck. arXiv preprint (0Xiv:23000038000 2023.
Vitaly Feldman. A general characterization of the statistical query complexity. arXiv preprint arXiv: 02198, 2016.
Margalit Glasgow. Sgd finds then tunes features in two-layer neural networks with npar-optimal sample complexity: A case study in the xor problem. arXiv preprint arXiv:2309.55111, 2023,
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? arXiv preprint arXiv:2402.09963 2024.
Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture. Advances in neural information processing systems, 31, 2018.
Bernard Harris and Andrew P Soms. The use of the tetrachoric series for evaluating multivariate normal probabilities. Journal of Multivariate Analysis, (02):252-2677, 1980.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent achieve arbi- trarily small test error with shallow relu networks. arXiv preprint arXiv: 12292, 2019.
Nirmit Joshi, Theodor Misiakiewicz, and Nathan Srebro. On the complexity of learning sparse functions with statistical and gradient queries. arXiv preprint arXiv:2407.00662. 2024.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45 (6):983-1006, 1998.
Yiwen Kou, Zixiang Chen, Quanquan Gu, and Sham M Kakade. Matching the statistical query lower bound for k-sparse parity problems with stochastic gradient descent. arXiv preprint arXiv:2404.12376 2024.
Siddharth Krishna Kumar. On weight initialization in deep neural networks. arXiv preprint arXiv: 1704008870 2017.
N Lebedev. Special functions and their applications. Courier Corporation, 1972. Translated by Richard A Silverman.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer, 2013.
Eran Malach and Shai Chaley-Shwartz Computational separation between convolutional and fully- connected networks, 2020.
01369
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels. In International Conference on Machine Learning, pp. 7389.7389. PMLR, 2021.
Jisoo Mok, Byunggook Na, Ji-Hoon Kim, Dongyoon Han, and Sungroh Yoon. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training?, 2022. URL
14577
12

---

Published as a conference paper at ICLR 2025
Ido Nachum and Amir Yehudayoff. On symmetry and initialization for neural networks. In LATIN 2020: Theoretical Informatics: 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings 14, pp. 401-412, 2020.
Ryan O' O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. doi: 10.1017/ 1B09781139814782.
Guillermo Ortiz-Jiménez, Seyed-Mohsen Moosavi-Dezfooli and Pascal Frossard. What can lin- carized neural networks actually say about generalization? 2021. doi: 10.48550ARXXIV21066 06770. URL
org/ httpg//bs/2200.... 06770
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
lyya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147. PMLR, 2013.
Taiji Suzuki, Denny Wu, Kazusato Oko, and Atsushi Nitanda. Feature learning via mean-field -ield langevin dynamics: classifying sparse parities and beyond. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Emanuele Troiani, Yatin Dandi, Leonardo Defilippis, Lenka Zdeborová, Bruno Loureiro, and Flo- rent Krzakala. Fundamental computational limits of weak learnability in high-dimensional multi- index models. arXiv preprint arXiv:2405.15480 2024.
Oldrich Alfons Vasicek. A series expansion for the bivariate normal integral. Journal of Computa- tional Finance, 1(4):5-10, 1998.
Roman Vershynin. High- Dineensinnii Probability: An Introduction with Applications in Data Sci- ence. Cambridge University Press, 2018.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Chiyuan Zhang, Maithra Raghu, Jon M. Kleinberg, and Samy Bengio. Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization. ArXiv, abs/2107..15800 2021.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. arXiv preprint arXiv: 1901:0900 2019.
A PROOFS AND DETAILS FOR SECTION 4
useful identity to remembered for later is, for every x, w E {+1]d:
kywy (-1) (-1)(d-w-z))) ww2)/2
(12)
13

---

Published as a conference paper at ICLR 2025
A.1 PROOF OF THEOREM 4
First, consider the case without GD noise. One step of GD with learning rate results in the following update:
d=u
of
4-1 = v/j + + 1211
πIa zjj
ow;
x + b,)
(13)
j=1
d-a II j=1
of + +y
Wij
(-1)(d
2/) >
Wij + b,)
(14)
j=1
d-a
II
Wej
(a) d.bi,
(15)
keeping in mind from equation 4
that
25)/2 Enn (-1)dd-a-Z 25)/2
Σ B3 + D
(16)
Since wy x is distributed as a sum of i.i.d. Rademachers regardless of w;, the value in equation indeed can be replaced with the factor A (a)
14
d,b.,a which does not depend wy.
Accordingly, after one step of GD starting zero weights w0 0, the output of the network is given by
N (z)
(w x x b.) 7 d,b..a II
(17)
For fixed x E {=1]d and in expectation over w and b, this using equation 12
d-a waya + b:)
E N' (x) =
Eb;
A d.bi.o E Eu [12)
(18)
i=1
d-a
d,b. E B (-11)dd= Eder wyyz) x + b))
Es,
j=1
1=1
(19)
d-a
d-a
z
Ebb
(a) d,b.. 12] =
II Ij
nd²
(20)
j=1
Let us come back the expression fa(xNN (z) for a fixed x E {+1)d. Its value random variable depending the hidden layer initialization W. By equation 17 it can be written sum of n i.i.d. random variables, and each of them has absolute value most yRCA. Furthermore, it follows from equation 20 that (a prediction error probability by Hoeffding's ' incquality:
=n Therefore, we can upper bound the
m
n
Pr(fa(z)N'' (z) < 0] arb
Pr wib
[a(=))\ (x)
S exp
S exp(-2d), (21)
2
where the last inequality holds for 2 I(d (dd
)= Therefore, by union bound, the network will make
correct predictions fz (z) 0 for all {11]" except with probability exp(-d).
In the presence gradient noise, the weights are given as et v² + 75, where & ~ -N 12)))
Then,
- + Σ (w, I + +b) > fa(z) -7R Σ
& (22)
1=1
14

---

Published as a conference paper at ICLR 2025
Using equation 21 except with probability exp(-d), will have fa(x) (x) 0 for every Note that El = T 22 so by
as long as yR 2 [al I 2 or equivalently E, 15x1
"ma²
nd² 2/2
assumption - 0 we have Σ, E
nd 422
Furthermore, as f; has Gaussian distribution, its absolute value |& is sub-Gaussian (see, c.g., Propo- sition 2.5.2 in Vershynin (018)). Therefore, by uub-Gaussian concentration, we can estimate
n 2
R2 ))
n
Pr
&&
< Pr
K.
Z
S exp
-S2
exp(-d))
2R
4R
(23)
where the last inequality holds as n 2 lid classifies all inputs correctly except with probability most 2 exp(-d)
ft
X2 and 7² = 0 ) All in all, the noisy network
A.2 PROOF OF THEOREM S
In the general case of noisy SGD, let ra R" be the update given by GD, that is 8/ Ea (1) x + b.). The SGD update can be written as
-++ = of + 7e, + +
1++
(24)
where: (a) et for 1 < i < n is a random variable with expectation Eef = i; and bounded by lefl S R: 5t (0, 7 Id); and where those random variables independent across time.
From equation
i Md ). except with probability exp(-d) over the choice of hidden layer weights w and biases b, for every x E {+1)d it holds
m
fa
n (w; + +b)))
(25)
2
Let {+1]d. We estimate
n
(x)
(Tu: +
Σ c
1 +
(
x bb)
(26)
?TnA²
T
-RR
c
U:
(27)
2
Accordingly, if E,
<
Tn4²
and |Σ e
U/
TnA²
for every S S n, then
SR
8R
fz(x) 0. We now show that each of those two events fails to occur with only exponentially small probability.
First, recall that we have almost surely lef1
< R. By Hoeffding's inequality,
2
T 27 R
Pr
Σ 1=1
c
v,1
< 2exp
S eexp(_d)/n.
8R
as soon as T 2 Q R' log By union bound, 1, e - < except with probability exp(-d).
Tnd 8R
holds for every 1 5 i S n,
As for the additional Gaussian noise, observe that for 7 = 0 .TA' R
we have
TnA
E
=nTVT 5
(28)
16R
1=1
15

---

Published as a conference paper at ICLR 2025
c: Ee
Similarly as in the GD case,
is a sub-Gaussian random variable. Therefore, we have
vT'
concentration
T
Tnd²
TnA²
Pr
S
Pr
Σ
(29)
8R
16R
1=1
TnA')
exx
-Ω
(30)
R2R
S exp(-d))
(31)
since O(vTA2/R) and QQ(
A.3 PROOFS COROLLARY D AND COROLLARY
Let Ad,bo == d.b.'r We need to find asymptotic bounds on |dd,a for o = ReLU and clipped-ReLU (let's denote it as CReLU) and | L deL.R for a > 0. We therefore turn to de-
veloping formulas for Ad,,CCRLLU and A (a) claim:
Ret. Let's first consider the following combinatorial
Claim 1. For any integer d, c> and d' such that S d:
1. -)) (-1)
=
2. Ei=c(-1)h((1 --)))((((((())((((3
(-1)))((33)
3. E- = --1) (-1) (t2)
4. --1)) + (-1))
Proof. Here and below, we follow the convention ( for < 0r
1. This follows by observing that it is a telescopic sum, with the term (-1)d(a=1) d
=
0 by
convention:
d
d (1)
((1 (d-1)
+ d k ( = -- d (d-1) )
1(11
(32)
1:
k
c-1
k=c
k=c
2. Here we use the above and the fact that k(()) d d((=))
d (d1)
= (-1) (d2) 2)
(-1)
11)
1)ah
(33)
3:
k- k-1
c
k=c
k=c
3. This follows from equation 32 indeed
d (
E-1)
d
Σ
(-1)* (1)
kk
(34)
k=c
k=c
k=c+11
d dd1 (c-1)
(-1)²² (4-1)
(-
(35)
4. Similarly this follows from equation 33
d
d
Σ (-1)** d
Σ(-1)*
(-1)**
(K)
(36)
k
k
k=c++
dd 2
2)
+ (-1) (dd- 2
= (--1)
2
-
16

---

Published as a conference paper at ICLR 2025
Lemma 1. Let d > 1, R, c == bd == [(d - b)/2] and c' = [(d b+ 5)/2]. Then,
(-1)dte
(d ( b) (d (d-2) 2)
(c- - (d b) (d (d-2) (
R.LL
(37)
2d
c 1 :
Ad,,,CROLU = (-1)ate
( (d-2)
( (d-2) 2)
(c-1)
(d+ b)
- (d b)
(38)
2
c-
(-1)uto'
d - 2
dd (d- c' }
+
(d+b- 5)
- (d b 5)
(39)
2d
c' 1
Proof. Recall that x. in the definition of Ads,o is distributed as i.i.d. uniform Rademachers. There- fore, we can write Ij = -1 + 2zj, where 2 are i.dd uniform Bernoullis. Using Claim | and the definition of A
Rd,U = (-1)4BB
(-1)23 s ReLU b- d 2
23
(40)
(d) k
= (-1))² -d
1)
(b - d + +1k).
(41)
k=c
(d-1) + 2d 2 2)
d-1 1
= (-1)dto2- d
(b- d)
(42)
c-
c-
(d(d-2)
c-22 - d (d- 2)
( 10-1) 1
= (-1)ato2-d
c- +b
(43)
c
(-1)a=c
(a)ddd1))) 2) - (d b)
(d-2)
d d 2)
(d (d+
(44)
2d
(--22 2
1
Similarly we have,
Ad,,CCRLUU = (- (-1)E, CReLU 6- b-d+2 2j
+CRLLU
(45)
J=1
dd
=-11)2-- -d
(-1)+
min - d 2kk,,
(46)
k.
k=c
(-1)d2 dd
1)*
dd)
(b d + 2k) + +5(-1)62-
Σ (-1)*
d
(3)
d
(47)
k
k
k=c
kmc
-(11ddta22d dd
(b
d)
d ( 1)
+ 2d
dd22 dd2)
2)
(48)
c
c- c-2
d d-11 2d d 2 c' 1)
+ +(-1)a+c)
2d
(b d 5)
(49)
-(11)dto2-d
d
2)
d-2
d [-1)]
(50)
c c- 2 c-
d (--2) d (d (1-2) + +(b- - 5)
(1
d (d-1) 1
d 1)
+ (-1)
(51)
(d--
(-1)dte
(d (d+b) b) (d-2) - (d b) (d 2) (d=2)] ]
(52)
2d
c- 2
(c-1)
(11)dte'
(d- 2 2)
(d - b + 5) (d-2)
(d + b - 5)
d' }
2d
c' 1
17

---

Published as a conference paper at ICLR 2025
A.3.1 PROOF OF COROLLARY
Recall the value = [d - b)/2] from Lemma that the bias is bg 0), we have c d/2 and:
For ReLU activation, in the case of even (recall
d
d d-2
- -d112- d-2
- ))
d d-3
Ad,oRoLul = 2d
d/2 22/ 2)
= 2d d/2 1)
(53)
1
(54)
where in the last line we applied an estimate 8 3va - d/2-11
2
1
2d 8 vd"
In the case of odd d (with
bias b; = 1) it holds (d + 1)/2, and we proceed similarly
1 d -
1 Vd
A
6
(55)
2d (d 1)/2
For the CReLU activation, in the even case, c = d/2 and d' = d/2 +2 22
2
- d 2 -
d/2 (1/2+1) - (d 5) ( d d-2 2
d d-2
ALD.CRELU =
d
+ (d - 5)
2d
2
d/2 + 2
(56)
3
d d-1
+
(57)
2
d/2
1)
d d 1
d/2 +
+
(58)
The last equality holds because as grows 4-3
(d/2-1) dominates over --1 d-1 In the case d odd
we have (d+1)/2 d' (d 1)/2 2 and we proceed similarly to get
1 d-1 2 (d ((a-1)/2)
6 ( d d -
) = (22)
Ad,-1,cneLul
+ d (d-
(59)
The rest of the corollary is application of Theorem 4
A.3.2 PROOF OF COROLLARY 2
Let b E R, by straightforward calculation we have
d
(a) d,h.o = E
(-1) -)
Σ
+
1=1
d-a
= =Ezu(t11
(-1)ld-o- Df 2,)
Σ
3ij +
Σ
3j + b.)
5=1
j=d-a+1
d-a
2j b )
(-1) Σner 22)/2
Σ
T. +a 2
Σ
1=1
j=d-at1
(4)
d-a
]]
E Boo(ti)d-a
(-1)(d-a-215- 2,)12
Σ
3 + 28 +b
2a
(0)
d-a.b-at2..0
24
E=0
18

---

Published as a conference paper at ICLR 2025
Recall that ReLU. Applying Lemma
where c(d,b) =1-21 and consequently c(d
a, - a + 26) = c E, we have
(a) A
d,b,a
2a k=
Ad-o.b-a+26.r
(60)
(-1)d-ate-
20(-)(ea))) a)) ( 2
dd
(d (d+b+2(e-
(61)
2a
2d-a
c- c - 2
1=
c- L -- (
d (d-a-1 a- -2
- -dd 20)
(62)
=: dd, + C(d, bB(d,c,a).
(63)
where
a(),c,a)= = (-1)d-ato
Σ
( 10
( c- 2-)
(1- a (-- +
(c-f-1)) (c-2-1)
d (d-a- 21-a-2)
(64)
2
2d-a
The following claim shows that suitable lower bound for [Bdd, c, a.) is sufficient to obtain lower (a)
bound for A l-
Claim 2. Let us assume that b E Z. If [f(,,,, > Cd (for some C. a > 0), then either (a)
AA
d.b.o
100
C d or (a) d
100
C d-a
Proof. Let us suppose there exist C and
such that [B(d, e, Cd If A
T00
C d= then we are done with the proof. On the other hand, if if (a)
d.b. S 100
dda then we have
A (a) 1 = (dT c, + C(d, (b 0.))(dd,,, (0-1)B/dd.)
(65)
(a) d, + +,,
(66)
d. (a) 1
(67)
0.1Cd 0.
(68)
C d=
(69)
100
Equation 65 holds because for every d, c(d, b) ادي
الممطاا = c(d, b + 0.1), so the
values of T(d, c, a), C(d,c,a) and B(d, c, a) (see equation 63 are the same for and b + 0.1. G
remains to find the order of magnitude for B(d, c, a)). in order to do so, let us consider a certain recursive sequence of differences of binomial coefficients.
Let E N and let n = n(d) = [d/2]. For n - d k a let
(70)
k
Aa(d, == 1 k) A +1)
for a > 0.
(71)
The main lemma that we will need is the following combinatorial bound: Lemma 2. Let N and l E Z such that either is even l 2 0. Then,
(d, k)) θ (a 1/2 1d-1/2-1a/2)
(72)
Furthermore, for large enough d, it holds sign( (d, k)) = (-1)la/21,
We will prove the lemma only for the case of even d, as the calculations for odd analogous. To that end, first let's give another formula for A, (d, k). Let
(n k) = 1,
(73)
Pa Pa k) (n le + a) (n, k) (n Pa + 1) for 0.
(74)
19

---

Published as a conference paper at ICLR 2025
Claim 3. For every N. even d, and -n
S S
Aa(d,k)= = 2-d k
II
ka(n,
(75)
+ k +
Proof. By induction on a. The base case a 0 is clear. For a 0 we use induction and the definitions of A, and Pa: (d = A-- (d,
Aa- (d, k + 1)
(76)
a-1
= 2-
(n-1(n,k)
(77)
k
+ k +
ii=1
d
-2-6
Pa-1(n,k+l
(78)
k 1)
n k - 1+i
i==
1
2-d
k)
n ks
n2
(79)
2
A: +1 k)(
k
We will say that a degree polynomial of one variable (Ak) has positive coefficients if all its coef- ficients until degree are positive. We state without proof a self-evident claim:
Claim 4. Let Q(k) be a polynomial with positive coefficients of degree > Then, 1(k++)-Q(() is polynomial with positive coefficients of degree t-
Claim 5. Let 0. Then, there exist some polynomials (k,(k)) such that
[a/2]
(n)
Σ (-1)'Qa, -
(80)
t=
and (k) is degree 2i polynomial with positive coefficients.
Proof. We proceed by induction on a. For a 0, the statement is clear with Qo,o(k) 1. Let
>>>>> 0. By equation 74
(a k) = (n + k + 1) (n, k) - (n - P) (m, +
(81)
= (a
Pa-1(n, k: 1)) + (k: + a) Pa-1 kPa- 1)
(82)
By induction, the degree in n of Pa-1 is 1 and therefore the degree of Pa is at most i + 1.
From equation 82 and assuming for convenience Qu-1,-1(k)) Qa-1,411 (k) 0, we have for every 0 <
1:
(--))
(k) (-1)
--000-000 +1
Q-)--
(83)
+ ak)kk)a)au--1) + (-1) "11'''Quu1,,0 (k +1)
(84)
and hence
= (o--())=0o-1-11-111------
+ (k: + a) Qo- (k) + kQ.
(85)
For 0 s t. by induction it holds that (1) as) (.0 with positive coefficients of degree 2i. On the other hand ( Qu-1,i-1kk) is either zero (for
i or when Qa-1,-1 has degree 0) or, by Claim 4 polynomial with positive coefficients of
degree 2i. Either way, Qa.i (k) is polynomial with positive coefficients of degree 2i.
remains consider
Qua
- (0)--a(k=1)-----11 Qo-
(86)
If a is even, then [a/2| = - Then, Qa-1e(1 (k) is a polynomial of degree with positive
coefficients and the right-hand side of equation 86 positive constant. If is odd (hence [a/2]
t), then (k) is a constant and therefore Q (b) = 0. In either case, we get that Pa (a k)
has the decomposition according equation 80
20

---

Published as a conference paper at ICLR 2025
Proof of Lemma 2 Let d be even, N and & E Z. Recall that by Claim 3
ko(d,k)= = 2-d d
1
Pa(n, k)
(87)
n2 k.
R: +
By Claim [ the degree of in (n, k) is t :- La/2].
Furthermore, if a is even, then the coefficient of Pa at n² is equal to (-1)a/2 multiplied by pos- itive constant. If a is odd, the leading coefficient is (-1)la/2) multiplied by linear function in k easy see that for even k 2 0, the leading coefficient of Pa evaluated at & is equal to (-1)[a/2) multiplied by positive constant. From this indeed it follows sign(Aa kd) sign(Pa. Pa (n, k)) (-1) [a/2] for d large enough.
with positive coefficients.
Furthermore, using known bounds on binomial coefficients
An ( = e =0 (d-1/3-1a/8))
(88)
As mentioned, the case odd d is proved by an analogous calculation.
Expanding the recursive definition, we can also write (a k) as follows: Claim 6. Let a, N, and ls E Z.
EC-1) Aold, E=
1 c 2a
a-1)
d
Aa
(89)
11 k
Proof. The proof proceeds by induction on a.
For 0, there is nothing to prove. Let a > O.
Σ E(-1) Aold,k+ 6=
Σ a- 1) 8
Ao(d,k+0) E(-1)
(a 1)
Ao(d, k + +
e-
(90)
Σ
a (a-1) (-1)
Ao )
+ > (-1)
a (a-1)
{-1
2=
1=1
(91)
Σ (-1) a--1) 1)
Ao(d,k+1)
(92)
6
Σ (1jett 1a-1) Ao(d,k+
(93)
2=
Ap-1 (d, Aa- (d
(94)
Ao k)
(95)
Equation 91 holds by the convention (o ( 0.
(0=1)
L
Recall that equation 64 can be rewritten
Bid, c) = (-1)d-a+e
Σ
1-1)) 1)) 12 dd-a add-a-2)
c -2) + (--22)) {
-
(96)
2d
2=
Comparing this with Claim
6 we have
B(d,c, c.) (-1)d-ate
(Aa a a a- 122nncc- - + Aa - - 2,, - c 1))
(97)
2at2
where n(d a 2) 1
d-a-2 2 |
and -
21

---

Published as a conference paper at ICLR 2025
From this point we conclude the proof of Corollary 2 Recall that choose the biases b
uniformly from the set fa + 2, - 2 0.13. In particular, taking b = a + 2,
n n d 2 d 2 21 1+120.
(98)
2
Furthermore, it is easy to see that {n - c+ 1,n - c+ C {0. 1, 2). Therefore, applying Lemma 2
with k = 0, 1,2 get, for large enough d.
[Bd, c, a)l = 2a+2 (| - a a- 2 + Aa a c+ :
(99)
- ( (d
(100)
Equation 100 holds because a is a fixed natural number and from Lemma 2 for d large enough, sign(4 A, a 2, + 2)) sign(An (d a 2, c+ 1)).
From equation 100 and Claim we get that A E (
(a) Cd-11-25 for some
)²|
C> 0. The rest of the proof of Corollary follows from Theorem
A.4 ALMOST FULL PARITIES d - 1 AND d 2
Here, we provide a simpler calculation for the specific cases almost full-parities, namely k = d-1 and k k= d 2.
Corollary 5. In the cases of almost full parities = 1 and a = 2, let b = -2 if d is even and b = -1 f odd. For a ReLU holds 2 O(d-3) Accordingly, 2 (2(d) hidden neurons are sufficient for strong learning in one GD step.
Let c: c(d. =
d-h1 thus c(d- 1,d 1) = e and 1, =0= 1. Using equation 37
2
and equation 60
we have:
ReLU
(1)
2
Ad 1.6- 1...-
+
2
1
(101)
1
(
(-1)d-1te
(d+b- 2) / d (d-3) 3
(
(d b) dd 3)
c c-1 }
(102)
2
2d-1
c- c- 2/
1
(-1)d-1tc
(d (d+ b) dd (d-3) 3)
(d b 2) d 3
c- 2 )
+
(103)
2
2
c- 3/
(-1)dtc
(d-3) - 2(d - 2)
(d-3)
(d /d-3) 3)
(d - b)
+ (d +1+b) b)
(104)
2d
c-1
c- 2
c ( 3
Then for d even i.e. b = -2 and
d+2 we obtain
2
A
(1)
1
(d + 2)
3
2(d - 2)
d-3
+ (d - 2)
d-3
d, ReLu
2d
d+2 -
2
-2
d+2
2
2
-2
d+2
2
3
1
(d - !
d+2
d+2
(d+ 2)
1)(d
2d
d242
1) ((d
2
2
2
d
++
d+2
d+2
d
2(d 2)(
1)(d
+ (d 2)(
2)(
1)
2
2
1
d-1
1)
(d - 2) [d] () -(d)))ddd)))))
2)d-2)]
2d
1)(d 2)
d+2 -1
2
2
d-1 1
2d(d
- 1)
d+2
- 1 2
1
0
dvd
Similarly, for d odd i.e. b -1 and d+1, we have
22

---

Published as a conference paper at ICLR 2025
d-1
-1 = 0 1
- 2d(d - 2)
(105)
d+1
dvd
2
Let's provide a similar analysis for (2) c(d - 2, 2) = - 2, so
d.b.RoLU- We have -2, -2 2) = =c, c(c
2, = c- and
A (2)
deb, 4 2-2. +
2 Re,, + 4 A-2,0+22.eLLU
(-1)atc
d dd-1 4)
(d - b) d - 4
d dd-0 4
(d (d+ 1 - 4)
c- - 2(d bb--)
2d
c-
c-3
c c- 2 (2
d (d-1)
+ (d b) d-4)
- (d- - b 4) (dd (d-4) 4
+ 2(d - b- - 2)
(c-4)
c 3/
(-1)atc
d (d-4)
d 4)
(d b)
(-11) + (3d b 8)
2d
c-2 2)
d (d-1)
c-3 (d b) d - 4
4
(3d + b- 8)
4
Then for d even i.e. b = -2 and
-
d+2 and observing that
d-4 =
( d-4 we get
1يه
|
1
- (d + 2)
d -
(4d 8) 2)
d-4
(3d 10) (
d - 4
3)
d,
2d
d+2 - 1
d+2
d+2 - 3
2
2
2
2(d 6)
(
d-2 2
2d 3) - 2)
d+2 - 1
θ
dvd
With the same procedure we can show that for d odd i.e. b b= -1 and c
d+1
we have
2
2 d d-2 θ ( (112)
| R, =
2d(d 2)
d+1 -1
ddv)
The rest of Corollary 5 follows easily from Theorem
4
A.5 POSITIVE RESULT: SGD FOR HINGE. LOOSS
we consider the two layer architecture, this time with possibly perturbed Rademacher hidden layer initialization N(x) = Σ 2/2 ReLU((w; + gi) + b,), that is Why (12) and 9új (N(0, Other weights are initialized as before, i.e., hidden layer biases are b.- = 0 for d even and b, = - for d odd, and output layer weights are e2 = 0. As in the case of the correlation loss, the exact bias values are not crucial.
As in Section 4.1 1
The training is with hinge loss [, 5) = max(0. 35) for some B 2 0 under i.i.d. samples from any fixed probability distribution on { { /d For simplicity we consider batch size SGD, though larger batches could also be used. This time we allow a more realistic setting where both layers are trained.
Theorem 9. For the network described above, for S C/d for sufficiently small C >>> O, except with probability 3 ex over the choice of initialization the following holds:
Let D be a distribution on {11]d, e > 0 and 0 < 8 < 1/2. If 2 (((t)) and n S poly(d), then after training with batch size one SGD for some choices of T poly In and learning rate
y = 1/ poly(d), using hinge loss La for < B S OdPny), except with probability 6 over the
choice of i...d. training samples from D. it holds Pr [sign(NT(x)) # f(x)] ee.
Theorem 9 follows from the bound on the number of nonzero SGD updates:
23

---

Published as a conference paper at ICLR 2025
Theorem 10. o Cjd for sufficiently small C> 0, with probability 3 exp(-d) over the choice of initialization, the above network trained with batch size one SGD algorithm learning rate 0 < S (dd-3.) and the hinge loss for S 3 I 16d will perform at most Odd)) nonzero updates.
Q(d²)) and poly(d). then, except
the full parity function any sequence of samples from {=1} with
crucial consequence of Theorem is that the full parity is linearly separable initialization:
Lemma 3. If uf are the output weights after step of noiseless GD correlation loss algorithm, and we take V² v² v²/ll''/,. Il. then, |oo| = vn for every 1 S S n and, except with probability exp(-d), for all E {+1]d.
VTA 2
fz
+ +,))
(106)
Proof. By equation 21 except with probability exp(-d) for every {+1}d we have
7
(x) = fa(x) Σ o x +b))
2
Recall that mt = >
s-a 1= Wij and let v² w¹ /||='|| In particular, it follows |u5] = 1/vn
d.b.
for every i. We also have |o S Anvn
VTA
Sa (1)
Σ oo x x
2
2 1
A.6 PROOF OF THEOREM 9
In this proof we will apply the following result about hinge loss SGD:
Lemma 4 (Lemma 4 in Nachum & Ychudayoff (2020). Let f X + 1-1,1 be function from some finite domain X S Rdd such that ||>|| & R for every x. E X and some R 2 1. Consider a one layer ReLU neural network initialization. For x E X, let 22 R be the embedding vector žn,i = ReLU(W; I + b,) and assume that ||2,||| S for every x E X.
Furthermore, assume that there exists > and a choice of output layer weights v² F with || = such that (xx Ei= of ReeUU(w; x + b:) 2 eforr every x E X.
2 Then, using learning rate 7 500K RZz and 0 < 3 < 4R27, the butch size one SGD algorithm using hinge loss L(x, y) = max(0, B B----Naa N()yy) run on any sequence of samples from will perform most 2012 nonzero updates.
Let X = { for all E X we have |||||| = Vd. First, let us consider the case of non-perturbed Rademacher initialization.
For x E X, let 2n E _ its embedding vector i.e., An,i = (weL + b:), we have || < (d + 1) 2d. By Lemma applied for = O, (see equation 106), except with probability exp(-d) over the choice of w, there exists o* E R" with |u;1 = 1/ n such that, for all x E X we have
f(x) Σ og ReLU(w: x x b:) 2 V
(107)
18
Now consider the perturbed initialization ReLU((w; + 9:) x + b:), where g N (0,
(0. S 1) for
some C < 72- Let E be the event that there exists < i n such that ||g:|| > vd and &, that there First, let us establish that each of these events occurs with
exists x such that E/_ 19s x Z n probability most exp(-d). d).
36v/
24

---

Published as a conference paper at ICLR 2025
Let us start with & Since Bl|g:ll2
C² d' by subgaussian concentration we have
C
+ { s exp (-n( ))
/d/2
Pr |1:11 2 d
(108)
C4
Substituting = d/2, we have particular Pr[llg.11 2 d) z ( Taking union bound over poly(d), we have Pr[Zi: !|9ill 2 d) exp(-dl)
As for Eg, note that Egg x any fixed v,
/2C I 72vd' And
Therefore, again by subgaussian concentration, for
Pr
Σ 9 x
S Pr
9 x
E
g
+
exp((S((n)).
36 d
72v
(109)
which is smaller than exp( for n 2 2.dd))
If neither & Eg happens, then for every we have
f(x)
ReLU(((; + + x b,) f(x)
Σ
ReLU(W; x +x)
1
Σ
99 x
(110)
vn
1=1
-=1
vn
(111)
36vd
Furthermore, for every and it holds I(w; + 9:) bel I ([ww)ll 119:1l + < 3d and consequently || s /d
Therefore by applying Lemma with ;= Vd, R2 3d and
36 we conclude that
using learning rate 0 < 7 S 500v7 9:36-70 = 0 ( ). the SGD algorithm using the hinge loss Ly, 9) = max 3 yů). with 0 < B < n6y will perform at most (dd)) nonzero updates
after which all samples will be classified correctly.
A.7 PROOF OF THEOREM 9
First, note that we can choose values of 7 = polyyyd and 0 B S O(Pny) such that Theo- rem 10 applies. In line with Theorem TO fix an initialization such that the SGD algorithm running on i.i.d. samples from D performs at most Co = Cdd nonzero updates, where is a universal constant.
Let us run the training until there are = 1 (In 1/5 + In Co) zero updates in row. the number of nonzero updates is at most Co. the algorithm runs for at most Co(1 + K) = poly(d) In steps.
Finally, let argue that that the classification error does not exceed except with probability 8. To that end, define a "bad event" & as follows: There exists / such that:
1. A nonzero update occurs at time
2. There are K zero updates in a row immediately following t.
3. Prz- Pra-dl(sign( (N*+1 (x)) + f(x))
It should be clear that if E does not occur, then at the final time T it holds Prz-o(signt (NTiggn(T((LA (T:)) + f())] Se.
Fix some time 1 such that the first and third condition above satisfied. Clearly, if the error probability exceeds e, then so does the probability of a nonzero update. By independence (and the fact that only nonzero update can change the network). the probability that there will be K zero updates in a row at most (1 " By union bound over at most Co nonzero updates,
Pr(E] Co(1 5) 58. 8.
25

---

Published as a conference paper at ICLR 2025
B PROOFS FOR SECTION 5.1
B.1 PROOF OF THEOREM 6
For brevity, we denote the population gradient at for target function by
I (0) == E. VoL(f(())
(112)
To prove our results we couple the dynamics of the network's weights 6f with the dynamics of the 'Junk-Flow'. The junk-flow the dynamics of the parameters of network trained on random labels. For that purpose let
1 (0) = Ex (V.L(L.,.))+Vooo VoL(-1,0,2))
(113)
In other words, (0) is the expected population gradient of random classification problem where r(z) (1d(1/2) independently for every input
Definition 6 (Junk-Flow). Let us define the junk-flor as the sequence vf E RPP that satisfies the following iterations:
y0 = 80
(114)
w = (T, + +
(115)
where şt itd (O, We call y the learning rate and T the noise-level of the noisy-GD algorithm used to train the network NN(x;;)
We show that HT and ThT close in terms of the total variation distance. Let us look at the total variation distance between the law 8T and bT, which, by abuse of notation, we denote by (V"0"; ;52).
Lemma 5. Ler TV :b)) ; be the total variation distance between the law of Tr and Th Then,
TV(OT: 16
(AL))
(116)
2T
The proof Lemma can be found in Section B.2
Recalling that f R - {+1), we have
P sigu(NN(<;; 0²)) = f(x) < sign 10 =T) -0x)) + :V
(117)
1
$ +
TV ;
(118)
2
1 2
V GAL,(
(119)
2r
1=0
In equation 118 we used the fact that the initialization is symmetric around Since for the corre- lation loss (, O. the junk flow just adds independent Gaussian noise and the distribution of the output layer weights v/" also symmetric around (and independent of other weights). There- fore, the distribution of sign(NN(2; 16 (fT) is also symmetric around 0 for every fixed Finally,
tuejjunk
in equation 119 we used Lemma 5
We are now left with showing that the right-hand-side of equation 116 is small, i.e. that the junk- flow dynamics does not pick correlation with f along its trajectory. Again, for the correlation loss, T- (x())) = for I, thus for all f, t6 A Ha + Vbyr H, where H (0, Tp). Thus, the result follows by the assumption in equation 5
B.2 PROOF OF LEMMA 5
This proof follows a similar argument that is used in (Abbe & Sandon 2020): Abbe & Boix-Adsera 2022 In the following let us write = 0T-1 and 1/ -² for readability. The total variation
26

---

Published as a conference paper at ICLR 2025
distance TV(0"; x)7 can be bounded in terms of 8 and & as follows:
TV(0"; ( TV -000---((00+++===0000000000000--
(120)
TV -=) +2))
(121)
+TV -TV(v~1)) (v-11110)++2))0-11100 +
(122)
TV (0; w)
(123)
+ TV 10 (z)
(124)
5. v))
(125)
+ +Bv 2
DKL (bb - (v) 23)0 + +*) 1b)
(126)
d)
TV (0" -1 +
E ( -rr)l1))
(127)
277
1 2T
TV (0 -, + E [1 (b) - (2
(128)
where in a) we used the triangle inequality, in b) the data processing inequality (DPI) and triangle inequality again, in c) Pinsker's inequality. Finally, d) follows since, conditional
on V, both distributions in the KI. divergence are Gaussian, and due to the known formula DRL(N(H, Id), Id))
||-="11 Thus. 20a
Egg -(,))r(rr(""))) (2))2)22
(129)
2T
(a)
T-1
V /AL,
(130)
2T
where in (a) used Cauchy-Schward
B.3 PROOF OF COROLLARY 3
Let us state a claim about Gaussians with slightly different variances:
Claim 7. Let F : R.P. > be a function such that 0 S F(x) I R for all x E R.P Let f ~ N (p, D), for some μ E R2 and D a diagonal matrix with diagonal entries (of..., and let vb ~ Nu,, D') some other diagonal D' with entries ((11)² ;..., (o'p)²) such that (0.)² S a1 + 1/P) every
every SisP P.
(F) S e, for some e, then EF( < 11
Proof. Let M > 0 and define the event E as (formula (3.5) in Ledoux & Talagrand (2013).
Wi-Ki
M. By Gaussian concentration
see also MO2 (2020)):
2
M2
Pr [r 5 4exp
< 4 4exp
(131)
8E
EP
-
Pimpes 0:
16P
27

---

Published as a conference paper at ICLR 2025
At the same time, if
E Liml
(z-=mi
)
2
I M2, then the density functions Pa and Py satisfy
0,
P
(zi (21-11)) ps)
(x(x) =
/2mO
exp
2(0,))²
(132)
1=1
(xi
1s)2
(o))2 - o?
(- (- (x; pz)²
I cxp
Σ
II V2TT;
exp
(133)
20
(o/)²
20
M
I exp
(P(()).
(134)
2P
So,
J F(z)po(x) + f F(x))o(1)
EF(b)
(135)
JZEEM
IFEM
M
M2
exp
4Rexp
(136)
2P
16P
Substituting M =
IGP 9
In 1/e, we get the bound.
Let F(O)= = rr,00) Conditional on the value of A, the distribution of 0 is Gaussian
00 ~ -N(AA,'DA) where DA is diagonal with entries (DA)pp = Var Let 0 S X s 72,2T. Then, the distribution of 0 + AH for standard gaussian is 0 + AH ~ Ni(A, + XPIp). Therefore, by assumption for every p P holds
a VarAp x2 < の² VarA, + + s VarA, (1+7)
(137)
By Claim (and averaging over A), follows
GAL, + XH) = (F + AH) & (4R+ 1)EF (4R + 1) GAL,((0)1//) (138)
Equation now follows directly by applying Theorem
B.4 PROOF OF COROLLARY
4 we focus connecco networks of bounded depth. For simplicity, we consider fully connected networks with one bias vector in the first layer, but we believe that, with a more involved argument, one could extend the proof and include bias vectors all layers. In particular, we use the following notation:
For Corollary
x (0 w(0x ((1)
(139)
(0 (0())) (A) = ( (2x
1= 2.....,, L,
(140)
and denote the network function NN(x; 0) x(()( (0). We assume that the activation satisfies the H-weak homogeneity assumption of Def. 5 We assume that each parameter of the network is independently initialized as g% AOO of, where lp denotes the layer of parameter 0,-
for E [P].
Corollary 4 follows from the following Proposition.
Proposition 3. Ler NN(x;0) 0) be network that satisfies the assumptions of Corollary 4 Then, if (0%) <e,
(1
722
GAL + +*HH)
<
II 1=1
1
(141)
of
where H TT)
28

---

Published as a conference paper at ICLR 2025
B.5 PROOF OF PROPOSITION
Recall, that 0" ~ (O, V), where V is P x P diagonal matrix such that Vp = viz where Ip is the layer of parameter p. and t/ (0, U), where U is P x P diagonal matrix such that Upp of +22 Thus, U CVC where C is P x P diagonal matrix such that
Cpp
(142)
of
Definition 7 (C-Rescaling) Let NN(x;; 0) be an L-layers network, with parameters 0 RR... Let C(), ,.., C(L) be L. positive constants, and let C be where hp is the layer of parumeter 0p. We say that the vector C. is a C-rescaling of 0.
diagonal matrix such that Cpp = (14))
Definition (Weak Positive Homogeneity (SPH)). We say that an architecture is H-weakly homo- geneous (H-PPH) for all C-rescaling such that minpE]P] Cpp > 1, it holds:
L
NN(x; T.0 [I00 NNN(2;)),
(143)
a NN(:; 0.0) 0) = =Dp.H do NN(x;)),
(144)
where Dy.H is such that pp.H S Ih (CW))*
Assume that the activation is H H-weakly homogeneous (as defined in Def. 55 with H 2 1. Then, NN(x; 0)
Lemma 6. Let (N(x; 0) be a fully connected network as equation 139 139 equation 140
H-SPH.
The proof of Lemma i in Appendix B.6
If we optimize over the Correlation Loss, i.e. Loore (y, 0) == -yû, then the gradients of interest are given by:
(0) - FE (f(x) Vo NN(x; 0)]; (0) = O.
(145)
(146)
Thus,
P
Eyr (1b')((b*))
-r,
Σ
E Er Oug NN(x: f(x))
Let C be P P matrix such that Cpp
where lp is the layer of fg. One can verify that the C-rescaling of 8d has the same distribution as vt. We can thus rewrite each term in the sum above as:
2y
Exe Egg (0 NN(a; (+) s(x)) (0x))()))
Eg [0 NN(x; C f(x))
D2 H Ego By Obg NN(x; 00) f(x))
where in (a) we used Lemma Thus,
P Eg - - - = Ego Σ D2 p.
Er (0pg NN(x;6") f(x))
p=1
(0)
<
K Ego
|G (09)
where K = I1= (1+ 182,2) H 07 and where in (a) we used that Dr.ul S Cp.
29

---

Published as a conference paper at ICLR 2025
B.6 PROOF OF LEMMA 6
We proceed by induction on the network depth. As a base case, we consider a 2-layer network. Let us write explicitly the gradients of the network.
V WiS0 NN(x; 0) - 00 (1) (0)).
(147)
NN(x; 0) - w/ (x (1) (0))s)
(148)
60 NN(x;; 0) W 0' (0).
(149)
Notice that the weak homogeneity assumption on the activation a (Def. 5p. we have for /
[1,
"C (C = II (CW)) x: (0),
(150)
thus equation 143 holds. Moreover,
(w0 NN(:; C 0) = (C(1) 0
w:O: NN(x;)),
(151)
0 w NN(x; C 0) = (C(2)) a NN(x; 0),
(152)
gg NN(x; C. 0) = (C12)) ( 8,00 NN
(153)
Therefore, for any parameter ppp p [P).
0o NN C 0) = Pp, NN(x;
(154)
with < Dp.H S max (CO))) s I
For the induction step, assume that for network of depth L - 1, for all parameters 0p.
00 NN(:; ((0) Dp. 0o, NN(I;0), 0),
(155)
with 1 < Dp. S (C Let us consider neural network of depth L, and let us write the gradients,
( NN(x; 0) = ax ()))
(156)
N1-1
i w-)) NN(x;0)= Σ
1= 1,... L 1, (157)
A=1
NL-1
0001 NN(x:0)=
Σ
w o' d'( ((( 0,0 (0)
(158)
where Nr.1 denotes the width of the (L - 1)-th hidden layer. One can observe that oi (L- 1) (0)
corresponds to the output of fully connected network of depth 1, and thus we can use the induction hypothesis for bounding 0,,=* (1,11)())) for all parameters 6p in the first L 1 layers.
Thus,
2 W NN(x;((0)) (C(L-1)3 Dw!! . w NN(x;)),
(159)
N i u NN(2; ((0)) = Σ
c(D 0' (L-1) (0)) D Dwgine ,I 0 2 (1- (L-1)(0).
(160)
k=
1= b 1-1,
(161)
No Σ
c(D) (L) d d' (2( ()) DT0, n 0,00 (11)))
000 NN(x:
(162)
Thus, the result follows.
30

---

Published as a conference paper at ICLR 2025
C SMALL ALIGNMENT FOR GAUSSIAN INITIALIZATION: PROOFS OF THEOREM 7 AND PROPOSITION
In order to establish Proposition and subsequently Theorem arising from the gradient formulas.
we will need two calculations
Definition 9. Let d E N and 2 0 and B be such that + |@] S 1. We say that random variables (ki G1, G2) are (d, a, 3 -llaterrng Gaussians if:
k ~ Bin(d, 1/2).
Conditioned on k, the pair (G1, G2) are joint centered unit variance Gaussians with co- variance - 2k//d)a + B.
Lemma 7. For each ogg > there exist C", C > such that if (k, G1, are (d, a, -llatternn Gaussians for a 2 co, then
(-1)+11( 2 0) 2 00] C exp(-Cddd
(163)
Lemma 8. For each oq there exist C², C such that if (k: G1, G2) are (d, a, -lltttrnnn Gaussians for a 2 Okg, then
B
( ReLU(G, ReLU(G2)) s (C'exp(-Cd)
(164)
crucial element of both calculations is the following claim: Claim 8. Let E N. For all n < d, for any polynomial P of degree n,
d
1-))
P(k) O. 1:
(165)
K=
Proof. We prove the statement by induction on n. If = 0, then
Σ
1) 1)
k = (1 =0,
(166)
and therefore the sum equation 165 indeed vanishes for every constant polynomial. Assume that the claim holds for some O. By linearity, it is enough that we only prove
d
1)*
0.
(167)
To that end, calculate
d k. ke
Σ k=
n++
(-1) 1)
(168)
k
k=1
d 1
1)a
kt"
(169)
d-1
( (1) 0,
11)
(170)
k=
where (a) applied (9) (g)k- = (d=1))- d and (b) is a change variables and applying the induction.
C.I PROPOSITION DIMPLIES THEOREM
Let < X2 < -2,2T. In order apply Theorem 6 for A O, need to check the gradient alignment for initializations 0 + XH, where H ~ (O, Idp). More precisely, that means we have initialization with independent coordinates where
Wii N (0. + x2 b N (0, x2) vi N (0. +x²)
(171)
31

---

Published as a conference paper at ICLR 2025
Let us normalize by dividing and b by v1 + dd2 and v by v1 + nd?. That gives new initialization
0^ (ūo, bx, ö) such that
Wiy ~ -
(0. 2) Bas ~
0² o²+ +x2
U ~N ~N((1))
0,
+ dx2)
(172)
In partieular, the variance of bx, is d'ts² uniform bound
0² + I+2² 0² + +0(1). By Proposition have
1²
I+d1?
GA (0x) < 2C' nd expl
(173)
By homogenity ReLUUcc)) (eI.U(x)) ()) for c 2 0, it is easy to check that
GAL, (0 + AH) S (1 + (1 + m^ GAL (0x) S exp(-I((d))
(174)
The result now follows directly from Theorem 6
L
C.2 LEMMA AND LEMMA g IMPLY PROPOSITION
Recall that GAL Ee| V 0))² We will estimate the expectation of each squared coordinate of this vector by O(exp(-Cdd) Then, equation 9 follows by summing up. Let us first write the neural network gradients for all types of weights 0 (w, b, v):
w NN v,1(w; x + b, 2 0)2z
(175)
Vo, NN v. I (w; x + b, 2 0),
(176)
V., NN = ReLU(w; x bb).
(177)
The square of the expected gradient (x (N; 0)² can be also written as the expectation over two independent input samples x, x, In particular, in the case of miy from equation 175 we have
d-a II xen'
Eg (Ex NN)² = Eza,'
(Eo,
(178)
(Fews, by (wi . x + b, 2 0)1 - + b, 2 xyzz (179)
Consider the set S == (1....,d d (1) where A denotes the symmetric difference. Abusing notation, let write x (y, 2) and x' = 22',2") where y, v.y' containt the coordinates in S and
2, 2' the coordinates from id] S. Let & be the Hamming distance h := du (y.y v/). Note that the
distribution of k is binomial k Bin([S), 1/2). Then, continuing from equation 179
1
Eg (En wis N Ez,e' & [ [(-1)=Em, [[[ x + by 2 (w: x' + 2 0)]
(180)
Fix some values of 2, z'' and k: Let G := wi w b; and G2 == w; xx +bg Notice that, conditionally on k. 2, 2', random variables G2 and G2 are joint centered Gaussian with VarG1 = VarGa 1+o and
Cov(G1, = (d - 2k (dH + 02
(181)
Let G. == G./VI+ for i 1,2. Then, द and T2 are two joint centered unit variancce Gaussians with correlation
o²
Cov|Gr,7a)
(d 2k 2dH (2,
(182)
d(1 + 02)
1 o²
(1
2k
SS|
d d-151 2d (2, do²
(183)
[
d(1 02)
d(1 +11+0 0z²)
Therefore, conditioned on z and z/, random variables (k,, G1. G2) are (d, a, 8) altetrarn Gaussians
for [S] x]+o2] 36 0. It is also easy to check that |@| <
[S] +d-+d18
1. By
d(1+a-)
Lemma 7 for some uniform constant > 0 it holds
B,.G,.2 [(-1)<1(G, 2 (G2 2 0)] E.G., (-1)+ > 0) 2 20]
(184)
< C' exp(-CCl)
(185)
32

---

Published as a conference paper at ICLR 2025
Plugging this into equation and and equation [80
get the desired bound. The case of the hidden
layer bias by proceeds by the same argument with S == {1...., . - a}.
Finally, in case of set S == {I....,, d )} and proceed with similar calculation
Eg (E, NN)² (1 + a 2' (-1)
ReLU(GG)))
(186)
S 5 [1++ d (d) & C" " exp((CCd,
(187)
where the last line we applied Lemma
C.3 PROOF OF LEMMA 7
is well-known (see, e.g.. Chapter 11 in O Donnell (2014). that for two p-correlated unit variance
centered joint Gaussians it holds (G1 2 0)I[G22 0) f(p) where f(x) = 1 2 arccos (1)).
By definition of (k, G1, G2), conditioned on k random variables G₁ and G2 have correlation p = p(k) = (1 2k a + B.
Hence,
B(-1)* 2 ()2 0)| [Bx f(p(k))
(188)
1 [3d/4]
Σ (-1)* (1)
(1))))) f(p) (())
P(k d/21 2 d/4)
aE[-1,1]
sup
If(x))
2d
k
(189)
k= Td/4
3d/44
(0) 2dx1(-
1 2
d
+
Σ
(-1)*
f (p)
(190)
A=
[4/4]
where (a) follows by Hoeffding's ' inequality.
remains to bound the last term in equation 190
Consider the Taylor expansion of
[(x)
1
π
(2n)!
I 2x+1
(191)
2
2
2
4th (2nn))2(2n + 1)
==0
1
1
(2n)!
Σ
2n+1
(192)
4
2T
4tH
( + 1)
7=0
1
1
(2m)
2n+1
(193)
4
2T
4mn2n + 1)
4th
+
Σ
ana
2n+1
and 2n+1
(194)
4
2n+l<d
2n+12d
(3nh
where On =
For future reference let us note that 0 S On S for every n. So the
(2x
second part of the RHS of equation 190 is upper bounded by:
3d/4
Σ
1-1)*
Σ
anp 2n+1
(195)
k= 1d/1
leed
:=T;
[3d/4]
+
Σ
(-1)
Σ 2np2
(196)
2d
k/47
k=
2n+12d
:=12
We are going show that [Ti| 2 exp d/10)) and together with equation 190 imply the theorem statement.
[2al ag
2 (1 on/2)² These bounds
33

---

Published as a conference paper at ICLR 2025
Let us start with T2. In the sum in equation
196 we have d/4 < k S 3d/4, 4, and can check that
(1
2k
a0
lpl =
a
+
3
-
a
|8| S 1
(197)
d
2
2
Therefore,
[3d/4]
d
[22|
Σ
(-1)
Σ
On
2n+1
(198)
2d
k
Amm [d/4]
2n+12d
[3d/4]
1
2n+1
S 2d
1
(199)
k
2
1= [d/4]
2n 12d
Σ
00
2n+
S
2
11
000
d
(200)
2
2
2n- 12d
For Tı, we follow two steps. First,
|3d/4|
(1)
d (
T S
Σ
Σ
(-1)*
(1)
(
2n+1
(201)
k
2n+1<d
[=|44
Applying Claim 8 (for this note that is a linear function of k. and therefore p is polynomial in l of degree 2n 1):
[3d/4]
d)
Σ
(-1)
pant1
(202)
2d
k
k=
dd/4]
1)
dd)
p
2n+1
+
Σ
(-1)
(d) k
aut1
(203)
2d
k
2d
k=0
k:|R ///- 2d/1
Σ
2-a
(204)
k
d:/2///3/2//4
P(kk d/2] 2 d/4)
(205)
$ 2 cxpp(d/10))
(206)
Finally, we substitute into equation 201 and conclude [Ti] S exx (-d/10).
C.4 PROOF OF LEMMA g
In this proof we will use the probabilist's Hermite polynomials H₂ (x)x) = (-1)* d vf dz p(x). where
(x()) = v2T exp(-22/2 is the standard Gaussian density, see, e.g.. Lebedey 1972) for more
details. One property that we will need is that for two centered p-correlated unit variance joint Gaussians G1, G2 holds
EH (G)HH, = 10 {ml
mml mf n,
(207)
otherwise.
We will also make use of the ReLU Hermite expansion, see, e.g., Proposition 6 in Abbe et al. 2022c). That is, ReLU(x) /2=
+ f Em am (x) for om
(-1)"+
and
/2 12mr2mmmmm- 1)m!
consequently, applying equation 207
E BRLLUG ReLU(G))) =
+ 4 1 Σ
2 (m
(208)
2m
m=1
Furthermore, in any case we always have
1
E ReL < (ReLU
(209)
2
34

---

Published as a conference paper at ICLR 2025
As in Lemmal 7 conditioned on k. random variables G1, G2 are centered unit variance Gaussians
with correlation p = p(k) = (1 - d' a + 3. In particular, by equation 197 as long as d/4 < k Σ
2k)
2o. 3d/4, then | S 2
Now we estimate, for 2 2, applying Claim in equation 211 and again
in equation 216
[B( 1) Re) ReI.U(G2)
(210)
1 40)
= E(-1)* REL
(211)
2π
[34/4]
d
DC Σ
< <rrllk d/2) > d/4]+
Σ
(-1)²
am (2ml) pm
(212)
k [d/4]
|3d/4]
1- d
$2cxp(-d/10) + Σ am (2ml)
Σ
p2m
(213)
2mddd
A=Id/al
|3d/4]
Σ 2m2dd
2 (2m!)
Σ
(-1)*
p2m
(214)
k=/d/A
[3d/4]
< <2exp(-d/11) +
Σ
Σ
(-1)*
p2m
+ Σ
(1 Cp
2m
(215)
k
2
2macd
J==
[4/4]
2m2d
d
S ex)( +
1))
p2m
+ + - -d/21 > d/4)
(216)
2mdd
k=0
C exp(-Cd).
(217)
D SMALL ALIGNMENT FOR PERTURBED INITIALIZATION: PROOF OF THEOREM g
D.1 PROPOSITION IMPLIES THEOREM
Take do. Cnd C' from Proposition 2 Let the setting be as in Theorem initialization w Ja (r + g) where Rad(1/2), N (0, and A (0, _ Id... Let's consider any a = (d) 2 0n-
g i.e. (w, v). with i.i.d.
As before, we would like to apply Theorem 6 Let 0 S X2 < 22,2T. Let us check the gradient alignment for 0 + AH, where H ~ N ldp). So we consider the weights with independent coordinates where
Wx,i5 = 1
(ris + 9hj) + Ahij, uAs ~ (o/N(11 (0. (x))
(218)
Va
where Pig N (0, Ti ~ Rad(1/2) and hi ~ N (0, 1). Let us rewrite wx.i
1 ((ms
WA Vd
(ras + Tx.s)) with gx.i N (0, 02 +2d))
(219)
Also let's normalize by dividing ea by vI + nA=. That gives a new initialization 02 = (wx. such
that T. ~ N (0, 4) Since we have - + X'd 2 o 2 oo. then by Proposition 2
(0,) S PC exp(-Cd)
(220)
Finally, by gradient formulas and homogenity of ReLU, we have
GA + AH) < (1 + ) GAL, S exp(-S(d))
(221)
35

---

Published as a conference paper at ICLR 2025
Therefore the result follows by Theorem 6
Let and r be two iid. vectors with n coordinates such that on each coordinate 9i ~ W (0, a) and r; Ra)(1/2). Let's define two values expressing the gradient alignments for weights in the hidden and output layers, respectively. For μ 2 0 and d E N:
dd-1
x 1l (g + pr) x 2 01 o1)
GALma d) Bgrr
Ex
(222)
GALout (1s d) Bygi
Ex,
II xy ReLU((g + ur) -ur) x0)
(223)
Lemma 9. There exists some cog C > 0 and Do such that, for d 2 Do, and μ S ao
holds
v8
GALnia (p, d) S exp(-Cd).
Lemma 10. There exists some 0r0, C > and Do such that, for d 2 Do. and S Ja
it holds
GALoue (1, d) S exp(-Cdd)
D.2 LEMMA 9 AND LEMMA TO IMPLY PROPOSITION 2
Let the setting be as in Theorem i... w; = (r: (r: + gi), ~ N (0, and r; ~ Rad(1/2). The gradient formulas for full parity:
NN = 0. 1 (w; x 2 0)
(224)
NN ReLU(w; x)
(225)
As the gradient has P = nd + n coordinates, it is enough to show the C' exp(-CCd bound on every coordinate of the gradient. Let start with hidden weight coordinates. By symmetry, can suppose w.l.o.g. that j = d. The alignment of hidden layer is given by:
Eg [R ( may NN)² 2 = Eo (E., f (xr)e;
(wy 2 0) 2zz)²
(226)
[
d-1 II
(ri + 9t) 9.). x x2222 =2))
1
E., Bair
Ex
xzl
(227)
Vd
t=1
E d-1
Byiir
x1
(ri
(228)
t=1
d-1
1 (1 + + x x2 1)
-
Ex
(229)
n
t=1
where 03 ~ (0, 2). Therefore, by Lemma 9
Eg (E,f(x)V way NN)² 2 GALnid hid
1 (1aa s C''xx'(-CC
(230)
n
where the constant C' compensates for the fact that Lemma Similarly, for the alignments output layer weights:
9 holld for d large enough.
( (r: + st) .2z :m))
1
Ea Vz), NN)² = Bgg.r
E II
Te ReLU
(231)
Vd
E=1
27
1 ( + gi)) T
= od o
Ex II
xe ReLU
(232)
8-1
= o² GAToou
dd)
(233)
oodd"
36

---

Published as a conference paper at ICLR 2025
D.3 CORRELATED GAUSSIAN EXPECTATIONS
We give general formula for expectation of functions of correlated Gaussians. We will then apply this formula to the cases of step function and ReLU:
Lemma 11. Let (ck)x and (dx) ) be two sequences of power series coefficients with infinite radius of convergence. Let (xx Ei=o dxH)(x) and G(z) == 2k=0 dgt". Then, for every a, E R and p-correlated joint standard Gaussians 7, 7
=k== (x)) and F(x) Σx=o CLa* Similarly, let g(z)
F(R) (1)
Ef(a + Z)g(b + B²)
(234)
k!
k=0
where F(l) denotes the k-th derivative of F.
Proof. Applying the Hermite polynomial identity Hm + b) = ki= (f)am=*HH(b)) HH(b))
f(a Σ
(m +2)
m
a
Hn(2)
(235)
k
m m=0
m=0
k=U
80
xa
Fxb) (a)
Cm
m
am
Hg(z)
(236)
h!
Taking expectation and using EH₁ (Z) (Z')
kk=
F (()
Ef(a + () Z²)
k!
Applying Lemma I1 to the case of the step function, we get the two dimensional case of the "tetra- choric series" Harris & Soms (1980).
Claim 9. Using the notation above, F(x) = (f ()(x)) Ex + Z)].
Proof. From the convolution property (f * g)¹ = f * g and identity g(k) = (-1)%
(Hxo)) f (())H)(z))(zzdd
(f (f)))((0)) (f * (0) = (- ct = (=((
(237)
(238)
Since the power series coefficients equal for every k. the claim follows.
Corollary 6. B[1o+z201l++ 220 = (b) + ((a)(())
Ha(a) (b T4IITAAA
Proof. Using Claim for for fx) L.20. we get that
F(x) [1 z2o] = (xx)..
(239)
The result follows by applying Lemma and (b))_ ((6-1) (-1)&-1HR-10) HR
Corollary 7. Ler R(x)= (2) + 6(x). Then,
Ha( p
E ReLUU(a Z) ReLU(b++++ z -(0))())((0000)0)000000000))))))
(k (k+ 2)!
(240)
Proof: Applying Claim 9 for f = ReLU we get
F(x) E [x + 2) / (1 (1+o))ot2200(W)1 = [[(0 (x ()+
(241)
x xx + / -d()))d==xxxx)++++---
(z) + = -R())
(242)
Again the result follows by Lemma and observing that R'(x) = ((x) + x0(x) + d(xx) ((x).
37

---

Published as a conference paper at ICLR 2025
D.4 PROOF OF LEMMA
Let us write μ a/Vd, so that by assumption ag. We have,
GALbid Eyzz,',
II 1 x pr. 2.g a' pr 2
(243)
Ex Eg,,,
II maa Prig x x pr. x. x' pm. x' 2 0]
E Rx,,, F(r,
(244)
As for every ,,, 8 E {-1, 1] 13d we have F(x,z',r) F(x (,) @ denotes the Hadamard product), it follows
B B = Ez, F(r,
(245)
so we can rewrite
GALbid Exr,
Il n Prig x - x. x' + p.pa x' 2 Er,,' F(x,,', 14)
Fix x and assume w.l.o.g. that I (la-d'-11" for some S d' d. Furthermore, divide x' (y.z) such that y E f-1,11d-dd and E {-1,1}d Assume that d' 2 d/2 and fix (If d' < d/2 we exchange the roles of y and and proceed with entirely symmetric argu- ment.) Let G( y, F(x, (v, 14). We want analyze B.,G(( y, z) so that the bound on Ex,z' F(z, x², 1 G 2) will follow by averaging. Let fe x' and be the number
of 11 entries in z. Note that we have 1
Continuing:
[,,((,, (-1)d' II B. (185((11))) (-1) t. x, 2.g--. o + p. x 2 20]
(246)
E ((-1)*Ap(u(d 2dd), (1 y 2k))]
(247)
= EE [(-1)* Ap(u(d
[(-1))A,(u(( - - -uldp - 2 (.)))
(248)
where (a, b) = Pro.o [g a -b = =t a. < b), where g. g' are two standard p-
correlated joint Gaussians. Note that the distribution of k is binomial, that is Pr[k: = k*] = d' (k)) for < ks < d'.
In particular, conditioned on x, y. the expectation in equation 248 can be written |E Gzz y, 2)
(L)) for some function W that depends only on p. Since p is a linear function of k, in the Gaussian case, will now expand W as power series and apply Claim g
Let
== :== p(d= B 24 y, Y,C == -pd and w == + Cpp
(249)
Take some 3 > O, where later on we will choose to be a small enough universal constant (in fact = 0.005 will be enough). Let us define two "bad" events: E, is |p| 2 1/2 and &g is |w] 2 3yd and let J be the complement of U &2.
38

---

Published as a conference paper at ICLR 2025
First, let argue that Pr|ci U&] exp(-c8fd) for some universal > 0 and d large enough:
Pr Pr|Ei U&] < Pr [&i] Pr[E2]
(250)
Pr |ll|
2 1/2]
+ Pr
[w|
3vd
(251)
d
Vd
Vd
$ Pr
Σ 124
+P
B
Pr
Cppl
(252)
2
2
2
d-d'
d
3d
< Pr
124
2
+r
Σ y/
M B
+Pr
2
(253)
4a
2a
f2
< 2eepp
+ 2exp
+ 2exp
(254)
320 (d d')
8a.2
$ <exp(-os (-c33
(255)
where equation 254 is by Hoeffding's inequality. Using equation 248 our bound becomes
GALnid S Bn,y (-) (Bx(-1)*ApA (A w)
(256)
s Pr(f U E2] + En,y E& AA(
(257)
I exp(-c (ap(-c52d) Ex,yy E&( Ex((1)*ApAA,uu) w||
(258)
To study the expression A,(A, w), let us recall some facts about the Gaussians. We have the follow- ing expansions:
(-1)*
(=)
2k+1
(2599
2m
2*k
k=U
6(z)
24
(260)
V 2T
24
k=0
as well as the tetrachoric series for A (convergent for every a, R and |pl < 1) Harris & Soms 1980,, Vasicek (1998):
(a(ab))=((aa00) o(a)(())
Σ Ha(()
1 (I+ + 1y.
(261)
Substituting into equation 258
GALni S exp(-c3²d
(262)
Em,,y
E& 1x(-1)<1=
((A))())) Σ (w
(E+1J!
(263)
S
+ Ey,yy
Es (1(-)))
(264)
0
p²41
Σ
E Bayy
Ex (((=1)"1=(4)d)\
(265)
(E 1)!
2=
I exp(p=oe -c5 d) + Ex,y Ex 1
(266)
8
E 1) (w) rt4
Eryy
(267)
2=
where in the last line we used the estimate from Harris & Soms 1980 proof of Theorem 2),
He(A)) s 2 exp((A' A² /4///
(268)
39

---

Published as a conference paper at ICLR 2025
which implies
(A))) S Ve!.
(269)
For tighter estimates on Hermite polynomials, see also BBonan & Clark (990). It remains to show that both Ti and T2 are exponentially small.
(-1)
Let start with 71. Recall equation 259 and let ag (2 triangle inequality,
Using equation 259 and
Ti S Buyy
Bx(-
15
Σ
arweet1
+
Σ lae((VV))ar
(270)
2
tcd/10
#24/10
1
< Ex,y
Ex(-1)*
+
Σ ag
+ Br.y
(-(-1)
(a(-))Iggue,,
Σ
2
2
t<d/10
ecd/20
(271)
(e)((BV))2++ 20+1
(272)
(24/10
Pr|E UE2]
Σ (ee(3v 62d/10
(273)
E<d/10
S Sexp(-c33e
2 +
())((aV))20+))
+
Σ |ael (Bv
(274)
Ł<d/10
E2d/10
In the right term in equation 270 used that event F implies |w| S BVd. In equation 271 apply Claim 8 to the first term. This is valid since w is a linear function of k; and since + 2d/10 1 d/2 S d', which holds for d > 4. In bounding the second term in equation 271
used a uniform bound |w] |μz'| avd.
We will now argue that both terms in equation 274 are exponentially small. Let us start with the second term:
(Bva)28+1
(e)((3V))
26+11 <
Σ
SBVa Σ
exp(EIn 28 enn +
120/10
22/11
f2d/10
(275)
S 3
Σ
exp(2f f +
(276)
f2d/10
= B
Σ
(
S
3vd Σ
28V722 -2110
d/10 <
exp(-
12d/10
/2d/10
(277)
where the first inequality in equation 277 follows if satisfies 10e < 1/2.
Now let us move to the left-hand side term in equation 274 It is sufficient to prove 1/2 + Excafio (a)((4/)) < exp(c(8d/2) and this is what we are going to show. Indeed,
(avd) 26+1
(eava)2
Σ
(eel(aVa)2e11
Σ
Savd Σ
(278)
el
Le
&<d/10
E<d/10
t<d/10
Consider the function f() (eavd)22
We check that its derivative f'(() = f(6) In (lea)
In Therefore, f achieves its maximum aded and we have
(eava)2e
s(L) < S(E*) = exp(ea2d)
(279)
8
40

---

Published as a conference paper at ICLR 2025
for every E 2 0. For small enough, for example if a²e I cB²/2 /2, substitute into equa- tion 278 to get Eeed/ao (el(avd)aett I adddexpp(ea d) and consequently
1/2+ + Σ lael(aVa)*+t) S <xp(cc3
(280)
t<d/10
In summary, by combining equation 274. equation 277 and equation 280 the inequality Ti exp(- is established for large enough d.
S
We now turn to bounding T2. The idea is essentially the same with a more complicated calculation. 1-1)a
Recall equation 260 let bm. 22 m and note for later that [bml S 1/ml. We write down
T2
Ba(- 11 1
(281)
E=
He(w) pet1
Ex Ex
bm
w 2m
(282)
V8!
&cd/10
mcd/10
T:a
He(w)
Σ
Exig.
1m
2m
(283)
m!!
vC!
tcd/10m22d110
pet1
[xΦ(w) Heww)
(284)
V
/2d/10
Let us argue turns that each of T3, T4, T5 is exponentially small proceeding in the reverse order.
For Ts, use equation 269 and the fact that event F implies ppl S 1/2:
Ts S
Σ 2 -+1 2-
(285)
E24/10
For T4, invoke equation 268 and event JF implying |w| S 8Bvd:
(3
Ta S 2dexp(33d/4)
Σ
2dexp(33d/4)
Σ (10e,33)m
(286)
m!
m24/10
m24/10
33 is chosen such that (10e;39)1/10 < 1/2 and exp exp((2/4) S 1.01, then we can continue and obtain the desired bound
T4 < 2d(1.01)22 < <exp(-ed)
(287)
Finally, we turn to Tz:
He(w) p=43
Ta
Σ
Exr,y
Ex( ER(-1)
Σ
2m
(288)
Bxdd/10
mcd/10
rc+1
Σ Ex.y
En
Ba(-1)*TE,ue,
2m
Helw)
(289)
Ve!
tcd/10
mcd/10
(a"d)m
< 2d U [s]exp(a"dd/4)
(290)
m!!
mcd/110
< 28 expl -ap(-c321) exp(a d/ exp(ea exp(-cd)
(291)
41

---

Published as a conference paper at ICLR 2025
The sum in equation 288 is equal zero by Claim 8 Indeed both and p are linear functions of k so the expression inside the absolute value is polynomial of degree at most 2m + + (e + 1) <
4d/10 + 1 < d/2 < d'. To bound the sum in equation 289 we applied 1bml < 11/m!, |wo| I 30 d. equation 268 and |p) < Finally, to bound equation 290 we applied equation 255 and equation 279 and the final inequality follows if we choose small enough so that, e.g., a=/4 + ea - cB²/2 (recall that 3 is already chosen to be small enough absolute constant).
Summing up, equation 285 equation 287 and equation 291 substituted into equation 284 give
T3 exp(-I(d)). Together with T1 S exp((S2(d)), substituted into equation 267 we estab- lished GALnia (11, d) I exp(-S((d)), which is what we set out to prove.
D.5 PROOF OF LEMMA 10
This proof follows a similar process as the proof Lemma g so we will skip some details and refer to Appendix D.4 Let us write μ = dd, so that by assumption S og. We have,
d
a ReLU(g I + pr. x) ReLU(g - a' + +ur purrxa)) 2t)
GALout Eg
(292)
= Ee ir
Il A ReLUUg + ur- pr. x)) ReLU(g a' + pr 2')l
(293)
= En i F(r,2'r)).
(294)
We still have for every x, x' rr, E (-1,134, F(a,)',)) F(x 8, 08, 8), therefore
GAL = Ryg F(x, ,', 1d)
II L ReLU(g + p. ReLU(g o' + n x2)2
= En
Let's recall the notations from Appendix D.4 let's fix and assume w.l.o.g. that (1a-8" ; 11") for some 0 d' S d, x' (y. =) such that y E { {-1, and 2 1,,1, Assume that d' 2 d/2 and fix y. Let G(z, v.
(xx, (y. 2), 19). We are going to analyze E,G(x, v. so that the bound on Ey F(x, a", 19) y. G(x y/ 2) will follow by averaging. Let p _ x'
1-y+2k-d' where & be the number of -1 entries in 2. We have, d
d_d
B_G(
(-1)a"
Be (-1)"T, [Re..U(g x p ReLU(g s' + p +,,xa)]]
(295)
= BB [(-1)* Aplu(d - 2d'), -d(dp 2 .))}
(296)
where in this case A,(a, b) = gg. [Re.U[g + a) ReI.Ug' + b)), with g are two standard p- correlated joint Gaussians. Let
A: ((d 2d'), B := :1 y == -ud and = B + Cp.
(297)
Let us define two "bad" events: E, is |pl 2 1/2 and Eg is |w| 2 3vd (for some 3 that we will set later) and let F be the complement of 3₁ U U
Using the same argument as in Appendix D.4 (see Equationsseuation 250 equation 255 we can show that Pr(&, U U&) & exp(-cff4) for some universal and d large enough. Continuing.
GAT I Fry.y ( w)
(298)
S exp( + Ez, (A(
(299)
From Corollary 7
we have
(() e+2
AA w) = + ((A))()))))))
(300)
(e+2)) 2)!
42

---

Published as a conference paper at ICLR 2025
with R(x) = ==(x)) + o(x).. Substituting the above into equation 300
GALnid S exp(-c88d) + En.y 11
(301)
Hr(A)H)(w))
R(A)R(w)
1812)
(302)
(e ((+22) +2]
< exp(- (xp(-c88d) + Ez,y Ex B + Ez,y
(303)
8
p=t2
+
Bz,y
Ex
(304)
(e+ 2)!
8=0
< exp( c88 d) + Es,y R
Bx 1 + Be,y [R(A)] BA (- 1 [
1xw0(w)
1
(305)
20
p e+
Eg,y [-((1))*1 11>
Exy
Ex( 1a(-1)< He
(306)
Ve!
2=0
(l 1)a (-1) < exp(-c8²d) + ldd Ez.9 E& (-1
+nd Bz.9 Ex(-1) 11-1) (z((W)
(307)
=:n
=f12
00
p²-2
Eg.g E&
+
Ensy Ex(- Ex(-I)"Zz((u)llll
(308)
V
=272
The bound in equation 307 and equation 308 follow because of equation 269 and the fact that [R(AA] & A| = 2 d') S μd.. remains to show that T11. Ti2 ,Tis and T22 are exponentially small. The term T22 differs from T2 in equation 267 the exponent of + 2 in instead of + 1. Thus for large enough, a similar proof as for Tn will show that T22 is exponentially small. The process to handle T11. Ti2 and Tis is the same in Ti. Indeed, for example:
Tú Exr,y
Ex(-1)*11
2 w
Σ
2422
+
Σ
(ve((3V7) 2642
(309)
tcd/10
#24/10
S exp((-c8'd)
havd+
Σ
(ae(
Σ
lar (3V()22)22
(310)
ted/10
#24/10
Both of the above terms can be handled similarly as in Appendix D.4
E EXPERIMENT DETAILS AND ADDITIONAL EXPERIMENTS
E. EXPERIMENT DETAILS
All experiments were performed using the PyTorch framework (Paszke et al. (2019) and they were executed on NVIDIA Volta V100 GPUs.
Architectures. For the results presented in the main, we used mainly a 4-layer MLP architecture trained by SGD with the hinge loss. In this Section, also present some experiments obtained with a 2-layer MLP trained by SGD with the squared loss.
4-layer MLP. This is fully-connected architecture of 3 hidden layers of neurons of size 512, 512, 64, and ReLU activation.
2-layer MLP. This is again a fully-connected architecture, with hidden layer of 512 neurons, and ReLU activation,
43

---

Published as a conference paper at ICLR 2025
Initializations. We compare few initialization schemes. In the following, dim denotes the input dimension of the layer of the corresponding parameter. All layers weights and biases are indepen- dently initialized according to:
o-perturbed Rademacher:
+ (Rad(1/2)+NN(0o33))
dim-(1++o2)
Gaussian: (0, dim
s-sparsified Rademacher: Ber(1 s) RRa(112)- (dim-(1-s)
Uniform o-perturbed Rademacher: (Rad(1/2) + Unifl-v3on v3ol)
(dim-1++o2)
Discrete perturbed Rademacher:
5-dim
Training procedure. We consider mainly the hinge loss: Lhinge (g. v) max(0, (y)- In
(9.
some experiments we consider the Eg loss: Lez (ú, () == (ú - y)² We train the architectures using SGD with batch size 64. In the online setting, we sample fresh batches of samples at each iterations. In the offline setting, sample batches from fixed dataset and stop training when the training loss is less than 0.01.
Hyperparameter tuning. The primary goal of experiments of different initialization methods. Thus, we did not engage in extensive hyperparameter tuning. We tried different batch sizes and learning rates, and we did not observe significant qualitative difference. We chose to report the experiments obtained for a standard batch size of 64 and learning rate of 0.01.
conduct fair comparison
Additional details for Figure 2 In the left plot of Figure 2 we are computing the quan- aL(w.a.r) dhra
where w N/O, 2 Ida) for one case and w Rad (1 1/2) for the other case, f is the full parity,
tity Ew Eg (L(ww,..f(w)) Bhra
Rad(1/2) and L(w, x. max (0, 1 (e..U(...)) is the hinge loss. For the approximated part we update the weights according rh0+1 wht - (v)))) with wh NNO0, 2 Ida) and y and we calculate
Egi
Ex,r
ToL(v' (xx) Ov
BL( 2.0) 0
E.2 ADDITIONAL EXPERIMENTS
12
0= 0.0
0.9
Test Accuracy
1.0
1.0
gauss.
0.8
0.7
0.0
Test
0
0.1
0.6
0.5
5000
10000
40000
70000
100000
10000
40000
70000
100000
Train Size
Train Size
Figure 4: Learning 3-parity (left) and 5-parity (right) with Rademacher, o-perturbed and Gaussian initializations, with SGD with the hinge loss on 4-layer MLP, with 50. We plot the test accuracy, for several training set sizes.
Sparse Parities. In Figure we train a 4-layer MLP with Rademacher initialization and perturbation (o E 0.1, 1) on two sparse parities: degree (left) and degree 5 (right), We observe no significant difference between these initializations, unlike the full parity case. This is because, for sparse parities, the learning bottleneck lies in recovering the support, which takes ((()) time for
44

---

Published as a conference paper at ICLR 2025
0.0
0.70
0.70
Test Accuracy
Test Accuracy
0.2
0.65
0.65
0.0.0
0.60
0.2
0.60
0.3
0.55
0.55
0.50
200000
400000
600000
800000
200000
400000
600000
800000
Epochs
Epochs
0.75
0.0
0.70
0r
Test Accuracy
0.65
0r 0.3
200000
600000
800000
Epochs
Figure 5: Learning the full parity with a-perturbed initialization by SGD with the hinge loss 4-layer MLP, with input dimension d 100 (top-left), d 150 (top-right) and d 200 (bottom), with online fresh samples.
any i..d. initialization. Hence, the initial embedding does not play the same role in the full parity scenario.
Larger input dimension. In Figure plot the test accuracy achieved by 4-yer MLP trained with the hinge loss on the full parity task, with different o-perturbed initializations. We report only the curves for small a. We observe that for fixed o,, learning becomes hard increases.
10-2
10
10
GAL
10-8
o=0(Rad.)
0=0.1
0=0.15
10
0=0.2
0=0.25
10 12
0=0.3
d=0.35
10a
102
input dim.
Figure 6: Computing numerically GAL, for correlation loss for one-neuron with threshold activa- tion. We report the estimated GAT, for different values of the input dimension, in a log-log plot.
Alignment for correlation loss. Figure 6 completes Figure 2 (right) in the main. Here we plot the numerically computed GAL, for larger values of a. We observe that the GAT, becomes
45

---

Published as a conference paper at ICLR 2025
sistently smaller increases. Moreover, from the plot the decay seems super super-poly soper-polynomially small for all 0 >
Two-layer MLP and squared loss. In Figure we train a 2-layer MLP with the squared loss and online fresh samples. In the left plot, we initialize the weights according to a o-perturbed Rademacher, for different values of a. the right plot, we initialize with other perturbations of the Rademacher initialization, namely mixture of (continuous) uniform distributions of mean +1 and -1 and stan- dard deviation a and s-sparsified Rademacher with = 1/3. We observe both plots a similar behavior for the 4-layer MLP with the hinge loss.
0.9
0.9
Test Accuracy
Test Accuracy
0.8
0.1
0.8
0.2
0.7
0.7
Rad +Unif, o:0.1
Rad.+Unif. 0:1.0
0.6
0.5
sparse Rad., #1/
20000
40000
80000
20000
a0000
60000
80000
100000
Iterations
Epochs
Figure 7: Learning the full parity with a-perturbed Rademacher (left) and uniform and sparse per- turbed Rademacher (right) with 2-layer MLP, with input dimension d = 50, trained with the squared loss, with online fresh samples.
Effect of the Loss. We consider the following Boolean function:
f(x) Ti 22 212234 2iaaya + T233344
(311)
In (Joshi al. (2024)) ) the authors show that this function is learned more efficiently by SGD with L1-loss than with L2-loss (see Section 7.1 therein). In Figure g we observe that such difference is captured by our loss- dess-dependent notion of Initial Gradient Alignment (GAL). This motivates future
work in comparing our GAL with previously defined measures (e.g. LGA (Mok et al. (2022) )) in broader setting.
Loss: squared
Loss: 11
Test Loss
GAL
0.3
Loss: squared
5000 10000 15000 20000 25000 30000 35000 40000
Iterations
Dimension
Figure 8: (left) Learning f (Eq. equation 3 311 with SGD with the LI and L2 (squared) loss on 4-layer MLP, with input dimension 50. (right) Initial GAL for f on the same architecture, with the two losses.
Output Layer Training with Correlation Loss. The purpose of Figure is to empirically verify our positive theoretical result from Theorem 5 To that purpose, we train a two-layer fully connected network with Rademacher initialization with ReLU and clipped-ReLL activation (ωx) = min(1 (1, max(0, x)) on the full parity task. We train only the output layer, consistently with positive result, with SGD with large batch size (1024) with the correlation loss and online fresh
46

---

Published as a conference paper at ICLR 2025
samples, until convergence of the test accuracy. We show the test accuracy achieved for different input dimensions (d) and different widths the hidden layer (w). Consistently with our theory, with clipped-ReLU, df hidden neurons sufficient to achieve accuracy 1 (left). For ReLU, observe that w = O(d2) is not enough to achieve perfect accuracy and we believe that our theoretical bound (i.e )) for learning with accuracy 1 may not be tight and that d or d3.5 may be sufficient (right).
1.00
1.0
Test Accuracy
0.95
Test Accuracy
0.9
W vd
0.85
0.7
g15
of
10
W-
80
120
140
160
180
30
4.0 45
50
55
60
Input Dimension
Input Dimension
Figure 9: Learning the full parity with a 2-layer network, where only the output layer is trained by SGD with the correlation loss. We the test accuracy achieved after training, for clipped- ReLL activation (left) and ReLU (right), for different input dimensions (d) and hidden layer width (w).
47


Reviews:
[{"review_id": "bSh0b03614", "reviewer": "Reviewer_hKEm", "summary": "This paper considers the learning of full parity and nearly full parity when the input is sampled from the $d$-dimensional hypercube. It shows that when a two-layer ReLU network is initialized with the first layer weights following the Rademacher initialization (uniformly distributed $\\pm 1$ values), and the noise level $\\sigma$ is sufficiently small, the network can learn the full parity problem with polynomial sample complexity when trained with GD/SGD of the second layer of the network. On the other hand, if the distribution of the weights at initialization deviates significantly from the uniform distribution on the hypercube (e.g., using a Gaussian distribution), the network is unable to learn the full or nearly full parity.", "questions": "**Extension to $(d-k)$-parity**\nIn the lower bound, we are able to handle the $(d-k)$-parity. On the other hand, the upper bound is stated only for full parity. Given the complexity theory and feature learning literature, I would like to see the corresponding between $k$-parity and $(d-k)$-parity. Can you derive something like $d^{\\Theta(k)}$ complexity? Or $k$-parity and $(d-k)$-parity are essentially different for $k\\geq 0$?\n\n**Connection to real-world problems**\nI would like to know if there are any real-world domains where learning high-degree or full parities is relevant,", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Novelty** : \nWhile sparse parity problems ($k=O_d(1)$) are well studied in the context of representation learning with two-layer neural networks, I did not know that full parity can be learned with polynomial complexity. Thinking analogously to the sparse parity problems, we would need to train the first layer matrix but the gradient would vanish as the order of the parity gets larger. However, for the full parity, if the Rademacher initialization used, the gradient of the second layer is exactly computed and does not vanish, and furthermore, changing the weight of the second layer suffices to solve the problem. The proof largely depends on the Rademacher initialization, but even so, the analysis seems novel and interesting. \n\n**Interesting phase transition**: \nThis paper shows that by adding small noise to the initialization then learning full and nearly full parities becomes significantly difficult. In addition to the Gaussian initialization, this paper extend this negative result to the midpoint between the Rademacher initialization and Gaussian initialization by introducing the quantity that characterizes the initial alignment of the gradient.", "weaknesses": "**Motivation**:\nAlthough this paper trains the two-layer neural networks, the mechanism of learning is significantly different from sparse parity.\nIn the sparse parity problems, people mainly discusses how the first layer weights align with the meaningful subspace. \nOn the other hand, every direction is equivalent in this full parity setting, thus I am not sure whether this paper is motivated as a feature learning paper. \nThus the paper should explain why solving full parity how neural network is motivated, especially connections to real-world phenomena.\n\n**Generality of the result**: \nAs the lower bound suggests, this result is specific to the Rademacher initialization. \nThe fact that the gradient does not vanish and such a transformation of equations is possible is quite interesting. However, if the results no longer hold after adding a small perturbation to the initial weights, then I wonder if those results lose their general significance.\nAs an analysis this is quite interesting, though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "yqU0K1FXxV", "reviewer": "Reviewer_3tT8", "summary": "The paper provides a theoretical analysis of learning full parities (all bits parities) $k=d$ with SGD from (small perturbed) Rademacher initialization. To my knowledge, there was no analysis known. The case where it was observed that SGD succeeds with this initialization.\nThe authors further make some important observations on the role of initialization as to when we succeed in doing so, and it turns out that the initialization is curicial. To complement, the authors provide also hardness results for learning *almost full parities* with correlation loss and the initialization that has poor initial alignment, proposed by some metric that they define. For example, as a corollary, they can show that Gaussian initialization is poor. \n\n1. **positive**: For the perturbed Radamacher initialization with noise level $\\sigma=O(d^{-1})$, a 2-layer ReLU trained with SGD (Definition 3) with either correlation or hinge loss, succeeds in strongly learning the **full (all bits) parity** function within poly(d) samples/iterations. \n2. **negative**: A general result that applies to a broader class of functions (including **almost full parities**) in terms of initial gradient alignment (GAL0 \"signal at initialization\"), where they show noisy SGD (Definition 3) has an edge over $1/2$ (null error) that is bounded by some function of poly(GAL0) and some other relevant hyperparameters, so if this GAL0 is exponentially decaying, we fail to weakly learn even with this initialization in poly$(d)$ samples. One example is Gaussian initialization.", "questions": "1. How big is this poly($d$) for positive results for sample complexity? This is my other minor quibble. The phenomenon was already known that it is possible to learn, so the value in positive results is in doing a careful analysis. Or at least empirically observe and report what is the complexity of learning full parity.\n2. What are the main techniques used in upper bounding the success probability in terms of initial gradient alignment? Also, an intuitive way of thinking why initial alignment is poor for Gaussian initialization but good for Rademacher or its \"mildly\" perturbed variant? To me, this is the main interesting contribution, but I did not find a clear description of the key ideas in the main text.\n\n**Suggestion / Typos**\n1. Perhaps it is worth expanding on the technique you used as I suggested above. And also for future work on deeper networks and other losses, there could be a much closer discussion on what are the difficulties. \n2. In Line 237, the full parity function has missing $x_i$ in the product. Also, for positive result, it would be much more helpful to just explicitly define $f$ (full parity) in the Theorem statements only. Or at least clearly refer to it in an equation as the result only applies to just that function.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "See summary. The paper has a nice negative result for correlation loss SGD trained network with poor alignment initialization.", "weaknesses": "My main criticism of this paper is two-fold.\n1. The paper, throughout the beginning (including the abstract), gives the impression that they show the success of SGD for even almost full parity $k=d-O(1)$, but the positive result is only shown for the full parity case $k=d$. For example, the abstract lines (14-17). Later also in Lines (65-77). I found this very confusing when I got to the main formal results. (See also my Question 1)\n2.  To me the real contribution is the negative result. Particularly, showing that with Gaussian initialization, we fail with SGD on correlation loss. As far as I knew, this was open (see [Abbe & Boix-Adsera] discussion). However, the fact that this only holds for correlation loss works against its generality. Also, the presentation of the paper should be in a way that it highlights this as a primary contribution in a clear way. \n\nOverall, both in terms of contributions and presentation, this paper requires more for me to recommend acceptance. Therefore, I am leaning toward a weak rejection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "8BXZAy223p", "reviewer": "Reviewer_oGKm", "summary": "This paper considers learning full parity functions over hypercube with neural networks. Their main results are twofold: : 1) Neural networks initialized near the Rademacher distribution can successfully learn full parity functions. 2) Conversely, neural networks with low gradient alignment at initialization, when trained using noisy gradient descent (GD) or stochastic gradient descent (SGD), fail to learn the task. Notably, Gaussian initialization results in poor gradient alignment, which significantly hinders network performance in this context.", "questions": "See the Weaknesses part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The manuscript is reasonably well-written. The primary contribution—demonstrating the gap between Rademacher and Gaussian initialization—is an interesting result, particularly in the context of how initialization impacts neural network learning.", "weaknesses": "* I would be careful when claiming negative results as they depend on additional noise injected to SGD, i.e., Z^t terms in Eq (3), which seems unnatural compared to other theoretical results related to ReLU networks. Is there a hope to extend to the negative results to SGD without additional noise injection?\n\n*  The positive result in the paper notably involves training only the output layer, meaning there is no feature learning. However, it is unclear whether the authors consider training input layer weights for their negative results, which introduces ambiguity in the interpretation of these results. Could the authors clarify this aspect in the rebuttal?\n\n* Since the positive results only require training the output layer weights, it is uncertain if the sample complexity of their SGD is tight. Could the authors discuss whether their sample complexity is indeed tight, and/or whether it might improve if the initial layer were trained as well? Additionally, what aspects of their analysis limit extending training to the input layer?\n\n* The authors introduce a new measure, termed \"initial gradient alignment,\" for analyzing their negative results. However, in the paragraph following Definition 2, they note that this measure aligns with the previously studied \"Label-Gradient Alignment.\" Could the authors elaborate on how their analysis diverges from or builds upon these earlier works?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "MeKXtz1vkA", "reviewer": "Reviewer_SB62", "summary": "This paper studies the role of initialization for learning dense parities with neural networks.\nIt is shown that the learnability by gradient descent heavily depends on the initialization through a notion of gradient alignment: if the initial gradient alignment is small, then it is hard for noisy gradient descent to learn the target.\nIn particular, for dense parities, initialization with Gaussian perturbations has small gradient alignment and thus prevents learning, while random Rademacher initialization is a special case that allows learning.\nThe results are supported by theoretical analysis and numerical experiments.", "questions": "1. Intuitively speaking, what is the role of the gradient alignment at initialization? How does it affect the learning process?\n2. In other common settings, such as regression with single- or multi-index models, what is the typical value of the gradient alignment at initialization?\n3. In the sparse parity case, what's the role of gradient alignment at initialization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and easy to follow. The organization is very clear.\n2. The paper provides an interesting perspective on the role of initialization for learning dense parities, and the observed phenomenon seems very different from the that in the case of sparse parities.\n3. The negative result holds beyond the case of dense parities, and potentially leads to a better understanding of the role of initialization for broader settings.", "weaknesses": "1. The negative result seems to hold only for noisy (stochastic) gradient descent. How about deterministic gradient descent? There is a gap regarding this, and it would be helpful if the authors could discuss this.\n2. It seems that the poly(d) width is crucial. It is mentioned in Section 4 that this ensures the linear separability of the full parity function. It would be helpful if the authors could discuss more about this design choice, and also what happens for narrower networks.\n3. It is unclear how the choice of the loss function affects the results. It would be helpful if the authors could discuss this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "S5TZF0KlAV", "reviewer": "Reviewer_YKeF", "summary": "This paper studies the problem of learning Boolean parities using gradient descent. This is a problem which in recent years has come to serve as a useful way of understanding the effectiveness and dynamics of training neural networks using gradient descent when the labels arise from a concrete, classical functional class. The set of all parities (or indeed any superpolynomial-size subset) is well-known to be SQ-hard to learn efficiently. This paper instead focuses on the the singleton function class consisting of the full parity, or the polynomial-size function class consisting of \"almost-full\" parities (of size $d - O(1)$). The main question tackled is the following: what is the effect of the precise neural network initialization on whether GD succeeds at learning such parities?\n\nThe main results are as follows:\n- In general, for any fixed target function, whether or not GD/SGD with a particular initialization scheme succeeds is largely determined by a quantity dubbed the \"gradient alignment\" at initialization. Importantly, the gradient alignment is both target-specific and input distribution-specific. (Caveats: this characterization holds assuming certain types of Gaussian-smoothed, symmetric initialization schemes, neural networks with linear outer layers, and certain natural losses.)\n- As an instantiation of this result, it turns out that Gaussian initializations as well as Gaussian-perturbed Rademacher initializations (with a sufficiently large perturbation) do _not_ have high gradient alignment and do not succeed at learning dense parities. (Subject to the same caveats above.)\n  - In particular, this holds for poly-sized two-layer ReLU networks with pure Gaussian initializations.\n- By contrast, the pure Rademacher initialization (or Gaussian-perturbed Rademacher with sufficiently small perturbation) is unusual and does succeed at efficiently learning dense parities.", "questions": "1. Repeating from above: it would be nice to get the authors' thoughts on the emerging picture around parities and complex function learning, and what the broader takeaways are.\n2. Similarly regarding differences in proof techniques from prior works, esp Abbe and Boix-Adsera 2022 and Abbe et al 2022 (the INAL paper).\n3. I am curious how Theorem 7 might be used in practice. It seems that the gradient alignment at initialization is something we can estimate purely using some labeled examples, without knowing the target. Does this mean that the following is a practical procedure when fitting any neural network by GD: first measure the GAL at initialization using some labeled examples, if it is small essentially abandon hope (for most reasonable architectures and initializations), otherwise proceed? Basically what power do we gain from the fact that we can estimate the GAL? Considering this is a target-specific, distribution-specific measure, this would be the dream result (namely a target-specific characterization of \"practical\" learnability) and seems like a very powerful operational interpretation --- if valid.\nI wonder if there is an important distinction between the GAL being merely polynomially small and superpolynomially small. If it is only polynomially small, it might still be learnable in polynomial time. And to check if it is truly superpolynomially small, we would need superpolynomial sample complexity. So perhaps it is infeasible to measure it accurately enough for it to be useful?\n4. Separately, a more minor technical point: it seems unfortunate that the main negative result (Thm 7) involves an additional Gaussian smoothing on top of an already smoothed initialization. I realize Corollary 1 tries to fix this but in any case it seems like an odd technical artifact. I am curious if things would be simplified if the initial Gaussian perturbation was itself defined as purely additive (i.e. $A + H_\\sigma$ instead of $A + \\\\sqrt{Var(A)} H_\\sigma$).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper makes a useful contribution to our understanding of what neural networks can learn using gradient descent. In particular, the role of the initialization is clearly important in practice, and this paper considers a natural toy theoretical setting in which to study it formally.  The main results (both positive and negative) and proof techniques are interesting, and the separation between Gaussian and Rademacher is arguably a little surprising a priori. The most general negative result for arbitrary target functions (Theorem 7) seems particularly interesting and potentially useful even in practice. The technical contribution here in general is solid, although it very much builds on a large body of prior work with similar techniques. The paper is clearly written.", "weaknesses": "I am a little unsure about the novelty and significance of the paper. The problem of learning parities started as a natural toy theoretical setting for understanding what neural networks can learn, and there have recently been several papers that have studied this problem in increasing detail. The picture that is emerging for parities looks roughly as follows:\n- In general they are trivially PAC-learnable by Gaussian elimination\n- But they are SQ-hard (and also GD-hard) unless our prior information restricts the target to a small subset\n- For parities of size $k$, GD and SGD on natural architectures do succeed in time $n^k$ (Barak et al 2023; Abbe et al 2023)\n- For a single fixed parity, it is learnable by GD under certain initialization schemes (inner weights all 1, as in Nachum and Yehudayoff 2019, or Rademacher, as in Abbe and Boix-Adsera 2022)\n- Again for a single fixed parity, it is not learnable by GD under other initialization schemes (such as the Gaussian, by the results of this paper, eg Theorem 3 --- under certain assumptions)\n\nIt would be nice if the authors could clarify how we should view this picture as a whole, especially keeping in mind the original motivation where the parities were just examples of complex functions. In general for learning a potentially complex function using deep learning, is there concrete guidance on what architectures, initializations etc do and do not work? For example, should we prefer Rademacher over Gaussian initializations in general? Should we always try to estimate the GAL before actually training? Does the GAL view subsume all prior results? My concern is that the parities are a very special case that allow various arguably superficial algebraic manipulations, and so lessons here may not be widely applicable.\n\nThe general negative result for general target functions is more interesting. I would view this as the main technical result of the paper. The techniques here borrow from prior work (esp Abbe and Boix-Adsera 2022, Abbe et al 2022), and the GAL quantity and the arguments here also seems related to quantities like the \"variance\" considered in Shalev-Shwartz et al 2017 and follow-up works. It seems that the main difference is that these prior works did not focus on the role of the initialization per se. Can the authors comment in more detail on the differences in proof techniques?\n\nit would be nice to have the authors clarify their case for novelty and significance in light of these remarks and questions. On balance I am leaning positively but would like to hear their case first and hence am rating this a 6 for now.\n\n\n#### References\n\nBoaz Barak, Benjamin L. Edelman, Surbhi Goel, Sham Kakade, Eran Malach, Cyril Zhang. \"Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limits.\" 2022.\n\nIdo Nachum, Amir Yehudayoff. \"On Symmetry and Initialization for Neural Networks.\" 2019.\n\nEmmanuel Abbe, Enric Boix-Adsera. \"On the non-universality of deep learning: quantifying the cost of symmetry.\" 2022.\n\nEmmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, Christopher Marquis. \"An initial alignment between neural network and target is needed for gradient descent to learn.\" 2022.\n\nEmmanuel Abbe, Enric Boix-Adsera, Theodor Misiakiewicz. \"SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics.\" 2023.\n\nShai Shalev-Shwartz, Ohad Shamir, Shaked Shammah. \"Failures of Gradient-Based Deep Learning\". 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "ER0XH9qkwv", "reviewer": "Reviewer_mApU", "summary": "The paper proves that the full parity is learnable with SGD on 2-layer rademacher-initialized neural networks, with the hinge and correlation loss. The paper presents a notion of gradient alignment, which measures the distance between the gradients on the true distribution and those of a randomly-labeled distribution. The authors then use this measure to upper bound the accuracy any NN with a linear output layer can achieve with noisy GD and the correlation loss, providing a general negative result for learning. They follow up with application of that result to show that almost-full parities are not learnable when initialized differently enough from the rademacher init., all in all providing a separation result for learning full parities, depending on the initialization.", "questions": "What is the obstacle in applying the technique of the positive results to almost-full parities?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors advance an active and open area of research, providing answers on the learnability of full parities and almost-full parities.\nThe authors introduce a new measure that might be used to derive negative learning results in future research.", "weaknesses": "The phrasing in the abstract and introduction can be a bit misleading, in a way that suggests that your positive results include almost-full parities.\n\nWhile the term \"full parity\" is mentioned in the abstract, no place indicates that the positive results refer to that case, and not the more general one of almost full parities. This omission is then continued in the introduction (lines 59-78), where you mention Abbe & Boix-Adsera who considered learning almost-full parities, then stating \"First, we show that SGD on a two-layer fully connected\nReLU network with Rademacher initialization can achieve perfect accuracy, thus going beyond weak learning\". Which could imply again that you have showed learnability of almost-full parities, as the last case you referred to is that of almost-full parities.\n\nPersonally I was confused, and have searched around the paper for the more general case for a while. (the only place where the result is carefully stated is the conclusion). I suggest changing the phrasing to avoid this confusion. It could be as simple as changing the above sentence to \"...can achieve perfect accuracy on full parities, thus going beyond weak learning\". Similarly, changing the abstract to \"enables efficient learning of full parities\".\n\nTheorem 4 is long. I suggest breaking it down claims / corollaries / etc, according to the items in the theorem.\n\nI suggest using a consistent format throughout all related theorems, containing all relevant information. e.g. for the positive results the reader is referred to the text to find the definition of the target function (full parity), while the target function for the negative results is stated in the theorem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)