Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs
Authors: Emmanuel Abbe
Elisabetta Cornacchia
Aryo Lotfi
Venue: NeurIPS 2023 poster (2023)
Keywords: curriculum learning
parities
time complexity
sample complexity
neural networks
SGD

Abstract: Experimental results have shown that curriculum learning, i.e., presenting simpler examples before more complex ones, can improve the efficiency of learning. Some recent theoretical results also showed that changing the sampling distribution can help neural networks learn parities, with formal results only for large learning rates and one-step arguments. Here we show a separation result in the number of training steps with standard (bounded) learning rates on a common sample distribution: if the data distribution is a mixture of sparse and dense inputs, there exists a regime in which a 2-layer ReLU neural network trained by a  curriculum noisy-GD (or SGD) algorithm that uses sparse examples first, can learn parities of sufficiently large degree, while any fully connected neural network of possibly larger width or depth trained by noisy-GD on the unordered samples cannot learn without additional steps. We also provide experimental results supporting the qualitative separation beyond the specific regime of the theoretical results.

Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs
Emmanuel Abbe EPFL
Elisabetta Cornacchia
Aryo Lotfi EPFL aryo. aryo.lotfi@epfl.co
EPFL, MIT
emmanuel. wwt.uuelelabe@epl....o.
ecornaccomit.edu
Abstract
Experimental results have shown that curriculum learning, i.e., presenting simpler examples before more complex ones, can improve the efficiency of learning. Some recent theoretical results also showed that changing the sampling distribution help neural networks learn parities, with formal results only for large learning rates and one-step arguments. Here show separation result in the number of training steps with standard (bounded) learning rates on common sample distribution: if the data distribution is mixture of sparse and dense inputs, there exists regime which a 2-layer ReLU neural network trained by curriculum noisy-GD (or SGD) algorithm that uses sparse examples first, can learn parities sufficiently large degree, while any fully connected neural network of possibly larger width or depth trained by noisy-GD on the unordered samples cannot learn without additional steps. We also provide experimental results supporting the qualitative separation beyond the specific regime of the theoretical results.
Introduction
Starting with easy concepts with simpler ideas or tasks, individuals can develop a foundation of knowledge and skills upon which more complex concepts can be built. This approach allows learners to gradually gain competence and accelerate learning [EA84] RK90 AKB 97, SGGI4].
effective way facilitate learning for humans. When presented
For machine learning algorithms, this is typically referred to Curriculum Learning (CL) BLCW09). Several empirical studies have shown that presenting samples in a meaningful order can improve both the speed of training and the performance achieved at convergence, compared the standard approach of presenting samples in random order [WCZ21] SIRS22 GBM 17 HW19 PSLI5].
The theoretical study of CL. is mostly in its infancy. While some works have analytically shown benefits of CL for certain targets [SMS22 WCA18 MKAS2I CM23 (see Section [.T for dis- cussion on these), it remained open provide a separation result between curriculum training and standard training on a common sampling distribution. Specifically, one seeks to demonstrate how a standard neural network, trained using gradient descent algorithm on given dataset and horizon, can successfully learn the target when certain samples are presented first during training, whereas learning does not occur if samples presented in random order.
This paper provides such an instance. We focus on the case of parities, as classical case of challenging target for differentiable learning. In the experimental part of the paper, we report results suggesting that a similar picture can hold for other large leap functions as defined in [ABAM23), although more investigations are required to understand when and how curriculum learning should be developed for more general functions.
We assume that the network is presented with samples (æ, Xs())), with x E {+1]d and (s(x)= = Ikks Js, for some set S (1....,d) of fixed size. We consider datasets where small fraction p of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the inputs are sparse, meaning they have, on average, few negative coordinates and mostly positive coordinates, and the remaining inputs are dense, with an average of half negative and half positive coordinates. We refer to Section 2 for the definition of the input distribution. Parities seem to be promising candidates for theoretical investigations into CI., as they are hard to learn the statistical query learning model [Kea98], or on dense data by any neural network trained with gradient- based methods having limited gradient precision [AS20]. but they are efficiently learnable on sparse data by regular architectures [MKA21] (see Section 1.1 for further discussion).
We say that a neural network is trained with curriculum if it goes through an initial phase where is exposed to batches consisting only of sparse samples (see discussion below on the interpretation of these as 'simpler' examples). Following this phase, the network is trained using batches sampled from the entire dataset. We compare this curriculum training approach with standard training. where the network receives batches of samples selected randomly from the entire dataset at each step. Our intuition is as follows. If the fraction of sparse samples is small, without curriculum, the network is exposed to batches of mostly uniform inputs, and the contribution of sparse inputs in estimating the gradients will be limited. As result, learning parities on the mixed distribution without curriculum is roughly as hard as learning parities on dense inputs (Theorem 2). On the contrary, if the network is initially exposed to batches consisting of sparse inputs, it can efficiently identify the support of the parity, and subsequent fitting using batches sampled from the entire dataset enables learning the target with fewer training steps compared to standard training (Theorem I].
In particular, we show that if the fraction of sparse samples p is small enough, (e.g.. P < d 4.5 where d is the input dimension), a 2-layer fully connected network of size 0(d) trained by layerwise SGD (or noisy-SGD, see Def. [ with curriculum can learn any target k-parity, with k: bounded, in T = ((d) steps, while the same network (or any network of similar size) trained by poDs without curriculum cannot learn the target in less than (df)) steps. We refer to Section 2 for a more detailed explanation of our results. While our theoretical results use simplifying assumptions (e.g.. layerwise training), our experiments show separations between curriculum and standard training in a broader range of settings.
1.1 Related Literature
Curriculum Learning (CL) was first introduced in the machine learning context by the seminal work of (BLCW09. This paper along with many other subsequent works presented empirical evidence that training neural networks with a curriculum can be beneficial both the training speed and the performance achieved at convergence in certain instances in different domains such as
computer vision [JMH144] HAMMH14/GHH**T |HZZ+ 18 CG15 STD19), natural language processing (NLP) [KB17 18 PSN+ 19), and reinforcement learning [FHW+17 NPL +0] . We refer to relevant surveys [WC21], SIRS22) for a more comprehensive list of applications of CL in different domains. In general. defining a complexity measure on samples and consequently an ordering of training inputs is not trivial. Some works determine the casiness of samples based on predefined rules (c.g., shape as used in [BLCW09] the samples dynamically as in self-paced learning (SPL) [KPKI0]. In this work, we follow the former group as we define the hardness of samples based on the number of -1 bits, i.e., the Hamming weight. Note that in parity targets. +1 is the identity element. Thus, one can view the number of -1 bits as the length of the sample. In this sense, our work resembles [SAJIO ZS14 KB17 PSN+ + 19 which use the length of the text inputs as part of their curriculum.
GBM 17
while others also use the model's state and performance to evaluate
Despite the considerable empirical work CL., there appears be a scarcity of theoretical analysis. Few theoretical works focused on parity targets, as in this paper. While parities are efficiently learnable by specialized algorithms that have access to at least d samples (c.g. Gaussian elimination over the field of two elements), they are hard to learn under the uniform distribution (i.e. on dense data) by any neural network trained with gradient-based methods with limited gradient precision AS20)] AKM*21] Parities on sparse data can be learned more efficiently on an active query model, which can be emulated by neural network (AS However, such emulation networks are far from the practical and homogeneous networks, and distribution class-dependent. A natural question that has been considered is whether more standard architectures can also benefit from a simpler data distribution. In [MKAS2]] the authors make first step by showing that parities on sparse inputs are efficiently learnable on a 1-layer network with parity module appended to it, with a one-step argument. In (DM20), it is shown that for two-layer fully connected network, sparse inputs help but
2

---

with variant of the distribution that allows for leaky labels. [ABLR23] obtains experimental results for a curriculum algorithm presenting sparse samples first with heuristics for regular networks and hyperparameters, but without proofs. In [CM23], the authors prove that a two-layer fully connected net can benefit from sparse inputs, with a one-step gradient argument requiring a large learning rate. This paper improves on [CM23] not only in terms of having more natural training settings and hyperparameters (i.e., we use SGD with bounded batch size and bounded learning rate), it is also establishing a separation between learning with and without curriculum on common sampling distribution, while [CM23] does not (in fact in their work curriculum involves both sparse and dense imputs while standard training involves dense imputs only). To the best of our knowledge, our paper is the first work that establishes a rigorous separation between training on adequately ordered samples and randomly ordered samples drawn from the same distribution, and our theorem gives condition on the mixture under which this separation holds (interestingly the separation does not take place for all mixtures parameters). Beyond parities, [SMS22] studies teacher-student model, where the target depends on sparse set of features and where the variance on the irrelevant features. Furthermore, [WCA18] [W200] show that some convex models, CL provides improvement in the speed of convergence of SGD. In contrast, our work covers an intrinsically non-convex problem.
2 Setting and Informal Contributions
We consider the problem of learning a target function f: {=132 + { that belongs to the class of k-parities on d bits, i.e.,
f (xs(x)=
II mÿ S [d. |S| k}, jES
(I)
where we denoted by [d] == (l....,d} d}. We assume that the network has access to a dataset (X, (X,Y)= (()(m) where the inputs xf are sampled i.i.d. from mixed distribution defined as follows:
D Dmnx DD, (1 p))
where D,, = Rad( ( 8 for some μ E [-1, Da = Unif and p E [0, is some fixed parameter, and y² J )) We will assume / E (0, In other words, we assume that the dataset contains approximately pm samples with in average 1_" dl negative bits (sparse samples), and (1 - p)m samples with in average half negative bits (dense samples). We consider training the neural network with stochastic gradient descent, with without gradient noise (SGD noisy-SGD, see Def.
2
Informal Description of the Curriculum and Standard Training Algorithms. We compare two training strategies: standard training and curriculum training. In the standard training, at each step, mini-batche are drawn from the whole dataset. For curriculum training,
first need to isolate the
set of sparse inputs in our dataset. Let us denote this set by X1 = fa² E X H(x)) < ( f)d}, 1) denotes the Hamming weight of xr, which is the count of
where H (xx)
Ejeta I (xx negative bits in x, and by Yi = (y" EY: E {1} the corresponding set of labels. Our curriculum strategy consists of training
only sparse samples for the first Ti steps, where Ti < T is some well-chosen time horizon and T is the total number of training steps. After this initial phase, the network is trained on samples belonging to the whole dataset. To sum up, we compare the following two training strategies:
(standard training): At all E (T), mini-batches are sampled from (X,Y);
(curriculum training): At < Ti, mini-batches are sampled from (X1, Yi) and Ti <1S T mini-batches are sampled from (X,Y)
Informal Description of the Positive and Negative Results. In this paper, we prove that if the fraction of sparse samples is small enough, there is a separation in the number of training steps needed learn the target parity up a given accuracy. We say that an algorithm on a neural network
1 Radd denotes the Rademacher distribution, i.e. we say that æ Rad(p), for p E (0. 1], P(( 1)
1 P(r = -1) = pp.
2 Unif denotes the uniform distribution. In particular, D. Do.
3

---

learns target function f: {=1}" + {+1} up to accuracy - for c 2 0, in T steps, if it outputs network N2 ) such that:
DanDDii (sg 0²)) f())) 21-c,
where sgn(.) denotes the sign function. In our main positive result, we consider training with the covariance loss (Def. 2 and we refer to Remark 2 for considerations on other losses. Let us state our main positive result informally.
Theorem (Theorem 3 Informal). Consider the imput distribution Dmix with mixture parameters p p= =Od = μ p= Let > O. Then, a 2-layer ReLU neural network of size O(d) initialized with an isotropic distribution, trained with the covariance loss, standard (i.e., non-diverging) learning rate schedule and either (i) a layer-wise curriculum-noiee soaauum--niiy--GDD algorithm with gradient range A = Ö( (d), noise-level r Ō(d") and sparse samples first, or (ûi a layer-wise curriculun-SGD algorithm with sparse samples first, can learn any k-parities, k 0(1), up accuracy at least in T ((d)/ /²2 steps.
We further show an additional positive result valid for a layer-wise curriculum SGD with the hinge loss, which holds for large batch size and diverging learning rate (Theorem 4). On the flip side, we have the following.
Theorem (Theorem 5 Informal). Consider the input distribution Dmix with mixture parameters = Ó(d-355-)), > O, and = 0(1). Then, any neural network of size Ö(d) (any depth), with any initialization and activation, trained by noisy-SGD algorithm (layer-wise joint) with gradient range A = O(Vd), noise-level T $2(d=1), batch size B = ((p=2), any almost surely differentiable loss function and any learning rate schedule, will need at least T ((ed"-6) steps to achieve accuracy + e for any k- k-paritiis (k 2 6).
Conclusion of Results. When using noisy-SGD, the curriculum learning algorithm that takes sparse samples first, for the first layer training, and then full samples, can Iearn in a regime of hyperparameters and training steps (Theorem I that is contained in the hyperparameter regime of the negative result (Theorem 2. for which is shown that the absence of curriculum cannot learn without additional training steps. Further, it is shown in part (ii) of the first theorem, that using SGD rather than noisy-SGD still allows to learn with the curriculum training; this result does however not come with counter- part for the lower- lower-bound, i.e., cannot show that SGD without curriculum could not learn such parities, as there is currently no proof technique to obtain rigorous lower- bounds for SGD algorithms (as for the case of noiseless honest-SQ algorithms); see for instance discussions about this in [AKM 21 ABA22), However, it is not expected that SGD can do hetter than noisy-SGD on 'regular' neural networks ABA22 ABAM22 ABAM23)
3 Positive Results for Curriculum Training
The Algorithm. Let us define the noisy-SGD algorithm, that is used in both our positive and negative results.
Definition 1 (Noisy-SGD). Consider neural network NN(:; 0), with initialization of the weights 0 and a dataset (X, Y) = {(x", .y" ,"" (ssm) Given an almost surely differentiable loss function L, the updates of the noisy-SGD algorithm with learning rate "t and gradient range A are defined by
B L(NN
0++1 = 0'
Σ
) 2n1))] }}
(4)
B
where for all 1 E (0....,T T 1}, Z: are i.i.d. Unif[-T, for some noise level and they are independent from other variables, B is the batch size, and [2]A = argmin Sv ly 2/, i.e., whenever the gradient exceeds A (resp. -A) it is rounded to (resp. A).
For brevity, we will write L(0", y.x) = L(NN(x;; 0*), x). We assume that for all E [B]. (attt, y**)) are chosen from (X,, Y)), where (X,, Y2) can be either the whole dataset (X,Y), or subset of it. We include the noise Zt and the gradient range A to cover the noisy-SGD algorithms,
20(d") = Old polylooo))) for any I.

---

MKAS2I ABA22 ABA22 ACHM22]. Note that if we set r = 0 and A large enough, we recover the standard SGD algorithm without noise.
used in SQ lower bounds e.g. in [A220 AKM 21
We assume that our dataset is drawn from the mixed distribution defined in (2, with parameters p. For the purposes of this section, we assume p = D(d-1/2) and jr E (0, 1). As a preliminary step, we isolate the sparse inputs from our dataset, by mean of Hamming weight. In particular, we define XI = fx² E X H (x²) < ( []d), where H (3r) = Le [ = -1) denotes the Hamming weight of z, and Y1 Ly" E Y x² X1). Note that, due to the concentration of Hamming weight, for d large enough, there will be approximately mp samples in X1 (see Lemma []. We assume that the training set is large enough, such that each sample is observed at most once during training.
In this section, we consider 2-layer neural network NN(2; 0). with 0 (a, w. b), defined by: NN 0) == Ei= (w,(w
(w,z + b,), where (xx) = ReLU(x)= == max (2,00, 0}. We assume that the
number of hidden units is N 2 k + 1, where le is the degree of the target parity. We initialize wi = 0, af = K and i = Ad + 1, for some K, A > O, for all i.j. We refer to x and A as the second layer initialization scale and the bias initialization scale, respectively. We adopt layer-wise curriculum training approach. During the initial phase of training, we exclusively train the first layer of the network using samples taken from (X1, Yi). Furthermore, we project the weights of the first layer, to guarantee that they stay bounded. In the second phase, we train only the second layer using the entire merged dataset. We refer Algorithm [ Appendix for the pseudo-code of the algorithm used in our proof. In the context of standard learning without curriculum, similar layer-wise training strategies are considered in e.g., [MSS20 BEG 22 ABAM23].
CM233 uses
a layer-wise curriculum training, but with one-step argument that requires diverging learning rate. In our analysis, we keep the bias weights fixed specific values during the whole training. We
believe that one could extend the result to include scenarios with more general initializations and where the bias weights are trained, but this would require further technical work.
The Covariance Loss. We train NN(x; () using noisy-SGID with specific loss function, namely the covariance loss, that we define here. The covariance loss appears in [CM33 with a slightly different definition: in particular, the following definition does not depend on the average estimator output, as opposed to their definition.
Definition 2 (Covariance Loss). Let (X, ((xx"("))))))) [eemm be a dataset, where for all s, x" X and y E {11,, and let ÿ J. EmE(m) V. Assume |ū| < 1. Let f: X + {+ be an estimator: We define the covariance loss as
Leor (f == (1- -1- f(x)) - -1))
(5)
where (a)+ = max(a,
The covariance loss can be applied to classification datasets with non non-negligible fractions of +1 and -1 labels. In Proposition [] we show that a small covariance loss implies small classification error.
Proposition 1. Let (X,Y) = {<x" : "y"))==mm) be a dataset, where for all 8, x² E X and y² E {+1).
Let ū Nh2 Eve(in) v² and assume [ø] < 1 - 8. for some ō > 0. Let f = x + {+1} be an estimator. "," If 1/ em((m] Lewo(f. (f," v²) < c, then J.2 [m)) (ssgn(f(**) + y²) < 5.
The proof of Proposition T can be found in Appendix D
Remark 1. We remark that for balanced datasets (j 0), the covariance loss coincides with the hinge loss. On the other hand, note that the right hand side of 5 can be rewritten as
(11 D¹ (1 y1--f((x))
Thus, in some sense, the samples in the under-represennted class (where ÿOu S 0) are assigned higher loss compared to those in the over-represented class (where y" 2 0).
Main Theorem. We are now ready to state our main theorem.
Theorem 3 (Main Positive Result). Let NN(x; 0) be 2-layer ReLU neural network with N 2 l hidden units, 2nd layer init. scale k > and bias init. scale A >> O. Let D mix be a mixed distribution,
son(dd)
as defined in ②). with parameters 0 < p <
and μ E (0, 1). Assume we have access to Vd.
5

---

a dataset (X, {2², 3 y' Iselm; where x² itd Puiss y² xs(x*)) with S k. Assume NN is trained according to the layer-wise curriculum-SGii algorithm (Algorithm loss, batch size B, noise level 7 and gradient range A.
with the covariance
For all < > O, there exist C,C,, C 0 such that if f S 1/A + 2), S R. A (((v)) m 2 4C" log(3d)dp B, and if
T = 2C'22 log(d))
L
2 T2 256(C1 + 24A + N
71 CAkd log(d)?
(6)
<log(d) (c)
2 log(d)
72 8(C) + 2 + d)
(7)
where Ty p k+1,, then, with probability least network such that m Exe(m] I (fT.+Ta, xx, y²) S.
6Nd- .the algorithm outputs
The following corollary is direct consequence of Theorem B and Proposition !
Let the assumptions of Theorem 3 be satisfied and assume that T = (K) and A, k constants. There exists 2-layer ReLU network of size at most (d + () + 1) and initialization invariant to permutations of the input neurons, such that for all e > 0 the layer-wise curriculum noisy-SGD algorithm with gradient range A = Ö(vd), d), after at most T = ((d) steps of training with bounded learning rates, outputs a network such that IP P (Ngn(NNNN:)) 0 with high probability.
Corollary 1.
f(x)) 2 1 e,
Remark 2.
The choice of the covariance loss is motivated by a simplification of the proof of Theorem 3 Indeed, with this loss, coordinates move non-negligibly, while the other weights stay close to zero (see proof outline). If we used another loss, say the hinge loss, all weights would move non-negligibly. However, we believe that one could still adapt the argument to cover the hinge loss case, by adding another projection to the iterates. In the following, technique, that holds for large batch size and large learning rate (Theorem 4
show that in the first part of training the weights incident to the relevant
also give positive result for the hinge loss, with a different proof
Remark 3. While we show that with appropriate hyperparameters, the layer-wise curriculum
can learn k-parities in (d) steps, we need to notice that to implement the curriculum, one has to first retrieve (X1, Yi). This involves computing the Hamming weight of d/p samples, which adds computational cost if the curriculum learning includes this part. Nevertheless, in the experiments that we performed, the recovery of (X1, Y1) was consistently efficient, with an average of less than 1 second running time for dataset of 10 million samples of dimension 100, On the other hand, the reduction of training steps due the curriculum yields significant time savings.
Remark 4. Theorem provides an upper bound on the sample complexity required to learn using a curriculum, of (dB p)) for SGD with batch size B. Consequently, while the number of iterations needed for learning remains unaffected by p. the sample complexity increases as decreases. Additionally, we do not eurrently have a lower bound on the sample complexity for learning parities with standard training with offline SGD. However, our experiments in Section 5 demonstrate noticeable difference in the sample complexity required for learning with and without curriculum. These findings may encourage future work in establishing a theoretical advantage in the number of samples needed to learn with curriculum.
Remark 5. We further remark that the proof method of Theorem 3 yields a tighter upper bound on curriculum learning's 's sample complexity than the 1-step argument used in [ 4). Specifically, using the technique of [CM23][Thm 4], we achieve upper bound of Ó hp). as opposed to the ((d/p) given by Theorem 3 ffor SGD with bounded batch size.
Remark 6. Tj depends on the degree of the parity i through the parameter Lyp We believe that such dependence cannot be removed, however, we remark that choosing sufficiently close to 1 (e.g. μ = })) allows bounding L,, independently from k. Indeed, our experiments (Figure 4) show mild dependence on the parity degree for curriculum learning with large μ.
Proof Outline. The proof of Theorem 3 follows& a similar strategy as in [GI2I ABAM23 TV19). We decompose the dynamics into a drift and martingale contribution, and we show that the drift allows us to recover the support of the parity in Ó(d) steps, while in the same time horizon, the martingale contribution remains small, namely of order O(1/ / (d)). In particular, we show that

---

after the first phase of training, with high probability, all weights corresponding to coordinates in the parity's support are close Á and the others are close zero. The fit of the second layer on the whole dataset corresponds to the analysis of a linear model and follows from standard results on the convergence of SGD on convex losses (e.g., [SSBD14). ) The formal proof can be found in Appendix A
Hinge Loss. While the use of the covariance loss simplifies considerably the proof of Theorem 3 we believe that the advantages of curriculum extend beyond this specific loss. Here, we present positive result that applies to a more commonly used loss function, namely the hinge loss.
Theorem 4 (Hinge Loss). Let (2 0) Eiz a.o 1oppx+1u b,) be a 2-1ayer fully connected network with activation (y) = Ramp(y) and N = (dd log(1/8))- Assume we have access to a dataset (X = ((x', ,"""""")) (y") with x did Dmix with parameters p > 0, p. E (0, 1), and y² = Xs(x), forr some target parity Xss with |S| = Then, there exists an initialization and a learning rate schedule, such that for any larget parity Xs and for any > O, the layer-wise curriculum SGD on the hinge loss with batch size B = (d' /22 2 log(1/6)), noise level T = 0( " log 1/6 ). Tj = and T2 = /2²)
do
with probability - 35, outputs a network such that PI-Duus (sgn (NN 0T)) f(x)) 1-6
As opposed to Theorem 3 Theorem only holds for SGD with large batch size and unbounded learning rate schedules. The proof of Theorem follows a 1-step argument, similarly to [CM23] and it is deferred to Appendix B
4 Negative Result for Standard Training
In this section, we present lower bound for learning k-parities the mixed distribution of eq. (2) without curriculum.
Theorem 5 (Main Negative Result). Assume we have access to a dataset (X,Y) {(x,, yy" se))
with x² did Dinxx with parameters p = (1).), μ E (0,1), and Y = Xs(x), with [S] k. Let NN(x; 0) be a fully-cnnnectdd neural network of size P, with initialization that is invariant to permutations of the input neurons. Then, the niisy-GGD algorithm with noise level T, gradient range A, butch size B, any learning rate schedule, and any loss function, after T steps of training without curriculum, outputs a network such that
(10)"+ C&P2 1
1/2
TPA
1
P Par-Daii mix (sgn(NN 8T)) = f(x)) S
(8)
7
B
where the probability is over x D Dmix and any randomness in the algorithm, and where C2 is constant that depends on k.
Remark For the purposes of Theorem 5 the network can have any fully connected architecture and any activation such that the gradients are well-defined almost everywhere. Furthermore, the loss can be any function that is differentiable almost everywhere.
Theorem follows from an SQ-like lower bound argument and builds previous results in AS20 Theorem 3]. We defer the formal proof to Appendix C Theorem SecorremSimpllee immples the following corollary.
Corollary 2. Under the assumptions of Theorem 5 if p Ö(d-3.5-6) and k 2 6, any fully connected network of size most ((d) with any permutation-tnvaariee trained by the noisy-SGD algorithm with batch size B 22pp=3 2), noise-level gradient range Ö(vd). after T Ô(d) steps of training, will output a network such that Par-Dma (Sgn(NN(z22)) 0)) (x))
initialization and activation,
Ö(1/d) and
Cd- log(d)) , for some c,C 0.
In particular, in Corollary 2 the network can have any width and depth (even beyond 2 layers). as long as the total number of parameters in the network scales as Ó(d) in the input dimension. Combining Corollary and Corollary 2 we get that if Ô ((566..-6), for some > O, and k 2 and for 1/10, say, a 2-layer fully connected network can learn any à parities up to accuracy - T = (d) steps with curriculum, while the same network the same number of steps without curriculum, achieve accuracy most 1 - 2e, for d large enough.
7

---

p=0.0001
p=0.001
p=0.01
Gen accuracy
1.0
Std.
1.0
Gen accuracy
1.0
0.8
0.8
Curr.
0.8
Std.
0.6
0.6
0.6
10
10a
10a
10
10a
10a
10a
10a
10
Number samples
samples
Number of samples
p=0.1
p=
10"
Gen. accurey
1.0
accuracy
1.0
No. samples
Std.
0.8
Curr.
0.9
Curr.
10a
0.6
0.8
10
102
10
10"
10?
10
10.
10-1
10"
10
Number of samples
samples
Figure 1: Comparison of the performance of the curriculum strategy and standard training for different training set sizes and values of p. In the bottom-left plot, we report the number of samples needed to achieve accuracy close to 1 for different values of p based on the other plots.
Remark 8. While our results show first separation in the number of training steps between curriculum and standard training, we do not claim that the given range of p is maximal, For instance, one could get a tighter negative bound by considering Gaussian, instead of uniform. noise in the noisy-SGD iterates. However, getting positive result with the curriculum for Gaussian noise would require more involved argument. Our experiments show separation the number of training steps and the sample complexity for different values of
Experiments
In this section, we present empirical results demonstrating the benefits of the proposed curriculum method[" We use a multi-layer perceptron (MLP) with hidden layers of sizes 512, 1024, 512, and 64 as our model. We optimize the model under the & loss using mini-batch SGD) with batch size 64. We also train all layers jointly. Each of our experiments repeated with 10 different random seeds, and the results are reported with 95% confidence intervals. Note that generalization error always computed based on Dmix- Here, we mostly focus on the common settings not covered by our theoretical results. We present additional results on other architectures, namely, two-layer mean-field networks [MMN88 and Transformers [VSP+ 17 and covariance and hinge loss functions in Appendix 1.2
Number of Samples. First, we focus on the difference in sample complexity, between curriculum and standard training. We consider learning f Z = 21 2243344415 with inputs sampled from mixed distribution with μ 0.98 and different values of p 10 10 10 2, 0.111, 0.5. For each p. we train the network on training sets of different sizes (between 10 and 10%) with and without curriculum. When using the curriculum, we first select the sparse samples as those with Hamming weight smaller than ( - )d, and we train on those until convergence (specifically, training loss smaller than 10 10-2). We then train the model on the entire training set until convergence. Similarly, when the curriculum is not used, the model is trained using all the available samples until convergence.
Figure shows the validation accuracy achieved for different values of p. m. can be seen that for some values of p, there is a reduction in the number of samples needed to achieve validation accuracy close to 1 when the currieulum is used. For the purpose of visualization, in Figure T (bottom-right), we sketch the number of samples needed to achieve accuracy close to 1 for different values of based on the previous plots. We notice that the sample complexity decreases as p is increased, for both curriculum and standard training. Among the p values that we tried, the gap between the two training strategies is maximal for = 0.01, and decreases as p gets larger or smaller. Also, note
'Code:

---

Standard Curriculum
Stops to learn
Steps to learm
10
10F
Std.
10
10
10
10
10
P
1.0
1.0
0.9
0.9
Gen- accuracy
Gen. accurecy
0.8
7
0.8
0.7
Std.
Curr.
Curr
0.6
0.5
10
10a
10
10*
10a
10c
Number of training samples
Number training samples
Figure 2: (Top-left) Number of training steps needed for learning 5-parity for different values of The gap between curriculum and standard training decreases as p increases. (Top-right) The number of training steps for different values of fu based on p. (Bottom-right) Performance for different values of f and different sample sizes. Curriculum boosts the learning for large values μ.. (Bottom-left) Performance for different parity functions. (The curves of standard training for k = 7 and & = 10 overlap.) The benefit curriculum potentially increases with the degree of the parity.
that for small values of the sample complexity for standard training is constant and equals 10 We note that with 10 samples, can learn (x) even with uniform inputs (p 0).
Number of Training Steps. Now we focus on the number of iterations needed for learning the same f as above. In order to study the number of iterations independently of the number of samples, we draw fresh mini-batches at each step. When using the curriculum, we sample from D, in the initial phase and from Diix in the second phase, while when using standard training we sample from the mixed distribution at each step. iterations needed for learning f for different values of is depicted in Figure (toplee((t It can be seen that the number of training steps needed for learning with the curriculum is constant w.r.t. p. In contrast, for standard training, the number of iterations increases with the decrease of Both these observations are consistent with our theoretical results. particular, for small values of p, the curriculum significantly reduces the number of training steps, while for large it provides little or benefit, and for = 0.5, is harmful.
cases, we train until convergence. The number of
Dependency on la and k. Next, we investigate the dependency of our results on and on the degree of parity k. For evaluating dependency μr, consider the function f as above and different values of First, we consider the number of training steps needed for learning f based on p. The results are shown in Figure (top-right). It can be seen that while the curriculum not beneficial for μ 0.02 (where D,, is close to D,, and all samples are dense), it can significantly reduce the number of training steps for moderate and large values of p. Further, the performance of the curriculum and standard training for different training set sizes. The results are demonstrated in ( (bottom-right) It is shown that for large values of μ such as 0.98 and 0.90, there is gap in the number of samples needed for achieving generalization accuracy close to 1 between curriculum and standard training. On the other hand, for smaller values of μu, this gain is diminished. Nonetheless, note that the relationship between the performance of the curriculum method and z not monotonous (e.g., g., see the number of steps plot), and this indeed reflected in analysis. More precisely, in Thcorem Ti scales with L/L where L, x b+1
fix & 0.01 and compare

---

0.4
Gen. loss
Gen loss
Std.
1.5
Std.
-+
Curr.
Curr.
0.2
Standard
Curriculum
0.5
0.0
10
10a
10
10
10a
10*
10a
10
Number training samples
Number training samples
Number training samples
Steps to weakdy leam
Stops to leam
10
Standardd Curriculum
10
Std.
Steps to leam
Std.
Curr.
Curr.
6 10
101
4 10'
10a
x 100
3 x000
10-1
10
10
10-1
10-2
10"
10-3
10
10
Figure 3: Considering gains in sample complexity (top row) and number of steps (bottom row) beyond parity targets. Plots in the left (corresponding fiett (z) 2122232243 + 22
middle z 112233443 + 5 x11). and right (frihht (x) = و + _ ... xg) columns present cases in which curriculum is beneficial, is only beneficial for weak learning, and is not beneficial, respectively.
(x) =
To analyze the effect of the degree of parity, k we fix Jr = 0.98, p 0.01 and the input dimension d = 100, and we compare the performance of the model trained with different amounts of training (bottom-left). One can see that, while without curriculum data. The results are portrayed Figure 2 the parity problem becomes harder to learn as k increases, the complexity with curriculum has mild dependence on k and it allows one to learn all the parities considered with 10 samples. The plot exhibiting the dependence of the number of optimization steps on &: is reported in Appendix E.2
Beyond Parities. Finally, we study target functions composed of multiple monomials. We consider three examples in 100-dimensional space: (i) fiett
I 222334444 + 1 (ii) (m) 31 2112233222 + 1 F 211. and (iii) fright (z)
(œ1ω² 21....20 26). We also fix μ = 0.98. In Figure we investigate the gain of curriculum method in sample complexity for p = 0.01 (top row) and the number of training steps (bottom row) needed to learn. The plots in the bottom row are obtained by training the network with fresh batches. The left, middle, and right column correspond to fiett fmiddle. and fright: respectively. Note that curriculum is beneficial for fieft, while it hardly helps with fright- Interestingly, for fuiddle. curriculum is advantageous for weak learning of the function. More specifically, it helps learning I1 21 monomial of fmiddle- Consequently, for the corresponding iterations plot (Figure 3 boddom--idddle) we plot the number of iterations needed for getting a loss below 0.26. This suggests that the curriculum method put forward in this paper mostly helps with learning of the monomial with the lowest degree. We leave improvements of our curriculum method to future work.
6 Conclusion
In this paper, we introduced curriculum strategy for learning parities on mixed distributions. Our approach involves training on sparse samples during the initial phase, which leads to a reduction in the number of required training steps and sample complexity compared standard training. In the experiments section, we presented some results for certain functions with multiple monomials. Although complete picture requires further investigation, these results suggest that starting from sparse samples provides advantages in the early stages of training. It would be interesting to investigate what variation of our curriculum strategy fits best the case of multiple monomials, beyond the initial phase. For example, one could explore multiple curriculum phases where training progresses from samples with increasing Hamming weight, or employ a self-paced curriculum that dynamically selects samples during training. Such analyses could offer valuable insights into the broader applicability of our approach. Here we focused mainly on establishing a formal separation in the number of training steps for the canonical case of parities.
10

---

References
[ABA22] Emmanuel Abbe and Enrie Boix-Adsera. On the non-universality of deep learning: quantifying the cost of symmetry. arXiv preprint 1rXiv:2208.03113,, 2022.
[ABAM22] Emmanuel Abbe, Enric Boix-Adsera and Theodor Misiakiewicz. The merged-staircass property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. In Conference on Learning Theory, pages 4782-4887. PMLR, 2022.
[ABAM23] Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. Sgd learning on neural networks: laap complexity and saddle-to-saddle dynamics. arXiv preprint urXiv:2302. 1005, 2023.
[ABLR23] Emmanuel Abbe, Samy Bengio, Aryo Lotfi, and Kevin Rizk. Generalization on the unseen, logic reasoning and degree curriculum, arXiv preprint arXiv:2301131105, 2023.
[ACHM22] Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, and Christopher Marquis. An initial alignment between neural network and target needed for gradient descent to learn, In International Conference on Machine Learning, pages 33-52, PMLR, 2022.
[AGJ21] Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. Online stochastic gradient descent on non-convex losses from digeeninnniinall inference. The Journal of Machine Learning Research, 22(1):4788-4836 2021.
[AKB+97] Judith Avrahami, Yaakov Kareev, Yonatan Bogot, Ruth Caspi, Salomka Dunaevsky, and Sharon Lerner. Teaching by examples: Implications for the process of category acquisition. The Quarterly Journal of Experimental Psychology Section A, 50(3):586 606, 1997.
[AKM*21] Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. On the power of differentiable learning versus PAC and SQ learning. In Advances in Neural Information Processing Systems, volume 34, 2021.
[AS20] Emmanuel Abbe and Colin Sandon. On the universality of deep learning. In Advances in Neural Information Processing Systems, volume 33, pages 20061-20072, 2020.
[AS23] Emmanuel Abbe and Colin Sandon. Poly-time universality and limitations of deep learning. to appear in CPAM, 2023.
[BEG 22] Boaz Barak, Benjamin L Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress in deep learning: Sgd learns parities near the computational limit, arXiv preprint 2rXiv:2207.08799 2022.
[BLCW09] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. Proceedings of the 26th annual international conference on machine learning, pages 41 48, 2009.
[CG15] Xinlei Chen and Abhinav Gupta. Webly supervised learning of convolutional networks. In Proceedings of the IEEE international conference on computer vision, pages 1431- 1439, 2015.
[CM23] Elisabetta Comacchia and Elchanan Mossel. A mathematical model for curriculum learning. arXiv preprint arXiv:2301. 2023.
[DBK 20] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
[DM20] Amit Daniely and Eran Malach. Learning parities with neural networks. Advances in Neural Information Processing Systems, 33:20356-20365, 2020.
[EA84] Renee Elio and John Anderson. The effects of information order and learning mode schema abstraction. Memory & cognition, 12(1):20-30, 1984.
11

---

[FHW 17] Carlos Florensa, David Held, Markus Wulfmeeer, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. Conference on robot learning, pages 482-495. PMLR, 2017.
[GBM 17] Alex Graves, Marc G Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. international conference on machine learning, pages 1311-1320. PMLR, 2017.
[GHZ* + 18] Sheng Guo, Weilin Huang, Haozhi Zhang, Chenfan Zhuang, Dengke Dong, Matthew R Scott, and Dinglong Huang. Curriculumnet: Weakly supervised learning from large- scale web images. In Proceedings of the European conference computer vision (ECCV), pages 150 2018.
[HW19] Guy Hacohen and Daphna Weinshall. On the power of curriculum learning in training deep networks. In International Conference on Machine Learning, pages 2535-2544. PMLR, 2019.
[JMMH14] Lu Jiang, Deyu Meng, Teruko Mitamura, and Alexander G Hauptmann. Easy samples first: Self-paced reranking for zero-example multimedia search. In Proceedings of the 22nd ACM international conference on Multimedia, pages 547-556, 2014.
[KB14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: /ttl///2.666. 2.890, 2014.
[KB17] Tom Koemi and Ondrej Bojar. Curriculum learning and minibatch bucketing in neural machine translation. arXiv preprint (eXXiv/707.09555 2017.
[Kea98] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983-1006 1998.
[KPK10] M Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. Advances in neural information processing systems, 23, 2010.
[MKAS21] 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, pages 7379-7389, PMLR, 2021.
[MMN18] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 166555)17665- 2018.
[MSS20] Eran Malach and Shai Shalev-Shwartz. Computational separation between convolutional and fully-connected networks. arXiv preprint arXiv:2010.01 369,, 2020.
[N] Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. The Journal of Machine Learning Research, 21(1):7382-744 14388227431,, 2020.
[PGM+19 19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[PSL15] Anastasia Pentina, Viktoriia Sharmanska, and Christoph H Lampert. Curriculum learning of multiple tasks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5492-5500, 2015.
[PSN+ 19] Emmanouil Antonios Platanios, Otilia Stretcu, Graham Neubig, Barnabas Poczos, and Tom M Mitchell. Competence- based curriculum learning for neural machine translation. arXiv preprint /903. 009848 2019.
[RK90] Brian H Ross and Patrick T Kennedy. Generalizing from the use of earlier examples problem solving. Journal of Experimental Psychology: Learning, Memory, and Cognition, 16(1):42, 1990.
12

---

[RSR' + 19] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li. and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. arXiv preprint arXiv: 1910. 10683, 2019.
[SAJI0] Valentin I Spitkovsky, Hiyan Alshawi, and Dan Jurafsky, From baby steps to leapfrog: How "less is more" in unsupervised dependency parsing. In Human Language Technolo- gies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 75 1-7759, 2010.
[SGG14] Patrick Shafto, Noah D Goodman, and Thomas L Griffiths. A rational account of pedagogical reasoning: Teaching by, and learning from, examples. Cognitive psychology, 71:55-89, 89, 2014.
[SIRS22] Petru Soviany, Radu Tudor Ionescu, Paolo Rota, and Nicu Sebe. Curriculum learning: A survey. International Journal of Computer Vision, pages 1-40, 2022.
[SMS22] Luca Saglietti, Stefano Sarao Mannelli, and Andrew Saxe. analytical theory of curriculum learning in teacher-student networks. Journal of Statistical Mechanics: Theory and Experiment, 2022 (11::111)144444 14014, 2022.
[SSBD14] Shai theory algorithms. Cambridge university press, 2014.
and Shai Ben-David. Understanding machine learning: From
[STD19] Shreyas Saxena, Oncel Tuzel, and Dennis DeCoste. Data parameters:
family parameters for learning a differentiable curriculum. In H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gamnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[TV19] Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with ar- bitrary initialization solves non-smooth, non-convex phase retrieval. arXiv preprint arXiv:1910. 12837, 2019.
[VSP+ 17) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[WA20] Daphna Weinshall and Dan Amir. Theory of curriculum learning, with convex loss functions. Journal of Machine Learning Research, 21(2)):1119, 2020.
[WCA18] Daphna Weinshall, Gad Cohen, and Dan Amir. Curriculum learning by transfer learning Theory and experiments with deep networks. International Conference on Machine Learning, pages
PMLR, 2018.
[WC721] Xin Wang, Yudong Chen, and Wenwu Zhu. A survey on curriculum learning. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2021.
[ZKK* + 18] Xuan Zhang, Gaurav Kumar, Huda Khayrallah, Kenton Murray, Jeremy Gwinnup, Marianna J Martindale, Paul McNamee, Kevin Duh, and Marine Carpuat. An empirical exploration of curriculum learning for neural machine translation. arXiv preprint arXiv:1811.00739) 2018.
[ZS14] Wojciech Zaremba and Ilya Sutskever. Learning execute. arXiv:1410.4675. 2014.
arXiv preprint
13

---

A Proof of Theorem 3
Algorithm Layer-wise curriculum- SGD. Init. scales K, A > 0, learning rates Y1, 7/ > 0, step counts Ti, 72, input param. P. batch size B, noise level and gradient range A.
1: input: Data matrix X E {+1 {=1]dxn and label vector Y E {=1}"
2: initialize: For all E [M] E [d], wh, 0, a. K. be Ad+1
3: X1 = ={x* ((x)) < d( } and
{v² :2 X11
Select sparse inputs
4: for =
1: do
5: Select unused zdd 11 and y ~ Y1, s E [b}.
6: Vi E [ E [d]:
7:
V +++1 1 = w/j 71
1 EBELB Owty x , + Unif[
8:
J ++1 1 | 1
D. [-]a: proj. on -A,
9:
6," b/, 0, ++ = =
10: end for
11: For all i E [N] Th
-1 2(i + 1)4, a. =0
12: for t = T to T2 11-1 do
Select unused "1 ~ X and nd ~ Y, [B]. 14: E [N]:
13:
15:
at+1 af 72 B EEEB 00: x²x ,"*)a + Unif[-r,r!)
(
16:
b,+1 =
17:
end for
In this section, we report the proof of Theorem The proof follows a similar argument used in [V19 [ we decompose the dynamics into drift and martingale contribution. Our work differs from the ones above in considering a mixed input distribution and the covariance loss. For the purposes of this section, we consider a 2- 2-layer neural network: NN(x; f) Σ a,o(w; =
6,). with N & + hidden neurons and activation o = ReLU. We consider the following initialization:
wij = 0,
0
(9)
60 = K S N(2Ad + 2)
(10)
60 = d
(11)
We train the neural network using the layer-wise curriculum-SGD algorithm (see Algorithm D for pseudo-code). Without loss of generality, we assume that the target parity is X[a] [[ zj. The result for other k-- k-parities follows directly since the initialization and the curriculum-Se algorithm are invariant to permutations of the input neurons. We show the following:
With large enough training set, there enough sparse inputs, which can be identified by computation of the Hamming weight.
We train the first layer's weights Wiy on the sparse data, keeping the o, b, fixed. We first show that with enough sparse samples, the labels' average will concentrate around Ez-1,, (x)), with high probability. This term is needed in the computation of the covariance loss. Then, we show that after Ti Ö(d) steps, with an appropriate learning rate, with high probability, the target parity will belong to the linear span of the hidden units. This is obtained by showing that the weights corresponding to the first i input coordinates move noticeably. while the ones corresponding to the other d - k coordinates remain small.
We train the second layer's weights a, on the full data, keeping the first layer's weights and biases fixed. Established results on the convergence of SGD on convex losses allow to conclude.
Bounding the Number of Samples. In the following lemma, we show that if the training set is large enough, the fraction of sparse inputs large, and their Hamming weights will concentrate around expectation with high probability as d increases.
14

---

Lemma 1. Let {a² {a" he(m)) be m ii.d. inputs sampled from D. with parameters p. Let X1 == fx": from
H(x)) d(2 b)} and let S1 {x² x² Du). If d < exp(d) and 2m1
for
p
C
i) With probability at least 1 - 2d
2d" 0², , 2 m.
ii With probability at least d d= S1 X1.
Proof.
1) For all s E [m], P(("* E 51 = p. thus,
IP
(x Si) - m1 P Σ
(x* E Si) mp S m1 mp)
(12)
#E p
s6 [m)
1(x 81) -m -7)
mp)
(13)
2
mmm
(0)
mp
Σ
1(x E 2 v logl log(d)m/2
(14)
sE(m)
(b)
S exxp (-2C" log(d)) S 2d
2d"C" 0
(15)
where in (a) we used that
mp Vdmp
2 VO* 1og(d)m/2
(16)
2
for some constant C*,, that depends only on p. and in (b) we used Hoeffding's 's inequality.
ii) It is enough to show that for all x² E S1, H(x)) < h for = dt 4) and for all
x= & S1, Hxx))= 2 h. Thus, for x² E S1.
P(H(r)) 2 h) = H(x²)
- u d 2 h - 1 d
(17)
2
2
1idd)
S exp
(18)
8
Similarly, for x S1, PP (H(*)) <h) < exp(-C'dd) for some C' > 0. The result follows from union bound.
In the rest of the proof, we will assume that the event in Lemma I holds.
A.1 First Layer Training
For the first training phase, we only use the sparse samples.
Computing Ø1- As a first step, we need to estimate the average of over the sparse set. To that purpose, we sample one batch of size B₁ from X₁. We denote by in such estimate
Lemma 2. Let Ø1 = Bi ExEBi Bij y. BB
B, 2 20 log(d)/{2, with probability at least 1 - d-c",
Ø1 n c.
(19)
Proof. By construction, and by Lemma Du Thus, by Hoeffding's 's inequality,
T1 is the mean of B, i.i.d random variables sampled from I
Bi
P(O E2-D, 2 5) < 2cxp
( 2
s 2d C
(20)
15

---

We assume that each sample is presented to the network at most once. For instance, this can be done by discarding each sample after it is used, assuming that the number of samples is large enough for covering all training steps. Denoting by Gwi, the gradient computed at step /. < Ti for weight wtj. the updates of the first layer weights are given by:
at+1
wij G
(21)
" [1 [
+++
(22)
where by [i|a denote the projection of all coordinates that exceed A (resp. -Á) A (resp. A)). Note that with our assumption on the initialization, NNN(x;0') < for all < T1. Thus, the gradients at each step are given by:
Guiy =
Σ sE[B]
(v"
F1) - NN(x" 0*) + Zuiy'
(23)
B
We decompose the dynamic into drift and a martingale contribution:
Gw = =Gut, + (G Garty
(24)
drift
martingale
where we denoted by
G = G
(25)
the (deterministic) population gradients.
Drift Contribution. In the following, denote by w/. w/y for an arbitrary neuron i [N]. We first bound the drift term.
Lemma 3. Let Lu = wh- tt Let Ç > O. B1 2 2C log(d)/(², with prob. c for all t < Ti,
Mj E [k]
Gwy + nLμl S KHS;
(26)
Vj [k] (aaz) S KKuG.
(27)
Proof. With our initialization, for all t < Ti,
Oug, NN(xt; 8h) kaz
(28)
Thus, for all j E [k].
Gw K (Bxlf(x)225) JE (x,
(29)
(1²-1 (11H)
(30)
Applying Lemma? 2 with probability e',
1Guu ابياع = |ku(Ø n²)1 S kpc.
(31)
Similarly, for all j é [k],
Gwy =pp(1* 5)
(32)
thus, applying one more time Lemma we get the result.
Martingale Contribution. We consider wf = why for an arbitrary neuron E [N]. For t E N and for all j, we define the martingale contribution the dynamics up time by
M
Σ
Gwg Gwg.
(33)
We show that for appropriate time horizon and learning rate, the martingale contribution stays small.
16

---

Lemma 4 (Lemma 4 in [ABAM23). Fix T & Cod Co for some Co > 0. For all C*, there exists C that depends on Co C such that if-
(34)
C(Kk + 7)2 log(d)
with probability at least d=c"
max max h Mf1 v o<t<T jEld
(35)
Vdlog(d)
Proof. Note that in our setting (Boolean imputs, ReLU activation) we have that for all <
M - 1 S Gwwl + Gwsl S 4m +
(36)
Thus, by Azuma-Hoeffding inequality:
IP (l7M)) 2 s) S 2exp
(37)
2T (4x + 7)
The result follows by choosing e = 1/v /dlo(dd and by union bound on all S Cnd loglo Co and
j E [d].
Bounding the Contributions to the Dynamics.
We define the following stopping times:
inf (t 2 0: loof
A n m4 + +)
(38)
sup jE(R]
(39)
We show that for 2 T rof stays close to A.
Lemma 5. Fix T < Cod log(d) for for some Co Let ( > 0 and let B₁ 20" log(d)((2 For
all C", there exists C such that in satisfies (34) and if( Valortayo with probability 3d -C"
for all j E [d]:
3 + Von
inf <KTT
w A
(40)
Vdlog(d)
Proof. For all j. let s = sup(t' S : wy > A 71 + r)}, then with probability 3d C" for all j E [d]:
[-1
= w - 7 Σ
m + 1MM--11 Mf)
(41)
I=s
2
A (14 T) 71truss Vdlog(d)
(42)
3
ViCH
A
(43)
V (dl
Vdlog(d)
3
Voou
(44)
(dg
/ /dlog(d)
where in (a) used that by Lemma with prob. 1 1 cd Gat < -kLp kpc < kpc for all
I [t] and Lemma in (b) we used that by (34). 71 71 (4x r) S 74 + T) < (log))) and
in (c) we used the assumptions on I' and Ç. Thus, the result holds.
We will now establish a nigh-proobbiiin bound on the time that it takes for all weights associated with coordinates in the support of the target parity to approach proximity with A.
17

---

Lemma 6. Let Ç > 0 and let B1 2 20 log(d)/(. For all C", there exists C such that if
Yn satisfies (34. { S Vologlajco and d is large enough, such that d lllo(d) 2 (vCon+1)2 with
A
probability 3d-C" C²;
2A
(45)
nnLL
Proof. Let T S Cod for some Co > 0. Let mintw/ : E [k], S 77 ST}.
Then, with probability 1 3d C
4-1
at 2 - Σ Go, - 711MM
(46)
2 -tt(-iil + mpth +
(47)
v dllogd))
Vlen
2 n
(48)
v /dlog(d)
(dlog())
(
Corf +
2 mtkLp
(49)
Vdlog(d)
where in (a) we used that by (34), Vtni < 1/ 11//dlogg dlog(d), and in (b) we used the assumptions on T 2A and d is large enough, such that Vou++1
and Ç. Thus ift 2 mhhp
A, we have
Vdlog(d)
2 24 - A
A
m (4x +T)
(50)
Thus, the result holds.
As our last lemma, we show that during the same time horizon, all coordinates that are not in the support of the parity will stay close to zero.
Lemma 7. Fix < Cod log(d) (o) for some Co > Let ( > 0 and les B₁ 2 20" log(d)/{² For all C", there exists C such that i satisfies
Vdlog(a) and d is large enough, such that
dlog(d) 2
(VCo++1)2 with probability 1 3d c² A
lw/l < Vou +1 +1
sup OSEST
sup (E
(51)
V /dlog(d)
Proof. Let |Bcl = max(|uf]== :j E [k + 1, dl S T}. Thus, with probability 1 - 3d-
t-1
13&1 = 71 Σ Go. M]
(52)
Sm Σ
Ga, + 7/ MM
(53)
a=0
I mttuuc
(54)
(loo(d)
ViCH+I 1
(55)
/dlo(dd)
Cap +1
(56)
/ dlg((d)
18

---

Thus, combining Lemmas 6 and 7 and by union bound on i E [N]. we get that for all C", there exist C₁, C2 such that I, and Yi are such that
2A
T < C(kk + 2 log log(
ST S Codlog(d)
(57)
n
for some Co C, with prob. 1 3Nd o², for all e [N].
C2
For all j [k]
|u A S
(58)
v Vdlog(d)
C2
For all j & [k]
| 1 1S
(59)
(olg((
For T S KG we can choose
Lا (gggd)
2C" AC"A² 2d 2d (d)
71
Ti
(60)
L
where C² C/50, and the result follows.
A.2 Second Layer Training
As mentioned, the second phase of training consists of training the second layer's weights a;, keeping Wiy and b, fixed. We do not train the biases, and directly assign 6.T to be well spread in the interval [A(2 - -k), A(2 + kt), that the target parity belongs to the linear span of the hidden units at time Ti. We believe that one could extend the argument to cover scenarios where biases are trained, but this would require further technical work. To train the second layer,
samples drawn from the entire dataset. Again, we take a large enough dataset and we assume that each sample used at most once. In the following, we assume that the events 58 (59 hold. Below, we show that there exist of such that Σ a; awo""," + b:) achieves small expected loss. For simplicity, we restrict our attention to A even, but an analogous Lemma to the below can be written for & odd. For a function S, an estimator f and input distribution D, let us define
- Te (f., = Enw (1 (o--((x)B - f(x) -Loo)))))))
(61)
Lemma 8. Assume k an even integer. Let N k + 1 for i {O,..., k}} let b, Ak + 2(i
1) A)A For all > 0, there exist A > D> max (C1, C2B such that if p < ( 2N - -D) V log(d)
and if
vdp
is large enough:
min a:]|a|] 54/A
Loov (f', X(M, D) < e/2.
(62)
Proof. We follow similar proof scheme in BEG 22), and choose at such that
4= = (-1) 4
Vi 10,1,...,,A 2},
(63)
A
0 = (-1)4-1
3
(64)
A
4f (-1)*
(65)
A
We denote f*(x) = E a (w r +-++b b:). One can verify that (x)) E af Eイ
b.). For all E [N], let us denote wij = wif A for all j E [k] and dij = wiji for all & [k]. Thus,
EnwD Σd - Dzyzy] pP Ey= dig conditioned on the event in 588- 59
|| /11 < C.vd for all
Vlog(d)
19

---

i [M], where C3 max C1, C2). d
A Then, SN
d
P PRDD
و
>8
S PRND
Σ
WifRy pulleiill1 > - pullieslla
(66)
j=1
(0)
P PDD
Σ Wijzr
pullcoella > D
(67)
(b)
D12 log(d)
D2
S 2exp
5 2d
203
(68)
2C3
where in (a) we used the assumption p and in (b) we used Hoeffding's 's inequality and the fact that
D²
40 2)=1(200)) v ld Thus, with probability 1 - 2Nd
over for all E {O....,
la 1o x bi) - (A Σ Ij + 6:)l -
Wiztz S
(69)
Consequently,
-x())
Σ aj
(w:
f bi) cA
Σ
3jj b:)
(70)
j=1
k
4NV <
Ja
8
8 = 1/2
(71)
A
t=0
D2
Thus, for d large enough, with probability 1 - 2Nd all r,
203
we have f (x) 2 1. Moreover, for
(ta)sNNllaall 24k VdC's
(72)
Vlog(d)
Vd
4N(C3 + 2AA)
(73)
Tog(d) A
Then.
Leov (f" X(k). D) ENND (1 X ( (I-= -xn()))())
(74)
EnnD(1 - (2) (1- (1) -xx
(xxg(=)f <1)
(75)
9N2(C's 21 (1 + pp
.d 20g 2
(76)
A Aloo(d
< </2,
(77)
for d large enough.
To conclude, we apply an established result from (SBD144) the convergence of SGD convex losses.
Theorem 6 (SSDD44). Let L be a convex function and let a" E argmin
|al SB L(a), for some
B > 0. For all t, let a' be such that E [a' a') = -Va [(aa) and assume
|| & & for some
B then { > 0. (0) 0 and for all t E [T] a = a' + taa, with 7 EVT
T
BE VT
Σ
C(a') s L(a*)
(78)
20

---

We refer to [SSBD14] for proof. Let us take L(a) = Loov (a, (l,,laa,,,, bb:,, X(e), D). Then, L is convex in and for all t E [T2],
a'
Va Leov ((a', wht oefib"t), b Xig x(q, Zar.
(79)
sE|B]
and, recalling := ReLUU we have
|a'll S 2sup 2 (1u"xx= +b, +
(80)
vdCa
2 2 +
+
(81)
v Ilg(dd)
d + V log(d)
(82)
and ||a0|12 1 W VN Thus, if we choose
N B
&
& = 2(C3 + 2AA T)
dN log(d]
T2 25 + 2
2A log(d)
(log(d)
72 S(C5+2AR+T)aN
obtain
min Loor (0', x(K) S Ta)
(83)
The result follows under the assumption that the training process is terminated once the training loss falls below e, thus guaranteeing that Levv (0Th (0Ti+T', ,XM), 2) S E.
B Proof of Theorem 4
Theorem 7 (Theorem
restatement). Let d, N be two positive integers. Let NN; 0)
EN (woz + by) be 2-layer fully connected network with activation ayy) = Ramp(y) (as defined in (84)) and N 2 (d + (dd k 1) log((d+ +1)dd- k+ 1)/5). Consider training (2
with layerwise curriculum-See SGD on the hinge loss with batch size B 2 N4{2N3) log( Nd+N noise and μ / -
level < Clog (Nd+N) 1/2 with S 3ad+1y<(d--4ツp>
25 Then, there
exists an initialization and a learning rate schedule such that after Ti = step on the sparse data and T3 / (d k 1) (d+ ()N (11+)) T)² steps the full data, with probability 1 36 the trained network has generalization error at most e.
This proof is similar to the proof of Theorem CM23) with the following two modifications: 1) the of mixed input distribution in the second part of training, and, 2) the addition of uniform gradient noise in the iterates.
B.1 Proof Setup
We consider a 2-layer neural network, defined as NN(x;; 0) = EN awo + b:), where N > (d + (d k + 1) log((d + () le + 1)/8) is the number of hidden units, 0 (a, b, w) and σ = Ramp denotes the activation defined as:
x S0
Ramp(x) =
0 0<r5h
(84)
<>1
Similarly as before, without loss of generality, we assume that the labels are generated by (x)
- Zt. Our proof scheme is the following:
21

---

1. We train only the first layer of the network for one step on data (a. X[x (2)) with ~ Dr..
with = 2p
2. We show that after one step of training on such biased distribution, the target parity belongs to the linear span of the hidden units of the network;
3. We train only the second layer of the network on (z, X[a with D, until convergence;
4. We use established results on the convergence of SGD on convex losses to conclude.
We train our network with noisy-GD on the hinge loss. Specifically, we apply the following updates, for all t E {0, 10, T
1}:
B
w ++1
w - 7t-
V w
L(0', x1(),=')) xx=,++ + Zwis)
B
==1
1+1 d
df m1
V at L(0', x11) + Za! + ce.
(85)
B
1
b-+1 X
b + B
b L(O', X14 x'5) + Zoz + +dl.
where L( .XM,, x: max 1 (1) (x; 0²) and Zui,, Zaz and Zo are i.i.d. Unif[-7,
for some т > Following the proof strategy introduced above, we set DO = Dus, where =
2(d 2j. and D = D, for all 2 We set the parameters of (85) to:
1 (k- (B-1)2N,
7/t 0
A4 2 1,
(86)
C
170 = 0,
N1 2N
7)2
V2 2 1.
(87)
N
th n
1/ =
7 2 1,
(88)
1
= 2N Ao (d (d+1) 1); do
C 0
1T
(89)
12
A
(90)
122 2
d.
(91)
and we consider the following initialization scheme:
w = 0
E [N].j [d]:
a 2N
Vi [N]
(92)
60 ~ Unif { bim
+ 1
EE (0, (-1,..,, d k3].
dd+1
2
where we define
m +
bmn = d 21
(93)
2 d - k
Note that such initialization is invariant to permutations of the input neurons.
B.2 First Step: Recovering the Support
As mentioned above, we train our network for one step on (z., (x)))) with Dr-
Population Gradient Initialization. Let us compute the population gradient initialization. Since set Eo 0, we do not need compute the initial gradient for Note that at initialization
22

---

INN(;;; 09) < 1. Thus, the initial population gradients are given by
AAA W
Gwns DDiBBDDD
II xi 2( + +b b, [0,
(94)
re(M)
Vj # 1 [I]]
G -ailBArDD [E|]uy
II Ti I((1;;)) + [0,
(95)
Vi [N]
Gb -aglEen
II [E(M]
x7 ((1g by (0,
(96)
Lemma 9, Initialize a, b, w according to (92 Then,
11 kb-
Vj [R)
Owis
(97)
2N
vj # [k],
Gun.s
(98)
2N
Gb
(99)
2N
Proof. If we initialize according since EE,D, [xs(x)) ا
92 have (w;, x) b. [0, 1] for all The results holds
Effective Gradient at Initialization. Lemma 10 (Noisy-GD). Let
Ger,s B
V 1
L(0", X(k) x1x), x²0) Zuris
(100)
1
Go, = Σ bo (00 X1(), + Zo.
(101)
be the effective gradients at initialization, where Gwis Go, are the population gradients at ini-
tialization and Zway Zo. are i.i.d. Unif[-7, If B 2 (u3N2)-''oos 8 and z
Ç çlog| (N 1/2 with probability 26: ||Guu, -Gw, Sc, ||G.. Go SG.
(102)
(103)
Proof. By Hoeffding's 's inequality
IP (1âuns -Owe.yl c) 2exp
2C²
28
(104)
(4N2B)-1 +
Nd + N
(IGb. -G, 22() S ( 2cxp
202
28
(AN2B)-1+
(105)
Nd + N
The result follows by union bound.
O
Lemma 11. Let
w wi,j G0
1 0
(106)
b3 Ao (Bº thu Gb.
(107)
(108)
B 2 (4C2 log( Nd+N and S ( (oog ( (Nd 1/2
with probability 1 28,
23

---

i) For all j E [k), d E [N]. Wii 11 S u
i) For all j & [k], |utt
2od ) I n
iii For all i E [M] 16. (d + () - 1 v M
Proof. We apply Lemma
i) For all j E [k]. E [N], | - 1| = -20 -700Guu (u - -Gwipl 1 15 px-11
2NC
ii) For all j & [k] E [V], hool, - -(1 2(d-x)) -oo(runn Gwnnl 1 S
2NC.
mi) For all i [V].
1 b 1oo + voOCr. Ao + :bo
[8 - (d + 1)(())
(109)
S Dol |vol |Gnn,GGG
- -Ga.
(110)
N(d + +1) 1)Ç
(111)
1
Lemma 12. N 2 1)(d + - 1)/6), then with probability 1 8, for
all E {0,... d), and all m E {-1,..., k} there exists such that by
htm.
a+1
2"
Proof. The probability that there exist (, m such that the above does not hold is
N S exp
k -
(1 (-(a+1)dd k
(-Td ()(d
N
S (d+ 1)(d - +1
(112)
The result follows by union bound.
d Lemma 13. Let Jl (z) Ramp (Ej=1 Ft [[d Σj>k Tty + btm with bim given in 93 If
B 2 (4C2N3) log Nd+N T < Clog (N -1/2 and N 2 (d+ 1)(d + 1) log((d (d+ 1)
+ 1)/8), with probability 36, for all m there exists such that
d
)= saa(d+ 1)(m**
(x) - Ramp Σ
8)
(113)
Proof. By Lemma 12 with probability - 5, for all 7, m there exists i such that 1.00 dim 3.2 For
d+l
ease of notation, we replace indices i + (Im), and denote &tm (z) = Ramp (2g wim + llm)) Then, by Lemma 11 with probability 25,
d
wim. - (1 (1- 2(d - k)
1 )) I + bim b
(x) 3mm (x)1= v
(wim. - 1)2, +
Σ $=k+1
1=1
< K2NCC (k-1) + (d k)2NCH (k-1) + N(d + 1)çH
< 3N (d 1)
We make use of Lemma 6 from (CM23), for which we rewrite the statement here for completeness.
24

---

Lemma 14 (Lemma 6 in (CM23)). There exists a" with 1a~ - 4(d k) such that
k
Tma = [x]](2)).
(114)
1=0
Lemma 13. Let (x) Ei, aim Tim (x) and let f(x) = Ei. aim ttm (z), with olm, Tim defined in Lemma 13 and a" defined in Lemma 14 If B 2 - log( N ) S < log ( 1/2
and N 2 d 1)(d K + 1) log((d + [](d k+ 1)/5), with probability 1 36 for all x,
L(fif", .2) S (d+ - A 12222
(115)
Proof.
(x) - = Σ aim (0 (x) 5lm (z)
(116)
1,m
s d(d 1))((" 11 sup
mm (1) 3bm (x)
(117)
Im
(d + 1) - k 1)
(118)
Thus.
(1 (1-f(z) (11
(119)
(t))()))
(120)
= 34 11)22k
(121)
which implies the result.
B.3 Second Step: Convergence
To conclude, we use one more time Theorem 6 Let L(a) EXED [I((a, bi, x(), Then, C convex and for all [T].
B a' E
(o' x) Zo.
Vo L w x.]]
(122)
Thus, recalling o Ramp, we have || 1+ and |aa S VN + r). Let a" be as in Lemma 14 Clearly, ||a 2| < 4(d - 1 + 1) Moreover, al = 0. Thus, we can apply
Theorem with B = 4(d - + 1)3/2 1) and = /N((1 + +T,, and obtain that
T [/ (d - k 1) + 1)N + +)
* 1/ 2M(1+}J for t E {1....,T):
then, with probability 1 - 38 over the initialization
EzeD min L (0', x(x),²) [E|2']
+ c
= e.
(123)
2 2
C Proof of Theorem
Let us recall the definition of Cross-Predictability (CP) from (A220] Definition Ccros--rredictabilityy (CP), (SS20). Let Py be a distribution over functions from (+13d to {+1} and Px a distribution over [+1]d. Then,
CP(Pr, = Ep Px (x))) (()
(124)
We invoke Theorem 3 from AS20), which we restate here.
25

---

Theorem 8 ([AS20) Let Ps be distribution on the class of parities on d bits, and let Px be distribution over {=1]a. Assume that P PE-Ps.>PP (F(
Oa(1). Consider any neural network (2; 0) with P edges and any initialization. Assume that a function { is chosen from Py and then T steps of noisy-SGD (Def. D with learning rate 7, gradient range batch size and noise level т are run the network using inputs sampled from Px and labels given by f. Then, in expectation over the initial choice of f. the training noise, and a fresh sample a ~ Px, the trained network satisfies:
P P(sgn NN 0*) = f(x))
1 2
TPA T
(CPIPE.PH)
(x)
1 1/2 + B
(125)
In Theorem 8
imported Theorem from AS20 with 1) the tighter bound for the specific case of 1/2 instead of (CP+11) +1/)1//) (see Theorem 4 and remarks parities, which gives term (CP +1/B)
in ):S20): 2) the bound to the junk flow term JF for noisy-SGD with uniform noise, instead of Gaussian noise, which gives a term P instead of /P (see comments AS23).
We thus compute the cross cross-predde prediccttttt between Px = D and Py being the uniform distribution on the set of parities of degree
Lemma 16. If μ 0(1).
1
CP(Unif (k-arit()),rrities), D) -
+ + 22
(126)
where C₁2 is a constant that depends only on
Proof.
CP(Unii((-parittes}) D) = Es,s BonD (x)(
(127)
d
-1
Es,s (xss)))
(128)
k
d
tss B (x)
(129)
k
(
d
k-1
p
d
(CL+
(130)
k
d
k-1
12
(Cx O(d
(131)
k
du
t=
d
d (dpt)-1-1
11 4/
C p²
(132)
k
where in (a) we used that for S and S' two randomly sampled sets of le coordinates, we have:
(-)
P(ISns|= =
(133)
((()(())))))) r(1+k-1) +0(1/a)
d!
(134)
< d (Cx + 0(1dd)
(135)
*()r()) where Ck is such that C 2 r(+*-()
for all / [k - 1].
p > 1/4, 1/4 then
(
( -1
(-prrii(s) D) <
+ C. p² 1
(136)
k:
where C% depends only on k.
26

---

Finally, we need to discuss that Theorem applies to any fully connected network with weights initialized from distribution that is invariatt to permutation of the imput neurons. Let Xs Xs(2 Iljes F.j. with |S| = k. and let be random permutation of the input neurons. Theorem 8 and Lemma 16 imply that after 7 steps of training with noisy-SGD with the parameters A, B and T, on data generated by DD and Xs, the trained network is such that
TPA
(()
1 B
1/2
(,P(NN 07) = (xs -
+ u
+
(137)
Recall that the network is fully connected and the weights outgoing from the input neurons are initialized from distribution that invariant permutation of the input neurons. Consider the action induced by on the weights outgoing from the input neurons. By properties SGD, follows that each conditional probability on contributes equally the left hand side of 137 thus the same bound holds also for the single function:
P(NN(1;0') = xs(x)) S 1 TPA
((1) k
1
1/2
+ CRP
4k
+
(138)
2
B
D Proof of Proposition
Note that
1 1-y'r 1'D-'''aa f(x")('' = (y-)² - -10 f'0-f(x''(0)
(139)
(y" 115-~((66) -f(()))) 9)
(140)
(1 (1 (1-'f(x²))(( (1'')
(141)
Since |0| < 1, sg - 0² = 1, and sgn((1
v'd)) sgn(1 v²f(x*)) Thus, (1- (1=))(t"))(1-
1 Σ
(142)
[m]
f(=)) v')) 1ly <1)
(143)
m
xE(m]
(1 (1- v' 1 1l <0)
(144)
#E(m]
Σ
( f(*)))x 0).
(145)
sc(m)
E
Experiment Details and Additional Experiments
In this section, we provide more details on the implementation of the experiments. Moreover, we present further experiments on the comparison the curriculum strategy and standard training.
E.1 Experiment Details
E.1.1 Architectures and Loss Functions
Architectures. We used an MLP model trained by SGD under the lg loss for the results presented in the main part. In this appendix, we further present experimental results using other models, particularly, mean-field field [MMI88] and Transformer [VSP+17 17). Below, we describe each in detail.
MLP. The MLP model is fully-connected architecture consisting of 4 hidden layers of sizes 512, 1024, 512, and 64. The ReLU activation function has been used for each of the layers (except the last one). Moreover, we have used PyTorch's default initialization which initializes weights of each layer with U
where dim is the input Vddim.
Vdiim.
dimension of the corresponding layer.
27

---

Mean-field. We also use two-layer neural network with mean- [MMN18 parametriza- tion. Particularly, define fMF(2) N Σi= a z) b.) where N 2 and о ReLU are the number of neurons and the activation function respectively. We also initialize the weights following a, U(-1, 1), w; ~ U va v2) and b, ~ (( ) where d is the dimension of the input. Note that with this parametrization, one should employ large learning rates (e.g., 1000) assuming SGD is used as the optimizer.
Transformer. We use the standard encoder part of Transformer architecture [VSP+ 17 which is commonly used in language modeling ([RSR#19) and vision applications (par- ticularly, Vision Transformers [DBK 20 More specifically, we first embed #1 into a 256 256-dimensional vector using shared embedding layer. Then, the embedded input is processed through 6 transformer layers. In each transformer layer, the size of the MLP hidden layer is also 256, and 6 attention heads used. Finally, linear layer is utilized for computing the output. We also use learnable positional embedding.
Loss Functions. We have mainly used the &g loss for our experiments. Nonetheless, we additionally present results on the hinge and covariance loss which are used in our theoretical results. We briefly review each of these losses below.
& loss. We use the squared loss (j y/² for each sample where ÿ and y are the predicted and the true values respectively.
Hinge loss. We use the hinge loss defined as max(0, 1 - jyy for each sample where the true label y E } and the predicted value ÿ E R.
Covariance loss. We also use the covariance loss defined in Definition 2 i.e., max(0, (v- (v - 0) max(0, 1 - vÿ ø(v 7)), where E [11]. ÿ E (-1,1) and y E E present the true label, the average of the true label (on the training distribution), and the predicted value.
E.1.2 Procedure
We have implemented the experiments using the PyTorch framework [PGM 19). The experiments were executed (in parallel) on NVIDIA A100, RTX3090, and RTX4090 GPUs and consumed ap- proximately 200 GPU hours (excluding the selection of hyperparameters). Note that each experiment has been repeated using 10 different random seeds and the results are reported with 95% confidence intervals.
Curriculum Strategy / Standard Training. Here we explain the general setting of training. When using the curriculum strategy, the model first trained on the sparse samples until the training loss reaches below 10-2 Then, in the second phase of the curriculum, the training is continued on the mixed distribution until the training loss drops below 10-3, On the other hand, during the standard training, the training is done on the mixed distribution, again, until the training loss becomes less than 10 33
Number of Samples/Number of Iterations. We generally focused on two components to compare the curriculum and standard training: sample complexity and the number of iterations needed for convergence. To compare the sample complexity, for given number of training samples, we first generate training set according to / and μ.. In the case of using the curriculum, the sparse samples are then selected by checking if their Hamming weight satisfies (xx) < d() 4) Afterward, training done as described earlier with or without the curriculum. Finally, the test accuracy (or the test loss) is compared. We are also interested in the number of steps needed for the convergence of models whether the curriculum used or not. To study the number of optimization steps independently of the number of samples, we consider an online setting in which each mini-batch is freshly sampled and there is no fixed training set. Note that in this case, when in the curriculum's first phase, we directly sample the sparse distributions from Dr,.. Similarly, the model is trained until the training loss drops below 10-3, and then the number of iterations is compared. The only exception is fmiddle in Figure where we were mainly interested in the weak learning of the target function. In that case, the training is stopped when the training loss reaches below 0.26.
28

---

Hyperparameter Tuning. Note that the experiments are aimed at comparing the standard and curriculum-basee training fair and similar context. As a result, we did not perform extensive hyperparameter tuning for our experiments. (Also note that the task and/or the training distribution varies from one experiment to another.) Nonetheless, we tried different batch sizes and learning rates to ensure the robustness of our findings. Generally, we did not observe any significant change in the patterns and potential gains of the curriculum method (of course changes like using a smaller learning rate would make both curriculum and standard training slower). Consequently, we used moderate batch size of 64 for all of our experiments (other than Transformers) and we selected the learning rate based on the speed and the stability of the convergence. Particularly, when optimizing the MLP model with SGD under the & loss (which covers all experiments presented in the main part). For the mean mean-field model, of Transformers, we used the Adam [B14) optimizer with batch size 512 and learning rate 0.0001.
used learning rate of 0.003
learning rate of 1000. Also for the experiments
E.2 Additional Experiments
First, we complete Figure by presenting the plot that shows the gain of the curriculum method in the number of iterations needed for convergence for different parity degrees in Figure Similar to the previous experiments, we consider the parity embedded in dimension d' = 100. As expected, it shown that parities of higher degree require more iterations be learned in general. However, this increase in iterations is mild when the curriculum is employed, which leads to an increasing gap between the curriculum and standard training as the degree of parity is increased.
Parity degree
k=5
k=7 7
Steps to learn
k- 10
10c
Standard
Curriculum
10-3
10
Figure 4: Dependency of the gains of the curriculum strategy in the number of training steps for different degrees of the parity function. The gain of the curriculum method potentially increased parities of higher degrees are used.
Next, we move the mean-field model. Similar to the other experiments, we evaluate the benefit of the curriculum strategy for both the sample complexity and the number of steps needed for convergence. We empirically observed that the mean-field model is able to learn parity functions more easily (with fewer samples and iterations) than the MLP model used in the main text. We thus use parity of degree i 7 in dimension 100 and μ 0.98 demonstrate the gains of the curriculum strategy more clearly. Particularly, we report the accuracy of the mean-field model trained under the f2 loss for = 0.01 and different training set sizes in Figure (left). Likewise, the number of iterations needed for convergence for different values of p is presented in (right). As expected, the gap between curriculum strategy and standard training both the sample complexity and number of optimization steps similarly exhibited if mean-field model is used.
29

---

1.0
+
Std. Curr.
+ Std.
curr.
Gen acc
0.8
Steps
0.6
0.5
10a
10a
10-3
10
10-1
Number of training samples
Figure 5: Comparison curriculum and standard training for the mean-field model trained under the l2 loss; (left) accuracy of the model trained on training sets with varying sizes, (right) the number of iterations needed for convergence the model. The general picture of the potential benefits of the curriculum method remains unchanged.
Moreover, study other loss functions studied in this paper. To this end, we keep the same setting as above, considering the mean-field model, parity of 7 bits, and d = 100, = 0.98, and p 0.01 (unless varying). We report the results of the hinge and covariance loss in Figure 6 and Figure respectively. It can be seen that the patterns are generally similar to the case that &g loss was being used (Figure 5 In sum, the curriculum method makes the learning of the parity function possible with fewer samples and iterations for small enough values of
1.0
- Std.
10a
Std.
Curr.
Curr.
acc
0.8
Gen
Steps
0.6
16a
0.5
10
10"
2
10
Number of training samples
Figure 6: Potential benefits of the curriculum strategy for the mean-field model trained with the hinge loss; (left) accuracy for different training set sizes, (right) the number of iterations (with fresh samples) needed for the convergence of the model. Similar to the case the Eg loss, the curriculum beneficial for small enough values of p.
Std.
Std.
10a
Curr.
Curr.
0.9
Gen. acc
0.8
Steps
10a
0.6
10
10a
10a
10
10
10-1
Number training samples
Figure 7: Comparing curriculum strategy and standard training for the mean-field model trained with the covariance loss; (left) accuracy for different training set sizes, (right) the number of optimization steps needed for learning the parity function. Similar to experiments where & or hinge loss are used, curriculum potentially reduces the number of iterations and also the number of samples needed for learning.
30

---

Finally, we evaluate the curriculum strategy for the Transformer model trained under the Eg loss. To make the optimization of the model faster, we use Adam [KB14 optimizer with batch size 512 for this experiment. We also stop the training when the training loss reaches below 10-2 instead of 10-3 Similar to the above-mentionet setting, we set 1 0.98, p 0.01 (unless varying), d = 100, and we consider learning the parity of degree k = 7. The validation accuracy of the Transformer for different training set sizes is presented Figure [ (left). can be seen that there is significant, albeit weak, advantage in terms of sample complexity when the curriculum is used. Similarly, the number of iterations with fresh samples needed for convergence the model is shown Figure (right). The gain in the number of steps is also weaker than the other models, nonetheless, it is significant (especially for small values of p such as 0.001).
8
1.0
Std.
Std.
10a
0.8
Gen.
Steps
0.5
10
10a
10
10
Number of training samples
Figure 8: Evaluating the curriculum for the Transformer model terms of sample complexity (left) and the number of iterations (right). It can be seen that the curriculum can still be significantly benefi- cial, although the difference between the curriculum and standard training weaker comparison to the MLP and mean-field model.
31


Reviews:
[{"review_id": "xl2BbvutaI", "reviewer": "Reviewer_RLGW", "summary": "This paper studies the impact of curriculum learning for the family of parity functions. Compared to previous work, in which their settings have been distanced from a realistic setting, e.g., considering a non-common activation function with a particular initialization, or a non bounded learning rate, this paper solves all of those issues, although still in special case of covariance loss. They have been successful to show how the order of samples given to the model will effect the sample complexity, both in theory and experiments. Besides, to the downsides of the standard SGD algorithm that samples are completely shuffled, they have provided quite tight upper bounds for the final accuracy of a general fully connected neural network with limited total size, when assuming the procedure is noisy to make it resemble SQ-learning setting and use similar proofs.", "questions": "1 - Would you please make a clarification on new points of your paper? It seems like your reference(CM23) has covered most of the claims as in your paper. \n\n2- I suggest to include other tasks that curriculum would come to be handful in your work.", "limitations": "The main limit of this paper is not to go anywhere else other than the parity task. Many papers have investigated the same object before.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1- Authors' suggested setting has been closest to reality so far. Unlike previous work they use a bounded learning rate throughout the training process, whereas the former algorithm had proceeded by using only one step of sgd with a learning rate that can get arbitrarily large. \n\n2- The combination of a lower bound for test accuracy when using curriculum learning (giving correlated samples at first so that it approximately learns the support) and an upper bound in case of standard random batch sgd, illustrates advantages of the proposed algorithm. \n\n3. Experiments are in fully agreement with results of theories, and they have implemented various settings for this: Comparison on number of samples, dependence on training steps, and different parameters.", "weaknesses": "1- Improvements over previous work is not very conspicuous. Essentially there is no new point in the paper but having former arguments in a more rigorous manner. \n\n2- Additionally, they don't give any assuring bounds besides two layer neural network, which is the exact model their reference work has considered. \n\n3- There are many non-free hyper parameters in their training process. Having assumed that the number of training steps for the first part of algorithm (T_1) depends on parity size is questionable. This can be the reason why previous work assumed only one step of SGD on sparse data. \n\n4- When attempting to come up with similar bounds besides the covariance loss, which is not common between experimentalists, they only consider hinge loss. And this causes their advantage over previous work to disappear because learning rates gets unbounded.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see the global response for the differences with the previous work [CM23]. We address the rest of the remarks and questions in the list below.\n\n- Q1. Does $T_1$ depend on $k$?\n\nA1. $T_1$ depends on $\\mu^k$, through the parameter $L_{\\mu}$. This dependence appears in the 1-step arguments as well, and we believe that it cannot be removed. However, we remark that choosing $\\mu$ sufficiently close to 1 (e.g. $\\mu =1-\\frac{1}{d}$ or $\\mu =1-\\frac{1}{k}$) allows bounding  $\\mu^k$ independently from $k$. \n\n- Q2. Hinge Loss learning rate is unbounded.\n\nA2. We believe that Theorem 3 could be extended to include the setting with hinge loss. This however would require a more complicated proof (e.g. by adding a second $l_\\infty $ projection to the iterations of SGD).\n\n- Q3. How does the proposed curriculum method generalize to other tasks?\n\nA3. We empirically investigated the suggested curriculum method for Boolean functions other than parity targets (see the last part of Section 5). We have shown that the suggested curriculum method can still be beneficial for learning or weak learning of some Boolean functions. However, we have also shown that there are functions for which the proposed curriculum is not helpful. Based on these experiments, we put forward the conjecture that curriculum can be beneficial in learning of the lowest degree monomials of a function and therefore (based on the structure of the function) it might be helpful or not. Beyond the Boolean functions, we believe similar observations can be found for functions on the Gaussian inputs.  We believe the most analogous real-world application of our setup is the use of input length in NLP/reasoning tasks (note that here $+1$ is the identity element so it can be also viewed as the padding element and the number of $-1$’s can be seen as length – see related literature)."}, {"review_id": "QFIpxa04So", "reviewer": "Reviewer_Sb2P", "summary": "This paper presents provable results showing the efficiency of curriculum learning for a specific problem setting with training data $(x,y)$, where $x\\in(\\pm1)^d$ is mixed distributed and $y=\\Pi_{j\\in\\mathcal{S}} x_j\\in(\\pm1)$. What's more, the study utilizes a 2-layer fully connected network and the noisy-SGD training method ", "questions": "1. This paper introduces a highly specific data setting. How can this setting be applied to real-world applications or more general settings?\n2. Is there a particular significance to the notion of \"sparsity\"? I am curious about the evidence if the model was trained on dense data instead of sparse data initially.\n3. In Theorem 3, why is $T_1$ independent to the first layer model size $Nd$, while $T_2$ is much larger than the second layer size $N$? Additionally, is the result evaluated using training accuracy?  \n4. In my opinion, a more appropriate point of comparison for standard training would be: **randomly** sample an equivalent dataset size (as in curriculum learning) to train the first layer, followed by training the second layer using the entire dataset. Since the first layer contains significantly more parameters, standard training might introduce overfitting due to the layer-wise training method rather than curriculum learning.", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper clearly proves the advantages of curriculum learning over standard learning by analyzing a well-defined problem.\n2. Numerous results are also provided and highlight the reduced sample and iteration requirements of curriculum learning.", "weaknesses": "Please see Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Q1. This paper introduces a highly specific data setting. How can this setting be applied to real-world applications or more general settings?\n\nA1. In our opinion, the closest curriculum method in the real world is the use of input length for NLP and reasoning tasks. Note that $+1$ is the identity element in the Boolean setting and thus can also be viewed as a padding element. Consequently, the number of $-1$’s can be seen as the length of the Boolean inputs (see related literature). We also expect similar results to be found in the learning of functions with Gaussian inputs. However, the goal of this paper is to prove the benefit of curriculum learning for a problem (with the same task on the same data distribution) where theoretical analysis is possible, and that is the reason that we have focused on the parity functions where we have been able to prove a separation result. \n\n- Q2. Is there a particular significance to the notion of \"sparsity\"? What about training the model on the dense data initially?\n\nA2. On sparse data (i.e., inputs with few negative bits), parities on different supports are correlated. In particular, $\\mathbb{E}_x[\\chi_S(x)\\chi_T(x)] = \\rho \\mu^{|S \\Delta T|}$ assuming $S\\neq T$ ($\\Delta$ stands for symmetric set difference, i.e., union minus intersection). This allows SGD to easily identify the relevant coordinates, and a subsequent fit on the whole dataset allows to learn the correct function. We remark that the same holds if we defined sparse inputs as those with few $+1$ bits, and mostly $-1$ bits (having negative $\\mu$ – note that the absolute value of the quantity above does not change). On dense data (i.e., inputs with roughly half negative bits), parities on different supports are not correlated ($\\mathbb{E}[\\chi_S(x)\\chi_T(x)] \\approx 0$), which makes identifying the support challenging for any progressive learner (including SGD). For this reason, training initially on dense inputs only does not help for identifying the support of the parity, thus we expect such curriculum not to be beneficial for learning parities.\n\n- Q3. In Theorem 3, why is $T_1$  independent to the first layer model size $Nd$, while $T_2$ is much larger than the second layer size? Additionally, is the result evaluated using training accuracy?\n\nA3. The model size, and more specifically the number of hidden units, has to guarantee that the network can represent any $k$-parity. During the first layer training the network identifies the set of relevant coordinate, and $T_1$ does not depend on the number of parameters (note that at each step of training all weights in the first layer move). For the training of the second layer, we used standard results on convergence of SGD on convex losses. $T_2$ depends on $N$, however it is larger that that since we took a small learning rate ($\\gamma_2 \\approx 1/ Nd$). The result is evaluated using the training loss (covariance loss), which in our case can be related to the training accuracy (see Proposition 1). Note that in the experiments (other than the ones in Figure 3), we directly report accuracy. \n\n- Q4. Using first layer then second layer training for both the curriculum and standard training; since the first layer contains more parameters, standard training might introduce overfitting due to the layer-wise training method rather than curriculum learning.\n\nA4. We remark that the benefits of the curriculum algorithm is not due to the layer-wise training. First note that in the experiments we train all the layers jointly for both the curriculum and standard training. For the theoretical results, the negative result for standard training (Theorem 5) is also valid whether the training is done layer-wise or jointly. We will clarify this issue in the paper as well. \n"}, {"review_id": "V67uIvZ6yn", "reviewer": "Reviewer_8Apd", "summary": "The authors present a separation result between curriculum learning and standard learning in the number of noisy-(S)GD training steps for a 2-layer ReLU network for case of learning noiseless k-parity. While the precise training algorithm deviates from the common deep learning setup, experiments verify that learning k-parity can benefit from learning sparse inputs before harder dense inputs - mostly in terms of an improved sample complexity.\n", "questions": "- To which degree does the performance actually depend on being exposed to the hard samples?\nCurriculum learning is based on the hypothesis that it is not only beneficial to learn from easy examples early but that learning from hard samples later also boosts the performance. \nI am aware the the negative result needs $\\rho$ to be small. Yet, I suspect that learning only on \"easy\" examples would already be sufficient to learn a parity function because the easy examples carry all relevant information about the parity function.\nTo analyze this question in more detail, it would be good to 1) make the generalisation accuracy independent of the mixed distribution and test whether the correct target function has been learned; 2) report how the performance changes during training.\n\n- Figure 2 (middle) implies a non-monotonous dependence of the accuracy in $\\mu$. It would be good to study this in more detail and show a figure with $\\mu$ on the x-axis. What could be an explanation? Does it matter whether $d\\mu$ is even or uneven?\n\n- To which degree are the experimental results dependent on hyperparameter tuning? Where the standard learning and curriculum learning be tuned independently?\n\n", "limitations": "The limitations have been pointed out under weaknesses and were mostly discussed by the authors. I do not foresee a major or immediate societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Theoretical evidence for benefits of curriculum learning.\n- Additional positive results for the hinge loss.\n- Bound on sample complexity for the positive case.\n- The negative result allows for a comparison with the positive one in some settings.\n- The experimental results suggest a strong difference between curriculum learning and standard learning (yet, not exactly in the theoretical setup so far) in the context of learning a parity function.", "weaknesses": "- The analysis is limited to a single and not very general learning problem (learning k-parity).\n\n- The analysis makes assumptions that are quite different from practical deep learning setups:\n1) Non-standard neural network initialization. \n2) Non-standard loss (covariance loss) that penalizes errors on samples with true negative labels higher than errors on truly positive samples. The hinge loss results rely on an uncommon activation function.\n3) The hinge loss results are relatively weak as they just state the existence of an initialization etc. that leads to successful training. Essentially, this is not stronger than an expressiveness results, because the initialization could just correspond to the optimal (potentially learned) parameters.\n4) No noise in the data.\n5) Curriculum learning and dense learning use learning algorithms that are different also in other aspects than just the order of samples. For instance, the batch size is required to be quite large in case of dense learning. Most importantly, the theorem for curriculum learning assumes a much larger proportion of easy examples $\\rho$ than the standard learning. This is important because $\\rho$ essentially controls how easy the learning problem is. In the experiments, for large enough $\\rho$ dense learning seems to perform better than curriculum learning. (Btw, this observation is not explained by the theory.)\n6) The learning algorithm is not standard SGD or GD but learns the layers separately.\n7) The bias parameters are not trained (and it is left unclear in the main paper how they are initialized).\n\n- Mismatch between experimental validation and theory:\n1) different loss (l2 in experiments, mostly covariance loss in theory)\n2) k = 5 in most experiments, while theory assumes k >=6 for separation result.\n3) MLP with four layers instead of 2.\nExperiments should also validate the theory and not only study fairly unrelated cases where we can make similar observations. The direct validation would be important to understand how relevant the constants in the theoretical results are, for instance.\n\n- The theorem statements are hard to understand because they rely on notation that has not been introduced in the main text. (Examples: $\\mu^{k-1}$ or $\\Delta$ or P.)\n\n- The proof techniques do not appear to be very novel but similar to previous work.\n\n- Missing information: How is the generalisation accuracy computed? I assume samples were drawn from the mixed data distribution, which depends on $k$ and $\\rho$? How many samples were used in the experiments?\nThis is important because it also influences how hard the learning problem is. \n\n- The theoretical and experimental results study the performance with respect to a test distribution that depends on the amount of easy versus hard examples.\nThis is suboptimal because it can therefore make no claims about the question what kind of data would benefit learning the actual parity function (on all possible inputs).\nIn contrast, the central question underlying curriculum learning is what kind of data (and which order) is best for learning a task.\n\n\n**Points of minor critique:**\n\n- Literature discussion:\nGiven the literature discussion, the study of the specific problem of learning parities in the context of curriculum learning does not seem to be in its infancy, as claimed.  \nFurthermore, [SMS22] does not really make the difficulty level criterion label dependent but dependent on the (irrelevant features). In some sense, the same holds also true for the submitted work, as the definition depends on the negative coordinates that also inform the label.\n(Yet, this does not change the fact that [SMS22] and the presented work are sufficiently different.)\n\n- More elements of the notation could be explained. For instance, Rad could be introduced as Rademacher distribution; Unit as uniform distribution; neural networks could be defined formally earlier, []_A could be defined mathematically, etc. The bias scale was not defined. \nHow are the biases initialized? \nThe size P of a neural network has not been defined precisely. Does it refer to the number of hidden neurons or number of parameters?\nWeak learning has not been defined/explained.\n\n- The set of sparse inputs does not have size $\\rho$ on average according to the definition of $X_1$ on page 3 (different from how it is frequently discussed). Also $D_u$ contributes to $X_1$, while $D_{\\mu}$ does not always. Later, $d$ is assumed to be large enough that the statement is approximately correct, but that comes a bit late (and is not very precise).\n\n- Only even values of $\\mu$ have been studied in the experiments. Uneven averages should also be considered.\n\n- Not all curves in Figure 2 (middle and right) are visible.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Q1. What about training only on easy samples?\n\nA1. Note that neural networks do not know that the target function is a parity function a priori, thus, they cannot recover the parity function only from the sparse data. (We agree that if the learner knew that the target is k-parity it would have been able to recover it only from the sparse samples, as identifying the support would have been sufficient.) Indeed, we observed that mismatch between the training distribution and test distribution would result in worse generalization and that training neural networks on sparse samples would cause the neural network to learn other lower-degree solutions rather than the actual parity function.\n- Q2. Non-monotonous dependence of the accuracy in $\\mu$. \n\nA2. We note that this non-monotonous dependency is indeed reflected in our theoretical results as well. Particularly, the results in Theorem 3 depend on the quantity $L_\\mu = \\mu^{k-1} - \\mu^{k+1}$, which is maximized near $\\mu = 1$  but does not increase monotonically with $\\mu$.\nDue to the challenges of defining sample complexity properly, we rather not to plot the sample complexity with having $\\mu$ on the x-axis. Please also check Figure 4 which also shows the dependency on $\\mu$. \nFinally, we remark that $d\\mu$ is a real-valued and continuous quantity; we thus do not expect any different behavior regarding evenness. We will add more context regarding the dependency of the sample complexity on $\\mu$. \n- Q3. Hyperparameter tuning.\n\nA3. We tried different values for hyperparameters (mainly batch size and learning rate) to ensure the robustness of our results and we did not observe any significant changes in the potential gains of the curriculum method. For the experiments presented in the paper, we selected hyperparameters based on the speed and stability of the convergence of the standard training. (We tried to use values that are common in practice as well, e.g., batch size of 64). To ensure fairness, we used the values that we picked for standard training for the curriculum method as well.  We have explained our hyperparameter tuning in Appendix E.1.2.\n- Q4. Limitation to parity targets.\n\nA4. Indeed, the focus of this paper is on parity targets. However, we experimentally investigated the proposed curriculum method for Boolean functions other than parity targets (see the last part of Section 5). Our experiments suggest that the proposed curriculum method can still be beneficial for learning or weak learning some Boolean functions, but a deeper understanding of those is left to future work. However, we have also shown that there are functions for which the curriculum is not helpful. \n\n- Q5: Different assumptions from practical deep learning setups.\n\nA5: For the positive result, we have made some simplifying assumptions on the training settings so that the theoretical analysis becomes feasible. Note that some of these assumptions, such as layer-wise training, are quite common in the theory of deep learning. On the other hand, our negative result holds for all fully connected architectures of any depth, and with any activation and initialization that is invariant to permutations of the input neurons. Also, in our experiments we tried to use common deep learning settings. \n- Q6:  Hinge loss result.\n\nA6:  In Theorem 4, we prove that there exists an initialization such that, under appropriate hypothesis, SGD can successfully learn *any* $k$-parity. Thus, this is not just expressiveness, as one does not know which $k$-parity is the correct target and our initialization is agnostic of the target function. We will clarify the statement of the theorem to avoid this confusion and we thank the reviewer for pointing this issue out.\n\n- Q7. Curriculum learning and dense learning use learning algorithms that are different also in other aspects than just the order of samples.\n\nA7: We addressed this question in the general rebuttal. \n- Q8: Mismatch between experimental validation and theory.\n\nA8: We cover more general and common settings in our experiments comparing to the theoretical part. (As pointed out by the reviewer, some of our assumptions for the theoretical side are not common in practice, for this very reason we focused on the common training settings for the practice). Nonetheless, we emphasize that this is an extension of our theoretical results and not a mismatch. Additionally, we have also covered the setting of our theoretical results in the appendix. Particularly, in Figures 5,6,7 we have covered 2 layer neural network (with mean-field parametrization), hinge loss and covariance loss. We have also used parities beyond degree 5 in Figures 2 and 4.\n- Q9. How is the generalisation accuracy computed? Number of training samples?\n\nA9. The generalization accuracy is computed based on $D_{mix}$. In Q1 we explain the need for using the same distribution for training and test. The number of training samples is shown on the x-axis for experiments regarding sample complexity. For other experiments that work with fresh samples and number of iterations the number of training samples would be given by batch size (almost always 64) * number of iterations. However, we once again emphasize that samples are fresh and only seen once. \n- Q10. What kind of data is most useful?\n\nA10. Note that for each single experiment (or theoretical result) the training (=test) distribution is shared between curriculum and standard training to make the comparisons fair. In our setting, we need sparse data to start learning the function (detecting the latent dimensions) and we also need to have matching train and test distributions so sparse samples alone are not enough (see Q1 as well). This indeed shows why such a curriculum is helpful. \n- Q11. Points of minor critique\n\nA11. We thank the reviewer for these points. We will revise the text to clarify the points raised. We will clarify the notation and how the biases of Thm 3 are initialized in the main."}, {"review_id": "S2okenwyFR", "reviewer": "Reviewer_3jFh", "summary": "This paper presents a theoretical analysis of curriculum learning, in which a neural network first presented with “easier” examples is able to more efficiently learn a target over more “complex” examples. The authors specifically consider the problem of learning $k$-sparse parities over a distribution which is a mixture of the uniform distribution over the hypercube and a biased distribution over the hypercube (the easy examples). The main positive results study a two-layer neural network trained via a layer-wise curriculum version of SGD (Algorithm 1), where first the first layer weights are trained on samples from the biased distribution, and next the second layer weights are trained on samples from the mixture distribution. Theorems 3 shows that this algorithm learns $k$-sparse parities with respect to the mixture distribution in $\\tilde O(d)$ steps of SGD. In contrast, the paper presents a lower bound showing that noisy SGD on the mixture distribution alone requires $\\Omega(d^{1+\\delta})$ timesteps to learn a $k$-sparse parity up to nontrivial error. The proof for the upper bound relies on the martingale plus drift argument to show that the $k$ relevant coordinates have been learned after the first stage, while the lower bound uses similar techniques to proving SQ lower bounds.", "questions": "- It appears that in Theorem 3, the algorithm receives far more samples from the biased distribution than the uniform distribution. In particular, during the first stage the algorithm receives $\\tilde O(d)$ biased samples, while in the second stage receives $\\tilde O(d)$ uniform samples. In contrast, when running SGD on the entire mixture distribution (like for the lower bounds in Theorem 5), the algorithm receives only $\\rho$-times as many biased samples as uniform samples. In the regimes where there is a separation, $\\rho$ is very small, in which case curriculum SGD is receiving far more samples from $D_\\mu$. It thus seems like the success of curriculum SGD is not necessarily due to viewing the “easy” examples first, but rather from having access to far more “easy” examples than in regular SGD. Is my understanding here correct, and can you please comment on this further?\n\nI am open to increasing my score after further clarifications on the above point and my concerns in the weaknesses section.\n\n- Minor typos: In Algorithm 1, should line 3 be $\\frac12 - \\frac{\\mu}{4}$ instead?\n\n", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written.\n- I skimmed the proofs in the appendix and they appear to be sound. The experiments section demonstrates that the proposed curriculum strategy is effective in settings beyond those considered in the theory.\n- Curriculum learning is a common procedure in practice, and yet there is limited theoretical understanding of its behavior. The sparse parity problem presented here is an interesting setting to study curriculum learning, with a clear measure of “easier” samples. The results here adequately show that a neural network can obtain an efficiency improvement from first training on these easier samples, which I find to be a very nice result.", "weaknesses": "- The novelty of the paper, in comparison to the prior work [CM23], is a bit difficult to discern. It appears that the main difference is that the current paper uses SGD for multiple steps in the first stage and uses the “drift plus martingale” technique for the proof, while [CM23] considers a single large step of GD with large batch size in the first stage and shows that is sufficient for learning the support. However, Theorem 3 here seems very similar to Theorem 3.4 in [CM23]. Also, Theorem 4 still uses the one-step algorithm. Could you please comment further on the novelty of the current paper in comparison to the prior work?\n- A minor weakness is that the algorithm is a bit restrictive and has some nonstandard modifications. In particular, during the first stage the biases are chosen to be very large ($\\Theta(d)$), and then resampled to different deterministic values before the second stage. Next, there is an $\\ell_\\infty$ projection on the weights during each step of stage 1. Could you please comment on the necessity of these modifications? I think the paper could benefit from additional discussion of these modifications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please see the global response for the differences with the previous work [CM23]. \n\n- Q1: A minor weakness is that the algorithm is a bit restrictive and has some nonstandard modifications. In particular, during the first stage the biases are chosen to be very large Theta(d), and then resampled to different deterministic values before the second stage. Next, there is an $l_\\infty$ projection on the weights during each step of stage 1. Could you please comment on the necessity of these modifications? I think the paper could benefit from additional discussion of these modifications.\n\nA1: Biases: We consider fixed bias parameters for simplicity of the theoretical analysis. Regarding the specific values that we chose, we initialized them to large constants in order to have simple expressions for the gradients of the network during the first part of training (eq. (25)). After the first part of training, we update the biases so that they are well spread in the interval $[-\\Delta k, \\Delta k]$ and the target parity belongs to the linear span of the hidden units at time $T_1$.\n\n$l_\\infty$ projection: We added an $l_\\infty$ projection to prevent weights from diverging. This projection is needed because the training process doesn't occur simultaneously for both layers. As a result, the training doesn't stop once the network fits the data.\n\nWe will add a discussion of the above in the paper. \n\n- Q2: It appears that in Theorem 3, the algorithm receives far more samples from the biased distribution than the uniform distribution. In particular, during the first stage the algorithm receives Theta(d) biased samples, while in the second stage receives Theta(d)  uniform samples. In contrast, when running SGD on the entire mixture distribution the algorithm receives only $\\rho$-times as many biased samples as uniform samples. It thus seems like the success of curriculum SGD is not necessarily due to viewing the “easy” examples first, but rather from having access to far more “easy” examples than in regular SGD. \n\nA2: It is true that our current theoretical results cannot distinguish between having more easy samples or less. Indeed although we have proved an upper bound on the number of samples needed, we do not have any lower bound on the sample complexity. We have tried to explain this in Remark 4. Nonetheless, in the sample complexity experiments (Figure 1)  we are using the exact same data and we only change the ordering for curriculum and standard training. \n\n- Q3: Minor typos: In Algorithm 1, should line 3 be $1/2-\\mu/4$ instead? \n\nA3: Yes, thank you for pointing out the typo\n"}]

Author rebuttal:
We thank all reviewers for their constructive comments. We address the remarks and questions in the lists below.

## Comparison to [CM23] 
Our result is not only an improvement of [CM23] in terms of having more natural training settings and hyperparameters (i.e., we use SGD with bounded batch size and bounded learning rate in Theorem 3), it is also establishing a separation between learning with and without curriculum on a common sampling distribution, while [CM23] does not.
 
More specifically:
1. We prove a separation between curriculum training and standard training on a common dataset (sampled from $D_{mix}$) in contrast to [CM23], where curriculum training involves both sparse and dense inputs and standard training involves dense inputs only. To the best of our knowledge, our paper is the first work that establishes a rigorous separation between training on adequately ordered samples and randomly ordered samples drawn from the same distribution, and our theorem gives a condition on the mixture under which this separation holds (interestingly the separation does not take place for all mixtures parameters).
2. We prove a positive result for layer-wise curriculum SGD with or without noise with bounded batch size and bounded learning rate (Theorem 3). This involves separating the dynamics into a drift term and a martingale term and adequately bounding each contribution. While such drift-martingales techniques appeared recently in previous works for spherical and Gaussian inputs, to the best of our knowledge, none of the references mentioned in the paper consider Boolean inputs and parity targets. In contrast, [CM23] makes a 1-step argument with an unconventionally large learning rate to show that correlations with the support can be obtained in the hidden layer, without tackling the full dynamics. 
3. The martingale proof technique allows us to obtain a tighter upper bound on the number of samples needed to learn with curriculum, compared to the 1-step argument used in [CM23]. In particular, in Theorem 3 we prove that with curriculum we can learn with $\tilde O(d/\rho)$ samples, while applying the same proof technique of [CM23, Theorem 4] allows to obtain an upper bound of only $\tilde O(d^2/\rho)$ samples.
4. We prove a non-trivial negative bound for standard training on inputs sampled from $D_{mix}$, while the negative part of the separation of [CM23] relies on previously established lower bounds for learning parities on uniform inputs. We emphasize that our lower bound holds for any fully connected architecture of any depth, with any activation, any learning rate schedule (e.g., layer-wise) and permutation-invariant initialization. 

## Further comments on curriculum and standard training in the theoretical results (Reviewer 8Apd)

- Q7: Difference between currriculum and standard learning.

A7: Batch size: indeed our negative result holds only for noisy-SGD with large batch size. We are not aware of any technique for proving lower bounds for SGD with small batch size. Our positive result holds for the same setting as our negative result AND for other settings as well, such as SGD without noise and any batch size. Thus, our theoretical separation holds for noisy-SGD with large batch size. On the other hand, our experiments use SGD with standard batch size for both curriculum and standard training. 

Proportion of easy examples: Our separation holds for small $\rho$, thus for datasets with a small fraction of easy examples. In Theorem 3, we assume the number of easy examples to be at least $\tilde \theta(d)$, which implies that our dataset must be of size at least $\tilde \theta(d/\rho)$. We remark that we do not assume a large proportion of easy examples, we assume instead a large enough dataset (indeed we prove an upper bound on the number of hard samples needed, but the algorithm can use more).

Theoretical results for large $\rho$: Indeed, our experiments surprisingly show that curriculum can be harmful for datasets with many easy samples (at least in terms of number of training steps needed to learn). This case is indeed not covered by our theoretical results. While we do not have a negative result for curriculum training, Theorem 3 gives, in the setting considered, an upper bound on the number of training steps needed to learn with curriculum that does not depend on $\rho$. On the other hand, if we try to apply the footprints of the proof of Theorem 3 to standard training, we would get an upper bound that decreases with $\rho$ (it would depend on the expectation of a k-parity under $D_{mix}$). We do not expect rigorous arguments for  such bounds to be easy extensions of our work.


Meta-review: The paper builds on prior work [CM23] towards understanding curriculum learning using parity functions. Compared to [CM23], they provide tighter convergence analysis under more natural settings, in particular, small batch SGD compared to one-step large batch gradient descent, and bounded learning rates. The paper also has a new negative result showing a separation between curriculum and standard training. 

The main concern that came up in the reviews was the novelty in comparison to [CM23] which the authors mostly addressed to the satisfaction of the reviewers. As most reviewers agree, this work provides new theoretical guarantees for the benefits of curriculum learning over standard training which would be of interest to the NeurIPS community. Therefore, I recommend accepting the paper. I encourage the authors to include the feedback from the reviewers as they prepare the camera-ready. In particular, it would help to add the discussion from their rebuttal on the comparison with [CM23], include clarifications to questions that came up for the reviewers, and be more transparent about the limitations of their technical results.
Decision: Accept (poster)