When Does Curriculum Learning Help? A Theoretical Perspective
Authors: Raman Arora
Yunjuan Wang
Kaibo Zhang
Venue: NeurIPS 2025 poster ()
Keywords: curriculum learning; learning theory; generalization; biased regularization; convex learning problems
Primary area: theory

Abstract: Curriculum learning has emerged as an effective strategy to enhance the training efficiency and generalization of machine learning models. However, its theoretical underpinnings remain relatively underexplored. In this work, we develop a theoretical framework for curriculum learning based on biased regularized empirical risk minimization (RERM), identifying conditions under which curriculum learning provably improves generalization. We introduce a sufficient condition that characterizes a "good"   curriculum and analyze a multi-task curriculum framework, where solving a sequence of convex tasks can facilitate better generalization. We also demonstrate how these theoretical insights translate to practical benefits when using stochastic gradient descent (SGD) as an optimization method. Beyond convex settings, we explore the utility of curriculum learning for non-convex tasks. Empirical evaluations on synthetic datasets and MNIST validate our theoretical findings and highlight the practical efficacy of curriculum-based training.

When Does Curriculum Learning Help? A Theoretical Perspective
Raman Arora Johns Hopkins University Baltimore, MD 21218
Yunjuan Wang Johns Hopkins University Baltimore, MD 21218 ywang509@jhu.cr edu
Kaibo Zhang Johns Hopkins University Baltimore, MD 21218 kzhang900 edu
arora0cs. j.u.jjuueh edu
Abstract
Curriculum learning has emerged as an effective strategy to enhance the training efficiency and generalization of machine learning models. However, its theoret- ical underpinnings remain relatively underexplored. In this work, we develop a theoretical framework for curriculum learning based on biased regularized empir- ical risk minimization (RERM), identifying conditions under which curriculum learning provably improves generalization. We introduce sufficient condition that characterizes a "good" curriculum and analyze a multi-task curriculum frame- work, where solving sequence of convex tasks can facilitate better generalization. We also demonstrate how these theoretical insights translate practical benefits when using stochastic gradient descent (SGD) as an optimization method. Beyond convex settings, we explore the utility of curriculum learning for non-convex tasks. Empirical evaluations on synthetic datasets and MNIST validate our theoretical findings and highlight the practical efficacy of curriculum-base training.
Introduction
In standard supervised learning, achieving low generalization error often requires large num- ber of labeled training examples and significant computational resources. contrast, humans can rapidly learn new concepts from only few examples by leveraging prior knowledge. This human- like ability to relate new a new concept to the knowledge they have previously learned motivates the of prior knowledge in ana, 1997], transfer learning [Weiss et al., 2016], and meta-learning [Baxter, 2000], the assumption that related tasks share information, allowing learners generalize more effectively. In param- eter transfer frameworks [Kuzborskij and Orabona, 2013, Pentina and Lampert, 2014), this shared structure is reflected in the assumption that tasks have similar optimal parameter vectors, enabling efficient learning through initialization and fine-tuning.
learning problem. In paradigms such as multi-task learning [Caru-
Curriculum learning [Bengio al., 2009] draws inspiration from the structured manner in which hu- mans acquire knowledge - starting with easier concepts and gradually progressing to more difficult ones. This paradigm proposes decomposing complex learning problems into sequence of simpler sub-tasks ordered by increasing difficulty. The central idea is that such a learning progression can improve both optimization and generalization. Bengio et al. [2009] demonstrated how learning benefit from gradual progression the hardness of training data. Subsequent works extend the idea other aspects of learning, such increasing model capacity [Karras al., 2017, Sinha et al., 2020, Morerio et al., 2017] and increasing task difficulty [Caubrière et al., 2019, Florensa et al., 2017, Lot- ter et al., 2017, Sarafianos et al., 2017, Zhang et al., 2017]. We focus curriculum learning across tasks, where parameters are transferred from simpler tasks to more complex ones.
In contrast to traditional transfer learning, which assumes all tasks are closely related, cur- riculum learning introduces an ordering over tasks based on their difficulty. However, such
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

an ordering does not imply that all tasks are mutually similar. In fact, strong similarity often limited adjacent tasks [Pentina et al., 2015]. Accordingly. we assume that only pairs of consecutive tasks are related, allowing for progressive knowledge transfer. This setup accommodates scenarios where the first and last tasks may be significantly different, as long as each intermediate step is incrementally learnable. Figure 1 illustrates this struc- ture, where successive tasks exhibit similar loss landscapes and closely aligned minimizers.
Curriculum learning offers both optimization and statis- tical benefits. From an optimization perspective, con- tinuation methods [Allgower and Georg. 2012] progres- sively increase problem difficulty-sarrting with convex, smooth objectives and transitioning to more challeng- ing nonconvex or nonsmooth objectives-thus helping the learner avoid poor local minima. Similarly, curric- ula that score training samples by difficulty [Weinshall et al., 2018, Weinshall and Amir, 2020] show improved convergence when training begins simpler examples. Self pelfd learning [Kumar et al., 2010] adapts this idea by dynamically weighting training sam- ples based their inferred difficulty during training. On the statistical side, recent works [Xu and Tewari, 2022, Cohen et al.. 2024] study the benefits of curriculum learning in simplified settings such mean estimation. They show that, under appropriate conditions, learning from easier and statistically similar source task can reduce the number of samples required to learn a target task.
Figure 1: An illustration of potential rela- tionship between tasks in a curriculum.
In this paper, we extend previous insights to broader supervised learning problems by studying the statistical benefit of curriculum learning in the multitask setting, with a focus on the general learning setting of Vapnik [2013]. We propose curriculum learning framework based biased regularized empirical risk minimization (RERM)Scchlkkopf et al., 2001, Denevi et al., 2019], where knowledge transfer is facilitated by incorporating bias vector Wo in the regularization term A/| - woll This inductive bias has proven effective in computer vision [Kienzle and Chellapilla, 2006, Tommasi et al., 2013], natural language processing [Daumé III. 20091, meta-learning [Pentina and Lampert, 2014, Kuzborskij and Orabona, 2017, Denevi et al., 2019, 2018], and continual learning [Li et al., 2023). We extend this idea design curriculum across tasks and provide theoretical and empirical support for its effectiveness. Our key contributions are as follows.
1. We propose a biased regularization- based curriculum framework (Algorithm 1) and introduce a novel (r, a)) condition that characterizes 'good' curriculum. This condition is simple, natural, intuitive, and depends only on the population loss two consecutive tasks. We show that ensures reduced sample complexity for subsequent tasks when is small.
Under convexity assumptions, we provide excess risk bounds for our biased-RERM. approach to curriculum learning. We show that the hardness of curriculum learning depends the Lipschitz constants of the loss functions for each task, the local Lipschitz constants near the minimizer, the smoothness parameter of the loss function, and the quality of inductive bias obtained from learning previous tasks. These factors also determine the order of the tasks in a 'good' curriculum. We extend our analysis efficient SGD-based training and apply results adversarially robust learning.
3. For nonconvex learning problems, introduce an ERM-based curriculum learning algorithm and establish generalization guarantees via uniform convergence, showing that even in nonconvex settings, carefully constructed curriculum can improve learning efficiency.
Paper Organization. In Section 2, we present the formal setup and define the (r, a) condition for a 'good' curriculum. Section 3 analyzes the role of biased regularization in a two-task setting. Section 4 provides theoretical guarantees for convex tasks using biased RERM and SGD. Section 5 extends our framework to nonconvex tasks using ERM. Section presents empirical results on synthetic and real datasets that validate theoretical findings.

---

2 Problem Setup
Notation.
Throughout, we denote scalars, vectors, and matrices with lowercase italics, lowercase bold, and uppercase bold Roman letters, respectively; e.g., u, u, and U. We use [m]] to denote the set {1, ................................ m and both || and ||2 for ég-norm. We use the standard O-notation (O, O and {2).
General Learning Problem. In a general learning problem, each example is drawn from data domain 2; for instance, for standard supervised learning, 2 X' Dr where X' is the input space and y is the output space. We assume that data are drawn i..d. from an unknown distribution D over DD' consisting of n i.i.d. samples. Let H. denote the hypothesis class, where each hypothesis is parameterized by a vector w E R". Let f 2 x H I denote the loss function. The population risk with respect to the underlying population, D, and the empirical risk on sample S ~ DD' are defined, respectively, as
2. The learner has access to a training dataset S (7+
1 [s(w) = |S]
LD(w)= == En-D[e(Z; w)],
((z;
ZES
A learning algorithm A Z - H maps any dataset S to hypothesis A(S) E H. The goal is to design a learning algorithm with minimal excess risk defined as E(w) == Lp(w) inf Lp (w'). We consider the following classes of problems based on the structural properties of the loss function.
Convex: The learning problem convex if É(z, w) is convex in w for every z.
Strong Convexity: The problem is X-strongly convex if f(z, w) - 2 w/l is convex.
Weak Convexity: The problem is (-weakly convex if E(z; w) + 1| is convex in w.
Lipschitz: ((---) is p-Lipschitz if, for all W1, W2 E H. [8(z; wi - ((z w2) S ||w] w2ll2.
Smooth: ((.,-) is H-smooth if VW1, W2 H. VV w1) V. w2) 12 H [[w] -2l12-
Biased RERM. Regularized empirical risk minimization (RERM) is popular learning algorithm known for its strong generalization performance. In its standard form, RERM returns a predictor A(S) E argmin [w) + / [[/ll where μ > is a regularization parameter that encourages low-norm solutions to prevent overfitting. We consider a variant called biased RERM, which returns
A(S) E argmin WEH
L ||w wo lå.
where Wo E RT is reference hypothesis that serves as an inductive bias. The regularization term now encourages solutions close to Wo. which can be interpreted as incorporating prior knowledge into the learning. We can benefit from biased RERM if there exists a good predictor near Wo-
Multi-task Curriculum. We consider a curriculum consisting of T distinct tasks. For each e (T), the 1-th task is defined by specific loss function (< w) and an associated unknown data distribution D; over the sample space Z. Both the loss functions and data distributions may differ across tasks, capturing scenarios such as regression followed by classification, or variations in label semantics or data modalities. For each task t E (T), we draw an i.i.d. sample of size n, from the corresponding distribution, S. D." The population and empirical risks for task are defined as
(w) == [((x,]]((
Ls. (w) :=
The Σ (z(::)). ZE.S.
1
The excess risk for task / is given by sy(w) (w) -in TeD, (w'). The goal of curricu- lum learning is learn the target task T' by sequentially training on all T tasks, while leveraging knowledge from earlier tasks to improve generalization on the final target task. In this paper, we focus on curriculum learning wherein each task is solved via biased RERM. Specifically, we use the solution from task t - 1 to initialize (aka, regularize) the learning of task t. This is done through bias function de that maps the learned hypothesis W from the previous task to a bias vector for the current task. For simplicity, we assume & is the identity map, i.e.. the bias for task t is directly given by w,-1. 1. However, our framework naturally extends to more general settings where each task I may have its own hypothesis class Hr, and the bias function Φ; H4-1 - Hr bridges the learned hypothesis from task L to a suitable inductive bias for task f. This sequential procedure using biased RERM across tasks is formalized in Algorithm 1.
3

---

Algorithm Biased Regularization- bassd Curriculum Learning
Input:
Wo. SI,...,Sy. MI, PT > O.
Wo Wg.
fort = port=122,... 1,,,... 1,2,...,Tob To
Wr argmin (Iss + + || w.-1183
end for return: WT-
(r, a) Condition of the Curriculum. To effectively apply biased RERM to task t. we require good bias (W,-). i... previous solution close good predictor for the current task after mapped onto H4. Since W is obtained by learning task t t- 1, this requires that consecutive tasks be similar enough for the prior solution to be informative. We formalize this similarity using the (Te, 0x) condition, which relates the excess risks of two consecutive tasks. Specifically, we assume that
inf w":l|w'- du Srr
<<(w) arEL-1(W),
(2)
for constants ra and dg E (0, When this condition holds, say that tasks t - 1 and t satisfy the a4) condition. We will assume Φe is the identity mapping only for simplicity in our core theorems.
Intuitively, this condition means that a predictor w has small excess risk on task 1, then there exists predictor w' within ball of radius r, centered at w, with excess risk at most aye on task t. Thus, a solution to task can serve as a useful initialization or inductive bias for task
We note that since the scale of the loss functions is arbitrary, one can always apply affine rescaling to them so that at the same across all tasks. Therefore, for simplicity, we assume a a (0, Vt. In practice, we do not rescale losses across tasks. But for theoretical clarity, assuming a constant allows us to streamline the presentation of our results without loss generality. If needed, our theorems could be extended to carry task deseddeenndnnt ag values throughout. Further, we emphasize that we do not need condition (2) hold for all w E R" Since we initialize the learning for task with predictor that generalizes well on task - 1, it suffices if (2) holds for w with (-1(ww) S for sufficiently small E (0, 1). However, we may need to set e differently for different settings. So, for convenience, and without loss of generality, we state the condition in (2).
3 Warm-up: Curriculum Learning with Two Tasks
In this section, we illustrate the role of biased RERM in curriculum learning by analyzing a simple setting with only two tasks, i.e., T = 2. The goal is to learn the second (target) task by first learning the first (source) task. Let w E argmin,, Lo, (w), w E argmin,, LD, (w) denote the optimal predictors for the two tasks. We assume that the first task is X-strongly convex with gradients uniformly bounded at the optimum:| (zl wfllla S Pr. Vz E 2. Second task is pz-Lipschitz
The curriculum solves the first task using empirical risk minimization (ERM), and the second task using biased regularized ERM. This procedure described Algorithm 2.
Algorithm 2 Warm-up: A Two-task Curriculum
Input: S2, #2 > 0. W argmin, T.s; (w).
W2 argmin, [L.s, (w) + #2
W
return: Wz.
Theorem 3.1. If the second task is convex, then setting μi
202
have
[lw4 (iwg-willes 11112 + x 122
21
(e2(W2) <
2p2 (lw3 - willz + vmz
Pr
A

---

Theorem 3.2. If the second task is L-weakly convex, then setting μ12 = +
202
(11v3
(ww--i w 112 x /n2
we have E [e2((W2)] S
[Iw2 willa Aym + 1/2 (lww2 willa + vT2
2p2
Aym
Theorems 3.1 and 3.2 show that curriculum learning can achieve fast generalization rate for the target task under mild similarity assumption assumpionn-seccffiallly when the optimal solutions of the two tasks, wi and w3, are close. This proximity ensures that hypothesis learned from the simpler first task (i.e., strongly convex) can serve as an effective bias for the more challenging second task. Importantly, the excess risk bound for the second task reflects this structure: it improves as the distance between wi and wá decreases and achieves a fast rate as the first task is easier to learn.
The regularization parameter μl2 in both theorems is chosen to optimize the theoretical bound and depends on unknown problem-specific quantities. These values are thus not intended for practical implementation. In practice, μa should be treated as a tunable hyperparameter, selected via valida- tion or cross-validation. Nonetheless, the analysis reveals that two-phase curriculum strategy- first solving well- well-behaved source task, then regularizing toward its solution can yield statistically significant gains in sample efficiency for the target task.
4 Curriculum Learning with Multiple Convex Learning Tasks
In this section, we consider a curriculum comprising T convex learning tasks that are learned sequen- tially. Our goal is demonstrate the role of the (r, condition in facilitating efficient learning of the target (i.c., the 2h task. Here, we focus on convex learning problems (with additional structure, e.g., Lipschitzness, smoothness, and non-negativity). We first provide thcoretical guarantees for biased RERM under this setup (Section 4.1), then extend the analysis to computationally efficient variants such as SGD (Section 4.2) and settings where tighter bounds can be obtained by leveraging local geometry (Section 4.3). We relax the convexity assumption in Section 5.
4.1 Learning Convex Lipschitz Tasks using Biased RERM
We assume that each task t E [T'] in the curriculum is a convex learning problem with a p Pr-Lipschitz loss function. Furthermore, we assume that every pair of consecutive tasks (t 1, satisfies the (Te, at) condition for some constants > O and a E (0, 1). We use the biased RERM algorithm described in Algorithm for curriculum learning. To highlight the benefit of the curriculum, we begin by analyzing two consecutive tasks: task /. 1 and task i.
Theorem 4.1. Suppose task / is convex and pe-Lipschitz and the (rt,a) condition holds between tasks (t- - 1, Then, setting 1 = 2p, yields the following excess risk bound:
revnn
2raPt
E [ex (w.)] S
+ aB (
The result above shows that if ri is a small constant, then using Wi-1 as the bias in biased RERM leads to a smaller sample complexity for learning task t. A natural setting where this occurs is when the minimizers of successive tasks are close. For example, in large language models (LLMs), task t-1 can represent a pretraining phase that yields model W close to the minimizer of many related downstream tasks. If task is such downstream task and its minimizer is close to that of task t t-1, 1, then small perturbation of w,-1 yields good predictor for task t. In this case, small value of r. justified, and the sample complexity required to generalize on task / is correspondingly small.
Proof Sketch. To upper bound the excess risk Ee (We), we begin by decomposing as follows:
Es, (E.(Ww) = Ess, LDD (w:)] inf LD. (w)
w
= Es. LD. (w.) Ls. (w:) +Es. Ls. (w:) Ls. Ls.)) [ (w)
inf LD. (W)(3)
where w/ is any hypothesis independent with S.. By the (rt, a:) condition, there exists w', s.t. I|w" We-1lle E rt and s<(w') I dct-1( (w,-)) hold. Hence, the third term in the decomposition can be
5

---

upper bounded by LD. (w') - inf LD. a Next, consider the second term. Using the definition of biased RERM,, we have:
Es. [s, (w:) [s'(w)) S Es, Us,(Wi) + Me
[e w Lss (w')
2
Es. Ls, (w') + I| - wi-1l12 -w-
Ls, (w') _
1477
2
2
where the second inequality follows from the optimality of W. under biased RERM and the final inequality uses the assumption ||w' w & lt-
Finally, we consider the first term in the decomposition: Es, LD. Ls. (we) the general- ization gap. Using the uniform stability results from Shalev-Shwarre and Ben-David [2014], and noting that the loss function is convex and p--Lipschitz, the generalization gap can be bounded by Es, w.) S Eg, Ls, (We)
2pī
,4r Putting the three terms together and optimizing the bound w.r.t. 14 minimize the sum of the first two terms yields the upper bound stated in Theorem 4.1.
Corollary 4.2. Assume the first task is learned with excess risk E (W1)] S c. Set the regulariza- tion parameter to 14
4r
and suppose the sample size n, 2 (1- Then, for all tasks t, the r / excess risk is bounded as I (w:)) S
In the above Corollary 4.2, assume that the first task is sufficiently easy to learn to small excess risk. This can be achieved, for example, by choosing a strongly convex learning problem, using a large number of samples, initializing from high-quality pretrained model.
However, requiring e-suboptimality for all tasks may be unnecessarily strict, especially when our goal is only to achieve small excess risk on the final target task. Instead, Theorem 4.1 allows to ensure that the excess risk forms decreasing sequence across tasks, culminating in a final bound of only for the target task T. This motivates the next corollary.
Corollary 4.3. Suppose the first task is learned to excess risk E (:(W)) S E1. Set the regularization 4r,
parameter μt
x)² Then, for 2p and assume the sample size satisfies n, (1-0))2(0+)))
Pey
every task 1, we have (++)] & 61 (1)
Since 1, the bound ei (2=1 1-1 decreases with This decay allows smaller sample complexity for earlier tasks in the curriculum and, correspondingly. the use of larger regularization parameters Me. Larger be yields strongly convex objectives with larger strong convexity parameters and thereby improving the computational efficiency of learning.
4.2 Learning Lipschitz Convex Losses with SGD
We show that, instead of using biased RERM, one can apply stochastic gradient descent (SGD) with a carefully chosen learning rate to achieve the same excess risk bound as in Theorem 4.1. The SGD procedure for task / is described in Algorithm 3.
Algorithm SGD for task
Input: Wo = Wt-1, S₁ .z,...... J. To > O.
for A 1, .... n1 do
Wi = W 1/c V. V
end for
n--1
return: W.
Σ Wx.
For simplicity, we analyze the case of two consecutive tasks, 1 and t, as in Section 4.1. Theorem 4.4. Suppose task I has a pr-Lipschitz convex loss function and satisfies the (rt, a) con- dition with task t Choosing the learning rate π) payas
r. the excess risk of SGD satisfies
(w)) 5 TePt
+ oF [cx- (w.-1))
/ne

---

The bound above matches the result in Theorem 4.1, and thus all subsequent corollaries carry over this setting. Crucially, the use of SGD offers computational advantages: it is an efficient single- pass algorithm and updates the model using only one example at a time. This makes it particularly appealing in large-scale or streaming settings, while still benefiting from the curriculum structure.
4.3 A Tighter Bound via Leveraging the Local Lipschitz Constant
To obtain a sharper excess risk bound, we refine our analysis to leverage local Lipschitz constant around the minimizers. Specifically, define local Lipschitz constant Pr over the set of predictors with excess risk at most &t. The intuition is that since the final hypothesis We is expected to achieve small excess risk, may suffice to control the gradient magnitude only in this restricted region-leading to potentially smaller constant Pe < Ps. Formally,
(l, w)
Pt 2 sup sup (w)SE,
Ow
Theorem 4.5. Choosing μr appropriately, the excess risk of curriculum learning satisfies
2r:
Gr pi) a EIV
1+a
B (w:)
Pe
E E(EE-I(W(--i]
We note that Theorem 4.5 recovers Theorem 4.1 as a special case by setting Pr = Pt. However, a meaningful improvement bound R3 2r. + ( Moreover, the bound depends on both & and pr. Since /ma
be obtained when n, is large and Pt < Pt- In such cases, the upper
P: (E,) can be interpreted a non-decreasing funetion of & (by definition in (4)), Gr. -11 This offers an minimize the overall upper bound by balancing the two terms: Pt and (I-a)Er/ma additional degree of flexibility in tightening the excess risk bound.
4.4 Learning Smooth and Nonnegative Convex Losses with Biased RERM
In this section, we assume that the loss functions satisfy smoothness, rather than Lipschitz continuity. Specifically, we assume that for all z, the loss function &, (z; w) of task t is convex, nonnegative, and 1 and t satisfy the (rr, a) condition for constants > 0 and (0, 1). Let L; inf LD, (w). As in earlier sections, employ biased RERM to learn each task and focus our analysis on two consecutive tasks.
Hi-smooth with respect to w E R Moreover, tasks
Theorem 4.6. Setting the regularization parameter max (2+6a) He 1 (I-a)ma
32H,
}, we have
7t
32L; Har?
9H₂r 1 1 (1 (1-a)m a)n
(ex(W))) S
+
E (
14
The proof closely mirrors the argument used in Theorem 4.1, relying on the same excess risk de- composition from equation (3). The second and third terms in the decomposition are bounded using the same techniques before. For the first term-the generalization gap-we apply a stability- -baed argument for smooth, nonnegative losses. Specifically, from standard results on uniform stability for
smooth objectives, obtain Es, L.D, (w:) S [ H, Es,, F.s, (Ws) long pen H+-
Thcorem 4.6 provides an optimistic rate for smooth convex losses. In the realizable case where L = 0, obtain fast rate of ((1/nz). Note that for this result to hold, the loss function must be well-defined over the entire domain w E " Similar to Theorem 4. the benefit the curriculum becomes evident when each is small, enabling significant gains in sample efficiency. Even in the absence of a curriculum, this analysis yields an optimistic bound by replacing with a larger constant. Thus, incorporating curriculum learning never worsens the sample complexity (up the parameters r, and a), and often leads to notable improvements.
While our analysis thus far has focused on multi-task curricula, the framework naturally extends to the single-task setting. Suppose we are given single learning task and aim to construct an effective curriculum within its dataset. One strategy is to begin training on a subset of "easy" examples-those
7

---

8rigi 2 (In (2) + In Braps + 1)). then with for which the loss is small-and then gradually incorporate the full training distribution. This aligns with the original motivation behind curriculum learning [Bengio al., 2009], where the learner is first exposed to simpler examples and then to increasingly complex ones.
From Theorem 4.6, the excess risk bound depends the regularization radius r, transferabilitty parameter a, smoothness He, and the optimal population loss L; We therefore aim to identify subset of training examples that satisfies two goals: (1) the resulting subtask is similar to the original task in the sense that the pair satisfies a (r, ae) condition with small r and a, and (2) the subtask has a smaller optimal risk Li, thereby reducing the sample complexity required learn it.
Practically, this involves selecting a 'good' subset of the training fata-i.e., a collection of examples with low loss values under initial model-to define auxiliary task. The learner can then solve this easier task first and use the resulting solution as a bias to efficiently solve the full task. This strategy mirrors the continuation principle embedded in curriculum learning: leveraging simple concepts as stepping stones to learn more complex ones. This idea is confirmed by Saglietti et al. [2022] and Abbe al. [2023]. They considered specific settings and selected sparse data and low noise data as the 'good' subset.
5 Curriculum Learning without Convexity
Deep learning has become the cornerstone of recent advances in artificial intelligence and ma- chine learning, powering state-of-the-ar performance across domains such as vision, language, and robotics. At the heart of deep learning is the training of deep neural networks-an inherently noncon- vex optimization problem. In this section, we investigate the benefits of curriculum learning in this nonconvex setting, focusing on tasks whose loss functions are nonconvex but Lipschitz continuous.
We assume a curriculum composed of T tasks, where each task t has a pr-Lipschitz, nonconvex loss function. As before,
assume each pair of consecutive tasks satisfies the (rt, a) condition for some rt > 0, a E (0, 1). Unlike the convex case, where we use biased RERM, we propose an ERM-based strategy for nonconvex problems. For each task f, select solution by minimizing empirical loss over a ball of radius Y2 centered at W,-1- This is formalized in Algorithm 4.
Algorithm 4 ERM-based Curriculum Learning
Input: Wu. Si...., Sr, r,....,
...,.., Pr >
Wo Wp.
for 1 = 1, 2,,, do
W. argmin Ls, (w).
w:|lw- we- Srrre
end for return: WT-
When Ls, (w) is convex, the projection-based ERM in Algorithm is equivalent to biased RERM with quadratic regularization as in Algorithm 1. However, in the nonconvex case, Algorithm enables a broader exploration of the parameter space. Although this procedure may not be compu- tationally efficient, in practice it can be approximated using methods such SGD. We also note that the radius rt is used primarily for theoretical analysis; in practice, it can be treated as a tunable parameter. For example, early stopping can serve proxy for tuning rt, by controlling how long we train on easier data subsets. Solving constrained ERM exactly is not practical in large-scale deep learning. However, the purpose of our non-convex analysis is provide generalization guarantees for implicit approximations to this problem, such as those computed via SGD and backpropaga- tion. From this perspective, theoretical analysis of constrained ERM remains meaningful. Next, we present key result for this setting.
Lemma 5.1. Let 8 (0, 1) and E O. If n. > probability at least 1 - over the randomness of S,
[wss(w) Lw) T,, + Lo, (we Se.
sup
w: | 1
8

---

the effectiveness This lemma establishes uniform concentration over { w) {(z; w lwwpl//lwwwwr -we-ille S 5mz}-
the loss class of shifted loss functions rather than {l(z; w) ||w w We-1lla S STe). This avoids dependence on potentially large loss values and instead leverages the Lipschitz condition: [é(z; w) f(z W & prta, which is small when rg is small.
We also remark that we can give tighter bound and remove the log term in (frapt + 1) via chaining. This can also be applied Theorem 5.2 and Corollary 5.3 below. We have an in expectation bound
3 + 9m
1T.s (w) LD, (w) - L.s, (Wc-1) + LDD (w--))) S 2rePey
sup
w: W
Sre
f4
The high probability bound can be derived from this using McDiarmid's Inequality.
Theorem 5.2. For any e > 0. if ne 2 S2ge (Im (3) + in (Smes + 1)) then with probability least 1 over the randomness of St, we have E (W.) S 2E aε (w.-)).
To prove Theorem 5.2, decompose the excess risk bit differently from Equation (3): Ex (.:) LTD (w:) inf T.D,(W) (w)
[w, - (we) LDD (w)-)) Ls. (wr-1) + [Es, (Wi, (w')
+ [Lss, (w') - LLD(WW/ - Lss ()) + LD, (8i--)) + [wD, -inf LD, (w)
where w' satisfies ||W' wo--wey W.-1ll2 < rt and (wW) S aεt- ( The fourth term is bounded by QE1-1 (W,-1) by the (r), condition. The second term is nonpositive as W. is the ERM solution. The first and the third terms are each bounded by using Lemma 1. completing the proof.
As in the convex case, smaller values of rt lead lower sample complexity requirements. We conclude with a
bound for the entire curriculum:
Corollary 5.3. Assume E (w1) S E. mf n. 2
32r2e²
(In (2F) + m In
[6 (T-a)c + +1)) for all
(1-a)"
E .,...,3 T, then Algorithm 4 ensures that with probability at least we have that er (Wr) S c.
6 Experiments
We conduct a simple empirical study using both synthetic and real dataset to support our theory. First, we investigate whether curriculum learning can enhance large-margin classifiers on separable data by first training on easy examples and then fine-tuning on harder ones. Specifically, we construct a binary classification task using mixtures of two-centered Gaussians in 12000 The "easy" distribution D2 has margin = 3 and low variance a = 0.5, while the hard distribution D2 varies over y E (0.1, 2.03 and {0.5, 1.0, 1.5, 2.0}. We generate IK training samples from D1, D:2-
Linear classifiers are trained using hinge loss and gradient descent (2K epochs, learning rate from 0.001, ... 1.0). The baseline trains only D2, while our curriculum method (Algorithm 2) first trains on D, and then fine-tunes on DD with & regularization A/[w2- will², where W1 is the solution from the first stage. is selected from (10-5. 10-1, 10-3, 10- 10-10-11000 10-1, 1,,10 using validation data.
Each experiment is repeated 10 times, and we report mean test accuracy and standard deviation in Figure 2. Curriculum learning consistently outperforms the baseline, demonstrating that starting with an easier task aids learning on harder ones. The performance gap widens as the target task becomes more difficult-i.e.. with smaller margins and higher of the curriculum approach under challenging conditions.
Next, we apply our theory and methods to adversarially robust learning. In adversarial robustness, an adversary perturbs an input x within perturbation set B(x), and the standard loss fx((x, y): w) replaced by the robust loss: (xx y); w) := supxęB(x) (x y); w). This replacement pre- serves convexity and Lipschitz continuity (see Appendix B.5), allowing us to extend the results of Sections 4.1.3.3 to the robustness setting. In Algorithm 3, the subgradient V grob (w Zz) is computed using adversarial training techniques.
However, smoothness does not generally earry over: while the standard loss may be smooth, the robust loss is known to be non-smooth [Xing et al., 2021]. Thus, Theorem 4.6 cannot be directly

---

Margin-0.1
Margin-0.5
Margin- 110
Margin-2.0
60
100
Baseline
Curriculum Leamiin
Accuracy
58
Accuracy
70
Accuracy
Accuracy
90
56-
80
60-
54
60
70
0.5
1.0
1.5
1.5
2.0
0.5
1.0
1.5
Standard Devietion
Standard Deviation
Standard Devistion
Standard Devietion
Figure 2: Test accuracy as a function of standard deviation for different margin "
applied. Nevertheless, we show (Appendix B.5) that if the standard loss is nonnegative and H,- smooth, then Theorem 4.6 still holds for the robust loss. This insight allows curriculum learning results to carry over to adversarial settings simply by substituting standard loss with robust loss. In practice, good bias/initialization for robust training can come from non-robust model, model trained with weaker attacks, or a related task.
We evaluate curriculum adversarial training with & regularization on MNIST dataset. Adversarial examples are generated using 10-step PGD with step size a/5 under an &o perturbation budget a E {0.1, 0.2, 0.3, 0.4]. For curriculum training, we define task & with attack strength at/T,, for / E [7] and 7' E [1, 2, 3}. No regularization is used for 1. From 2 2, we incorporate & regularization of the form Al[w;, w.-1l where w,-1 is the previous model and À E {10-5, 10- 10-1,1003 1,00,,10-))
We use CNN with two convolutional layers followed by max max- pooolpoolin and two fully connected layers with ReLU activations. The conv layers use [input, output, kernel] = [1. 10, 5] and [10. 20, 5]; the fully connected layers have dimensions [320, 100] and [100, 10]. Models are trained with cross-entropy loss using Adam for 100 epochs, batch size 128, and learning rate chosen from (10-4, 10-3 10-2 10 10-1). Early stopping is used based on robust validation accuracy (measured with PGD attack of size a) to select both the model and hyperparameters.
We report both standard and robust accuracy under PGD attack of size a in Table 1, averaged over three runs with standard deviation. We note that curriculum adversarial training maintains performance for small a and provides notable improvements for larger a values-particularly when 2 0.3. This supports the hypothesis that initializing from easier tasks (weaker attacks) enhances robustness against stronger adversaries.
For additional experimental details and extended results, please see the supplementary material.
T
3
nat
pgd acc
nat
pgd acc
nat acc
pgd
0.1
90.08
96.07=0..02
99.27+00.07
95.65
99.36+0.03
95.74+10.14
0.2
98.80-10.03
94.73+0.22
98.86-10.15
94.60+1..3
94.38+0..2 98.6710.05
0.3
98.2710.46
1.27
98.7710.15
94.74:1.112
98.23+0.115
93.61
0.4
11.35
11.35::0.00
98.3910.229
95.54
98.5240.14
95.63+0.12
Table 1: Standard (nat acc) / robust (pgd acc) accuracy under Ezo PGD attack of size a (MNIST).
7
Conclusion
In this work, we provide theoretical guarantees for both convex and nonconvex learning problems under multi-task curriculum learning framework that leverages implicit bias from prior tasks. Cen- tral to our analysis the proposed (r, a:) condition, which characterizes 'good' curriculum by quantifying task similarity and enabling reduced sample complexity. While the (r,a) condition offers a principled way to evaluate curriculum quality, it may be difficult to verify in practice. A promising direction for future work is to investigate when this condition holds for specific problem families and how it can guide the design effective, data-driven curricula.
Acknowledgments
This research was supported, in part, by the NSF CAREER award IIS 194421.
10

---

References
Emmanuel Abbe, Elisabetta Cornacchia, and Aryo Lotfi. Provable advantage of curriculum learning parity targets with mixed inputs. Advances in Neural Information Processing Systems, 36: 24291-24321, 2023.
Eugene I. Allgower and Kurt Georg. Numerical continuation methods: an introduction, volume 13.
Springer Science & Business Media, 2012.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Yoshua Bengio, Jérôme Louradour, Ronan Collobent and Jason Weston. Curriculum learning. In Proceedings of the 26th anmual international conference on machine learning, pages 41-48, 2009.
Rich Caruana. Multitask learning. Machine learning, 28:41-75, 1997.
Antoine Caubrière, Natalia Tomashenko, Antoine Laurent, Emmanuel Morin, Nathalie Camelin, and Yannick Esteve. Curriculum-baat based transfer learning for an effective end-to-end spoken language understanding and domain portability. arXiv preprint (rXiv:1906.07601 2019.
Omer Cohen, Ron Meir, and Nir Weinherger. Statistical curriculum learning: An elimination algo- rithm achieving oracle risk. arXiv preprint arXiv:2402. 13366, 2024.
Hal Daumé III. Frustratingly easy domain adaptation. arXiv preprint 1rXiv:0907.1815, 2009.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around a common mean. Advances in neural information processing systems, 31, 2018.
Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-leam stochastic gradient descent with biased regularization. In International Conference Machine Learning, pages 1566-1575. PMLR, 2019.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse cur- riculum generation for reinforcement learning. In Conference on robol learning, pages 482-495. PMLR, 2017.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for im- proved quality, stability, and variation. arXiv preprint arXiv: 10196, 2017.
Wolf Kienzle and Kumar Chellapilla. Personalized handwriting recognition via biased regulariza- tion. In Proceedings of the 23rd international conference on Machine learning, pages 457-464, 2006.
M Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. Advances in neural information processing systems, 23, 2010.
Ilja Kuzborskij and Francesco Orabona. Stability and hypothesis transfer learning. In International Conference on Machine Learning, pages 942-950, PMLR, 2013.
Ilja Kuzborskij and Francesco Orabona. Fast rates by transferring from auxiliary hypotheses. Ma-
chine Learning, 106:171-195, 2017.
Haoran Li, Jingfeng Wu, and Vladimir Braverman. Fixed design analysis of regularization-brr based continual learning. In Conference on Lifelong Learning Agents, pages 513-533. PMLR, 2023.
William Lotter, Greg Sorensen, and David Cox. A multi-scale enn and curriculum learning strategy for mammogram classification. In International Workshop Deep Learning in Medical Image Analysis, pages 169-177. Springer, 2017.
Pietro Morerio, Jacopo Cavazza, Riccardo Volpi, René Vidal, and Vittorio Murino. Curriculum dropout, In Proceedings of the IEEE international conference computer vision, pages 3544- 3552, 2017.
Anastasia Pentina and Christoph Lampert. pac-hayesian bound for lifelong learning. In Interna- tional Conference on Machine Learning, pages 991-999. PMLR, 2014.

---

Anastasia Pentina, Viktoriia Sharmanska, and Christoph H Lampert. Curriculum learning of mul- tiple tasks. Proceedings of the IEEE conference on computer vision and pattern recognition. pages 5492-5500, 2015.
Luca Saglietti, Stefano Mannelli, and Andrew Saxe. An analytical theory of curriculum learning in teacher-student networks. Advances in Neural Information Processing Systems, 35:21113 13221113-2112,, 2022.
Nikolaos Sarafianos, Theodore Giannakopoulos, Christophoros Nikou, and loannis A Kakadiaris. Curriculum learning for multi-task classification of visual attributes. In Proceedings of the IEEE International Conference Computer Vision Workshops, pages 2608-2615, 2017.
Bernhard Schölkopf. Ralf Herbrich, and Alex Smola. A generalized representer theorem. In International conference on computational learning theory, pages 416-426 Springer, 2001.
Shai Shalev-Shwartz. and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Samarth Sinha, Animesh Garg, and Hugo Larochelle. Curriculum by smoothing. Advances in Neural Information Processing Systems, 53:21653-21666 2020.
Tatiana Tommasi, Francesco Orabona, and Barbara Caputo. Learning categories from few exam- ples with multi model knowledge transfer. IEEE transactions on pattern analysis and machine intelligence, 36(5):928-9)) 2013.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Daphna Weinshall and Dan Amir. Theory of curriculum learning, with convex loss functions. Jour- nal of Machine Learning Research, 21(222):1-19, 2020.
Daphna Weinshall, Gad Cohen, and Dan Amir. Curriculum learning by transfer learning: Theory and experiments with deep networks. In International conference on machine learning, pages 2238-5246. PMLR, 2018.
Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3:1 40, 2016.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training, Ad- vances neural information processing systems, 34:26523-26535, 2021.
Ziping Xu and Ambuj Tewari. On the statistical benefits of curriculum learning. In International Conference Machine Learning, pages
PMLR, 2022.
Yang Zhang, Philip David, and Boqing Gong. Curriculum domain adaptation for semantic segmen- tation of urban scenes. In Proceedings of the IEEE international conference on computer vision, pages 2020-2030, 2017.
12

---

A Missing Proofs in Section
Lemma A.I. ES [ w
e
Proof of Lemma A.I. Denote gi ()) = (z,i(z;w). The gradient of the population loss can be written
0= V V. (w1) (, = EAWD Vuli(z;w)) = BEDD 81 (1; wi).
This leads to
E S V Lss (wi)ll²
=E s DD''
V Lw (wi) VWLD, (wiDl(
(2; w1)
Fh 7ES;
=ES,>D"' ni ZES,
(2: - ELND. Bi wi)l
1
BanD |1 (2; wi) EI w2;
11
1
(BaDD, 11gi (2) will gI = pी.
n1
12
Since L.s, (w) is d-strongly convex,
WwIsslliille = WI (wi) (wIs,(W1))) 2 A//wi - will2.
Therefore,
of
E SADD." [[] will s Bs. (
22
Theorem 3.1. If the second task is convex, then setting #2 = (llw3- willat
203
we have
x
[e(2(W2))
2pa /az
(Iww will2 A
Proof of Theorem 3.1. From the theory of RERM in Shalev-Shi Sawlar-S and Ben-David [2014] Chapter
13, S₁ is fixed, the second phase RERM -éifforol stable only one data in S2 is replaced. Therefore,
20
2pp
Es, LD, (w2)) S Es, Ls, (Wz)
f22
< Esp
Ls, (wz) +
/12
W2 W1 [3]
2ph
2
P2R22
< Ess,
T.s, (w%)
+
U2
w/ w1112]
2p3
(from the definition of RERM)
2
12222
2p2
-L,, (w3)
112
l/w
W1
1
P2T22
13

---

Taking expectation w.r.t. S1 ~ D'
Es,,s,LD,WW) S LD,(W3) + 2 Es 11 - - + 2p²
2
12222
I IDD((3))
+ 12 Es, (1lw3 - will2 + || -will2)² +
20
2
M2 (triangle inequality)
< LDD (w3) +
42
||w3 will2 + X
+ 2p
(Lemma A.1)
2
122
Setting μ22 (ww wa x Vmz
we obtain
E [bD (W2) S (w*) +
202
(Iw6
will2 +
PI
A/11
Theorem 3.2. If the second task is 1-weakly convex, then setting /12 1
202
(Iwg wwj Ila
x
/12
we have E (w2)l S /ma [Iwå
will2 + > + 1 (Ilw will2 + Au/nI
Proof of Theorem 3.2. S1 is fixed, for any M2 > 1, the regularized loss f2 w) + R2 |w - w1
2 is (μ2 l)-strongly convex. From the theory of RERM in Shalev-Shwartz and Ben- David [2014]
2p uniformly stable if only one data in S₂ is replaced.
Chapter 13, the second phase RERM is Therefore,
(02-1jmg
2pp
Es, LD. (w2) s Es, (s, + (p2 1)m22
[ssp (W2) + 1/2 1| - W1 12
2pp
$ Es²
+ (#2 - 1)m²
2
< Esa
Lss (w?) +
42
| - 01112]
+ (112 1)m2
2p3
(from the definition of RERM)
2
2pp
ID, (w:) + 122
|w Wn 11 + (12 1)m22
2
Taking expectation w.r.t. S D'n1.
.s Ls, (W2) LDz (w3)
μ12 Es, ll will2 + ( - 1)m2
2p²
< LD, + #2 Es, (1lw/ -will + 1| - w(ll2)² + (u2 - 1)mz
2p2
(triangle inequality)
PI) )² + (μ12 1)mz2
2p
(w²)
||
will -wile + A
(Lemma A.
Setting #2 =l+ (11wg-wi
we obtain
w
+ x Vm2a
E LD, (We)) $ LD. (w*)
2p2
[w willa
Pi Avni
(Iwá willz
Pi A/ni
122
14

---

B Missing Details in Section 4
B.1 Missing Proofs in Section 4.1
Theorem 4.1. Suppose task t is convex and Pr-Lipschitz, and the (re, a) condition holds between yields the following excess risk bound: tasks (t - 1.).. Then, setting μr revar
2p,
2rePt Vm
ex (w.)
+ aE (e
Proof of Theorem 4.1. ,I....,,,-.. is fixed, for any He > O, the regularized loss & w) 2 [|w Wr-1l12 112 is pe-strongly convex. From the theory of RERM in Shalev-Shwartz and Ben-
David [2014] Chapter 13, the 1-th step RERM is 2Ø -uniformyyy stable if only data in is jez replaced. Therefore, Vw' R" independent with SI....,S,,
2pp
Es, (ws) S Es, Ls. (W)) +
$ Es, Ls. (w:) + Ht
| w
+ 2p²
2
H4N4
$ Es. Ls. (w") + Pt l|w - w
2p²
+
(from the definition of RERM)
74
LD. (w') + 11 || w
2p²
Since task 1 and task satisfy (re, a) condition, there exists w', s.t. l|w Wo-1ll2 S re and Er(w') S (0:-1((w-1) hold. Thus,
Es (wi) LD. (w') Ht I|' - -w--112+
2p
MeTee
inf LD, + =c((')
- *|lw"= - W.
2p
2
S inf LD. (w) + ( + peri
2pī
2
Pene
Setting H /eyme" St...., S,-1. we obtain
20
we have (s,e((W.) S 1.E-1 (w.-)
2ries vns
Taking expectation w.r.t.
2raP: +aE (0B(e--(W---))-
E (ex(
Corollary 4.2. Assume the first task is learned with excess risk EE
[E ([1((w)) S c. Set the regulariza-
2p, and suppose the sample size 2 (T-aPzz. Then, for all tasks Ł, the tion parameter to /4, /./m, excess risk bounded as (w.) S
1r2
Proof of Corollary 4.2. Theorem 4.1 gives
2r,pt
E E (w))
<
+ oF (et-1(We-11 (W--1) & al
+(1 a)e.
We can use induction to prove that (e,) <.
Corollary 4.3. Suppose the first task is learned to excess risk E [5i([W)))) (W1)) S Set the regularization
parameter as μt rec/p and assume the sample size satisfies n, (1-a)es
4m --) Then, for
every task i, we have E. (e, (w.) & 6 +
15

---

Proof of Corollary 4.3. Theorem 4.1 gives
E [w))
2reP:
+ a. ( S a. (e.-1(
- a
/ a +
61 2
Vng
We can use induction to prove that E (W.( I 61 (221) 1-1
B.2 Missing Proofs in Section 4.2
Theorem 4.4. Suppose task t has a pe-L.ipschiz convex loss function and satisfies the (rr, a) con- dition with task / - 1. Choosing the learning rate 7
n the excess risk of SGD satisfies
Payns'
[e)((W))]
< Tept
+ oF (
V
Proof of Theurrm 4.4. Let's first fix Si,..., Si-1. Since task - and task satisfy (rr, ()) condi- tion, there exists w', s.t. l!w' - w1-1ll2 S r, and (ww' S u0 (w(-1) hold. For k = 1,2, ................................ n1.
[ - w' = | w'
( 31
= W - w113 + vh / ( (W- + 2n (w' WR-1. Vuls(Wa-1izz)
- W w112 ph 2m (Le (w/ :2x) le (wx-1;7k))
(Lipschitz and convex loss)
Rewriting this inequality gives
neP ||
w/1l 113
|| w'll2
((Wx-112z)) (e(3;;za) +
21/t
Taking average over k; we get
n1
1 n2
(e(w;z)) (4) + noPE
|wr-1
w/
113 ||
w/1
& (wk-1iZN)
+
T1e
The
2
20/e
1 Re
TePi
r?
(w(3:zz))
+
T8g
21
1 nh
(w(:2))
TePs Vnn
Since zy is independent with Wk-1. taking expectation w.r.t. S. ~ D. gives
Es. [L, (w=-1)]
Bs. (Wk-
The
nh
Es, (w': + TePe
km 1
LzD, (w') + TePe
Using Jensen's Inequality,
Es, [e: (We)] = Es, [LD (w:)) - -inf LDD(W)
1 ne
Es, (Wx=(] - inf (w)
71g
w
< LDD (w') +
Tept
inf (w)
VTu
w
TiPt + 1
<
/nz
Taking expectation w.r.t. Si...., St-1, obtain
TePt
E (.r((w)) <
+ alE (o:1(W:-1))
The
16

---

B.3 Missing Proofs in Section 4.3
Theorem 4.5. Choosing 14 appropriately, the excess risk of curriculum learning satisfies
Gr (r pi) Vne Pr + (1 - a)E:/'s
2r
+ 1 a E (err-1(W.-1))
B (w:)] S
Proof of Theorem 4.5. Let Me be constant to be determined.
Po == PS LD, (we) inf LD, > E1). Recall Es, (wx inf (w). Using Markov's Inequality,
Bs (Ws)
Es, [c,(WW))
Po S
(5)
Et
Let S. = (Z1, Z....., Znet } D and S {z/,, 22,22,... ... Znd } D. be two neighboring data sets that differ in one single example. S, U S = (1/ ?i,,,,? "2. m ~ Dmrt1.
Recall Wr E argmin (Ls,, (w) + + ||w - W. 113)) W/ E argmin (Ls((w) + l| w
Since the optimization objective Ls, (w) + ne
2 ww - w is μ ptoonglygly convex, we have
Ls.(W/ Me W/ w1 ス Ls. (we) + He || W 112 + pt ll
W. 12
(6)
2
2
Similarly,
Lsg (w.) Me Wr wr 112 2 Ls: (w/) + 1 wr-1
+
Pt
1W: 10,1-,133
w.
(7)
2
Adding up equation (6) and equation (7),
prll Rell3 S (((1; lz(zi; Wi) le(z'; we) f
(8)
14e
T4e
We say S. U. is good if LD, (we) - inf LD, (w) S & and Ldd (w)) inf LD, (w) < 6. hold simultaneously. Otherwise, we say St U Sy is bad. Applying a union bound and combining with equation (5).
P Suuus (S, U St is bad) & 2po 2Es, (wo(
(9)
E If S, U S is good, by the assumption on the local Lipschitz constant, (e,(2; - (/( S Pel pell well2 holds for any z. Equation (8) implies
Le(z1; W/ - le(2); w.) PellW( - well3 <
le(z;: - Ca(2); W/
2pt |w Well2.
The
n4.
n4
Therefore, | - W. S
28, if if U.S. is good. Thus, we also know that [&< wx) (z w\)l s
peme
WellW - Well2 S pine
22L holds for any z. If St U St is bad, using the global Lipschitz constant,
[e,( w.) - (2; W/ll S pell - welle holds for any z. We similarly get | wellz V 20,,
pem
2 is true for any z. S, U S is bad. We also know that (ee(z; w.) be(z; W!) S p:llW Wella S pmn,
Now upper bound the generalization gap of RERM:
ES.DD.' (Ix) (wx))
= S,SSS (4(2) w/) (:()):::))
2ph P
2pì
S.US(-Diit (S, U.S. is good) Men.
P S..uswDDrut (S, U St is bad)
Men
2pp
2(p
p?)
+
S108/DD!111 (S, U. is bad)
ne
277
Alpi
o (eo (w.))
+
(equation (9))
Hui
m.Em
17

---

Since task t - 1 and task t satisfy (re, a) condition, there exists w', s.t. 1/w' - -Wo-1ll2 S re and <((')) I a hold. Now we upper bound the excess risk of RERM:
Es, (wx) wD LD. (w.) - inf LD. (w)
=B [LD,
Ls. (we)
+ B.SWD
[Ls. (w:) inf LD, (w)
<BS (w1) Ls. (wx)
+ E ES
(w.) + Me || - -we-1 -inf LD. (w)
2
<BS
(LD(())) - Ls. (m:)
+ ES (u's(w)) + 1/ lIw' - -w,-1l2 - inf LDD (w)
2
w
-Bs
(LD, (we) - Ls. (w:)
+ LD. (w) + 14 ||w -
-w ww inf (w)
2
2p? 4(p; 1ss, (Eo (We))
Q (w/-1) uo72
Pe
2
Taking expectation w.r.t.
we obtain
2ph 10
1 (w.) + aB 1 (wc-1)]
Meri
E [[er(W.)] -
+
2
4(p² P.) MeEele
If
< 1, we can solve the above inequality, and get
202 + aF [st-1 (W (w)-1)) + mie
B [(e)(w))]
1 -(p(-P)) M15,ng
Denote
4pt V mir?
+ (1-0)e7ng
32( 22)
4(p
and select ue max 4(1+a)(p? -p1)
(I-a)reme æ). We get
Come
2
+ aE [5t-1 10 (w/-1)) + mo2
E (We)(W)) S
pen,
-
1
Meferee
2
peti
3
aE [
(We-1)l
2
4pp -2?)
4 -
Medatte
peEeme
20
+
2 14
oF (0 1
1(p--p))
I-a
I+x
DEOR
20
4(1 (pf
+
(1-0)Emm4
1+a a
E
[ (o-1(W:-1)
41pp-1i
2
4(1+a)
2
2
(1-a)EERe
1 a
E
(6-1((((1))
1(p--17
2
x
Eette
32(p? - -?
(6- 2 -P:) pT)
1
2
E (
V neTT
(1 (
(1 (1-a) -0)
2
Pr +
(v
1 1-a a + 6- 2a
32
r/l0t - p
1 a
+
E
\Tu
1- a
ELT4
2
WA++BS VĀ+ vB)
2riPt
12 ( - p?)
1+a a
E (E)-1((._1))
TT=
a
Er
2
2r:
Grelpt p?)
1
pt
+
E
(1- - Tup
18

---

B.4
Missing Proofs in Section 4,4
Theorem 4.6. Setting the regularization parameter max (2+6a) 1
}, we have
(1-a)m i
H
9H
+
E (E S
+ 13 (
R1
(1 a)m,
2
Proof of Theorem 4.6. Let St = {21, Z2..... 2n ~ Di and S (2,,22..... Zn.] Di be two
neighboring data sets that differ in one single example. S, U S = {7/ 71, 72 ... ?n Dittt. Recall We E argmin (Ls, (w) + 2 w1-11B): W/ E argmin [Lsy(w] (w) + 2 1| --
Since the optimization objective Ls, (w) _ w w,-1 11 is μ strongly convex, we have
Ls,(w() + | 1/ 1111112 2 Ls. (we) (we) + | || w.
mr lw:
w. 1
2
2
Similarly,
Est (w.) Me W -w--1l13 1s:(m) + Me 1| - W.
Pe
Iw,
w. 12.
2
2
2
Adding up these two inequalities,
Mel | wel12 S le(zi: (() & (21: (.):
le(z'; we) fe(zi:
(10)
14
n4.
By the smoothness assumption and using the self-bounded property,
Hg 2
(/( Le(z): w.) < (v.le W/ - w.) +
W/ well3
Ht 1 Well3
< Vwlllzz we 122l - Wrll2 +
2
S (2H 11) well2 +
|W well2.
(11)
2
Similarly,
l (((2: Wc) W(( S 22H, Wella + He W we113
(12)
From the choice of μ4l we know that nu > He. Plugging these two inequalities into equation (10), we get
| - Well2 S V2II
(Vile)s + ve((4:
P4n H,
Adding up equation (11) and equation (12), and combining with the inequality above, we get
(1,(21;; w/) - We)) + (Ee(zhi we) - (((2);W))
2H,
2H?
(el(zzswe + / /2((2):w))
14774 H1 + (umT - -H.)²
4H1,
4H2
-c(k; w))
1:7 H. (HuTI H
Now we upper bound the generalization gap of RERM:
ES - Ls. -LDs(M))_Lss(..)))
4,/211 E B..us/DDiet [(G(2)] (((z):We) + -<(1)::))))((1: w())]
19

---

2H:
2H2
E Bssust [4e(2] wi) + (()))))
11T44 Ht (umT - H³)²
4Hl
411
ES,.DT [Tss(
1404 - Ht (NeMe H
Since task - 1 and task t satisfy (re, a)) condition, there exists w', s.t. 1|w Wo-1ll2 S re and E<(W") I 100-1(W1-)) hold. Now upper bound the excess risk of RERM:
Es, (wx))
DD LTD, (W:) - L
4Ht
4H2
1 Hi He
+
E Es (wr) Li
(mmm: - H1)²
1
4H,
+
AH?
E ES [ss(W))
Me 1| w 11
He
(pem - H₂)²
4HL
4H2
DS [Tos, (w') + 14 l|w - i 1
1
He
(pim) - H,,²
2
4Ht
+
AH?
(LD,(W') + Ht
- w6-111² L
Hene
Hi
(pin - H1)²
2
4H,
AH2
[1 + a0 1 (w + (² 1i
+
HeT
He
(pmme - H2)
4H,
4H?
0E1-1 (w
POn Hi
(MiT - H1)²
4H,
4H?
(Li
H4 ! - LT
+ 1 +
+
(13)
MeT H1,
(HeMe - H.)²
2
Since mm 2
(2+6a)
(1-a)m
4H,
AH2
4(1 - a)
4(1 a)²
1+
+
as
1+
uene He
(um - -H,)²
1+7a
(1 7a)
1+ 8 + 24a (1 a)
(1+7a)2
1 - a
1 +
1
2a
2
4H,
4H2
8H,
8H,
1+ pen - He (HiTs H,)²
+
14
16H,
Mett
Plugging these two inequalities into equation (13), we get
Es, (wr)
1+a Ee-
1w +
1+
16H.
(L;
+
Mr ,2
L;
2
pe
2
1+a
8H
He
Ex
1 (W,-1)+
+
+ 16L;
2
2
20

---

1 1
8
(2+6al) 6a)H,
1
32H,L2
H
E (W]1)
1671
n4e
2
(1 at
rt
11
32
74
1+a
E(-1 (w-1 (9-5a) 50) Hire
32H,14
+ +TV
2
(1 a)
n4
32L; Heri
9H11
1 a
+
8t-1 (We-)).
The
a)n
2
Taking expectation w.r.t. Si...., S we obtain
32L; Har?
9H.r
1 a
B (E
+
[
Rt
(1 a)m,
2
B.5 Missing Proofs for Adversarial Robustness
Proposition B.1. If the standard loss (x((x, y); w) is convex, then the robust loss ero ((x, y); w) ==
sup (e((, y); w) is convex.
xEB(x)
Proof of Proposition B.I. Vw1, W2, [0, 1].
(xx v); Aw1 + (1 AJw2) = sup
(x((8, u): Aw1 + (1 A)w2)
kEB(s)
S sup
1)) we)l
ke((x)
sup
[Alx((8) w1)] sup
[(1 - A)ee((K, w2)]
REB(x)
xEB(x)
= Aeeoo y):
((x,)):; wi) + +1 (xx))::))
Proposition B.2. If the standard loss le((x, ((xx,)); (rob((x, w): ;= sup (x((,, (): is p p-piscchit xcB(x)
y): w) is pr-Lipschitz, then the robust loss
Proof of Proposition B.I. VW1, W2.
2.0h ((x, w1) f ((x, y): w2)
sup
4e((,, v): w1) sup (1 y): w2) SEB(x)
REB(x)
< sup
[& w): - W2)]
ReB(x)
< sup
(p: [|w w2ll2)
xEB(x)
Pr -ellwi - W2ll2.
Now we prove Theorem 4.6 in the adversarial robustness setting. In this setting, all tasks are learning the robust loss; the empirical risk, expected risk and excess risk are defined using the robust loss. We assume that Vz, the standard loss fz(z; w) is convex, Hm-shooth and nonnegative. In addition. task 1 and task t satisfy (re, a:) condition for constants ri 0 and (0. 1). Denote L inf T.go/ (w). We use biased RERM described in Algorithm to learn these tasks. We focus two consecutive tasks: task t and task f as before.
21

---

Theorem B.3. Setting the regularization parameter 14 = max (2+6a)HH
1 /32H,2
}. we have
(1-a)m+ /
32L; Her?
9Hr
1
E [eer(W S
V
+
(
n4
(1 11-01 -a)m
2
Proof of Theorem B.3. Let Sc = {z1, Z2, ................................ Zne ~ D and S = [z/, 22, ................................ ,,n, } ~ D. be two
neighboring data sets that differ in one single example. St U S = (z,, Z2 ................................ 2ns ~ D. Recall We E argmin (w) + 2 |Iw fllw- w W/ E argmin
(Irg (w) + 2 l|w We-
w
w
Since the optimization objective (w) + t ||w w 12 is strongyy convex, we have
Lga (w/) + Me | W/ we-111 2 D5d (w.) + Mt w| w 112 1 - we
2
2
Similarly,
Trob (1)) Mt We We- 2 T.s (w,) + Me 11 W. 112 + Me 1| - we
Trabb
2
Adding up these two incqualities,
Me W We egod (21; w/ - -grob (71; W.) n2
ezob(z We) pro0((1 W/)
(14)
ne
By the smoothness assumption and using the self-bounded property for the standard loss, efoh (21; w.) - Cxo W.) = sup kEB(x:)
((((x,11:(() sup & (x((,, w))
SEB(x))
s sup xE(((1)
[4(((, w/ - C, (1((
(Vulr((,,w)) W.), R - -w:) + H 1l - wel12 2
sup
xeB()))
Hr 1 - weel
sup xEB(x1)
[V yn); Wlall -well2 +
well2
He l Well2
sup sEB(ai)
22,41 v1): we W -Wele +
2
- 211 (215 w.)l - + 41 || w..12
H,
(15)
Similarly,
- - (2:: w/) S V 22 (2; W/
we1l2
+ He Iw w.
(16)
From the choice of be we know that pan > He Plugging these two inequalities into equation (14), we get
V2H, (Vero)es:
| Welle S
(e): + e W')
M:774 H₁
Adding up equation (15) and equation (16), and combining with the inequality above, we get
(21; erob (21; w.)) (c:00 We) erou W:))
2H,
2H?
(V ego We) + v (roo w/)
Hellie Hi + (uiM - -H,)²
4Hl.
A11
(ET0) -r:00(z's (21:
H4m Hr + (Heme - -H,)²
22

---

Now we upper bound the generalization gap of RERM:
ES (L3. - - (wr))
E Bssus [[e]a] (z1; W/)
(21::e)) (2) We) ff w())]
2
211
2112
E BsuuswDDicta [2)o0(21; We) + ero0 (z): W!]]
H4 H4
(HmM H²)²
AH,
AF?
E Wg [2.) (w.))
H4 Hi (HOT H₂)²
Since task - 1 and task t satisfy (re: a)) condition, there exists w', s.t. l/w' - wo-2l12 S re and (w') I 0E; 1 (W+-1) hold. Now we upper bound the excess risk of RERM:
Es, (w:))
Ds I.oo((e)) L
AH,
AH?
+ 14 He
D3000 (We) (w:)
Li
(piThs H₂)² ?
+ 14 He
4H,
AH?
ES 1 (we) + 1e
Wi - - -i
(WiTHe - -1,)²
2
4H,
AH?
ES [ [rob(w") + He
l|w W w. 113
L
He
(NmM -H,)²
2
4H.
AH2
(w') + Mt l| - -w.-113) - 11
(w')
14TH
He
(pim+ -H,)²
2
4H,
AT??
LI + OE 1 + Me r?) - Li
+
2
Hin
Hi
(piT
He)²
4H,
AH2
dEI-1(W(-1)
14 Hy,
(piM H,,²
1+
411e
4H1 (peme H.)²
(Li
-177 -1) LG-
Hr 2)
(17)
1uT He
Since me
(2+6a)H: He (I-o)n;
4H,
4H?
1+ 4(1 - a)
4(1 - a)
1 +
+
a
pite 11,
(umme - -H,)²
1 7a
(1 + 7a) 7
8 + 24a
+
(1 + 7a)
(1 a)
a
1 a
1 + a
+
a
20x
2
4H,
AH?
+ 8H,
8H,
1 pen Hi (WiT - H₂)²
+
44
16H,
+
Plugging these two inequalities into equation (17), we get Es, |Ec (w:)]
23

---

1ta
1+ 16H,
E(-1 (w +
Li +
iT
Men
2
1+a
8Hir
He
Et- (W/-1)+
F4
+ 16
2
2
14
1+
8Hr2
ri
(2 + 6ox H (1 a)
1
32H,L2
H
81-1 (wI-1)+
+
167
2
n
2
r1
32 H
71
1+a
E(-1 (w(-1)+ + (9- HIT
32H,Li
+TV
2
(1 a)1
11t
32L;
Har
9Hr?
1 a
+
El-1 (W(1))
74
(1 - a)n
2
Taking expectation w.r.t. SI, ......, Se-1. 1, obtain
32L; Her
9Hrt
+ 1 a E 12 (w.-)])
E (E,)(
V
n4
(1 a)n,
C Missing Proofs in Section 5
Lemma 5.1. Let 8 (0, 1) and e O. If n4 2 briei (In (2) + mm (Sree + +1)), then with
probability at least 1 - over the randomness of St,
[ss(w) - LD,(w) (w:-1) + Lo. (wa-))le
sup
wc |W- W ST
Proof of Lemma 5.1. Define s(z:w) lo(z; w) le(2, w1-1), then
1 n
- Lw. (w)(w))DD(ww) Ls, (w.-1) LD, (w, LD,(W,,,)),
((i:w) ELND ((:
From the Lipschitz assumption, if ||w wr-1l12 S rs, [[;; w) S ripe is bounded. From Vershynin [2018] Chapter let (V1.-.., Vx} be कp. -nt of {w || w,-lllz rr). such that K s
Brips + +1 m VVz, from Hoeffding's Inequality, we get
Ps. 1 f(z.vz)) - EEwD. >
c
S 2
2exp
(-
(-sr
2
2
8r?pp
Taking union bound,
1 The The
?
Pss.
Σ
f(zavv) EawD.((ziVs) S 5.155
2 2K exp
8r?pt T4
SraPe +11
2
2 2
exp
Sri n4
If the event
f(zniz)) - En:D, S holds for all Vj. I claim
[[ss(w) (w) - (.,, + Lo, (we-1)] Se.
sup
w: 12
24

---

vw that satisfies l|w Wr-1ll2 I rt, from the definition of the net, there exists vy such that l|w Vyll2 S पp. Using triangle inequality.
Ls. (w) LD. (w) Ls, (we-1) LD, (W:-1)]
Ls, (V,) - L.D, (v,) - Is (80,-1 + (W: [v;) Es, (w)l + (VD)(vz)) - (w)
v(z;V)) Dn Vz)
+ +VEss(v,) [s)(w] + (LD(())) - (D)(w]
2 + 2pe p/ - v3l12 5 2 4p:
+ 2pt =c.
Therefore.
Ps..
sup
(w) - LD.(w) - -ss, (Wr-1) + LD, (wo- Se
w:llw
We-
>Ps
[ [(zx; - BewD, 25.
nt
t=1
21 - 8.
Theorem 5.2. For any <> 0, nf 2 srigt (In (2) + m In Srapt 1)) least 1 over the randomness of St, have E (We) 2c Q (W(-1).
then with probability
Proof of Theorem 5.2. From Lemma 5.1, with probability at least
5,
L.s. (w) (w) [s,(W.:)) + LD. (wr-))) SC.
sup w: [w- Sr
Since task - 1 and task satisfy (re, condition, there exists w', s.t. l|w - We-ille S rt and (ww) I d (1, hold. Now upper bound the excess risk:
Ee (We) = (w:) inf LD. (w)
(w.) Ls. (we) + (Ls.(w)) (w:) - inf LD.(w)
(w.) Ls. (wr) LDD,WWW (Wi-1) + Ls, (Wc-1))
+ LDD (W.-1) 1)- Ls, (wr-1) + (Iss, (w:) -inf
inf LoD (w)
Set (w,(w) - T.s, (W.-)) + (T.s(w'') (w') - inf LDD (w)
iinf = [Ls. (w) - LD, (w)) - Ls. (w.-1) + LD, (w--)) + (LD, (w)) - inf LD, (w))
< 26 + 06 (w--1).
Corollary 5.3. Assume Ei (w)) < c. nf, >
32ri
In (T
m In
16rePs [T-aje
+ +1)) for all
[I-a)=
t t.,, then Algorithm 4 ensures that with probability at least 8, we have that S (WT) S
Proof of Corollary 5.3. Replacing e with 1 in Theorem 5.2, we know that e, (w.) S (1 a)e
aEt-1(W(-1) holds with probability at least 8 Taking a union bound, with probability at least 1 8, (w:) S (1 ade + ( holds for every We can use induction to prove that E, (w,) S
7-
D
25

---

D Additional Experimental Results
D.1 Regression
We consider three regression tasks Ti, T2, T3. where T3 is the target task. The data of the tasks are
vectors in I& with d = 1000. Set μ4i (1,0,...,0 ,0) 122 (1.5,0, O.... D)__ M3 = (2, 0. .... O)T. The underlying distributions of the three tasks are D, = ((m, , D2 = (12,, D3 N(p3; 10la). For any example and weight vector w, the squared loss is defined |[w zI12. Since we are using a constant vector w to predict every input, the three formulated tasks are equivalent to three mean estimation problems. We solve the three tasks using regularized ERM. Set Wg = O. For each task, we incorporate an l regularization term into the empirical risks, A/[w,- 1. where w,-1 represents the optimal weights learned from the previous task
f 7)
For
the mean estimation of (H,,oPla) the regularization parameter is set as X without using validation, where is the sample size of the current task. Here À is set to minimize test loss in expectation. We fix the sample size 1i1 - n2 1.5K for the first two tasks. We choose different sample size of the target task ny and demonstrate the statistical benefit of riculum. We compare six different training methods: learning T3 directly using ERM; learning T3 directly using RERM; learning Ti T3 sequentially; learning T2, T3 sequentially; learning T2, Ti, T3 sequentially: and learning Ti, T2. T3 sequentially. Table 2 and Figure 3 report the averaged test loss || ///l2 for all training methods over 5M repetitive runs. Our results show that learning easier task before solving the target task T3 leads to a smaller expected risk compared with solving T3 di- rectly. The curriculum that learns Ti, 22, T3 sequentially achieves the smallest expected risk among all methods.
11 directly
do²
12
(EREM
T3(RERM)
Ti+T3
Tu+T3
+T
T++T++Tss
IK
10.000
2.857
1,803
1.677
1.329
1.326
2K
5.000
2.222
1.528
1,436
1.173
1.171
3K
3.333
1.818
1.325
1.255
1.050
1.048
4K
2.500
1.538
1.170
1.115
0.950
0.948
5K
2.000
1.333
1.047
1.003
0.868
0,866
6K
1.667
1.176
0.948
0.912
0.798
0.797
7K
1.429
1.053
0.866
0.836
0.739
0.738
8K
1.250
0.952
0.797
0.771
0.688
0.688
9K
1.111
0.870
0.738
0.716
0.644
0.643
10K
1.000
0.800
0.687
0.668
0.605
0.604
11K
0.909
0.741
0.643
0.626
0.571
0.570
12K
0.833
0.690
0.604
0.589
0.540
0.539
13K
0.769
0.645
0.570
0.557
0.512
0.512
14K
0.714
0.606
0.539
0.527
0.487
0,487
15K
0.667
0.571
0.512
0.501
0.465
0.464
16K
0.625
0.541
0.487
0.477
0.444
0,444
17K
0.588
0.513
0.464
0.455
0.425
0.425
18K
0.556
0.488
0.444
0.435
0.408
0.407
19K
0.526
0.465
0.425
0.417
0.392
0.391
20K
0.500
0.444
0.407
0.401
0.377
0.377
Table 2: Test loss of different training methods under different sample size 71g-
D.2 More Details Synthetic Datasets Experiment
Here we provide more contents regarding the synthetic dataset experiment as described in Section 6. We aim to investigate whether leveraging curriculum learning can improve the performance large- margin classifiers when dealing with separable data. The motivation is rooted in the intuition that we can distinguish between data points that are easy versus hard to classify, we may benefit from curriculum learning strategy. Specifically, by first training easy-to-classify points to learn an initial model and then fine-tuning using harder examples, we hypothesize that the model can better generalize to challenging tasks.
26

---

task 3
2.5
task 1 + task
task 2 task
test loss
2.0
task + task task 3
1.5
1.0
0.5
5000
10000
15000
20000
sample size of task 3
Figure 3: Test loss function of the sample size na-
To test this hypothesis, we consider a binary classification task where data is drawn from a mixture of two distributions, Dj and 2D. Each distribution is defined as two-centered Gaussian in IR with dimension = 100. For each distribution D,, i E {1, 2}. the two centers are located at the origin and at ly, 0, ................................ 0J²,, with the spread determined by the Gaussian noise standard deviation o. We generate IK training samples from each distribution. Distribution D1, with 7 3 and o = 0.5, considered "easy" due to its large margin and low variance. In contrast, D2 is constructed "hard" distribution, with parameter y E [0.1, 0.5, 1.0, 2.0) and a E [0.5, 1.0, 1.5, 2.0]. Additionally, generate 400 validation samples and 400 test samples from D:2.
train the linear model using both logisitic loss and hinge loss, and optimize it with gradient descent for 2K epochs, using learning rate selected from (0.001, 0.01, 0.05, 0.1, 0.5, 1.0). No regularization is applied when training the easy distribution D1. When fine-tuning on training dataset from 22, we incorporate an E regularization term into the loss functions, A/ W2 will? where w, is the optimal model weights from previous training and the regularization parameter À selected from the set (10-5, 10 10 10 10-1 10). Experiments are repeated 10 times, and report the mean test accuracy along with standard deviation in Figure Our results show that curriculum learning consistently outperforms the baseline, indicating that starting with easier task facilitates learning on the more challenging target task. Furthermore, the harder the target task (characterized by smaller margin and larger standard deviation), the more significant the improvement achieved through curriculum learning.
Margin=0.1
Margin=0.5
Margin=1.0
Margin=2.0
100
Raseline
Curriculum Learning
Accuracy
58
Accuracy
Accuracy
80
Accuracy
90
56
60
60
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
Standard Deviation
Standard Deviation
Standard Deviation
Standard Deviation
Logistic Loss
Margin=0.1
Margin=0.5
Margin=1.0
Margin=2.0
Baseline
Curriculum Leamning
Accuracy
58
Accuracy
70
Accuracy
Accuracy
90
56
70
60
54
70
0.5
1.0
1.5
2.0
0.5
1.0
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
Standard Daviation
Standard Deviation
Standard Deviation
(b) Hinge Loss
Figure 4: Test accuracy as a function of standard deviation for different margin ?
27

---

D.3 More Details on Adversarial Training Experiments
We provide additional details and results on evaluating curriculum adversarial training with l2 regularization on MNIST dataset. We consider adversarial examples generated using both &o" norm perturbation (with budgets a E {0.1, 0.3, 0.4)) and f--norm perturbation (with budgets E (1.0, 2.0, 3.0, 4.0)). All adversarial examples are generated using 10-step PGD with a step size of a/5. We hold out 20% of the training data as a validation set and use 10-step PGD adversarial examples, crafted with the same perturbation budget a, for hyper-parameter tuning and model se- lection. No regularization is used for = From t 2 2, we incorporate lg regularization of the form Al[w, w where W,-1 is the previous model and À {10-5, 10-4 10 1002). We use previous model Wt-1 as initialization for t. The setting has been described in Section 6. We report both standard and robust test accuracy under PGD attacks of size over three repetitive runs in Table 3 for &g -attacks and Table 4 for & fz-attacks. We observe that curriculum adversarial training maintains performance for small a and provides improvements for larger (a 2 0.3 for lo -ttaccks
and a 2 3.0 for & attacks).
2
3
nat acc
pgd acc
nat acc
pgd acc
nat acc
pgd acc
0.1
99.18+0.00
96.07
99.27-+0.07
95.65++0.18
99.36++0.03
95.74++0.14
0.2
9..0
94.73++..22
98.86110.15
94.60=10.3
94.38::..33 98.67+0.05
0.3
98.77=0.15 92.77=1.20 98.27=0.46
94.7410.12
98.2310.15
93.61
0.4
11.35=:0.00
11.35::0.00
98.39-10.29
95.5411041
98.5210.14
95.63
Table 3: Standard (nat acc) / robust (pgd acc) accuracy under Ezo PGD attack of size (MNIST).
2
3
nat acc
pgd acc
nat acc
pgd acc
nat acc
pgd ace
1.0
99.32.10.05
94.53:0.116
99.26-10.05
94.4410..03
99.3710.044
93.9
2.0
0..3
76.23+10.39
98.5110.10
76.04:10.30
98,40=0.08
76.56:10.27
3.0
94.3
52.1110.60
94.8710.30
52.53:10.35
94.06+1.29
52.65
4.0
89.12#2.79
31.47=0.41
87.62+1.53
31.93:+0.94
84.55+1.35
32.00
Table 4: Standard (nat ace) robust (pgd acc) accuracy under Eg PGD attack of size a (MNIST).
D.4 Noisy MNIST
We construct a noisy MNIST dataset by adding Gaussian noise to each example, sampled from the distribution (1, 07,8.4)))) Our goal is find model that perform well on the noisy MNIST test data. To perform curriculum learning, we manually categorize the digits into four groups: [1,4,7], [3,8,]] [6,9], [2,5] and create four tasks as follows: 1). train on digits [1.4.7]: 2). train on digits [1,4,7]U[3,8.00] 3). train on digits [1447]J[[3..00J[[6..91 4). train on all digits. The reason for selecting these categories is based on the visual similarity in the shape of the digits.
We consider three different architectures: a linear model, a two-layer ReLU network with a hidden width of 100, and convolutional neural network (CNN). The CNN consists of two convolutional layers followed by max-pooling and two fully connected layers with ReLU activations. The first and second convolutional layers have [input channel, output channel, kernel size] = [1, 10. 5] and [10, 20, 5], respectively. The first and second fully connected layers have dimensions [320, 100] and [100, 10], respectively. For each task, we train the model using cross-entropy loss and opti- mize it with stochastic gradient descent (SGD) for 200 epochs, using a batch size of 128 and a learning rate selected from {10 4 10100- 10 1001), }). with weight decay of 10-4, No regular- ization is applied during the first task. From the second task onward, we incorporate an & regu- larization term into the loss functions, A//w, w for task t 2 where w,-1 represents the optimal model weights from the previous task t - 1. The regularization parameter X is selected from {10-5 10-4, 10 10-2 10-1,13. We randomly set 20% of the training data aside as the validation set and use the validation accuracy to select the optimal hyperparameters for each task and to determine the best-perforning model checkpoint. The optimal model weights from task / 1 are used both to initialize model training and as the reference point for the l, regularizer in task Table 5 reports the averaged results over three runs, including standard deviations. Our results demonstrate that curriculum learning consistently outperforms the bascline, particularly when the
28

---

noise level a is higher. This indicates that curriculum learning is especially beneficial in more chal- lenging settings where the data is noisier.
Model
0
Baseline
Curriculum
0.0
92.0420.05
92.3410.10
Linear
1.0
68.93-0.63
70.69
2.0
42.18=00.65
44.63:0.29
0.0
97.87 14
97.85:10.05
Two-layer ReLU Network
1.0
80.55+0.24
81.26::0.13
2.0
45.79=10.91
46.43:10.26
0.0
99.00=00.66
99.04:1.044
Convoluted Network
1.0
85.08++0.11 0..29
2.0
0.66
48.33++0.15
Table 5: Accuracy the o--oisy test data under different a and different model architectures.
29

---

NeurIPS Paper Checklist
A. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We listed our contributions in the introduction and proved our claims from Section 3 to Section in the main paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
B. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discussed the limitations and future directions in the Conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
C. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer: [Yes]
Justification: The paper provide the full set assumptions and a complete and correct proof for each theoretical result. Please Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should comple-
mented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
D. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We include the details of our datasets and our algorithms when describing our experiments. We repeated each experiments for multiple times and compared the results in detail.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
31

---

E. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We attach the code of our experiments in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.co co/
sublic/guides Sodidee//CooeeSubisssiinne
for more details.
While we encourage the release of code and data, understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.co stapss.cc/ubblie wttpc//ppwcc.guudeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
F. Experimental setting/details
Does the paper specifyy all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: All training details and the choice of hyperparameters included in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
G. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We run each experiment for multiple runs and make comparisons between the standard training and training with the curriculum.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
H. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments are conducted on single V100 GPU, Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't 't make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /
Answer: [Yes]
Justification: This is a theoretical paper. and to the best of our knowledge, respects every of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction)
J. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This is theoretical paper. We focused on solving problem, but the problem domain itself has a potential for positive socictal impacts, where our techniques can facilitate learning the problem efficiently.
Guidelines:
33

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
K. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical paper. The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
L. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
This is a theoretical paper. The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
34

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswith thcode www.coo///aoooo datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
M. New assets
Question: Are assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
This is theoretical paper. The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
N. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: This is theoretical paper. The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
O. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
35

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
P. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https:/ http://eeeeeecceeeeeeeeeeeeeeeee htt.rppp....//oteeeercc///////// for what should or should not be described.
36


Reviews:
[{"review_id": "4VVI6nqUhR", "reviewer": "Reviewer_wHsc", "summary": "This paper aims to provide a solid theoretical foundation for Curriculum Learning (CL), an effective strategy in machine learning whose success is currently largely empirical and lacks sufficient theoretical understanding. To address this gap, the authors propose a theoretical framework based on biased Regularized Empirical Risk Minimization (RERM). The paper's core contribution is the introduction of a novel (r, a) condition to mathematically characterize a \"good\" curriculum.\nWithin this framework, the authors analyze the performance of CL across different learning tasks:\nFor convex learning tasks, they derive excess risk bounds and demonstrate that satisfying the (r, α) condition can effectively reduce sample complexity. This analysis is also extended to the widely used Stochastic Gradient Descent (SGD) algorithm.\nThe theoretical analysis is extended to non-convex tasks, providing generalization guarantees for the application of CL in modern scenarios such as deep learning.\nFinally, the paper empirically validates its theoretical findings through experiments on synthetic and MNIST datasets.", "questions": "How robust is the model if early tasks are misleading or corrupted?\nWill incorrect prior tasks lead to worse generalization, and how can this be mitigated?\nWhy are the datasets limited to synthetic and MNIST?", "limitations": "(r, α)-condition is difficult to verify or enforce in practice. While theoretically elegant, it's unclear when or how this condition holds on real datasets.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper successfully identifies the disconnect between the practical application of CL and its theoretical underpinnings. Providing a theoretical basis for this widely used heuristic is a valuable and compelling research direction.\n2. The proposed (r, α) condition is a central highlight of the work. It offers a novel, intuitive, and formal tool for defining what constitutes a \"good\" curriculum, providing a powerful instrument for analyzing CL's effectiveness.\n3. The theoretical work in this paper is solid. The authors provide rigorous excess risk bounds for convex tasks and extend the analysis to the practical SGD optimizer, strengthening the connection between theory and practice.\n\nWeaknesses:\n1. While the theory is elegant, it provides limited insight into how to design a good curriculum in practice, especially for real datasets. There's no principled method to determine task order or difficulty.\n2. Though the paper attempts to extend to nonconvex settings, the treatment is still mainly theoretical, and the methods like ERM over radius-constrained balls are not practical for large-scale deep learning.\n3. Experiments are mainly conducted on synthetic data and MNIST, with relatively simple settings. The generalizability to complex domains (e.g., NLP, vision benchmarks) is not demonstrated.", "was_revised": true, "final_justification": "I have read the rebuttal by the authors and my concerns are addressed by it. I will increase my score.", "rebuttal": "**(W1) Insight into Designing a Good Curriculum:**\n\nWe respectfully disagree with the claim that our theory provides limited insight into curriculum design. While our primary goal is to formalize when curriculum learning helps, our framework also suggests how to design effective curricula. Specifically, under mild regularity assumptions (e.g., smooth loss, bounded hypothesis class), our results imply the following two practical principles (among others):\n\n-  Build curricula by expanding the hypothesis class incrementally, e.g., using norm-based constraints as in structural risk minimization.\n- Order training examples by increasing difficulty, such that the empirical distribution D_{t+1} is only a small shift from D_t, helping ensure the (r,α)-condition holds.\n\nThese ideas are discussed (lines 269–284) and implemented in our adversarial robustness experiment, where the curriculum reflects increasing attack strength.\n\nMoreover, our theory provides tools for proving that a given curriculum will be effective, not just a post hoc justification, but a predictive framework for algorithmic design. We also note that curriculum learning differs from multitask learning: it does not assume a fixed pool of tasks to be permuted, but rather supports sequential design of tasks informed by learner progress, a perspective our framework explicitly supports. \n\n\n\n**(W2) Practicality of ERM over Radius-Constrained Balls in Non-Convex Settings:**\n\nWe acknowledge the reviewer’s concern and agree that solving constrained ERM exactly is not practical in large-scale deep learning. However, the purpose of our non-convex analysis is to provide generalization guarantees for implicit approximations to this problem, such as those computed via SGD and backpropagation. While SGD does not solve ERM exactly, it is widely believed to approximate regularized ERM under certain stability or implicit bias conditions. Thus, theoretical analysis of constrained ERM remains meaningful, as it captures the idealized behavior that practical algorithms aim to approach. This is especially important since most generalization guarantees in deep learning are also based on such surrogate analyses. We will clarify this connection in the revision.\n\n**(W3) Scope and Simplicity of Experiments:**\n\nWe appreciate the reviewer’s concern and agree that broader empirical validation is valuable. However, we emphasize that this is primarily a theoretical paper aimed at developing foundational understanding of curriculum learning, a widely used but poorly understood paradigm. Our analysis provides novel generalization bounds under the (r, α) condition, which we believe is a significant step forward in a largely under-theorized area. \n\n\nWhile the experimental section is limited in scope, it includes a nontrivial application to adversarial robustness, a realistic and practically relevant setting for both NLP/vision, demonstrating how our theory can guide curriculum design. The additional experiments on synthetic and MNIST data serve as proof-of-concept to validate key ideas in controlled settings. In particular, in Appendix D, we present an experiment on Noisy MNIST where the label space expands over time. We group digits into progressively larger categories to construct a curriculum with an increasing target label set, offering a simple empirical validation of our framework in such a setting. We view these results as complementary to the theory, not as the central contribution.  \n\n**(Q1) Robustness to Misleading or Corrupted Early Tasks:**\n\nWe appreciate this thoughtful question. It highlights an important distinction between curriculum learning and other learning paradigms. Unlike multitask learning or adversarial training, curriculum learning assumes a learner-driven or teacher-designed sequence of tasks. As such, the notion of robustness to arbitrary or corrupted early tasks is somewhat misplaced: if the curriculum is poorly constructed, one should not expect curriculum learning to help.\n\n\nIndeed, our framework makes this precise: if early tasks do not satisfy the (r, α) condition, then the curriculum may not improve generalization and may even hinder it. Our theory not only formalizes when a curriculum works, but also helps explain when and why it fails. In this way, it offers diagnostic insight into the success or failure of curriculum learning strategies. \n\n\nThe goal of this paper is to move toward a formal definition of what makes a curriculum “good.” The (r, α)  condition provides this structure, and supports intuitive strategies such as gradually expanding the hypothesis class or presenting examples in order of increasing difficulty. These are natural analogs to pedagogical design (e.g., learning algebra before calculus), and our theory helps justify them rigorously.\n\n\n**(Q2) On Mitigating the Impact of Misleading Early Tasks:**\n\n\n\nRegarding mitigation, the key is not to fix the learner, but to design better curricula, just as we would not attempt to \"mitigate\" the failure of teaching algebra to kindergartners, but would instead reorder the curriculum to build foundational skills first. Curriculum learning depends on inductive bias; our framework offers a formal tool for verifying when such bias is appropriate.\n\nIn short:\n- **Why are early tasks misleading?** Possibly because the curriculum was poorly constructed.\n- **How can this be mitigated?** By applying structure, such as the $(r, \\alpha)$-condition, to ensure tasks are ordered so that learning is cumulative.\n- **Is this a flaw?** No—this is an inherent aspect of any learning system that leverages prior knowledge. There is no free lunch in machine learning: learning always requires assumptions. In curriculum learning, the key assumption is that the early tasks help prepare the learner for the final task. Our framework does not claim to discover an optimal curriculum automatically; rather, it aims to formalize what makes a curriculum effective, and to provide a theoretical foundation for analyzing or comparing curricula.\n\n\n\nWe will clarify this perspective more directly in the revised version.\n\n\n\n**(Q3) Dataset Choices:**\n\nSince this is primarily a theory paper, we used synthetic data and MNIST to validate core ideas in controlled settings. These domains allow us to construct curricula that clearly satisfy or violate the (r, α) condition, making them ideal for illustrating our theoretical claims. We agree that extending to more complex datasets is a valuable direction for future work. Also, see response above labeled (W3).\n\n\n\n\n**(L1) Practical Verifiability of the (r, α) condition:**\n\nWe agree that the (r, α) condition may be difficult to verify directly in practice. However, its value lies not in being easily checkable, but in serving as a guiding principle for curriculum design. Much like how educational curricula are designed to build progressively, ensuring that foundational concepts are mastered before introducing more advanced material, the (r, α) condition captures the idea that transitioning from task t to task t+1 should not require a complete re-learning of the problem. In this sense, it offers a formal lens through which to reason about inductive biases and curriculum structure, and can inform the development of heuristic or adaptive curriculum strategies in real-world settings. We will clarify this role in the final version."}, {"review_id": "GHCzrH1Yjf", "reviewer": "Reviewer_CsMF", "summary": "In the present paper, the authors develop a biased-regularised ERM view of curriculum learning. Given a sequence of $T$ supervised tasks, each task $t$ is learned by minimising the empirical loss plus an $L_2$ penalty that keeps the parameters close to the solution of task $t-1$. The analysis is based on the definition of an $(r, \\alpha)$ “good curriculum” condition, used for proving excess-risk bounds for convex, Lipschitz, and smooth losses. The results are then extended, under some assumptions, to SGD and a non-convex setting. The empirical evaluation is based on experiments on synthetic data and MNIST (including adversarial training).", "questions": "On the tightness of the bounds: Could the authors overlay the analytical excess-risk curves on the experimental plots, so readers can see how loose/tight they are?\n\nOn choosing $(r, \\alpha)$ in practice: Can the authors comment on how one would estimate or tune $r$ when the optimal risks or parameter distances are unknown?\n\nOn the relation to earlier work: Can the authors discuss the connections to Sarao Mannelli et al. (2020) and clarify the novelty of their practical findings?\n\nOn the connection to continual-learning: The drift-per-task setting resembles CL more than classic curriculum. How does this method fare in settings where catastrophic forgetting can take place?", "limitations": "The discussion of the limitations is very limited (a comment in the Conclusions).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- The work is technically solid: assumptions are carefully stated, proofs are complete, and empirical evaluation seems sufficient (especially considering the long appendix). \n- The idea of introducing the $(r, \\alpha)$ compatibility metric seems to allow a simple formalization of task similarity. \n- Overall, the paper is clearly written. \n\n**Weaknesses**\n- Some relevant references to theoretical works on curriculum learning are missing (e.g., the recent line by Abbe et al). In particular, a similar curriculum protocol with elastic penalties was analysed analytically and experimentally in \"An Analytic Theory of Curriculum Learning\" (Sarao Mannelli et al., 2020), which the paper does not cite.\n- The derived generalisation bounds depend on (potentially unknown) global Lipschitz, smoothness, and local-geometry constants. This makes it hard to judge their tightness or to understand how they can be used in practice (the bound curves are not plotted alongside the learning curves in the empirical experiments). \n- It is a bit unclear whether the analyzed setting is truly connected to curriculum learning or rather represents a generic continual/transfer learning setting.\n- The $(r, \\alpha)$ condition and the regularisation schedule presume task knowledge that a learner rarely has access to.", "was_revised": true, "final_justification": "Overall, assuming the related literature is incorporated and that the authors will clarify the distinction between theoretical assumptions and practical implementation, potentially highlighting the gaps, I am inclined to raise my score to a 4:borderline accept.", "rebuttal": "**(W1) Missing References (Sarao Mannelli et al., Abbe et al.):**\n\n We thank the reviewer for highlighting these works. We will cite and discuss both in the revised version.\n\nThe paper by Abbe et al. (Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs) studies a highly structured learning task and proves that a two-phase curriculum improves generalization in that specific setting. While their setup is quite different from ours, the underlying motivation aligns with our goal of providing rigorous conditions under which curriculum learning is beneficial.\n\nSimilarly, An Analytical Theory of Curriculum Learning in Teacher-Student Networks (Sarao Mannelli et al., 2020) analyzes a teacher-student model with inputs drawn from Gaussian distributions and labels generated by a perceptron. They focus on a specific curriculum involving low-variance inputs and introduce elastic penalties between tasks, conceptually related to our regularization framework. However, their analysis relies on tools from statistical physics and is restricted to specialized synthetic settings. In contrast, our work provides generalization guarantees for convex and non-convex losses in a more general supervised learning framework.\n\nWe appreciate the connections and will incorporate a comparative discussion in the related work section.\n\n\n**(W2) Tightness of Bounds and Practical Use of Constants:**\n\n We would like to clarify that the global Lipschitz and smoothness constants used in our excess risk bounds are not unknown once the hypothesis class and input space are specified. These constants are standard in learning theory (see, e.g., Understanding Machine Learning by Shalev-Shwartz and Ben-David) and are determined by the choice of loss function and input domain. \n\nMoreover, these constants are not needed to implement our algorithm. In practice, the regularization parameters can be tuned using validation, as we do in our experiments. \n\nOur theoretical contribution shows that under the (r, α) condition, curriculum learning leads to improved generalization. The key driver of this improvement is the parameter r: when r is small, our excess risk bounds are small, regardless of whether the constants are numerically tight. The purpose of our analysis is to provide structural insight into when curriculum learning helps, not necessarily to optimize constant factors in the bound. We will clarify this point in the revision. \n\n**(W3) Connection to Curriculum vs. Continual and Transfer Learning:**\n\n\nWe appreciate the reviewer’s observation and agree that at a surface level, our regularization-based formulation might resemble continual or transfer learning. However, the underlying goals are fundamentally different:\n\n- In continual learning, the aim is to learn a sequence of tasks without forgetting earlier ones. In contrast, curriculum learning is focused on improving generalization on a single target task through a structured progression of tasks.\n- In transfer learning, prior tasks provide general knowledge for initializing or regularizing learning on a target task, but there is no explicit task sequencing. Curriculum learning, by contrast, uses a deliberate ordering of tasks to facilitate smoother optimization and improved generalization.\n\nOur work models curriculum learning as a form of biased RERM, where earlier tasks shape the inductive bias to improve performance on later tasks, particularly the final one. While some structural similarities exist (e.g., between our regularization and knowledge retention), our framework is tailored to curriculum learning and does not seek to address catastrophic forgetting or full-task retention. We will make this distinction clearer in the revised version.\n\n**(W4) Assumptions on Task Knowledge for Regularization Schedule:**\n\n We appreciate the reviewer’s concern. The task knowledge referenced in our theoretical analysis, such as optimal risks or parameter distances between tasks, is used solely to derive generalization bounds and to formalize the conditions under which a curriculum is effective. These assumptions are not required in practice to implement the algorithm.\n\nIn the biased RERM algorithm, the regularization weights can be tuned using standard techniques such as validation, which is precisely what we do in our experiments. The goal of our analysis is to provide a framework that explains why and when curriculum learning helps, not to prescribe a fixed regularization schedule dependent on quantities that are inaccessible during training.\n\nWe also note that assuming Lipschitz continuity and smoothness is standard in the learning theory literature (see, e.g., Understanding Machine Learning by Shalev-Shwartz and Ben-David), and is necessary to make any meaningful theoretical claim about generalization.\n\nWe will clarify this distinction between theoretical assumptions and practical implementation in the revision.\n\n**(Q1) On the Tightness of Excess Risk Bounds:**\n\nAs is common in learning theory, our upper bounds are distribution-free worst-case guarantees, and thus often significantly looser than empirical performance on specific datasets. This does not diminish their value: they provide a structural explanation of when and why a curriculum helps. We will clarify this distinction and, where feasible (e.g., in synthetic settings), consider illustrating the qualitative alignment between bound behavior and learning curves in the revised version.\n\n**(Q2) On Choosing or Estimating (r, α)  in Practice:**\n\nWe appreciate this question and would like to clarify that (r, α) are not parameters to be estimated or tuned in practice. Rather, it is a theoretical condition that characterizes a good curriculum, similar in spirit to margin assumptions or noise conditions in classical learning theory. We assume the (r, α) condition in order to derive generalization bounds and to understand why certain curricula are effective.\n\nIn practice, the only parameter that needs tuning in our biased RERM algorithm is the regularization weight. This can be selected using standard validation techniques, which is exactly what we do in our experiments. We will emphasize this more clearly in the revised version to avoid confusion between theoretical assumptions and tunable hyperparameters.\n\n**(Q3) On Relation to Sarao Mannelli et al. (2020):**\n\n We thank the reviewer for raising this connection. We will cite “An Analytical Theory of Curriculum Learning in Teacher-Student Networks” (Sarao Mannelli et al., 2020) and clarify the distinctions.\n\nThat work analyzes a highly specific teacher-student setup where labels are generated by a one-layer perceptron and inputs are drawn from Gaussian distributions. The curriculum is constructed using low-variance data to form an auxiliary task, and elastic penalties are introduced primarily to preserve long-term memory, a setting more aligned with continual learning.\n\nIn contrast, our paper develops a general theoretical framework for curriculum learning based on biased regularized ERM. We make minimal assumptions (e.g., Lipschitz/smooth losses) and provide generalization guarantees via the (r,α) condition. While their use of elastic penalties bears some similarity to our regularization approach, their analysis relies on statistical physics techniques and is primarily empirical.\n\nFurthermore, our notion of auxiliary task design (e.g., Sections 4.3–4.4) is more general: we define task difficulty via local Lipschitz properties or population risk, and we discuss practical approaches for identifying good subsets (e.g., using pretrained networks). We believe this broader formulation and its theoretical grounding represent a novel contribution.\n\n**(Q4) On the Connection to Continual Learning and Catastrophic Forgetting:**\n\nWe appreciate the question and would like to clarify this distinction. In curriculum learning, as modeled in our paper, the objective is to learn a single target task more effectively by leveraging a sequence of progressively structured tasks. At each stage, the learner focuses on the current task, potentially using prior solutions to guide learning, but not with the goal of retaining performance on earlier tasks. As such, catastrophic forgetting can occur, and is not viewed as a failure mode in this context.\n\nIn contrast, continual learning explicitly aims to preserve knowledge across tasks and avoid forgetting. Our formulation does not attempt to maintain performance on previous tasks, and instead embraces the idea that the tasks may drift significantly, with the final target task being quite different from the initial ones. The prior knowledge is used only as an inductive bias to facilitate learning the current task, not as a memory mechanism.\n\nWe will clarify this distinction more explicitly in the revised version."}, {"review_id": "BzFsYAgA8s", "reviewer": "Reviewer_DGsF", "summary": "The paper introduces (for the first time?) a theoretical analysis of curriculum learning. It studies a scenario where the learner goes through a sequence of tasks where the parameters found at the end of training for each task is a good initialization for the next task (and not far from a good solution for the next task). This is a scenario that is reminiscent of continuation methods in optimization, but the paper provides a number of theoretical bounds on generalization at each step, given the expected error at the previous step. Several other theoretical assumptions are leveraged to obtain a diversity of results, e.g., if the losses are convex in the parameters, if it is Lipschitz, and if it is smooth. Some of the results apply in the SGD non-convex case typical of neural networks and the paper describes numerical simulations which support the theoretical results.", "questions": "Is there absolutely no previous work on a learning-theoretical analysis of curriculum learning?\n\nHow are the proof techniques related to previous work in learning theory?", "limitations": "In the conclusion, briefly.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "ular pre-training followed by successive fine-tuning stages can be seen as instances of curriculum learning that plausibly fit some of the scenarios studied in the paper.\n\nAs far as I know, this is the first learning-theoretical analysis of curriculum learning, but I would have liked to see confirmation or not in the paper, along with a review of relevant related work, if only in terms of the theoretical tools being used, as well as non-theoretical work on curriculum learning.", "was_revised": true, "final_justification": "The authors have satisfactorily answered my questions, so I maintain my rating.", "rebuttal": "**(Q1) Is There Absolutely No Previous Learning-Theoretic Work on Curriculum Learning?**\n\nWe appreciate the reviewer raising this important question. While our work is, to the best of our knowledge, the first to offer a general learning-theoretic framework for curriculum learning with generalization guarantees across both convex and non-convex regimes, we do cite and build upon several earlier theoretical efforts:\n- **Pentina et al. (2015)** (Curriculum Learning of Multiple Tasks) consider a similar sequential task setup and propose a biased regularizer in an SVM setting. Their analysis focuses on minimizing the average population risk over all tasks, whereas our objective is to minimize the population risk on a final target task. Our framework is also more general in that it applies to arbitrary convex losses and allows for multiple tasks with general data distributions.\n\n\n- **Weinshall et al.** develop curriculum strategies based on difficulty scores and show improved convergence rates. Their analysis is rooted in optimization and focuses on acceleration rather than generalization. Our focus is on sample complexity and excess risk.\n\n\n- **Xu and Tewari (2022)** and **Cohen et al. (2022)** analyze simplified two-task curricula in mean estimation problems to highlight statistical benefits. Our results extend this line of work to general hypothesis classes and arbitrary sequences of tasks.\n\n\n- **Abbe et al. (2023)** and **Sarao Mannelli et al. (2020)** both study very specific structured tasks (parity functions, teacher-student models with Gaussian inputs). While they propose concrete two-phase curricula and analyze special cases (often using statistical physics), our framework allows for arbitrary-length curricula with minimal assumptions on the data distribution, hypothesis class, or task structure.\n\n\nIn summary, while some elements of our approach,  such as the use of biased regularization, have appeared in specific contexts, our contribution is the first to unify and generalize these ideas into a broadly applicable learning-theoretic foundation for curriculum learning. We will incorporate this discussion more explicitly in the related work section.\n\n\n**(Q2) Connection to Proof Techniques in Learning Theory:**\n\nMost of our proof techniques are grounded in standard tools from statistical learning theory. In particular, we use algorithmic stability to analyze biased RERM (especially in the SGD setting), and uniform convergence arguments for ERM-based excess risk bounds. \n\nThe key novelty lies in how we integrate these classical techniques with the (r,α)-condition, a structural assumption that captures task-to-task compatibility in a curriculum. This allows us to propagate guarantees across tasks and formally characterize when curriculum learning improves generalization. We will clarify these connections and include the relevant citations in the revision."}, {"review_id": "a3dXGMh0EI", "reviewer": "Reviewer_kjZ2", "summary": "The paper presents several key contributions to the theoretical understanding of curriculum learning—the strategy of training a model on progressively harder tasks. The authors introduce a formal framework for analyzing multi-task curriculum learning. This framework is centered on Biased Regularized Empirical Risk Minimization (RERM) by using an easy task to provide better inductive biases  to regularize the learning process for the next, more difficult task.\n\nSome theoretical contirbutions of this paper:\nThe (r, α) Condition which connects task similarity and empirical risk. This condition mathematically formalizes the similarity between consecutive tasks. It asserts that if a model performs well on one task, a slightly perturbed version of that model will also perform reasonably well on the subsequent task, so as long as the r is small enough.\n\nThe analysis provides rigorous proofs and performance guarantees for different types of optimization problems.\nFor Convex Problems:\nThe paper provides proofs and excess risk bounds showing that a good curriculum (one with a small r) can significantly reduce the sample complexity required for subsequent tasks.\nThese guarantees are proven for both the RERM framework and the more practical Stochastic Gradient Descent (SGD) method.\nFor Non-Convex Problems:\nThe analysis is extended to non-convex settings, which are highly relevant for modern deep learning.\nThe authors propose an ERM-based algorithm and establish generalization guarantees, demonstrating that a well-designed curriculum improves learning efficiency even in these complex scenarios.", "questions": "1. [Eq 2] how do you define this norm when there are arch changes, tasks need not have errors at the same scale\n2. In your work you mentioned about the scale of loss being different in different subsequent tasks, does that not affect the $\\alpha$ parameter? how if at all any rescaling operation done? if not then despite being a optimal curriclum, the scale difference might indicate a high α\n3. Can you provide some experimental evidence for curricula where the task does not necessarily share the same arch. or target label set, basically increase the complexity of the underlying set of tasks in  the curriculum to show if it is possible to empirically validate the theoretical findings to a more realistic setting.", "limitations": "This work specifies the generalization on the subsequent task given a particular curriculum. The harder and perhaps more important question is what is the optimal curriculum. given the inability to define the (r, α) criterion for a general setting, the applicability of this method seems limited.\n\nHow can we identify the (r, α) criteria for a given curriculum in a general setting?\n\nIt's unclear how these results and the underlying theoretical dynamics would scale to much larger and more complex real-world scenarios. For instance, training massive models like large language models (LLMs) or state-of-the-art vision models on datasets like ImageNet involves far more complex dynamics. While the principles might hold, the practical benefits could be different or harder to achieve, and the cost of exploring different curricula would be prohibitively high.\n\n\nThe process of ordering tasks remains largely a heuristic, domain-specific art that relies on human intuition. For example, in their experiments, the authors rely on common-sense curricula: increasing the difficulty of a classification task by reducing the margin, or increasing the strength of an adversarial attack. The framework doesn't offer a general algorithm for discovering this optimal ordering automatically.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths of this paper:\n\n1. This paper, to my knowledge is one of the first to present the notion of (r,α) condition of task similarity to empirical risk. \n2. Authors provides guarantees for both convex and non-convex optimization problems (thm 4.1, 4.2). Since most modern deep learning involves highly non-convex landscapes, this makes the paper's conclusions far more relevant and impactful for practitioners working with neural networks.\n3. The authors extend their analysis from the more abstract Biased RERM to Stochastic Gradient Descent (SGD), which is the optimizer used in the vast majority of real-world machine learning. \n\nWeakness:\nThis work, to my understanding hinges on the (r, α) condition. which in this paper works only when the task sequence have the same domain and target space and the arch. is same. For a more general setting this might not be possible\n\nThe experimentation is a bit weak, for a general setting of sequential how can we identify the rho and alpha, While the experiments are well-designed to support the theoretical claims, they are conducted on relatively small-scale and controlled environments (synthetic data and MNIST).", "was_revised": true, "final_justification": "The authors have successfully adressed the majority of my concerns as mentioned in the rebuttal.", "rebuttal": "**(W1) Applicability Beyond Shared Architecture/Label Space:**\n\n We would like to clarify that while Eq(2) is initially stated assuming a shared parameter space across tasks, our framework can accommodate architectural changes.\n\n\nAs discussed (lines 121–131), we allow for the existence of a mapping $\\phi_t : \\mathcal{H}_{t-1} \\to \\mathcal{H}_t$ that transfers the solution from task $t-1$ into the parameter space of task $t$. This captures cases where the architecture changes across tasks, for instance, embedding a smaller network into a larger one by initializing new weights carefully (e.g., identity padding, layer-wise expansion). In such settings, we replace $w$ with $\\phi_t(w)$ in Equation (2), allowing our $(r, \\alpha)$-condition to remain meaningful even when the architecture or hypothesis class evolves.\nWe assume $\\phi_t$ is the identity for simplicity in our core theorems, but the underlying idea is that a good solution from task $t-1$ provides useful prior knowledge, potentially through transfer mappings, for task $t$. We will make this interpretation clearer in the revision.\n\n\nFurthermore, in Appendix D, we present an experiment on Noisy MNIST where the label space expands over time. \n\n\n**(W2) Weak experimentation, need to know (r, α) in practice, weak experiments**:  \n\nWhile the experimental section is limited in scope, it includes a nontrivial application to adversarial robustness, a realistic and practically relevant setting for both NLP/vision, demonstrating how our theory can guide curriculum design. The additional experiments on synthetic and MNIST data serve as proof-of-concept to validate key ideas in controlled settings. We view these results as complementary to the theory, not as the central contribution.  \n\n\nAlso, (r, α) are not parameters to be identified or estimated or tuned in practice. Rather, it is a theoretical condition that characterizes a good curriculum, similar in spirit to margin assumptions or noise conditions in classical learning theory. In practice, the only parameter that needs tuning in our biased RERM algorithm is the regularization weight. This can be selected using standard validation techniques, which is exactly what we do in our experiments. We will emphasize this more clearly in the revised version to avoid confusion between theoretical assumptions and tunable hyperparameters.\n\n\n**(Q1a) On the Norm in Equation (2) Under Architecture Changes and Loss Scaling:** \n\nIn Eq(2), the norm $\\|\\|w - w'\\|\\|$ is defined over the shared or mapped parameter space across consecutive tasks. When the architecture changes, we explicitly address this in our paper (lines 121–131) by introducing a mapping $\\phi_t : \\mathcal{H}_{t-1} \\to \\mathcal{H}_t$​ that embeds the solution from task $t-1$ into the space of task $t$. In that case, the comparison in Equation (2) becomes $\\|\\|\\phi_t(w) - w_t^\\star\\|\\|$, and the norm is taken in the ambient space of $\\mathcal{H}_t$. This allows for increasing model capacity, e.g., by adding neurons or layers, while preserving the interpretation of prior solutions as inductive biases for future tasks.\n\n\nRegarding loss scaling, the magnitude of $\\alpha_t$ is indeed influenced by the relative scale of loss functions across tasks. However, as discussed in our response to point (2), the $(r, \\alpha)$-condition is invariant to affine rescaling of the loss. That is, multiplying a loss function $\\ell_t$ by a positive constant rescales $\\alpha_t$ accordingly, without changing the underlying minimizer or risk structure. We assume comparable loss scales across tasks for simplicity, but this can be adjusted in practice through normalization if needed.\n\n\nIn summary, both norm comparability (via $\\phi_t$) and loss scale (via normalization) are accounted for in our framework. We will clarify these assumptions more explicitly in the revision.\n\n**(Q1b) Scale Mismatch and Loss Normalization in the $(r, \\alpha)$-Condition:**\n\nWe assume for simplicity that the $\\alpha_t$ in Equation (2) satisfies $\\alpha_t < 1$, and that loss functions across tasks are scaled similarly. This assumption is not essential and can be relaxed by a straightforward rescaling of the losses.\n\n\nAs we explain (lines 142–147), if the loss for task $t$ differs in scale from previous tasks, this can be absorbed by appropriately scaling the loss function $\\ell_t$ and adjusting $\\alpha_t$ accordingly. For example, if the loss at task $t$ is twice that of task $t+1$ (say, due to arbitrary units in squared loss), then multiplying $\\ell_t$ by a constant would reduce $\\alpha_t$ without affecting the minimizer or theoretical guarantees. The key insight remains: a small value of $r_t$, indicating a good initialization,  is far more important than the absolute value of $\\alpha_t$, which reflects loss scaling.\n\n\nIn practice, we do not rescale losses across tasks. But for theoretical clarity, assuming a constant $\\alpha < 1$ allows us to streamline the presentation of our results without loss of generality. If needed, our theorems could be extended to carry task-dependent $\\alpha_t$ values throughout. We will clarify this in the revised version.\n\n\n**(Q2) Experiments on Complex or Heterogeneous Tasks:**\n\nWhile our primary focus is theoretical, we do include some experiments that begin to address this setting. In Appendix D, we present an experiment on Noisy MNIST where the label space expands over time. \n\n\nWe cite (lines 31–32) several prior empirical works study curriculum-style training where model capacity is increased over time. These can be interpreted as tasks with varying architectures, where parameters from the previous model are carefully mapped into a larger one, consistent with our theoretical allowance for task mappings (via $\\phi_t$).\n\n\n\n\n**(L1) On Identifying the $(r, \\alpha)$ Condition in Practice:**\n\n We agree that directly computing or verifying the $(r, \\alpha)$-condition in general settings may be difficult. However, the purpose of our framework is not to prescribe explicit values of $r$ or $\\alpha$, but rather to provide a theoretical lens that characterizes when curriculum learning is effective. Just as assumptions like margin conditions or realizability are used to structure classical learning theory, the $(r, \\alpha)$-condition helps formalize what it means for one task to serve as a good precursor to another.\n\n\nWhile we do not expect practitioners to estimate $(r, \\alpha)$ precisely, the condition informs practical design principles. Specifically:\n\n- Good curricula should transition gradually between tasks, ensuring that task $t+1$ is not too far (in risk or parameter space) from task $t$.\n\n\n- This can be achieved, for instance, by ordering training examples by increasing difficulty, or incrementally expanding the hypothesis class, strategies reflected in our adversarial robustness experiment and discussed in Section 4.4 (lines 269–284).\n\nIn short, the $(r, \\alpha)$-condition is best viewed as a guiding structural principle for designing curricula, not a parameterization to be optimized. We will clarify this role more explicitly in the revised version.\n\n**(L2) Scope and Complexity of Experimental Evaluation:**\n\nThis is primarily a theoretical paper, aimed at providing a rigorous foundation for curriculum learning, a widely used but under-theorized paradigm. We introduce a novel sufficient condition for curriculum learning and establish generalization guarantees for both convex and non-convex settings, a significant step forward in understanding curriculum structure.\n\n\nWhile our experimental validation is limited in scope, it serves to complement and illustrate the theoretical results in controlled settings:\n- Our adversarial robustness experiment demonstrates how the theory can guide curriculum design in a practically relevant deep learning scenario. This setup is applicable across both vision and NLP domains where adversarial training is widely studied.\n\n\n- In Appendix D, we present a Noisy MNIST experiment that progressively increases the label space,  offering a simple empirical example where tasks differ structurally (i.e., increasing classification complexity), yet the curriculum remains beneficial.\n\nWe acknowledge that extending our framework to more diverse curricula, including tasks with shifting data distributions, output spaces, or architectures, is important future work. \n\n**(L3) On the Role of Heuristics in Task Ordering and the Absence of an Algorithm for Optimal Curricula:**\n\nWe appreciate the reviewer’s observation and agree that designing effective task orderings often involves heuristics or domain knowledge. However, this is not a limitation unique to our work, but rather a fundamental feature of curriculum learning itself. As the reviewer notes, curricula in our experiments (e.g., increasing adversarial strength or classification difficulty) are designed using common sense. This “common sense” corresponds precisely to inductive bias or prior knowledge, which is essential in any learning setting. Our contribution is to formalize this inductive bias through the $(r, \\alpha)$-condition.\n\nThere is no free lunch in machine learning: learning always requires assumptions. In curriculum learning, the key assumption is that the early tasks help prepare the learner for the final task. Our framework does not claim to discover an optimal curriculum automatically; rather, it aims to formalize what makes a curriculum effective, and to provide a theoretical foundation for analyzing or comparing curricula.\n\nIndeed, the $(r, \\alpha)$-condition offers both predictive and diagnostic power: it not only guides curriculum design (e.g., gradual expansion of the hypothesis class or task difficulty), but also helps explain why a curriculum may fail, e.g., if early tasks do not sufficiently prepare the learner, generalization on later tasks will suffer. This is a fundamentally different perspective from multitask learning, which assumes a fixed set of tasks to be learned jointly or reordered."}]

Author rebuttal:

Meta-review: This paper received three borderline accept ratings and one strong accept rating. The reviewers found several weaknesses, which were addressed by the rebuttal comments. The paper is technically solid, providing a strong theoretical contribution that addresses an important topic, which justifies an accept decision on behalf of the AC.
Decision: Accept (poster)