Convergence and Implicit Bias of Gradient Descent on Continual Linear Classification
Authors: Hyunji Jung
Hanseul Cho
Chulhee Yun
Venue: ICLR 2025 Poster (2025)
Keywords: Continual Learning
Sequential Learning
Gradient Descent
Linear Classification
Convergence
Implicit Bias
Primary area: transfer learning, meta learning, and lifelong learning

Abstract: We study continual learning on multiple linear classification tasks by sequentially running gradient descent (GD) for a fixed budget of iterations per each given task. When all tasks are jointly linearly separable and are presented in a cyclic/random order, we show the directional convergence of the trained linear classifier to the joint (offline) max-margin solution. This is surprising because GD training on a single task is implicitly biased towards the individual max-margin solution for the task, and the direction of the joint max-margin solution can be largely different from these individual solutions. Additionally, when tasks are given in a cyclic order, we present a non-asymptotic analysis on cycle-averaged forgetting, revealing that (1) alignment between tasks is indeed closely tied to catastrophic forgetting and backward knowledge transfer and (2) the amount of forgetting vanishes to zero as the cycle repeats. Lastly, we analyze the case where the tasks are no longer jointly separable and show that the model trained in a cyclic order converges to the unique minimum of the joint loss function.

Published as a conference paper at ICLR 2025
CONVERGENCE AND IMPLICIT BIAS OF GRADIENT DESCENT ON CONTINUAL LINEAR CLASSIFICATION
Hyunji Jung"
Hanseul Cho", Chulhee Yun
Graduate School of Artificial Intelligence
Kim Jacchul Graduate School of AI KAIST
POSTECH
jeongh @postech.c.o ac..chhh................... ac.kr
(js44015, chulhee. yun @kai iitiaist.ac kr
ABSTRACT
We study continual learning multiple linear classification tasks by sequentially running gradient descent (GD) for a fixed budget of iterations per task. When all tasks are jointly linearly separable and are presented in a cyclic/random order, we show the directional convergence of the trained linear classifier to the joint (offtine) max-margin solution. This is surprising because GD training task is implicitly biased towards the individual max-margin solution for the task, and the direction of the joint max- max-margin solution can be largely different from these individual solutions. Additionally, when tasks are given in a cyclic order, we present non-asymptotic analysis on cycle-averaged forgetting, revealing that (1) alignment between tasks is indeed closely tied to catastrophic forgetting and backward knowledge transfer and (2) the amount of forgetting vanishes to zero as the cycle repeats. Lastly, we analyze the case where the tasks are no longer jointly separable and show that the model trained in a eyclic order converges to the unique minimum of the joint loss function.
single
INTRODUCTION
Continual learning (CL) aims to sequentially learn model from stream of tasks datasets, to extend its knowledge continuously. The main challenge in CL is catastrophic forgetting, meaning that their performance previous tasks degrades after learning new ones (McCloskey & Cohen, 1989; Goodfellow et al., 2013). It has led to a growing body of works focusing on heuristic methods of mitigating forgetting, including regularization-base methods (Kirkpatrick al., 2017: Aljundi et al., 2018; Li & Hoiem, 2017), replay-based methods (Chaudbry et al., 2019; Lopez-Paz & Ranzato, 2017; Shin et al., 2017), and aetimization-basee methods (Farajtabar et al., 2020; Javed & White, 2019; Mirzadeh et al., 2020).
As CL is receiving significant attention in practice, is also important to theoretically understand the mechanism of continual learning. A vast amount of the theoretical works on CL so far has focused on regression problems (Bennani et al., 2020; Doan al., 2021; Asanuma et al., 2021; Lee et al., 2021; Evron et al., 2022; Goldfarb & Hand, 2023; Li et al., 2023), whereas most of the practical application of deep learning based on classification. Thus, theoretical analysis of continual classification methods and their learning dynamics is of significant interest and importance. Indeed, few results study continual classification (Raghavan & Balaprakash, 2021; Kim et al., 2022; 2023; Shi & Wang, 2023), albeit focusing theoretical perspectives that are different from ours; we review these related works in Appendix A.
This paper is mainly motivated by a recent result studying continual linear classification collection of jointly separable datasets (Evron et al., 2023). The authors consider continual training of a linear classifier under weak regularization, where the linear classifier is trained until convergence every given task. By taking the limit of the regularization coefficient À + 0, this training procedure is shown to be equivalent (in terms of the parameter direction À - 0) a projection-based scheme called Sequential Max-Margin (SMM): every time we encounter a new binary classification task, we project the current model parameter vector to a convex set defined by the margin conditions of the given dataset. Then, under this framework of projection onto convex sets, the authors show linear convergence of the iterates of SMM to an offline solution (i.e., a classifier that solves all tasks at once) under cyclic/random ordering of the tasks. More details can be found in Appendix B.
Authorr contrihuted equally to this paper.

---

Published as a conference paper at ICLR 2025
In light of the insightful analyses by Evron et al. (2023), now highlight some aspects of their work that motivate the setup of our interest. First of all, Evron et al. (2023) consider minimizing the regularized training loss of each task until convergence; however, it is far more common to spend finite budget of iterations per task in practice (i.e., online one-pass setting, or fixed-epoch setting). Training until convergence, combined with sending the regularization coefficient À 0, also raises an issue on the claimed equivalence of weakly regularized training and the projection-basee scheme. As À + O, the solution of the training objective diverges to infinity, which does not match the fact that the iterate of the SMM travels only for finite distance at every stage. Another noteworthy characteristic of the considered SMM scheme is that it does not always converge to the offline max-margin solution, i.e., the hard-margin support vector machine solution that solves all tasks jointly, which known to be beneficial in terms of generalization (Vapnik, 2013). Lastly, in their concluding section, Evron et al. (2023) also suggest studying unregularized continual training with early stopping and highlight that the behavior may be different. These observations triggered our investigation into pradient-based algorithm for continual linear classification and its convergence and algorithmic bias.
In this work, we theoretically study continual linear classification via sequentially running gradient de- scent (GD) on the unregularized logistic loss for a fixed budget of iterations at every stage.² When all tasks are jointly separable and revealed in the cyclic order (as studied by Evron et al. (2023)), we show that sequential GD converges in the direction of the offline max- max-margin solution, unlike SMM. We high- light that this an interesting result for at least two reasons:
Task datapoints
Task datapoints
Task Only
Task Only
Joint Training
Continual (Cyclic)
It reveals clear difference between sequential GD and the projection-baie based SMM algorithm in terms of algorithmic bias.
It is well-known that GD applied to an individ- ual task has its implicit bias towards the task's own max-margin direction (Soudry et al., 2018). However, the direction of the offline max-margin solution can largely differ from the max-margin directions of individual tasks, not even lying on the subspace spanned by the individual directions (see Figure and Appendix C.I).
Figure 1: Trajectory of sequential GD on two-task toy example (Appendix C.I) in which the offline max-margin direction is not on the subspace spanned by individual task max- margin solutions. Sequential GD iterates initially oscillate but quickly start to evolve along the same direction the offline max- margin direction.
Therefore, the convergence of sequential GD to the offline max-margin solution highlights that repeated continual training eventually drives the model to learn all tasks well, overcoming the biases towards individual tasks. In addition to the implicit bias result, we also characterize the convergence rate in terms of total loss and the vanishing rate of the per-cycle forgetting. Our analysis reveals a surprising but intuitive link between positive/negative task alignments and forgetting. Furthermore, we broaden the scope of our analysis the random task ordering case and a jointly non-separable case. We summarize our main contributions below.
1.1 SUMMARY OF CONTRIBUTIONS
We study continual linear classification using sequential GD, where the model is updated by K iterations of GD on the unregularized training loss of each given task.
In Section 3, we study the scenario where the tasks are jointly separable and are given in a cyclic order. We prove that the joint (full) training loss asymptotically converges to zero (Theorem 3.1) and the sequential GD iterates in fact align with the joint (offline) max-margin solution (Theorem 3.2). We also provide a non-asymptotic analysis of the cycle-averaged forgetting, diminishing at the rate of O In+ J
(Theorem 3.4), based on aon-asymiiotic loss
Jz
Recall that Evron ct al. (2023) show their equivalence in terms of parameter direction. We focus this setup instead of carly stopping because is closer common practice in deep learning.
2

---

Published as a conference paper at ICLR 2025
convergence bound of rate O( which holds for all number of cycles J > 1. Our analysis delivers a clear intuition on how positive or negative task alignment has an impact on forgetting.
In Section 4, we again consider the jointly separable setup but with the tasks given in uniformly random order. We show that the asymptotic loss convergence and directional convergence to the joint max-margin solution still happen, albeit almost surely (Theorems 4. and 4.2).
Lastly in Section 5 we consider the case where the tasks are no longer jointly separable. in which the global minimum of the joint training loss uniquely exists. We derive a fast non-asymptotic convergence rate O in
towards the global minimum when the tasks are presented cyclically,
PROBLEM SETUP
In this section, we outline the problem setup considered throughout the paper.
Notation. We denote the joint data matrix X dR whose columns are the d-dimensional data points æ; 's. For a square matrix A, we denote the maximum/minimum eigenvalue of it by Amax ( (A) and Aminn ( (A), respectively. In particular, we write max = Amax [ X the maximum singular value of X. The Euclidean (f2) norm of a vector v is denoted as ||e/] Let IR be the set of N- dimensional vectors whose elements are greater than or equal to zero. Also, for a pair of integers
K1 < K2, we write [Ki K2] to denote set of consecutive integers (K1, Ki + l,..., K2).
2.1 CONTINUAL LINEAR BINARY CLASSIFICATION
We consider binary classification, where each input data x E TRdd has its own label y E +13. We assume that our learning algorithm encounters M different binary classification tasks in a sequential manner, and our goal is to find an offline solution that jointly solves all the tasks. Each task consists of a set of data pairs {<;; (.)...... where In C [0 N is the set of data indices in task m E [0 M - 1]. Let us use the notation that the total index set I == J0 N 1] is partitioned into + - I thus, we use disjoint index sets for distinct tasks.
We consider simple linear model f(; w) x w parameterized by weight vector R With a differentiable loss function E(u), we aim to minimize offline (joint) training loss defined as
((w): Σ l (yif(x; ser
Σ iEl
(y: w)
Likewise, the training loss of task m [0: M - 1] is defined as
Lm (w)) = Σ l (yar) w)
2EAm
Consider CL setup run in multiple stages. At each stage O. the only available dataset for training is taken from single task m. E [0: M 1]: we denote the corresponding index set at stage / as T(t)= Im Note that the learning algorithm does not have the freedom to choose the next task; we assume that the task is presented to the algorithm by the "environment." We study two common scenarios that dictate the order of the tasks to be learned:
(1) Cyclic task ordering. The tasks are revealed a predefined cyclic order, i.e., m, 1 mod M. (2) Random task ordering. Every task is independently sampled uniformly at random, i.e.,
my lid
[ni - 1]).
Both ordering schemes have been studied theoretically and empirically (Evron et al., 2022; 2023; Cossu et al., 2022; Houyon et al., 2023). Indeed, such schemes naturally occur in real-world scenarios. For instance, cyclic task ordering covers search engines influenced by periodic events? and seasonal financial data (Gultekin & Gultekin, 1983; Yang et al., 2022). Random task ordering bears resemblance autonomous driving randomly recurring environments (Verwimp al., 2023).
"A trend of interest about keyword, e.g., trends. ww..gll..cm/tteenaaaa.....
3

---

Published as a conference paper at ICLR 2025
2.2 ALGORITHM: SEQUENTIAL GRADIENT DESCENT
At every stage run GD with fixed learning rate r > 0 the corresponding training loss
(w)(w)) == Lm, (w) = Σ
(y.z, w) (:. 1 Im.)
(E/()
for fixed budget (K 2 1). We call this algorithm sequential GD and its update rule is written as (8)
(1) w k+1 u n/ (() (w)") for ls E [0: K -
w
(++1)
(2)
K steps of GID updates and move the next task That is, for the task my given stage i, (f++1) by setting the initial iterate of the next stage wp
as the last iterate of the current stage w (t)
3 CYCLIC LEARNING OF JOINTLY SEPARABLE TASKS
In this section, we focus on the jointly linearly separable datasets (Evron et al., 2023). We dive deep into the case of cyelic task ordering and prove that sequential GD on separable linear classification tasks converges in direction to the offline max-margin solution of the total dataset. Additionally, through a non -on-asymptotic analysis of the loss convergence, we also characterize the average forgetting within cycles and show that the forgetting vanishes to zero faster than the loss convergence.
3.1 DEFINITIONS AND ASSUMPTIONS
The first assumption that the total dataset is linearly separable. Assumption 3.1 (Joint Separability). There exists w E Rd such that y; w > for Vi E
Under Assumption 3.1, we can state important definition central to our analysis. We define the joint (offline) le max-margin solution (where we usually omit "E2" for convenience)
i := arg min |w weR*
subject to y w 2 1, E
It can be shown that the optimization problem in Equation (3) has unique solution ò (Mohri al., 2018). The max- margin solution is of key interest in the study of linear classification, because it is well known that it has a good generalization guarantee (Vapnik, 2013) and GD applied to a single separable binary classification problem has an implicit bias towards its & max-margin solution (Soudry et al., 2018). To be more specific, it is shown in Soudry al. (2018) that the norm of GD iterates diverges to infinity, but their direction converges to || running multiple steps of GD single task before switching the joint max-margin solution that solves all tasks at once.
db
In our CL setting, we consider
different task, and still aim to find
Given the definition of joint max-margin solution, we now define several key quantities. The maximum margin of (normalized) i defined as
y i
= min 'ET
(4)
In fact, it can be shown that & = 1/ | minimum Φi we define the index set of support vectors as S = (i E I y the index sets of support vectors of each task Sm == S n Im for all m E [0 M - 1]. Let the support vector matrix be Xs E dx submatrix of the data matrix X that only contains columns corresponding to support vectors. Lastly, we define the second margin == minter,s y à > 1, which will appear in our techincal analyses.
support vector is a data point æ; that attains this t0
|[ = Φ). and define
To show directional convergence the joint max- max-margin solution (Theorem 3.2), we additionally pose a mild assumption on the support vectors.
Assumption 3.2 -on-eeegnyy of Support Vectors, e.g., Soudry al., 2018). For each E S, there exists unique a; > 0 satisfying v Σies Q: y;o,; i.e., no support vectors are degenerate.
It is worth mentioning that Assumption 3.2 is valid for almost all linearly separable datasets sampled from a continuous distribution where no more than d support vectors can be on the same hyperplane.
In the upcoming sections, we present several results convergence, implicit bias, and forgetting of sequential GD. They rely on different assumptions on É(u); we collect them here. It is noteworthy that the renowned logistic loss (u) = In(1 + e-) satisfies all the assumptions listed below.
4

---

Published as a conference paper at ICLR 2025
Assumption 3.3. The loss function f(u) is positive, 3-smooth, monotonically decreasing (i.e., 1im {(u) = 0), and satisfies lim sup (()) < O.
Assumption 3.4 (Tight Exponential Tail, Soudry et al., 2018). The negative loss derivative f" (u) has tight exponential tail, i.e., there exist positive constants + _t-, and i such that for all W:
(1 - (-=xp--uu - (w) - (1+ exp(-H+u))e
Assumption 3.5 (Convexity). The loss E(u) is convex, i.e., {(u) 2 {(v) + (()) (u v) (u, v E R).
3.2 ASYMPTOTIC RESULTS: Loss CONVERGENCE & IMPLICIT BIAS TO JOINT MAX-MARGIN
Now, we analyze the asymptotic convergence of offline training loss and characterize the directional convergence of sequential GD (2) on jointly separable cyclic tasks. We start by understanding the asymptotic behavior of the joint task loss ((w)..
Theorem 3.1. Let { hee(0=K-11,120 be the sequence of GD iterates (2) (2o any starting point
(0)
where lasks are given cyclically. Under Assumptions 3.1 and 3.3, if the learning rate satisfies
6²
n
2K max mma))
then
Loss converges zero: lim
(0) -
-1].
2. All data points eventually classified correctly: lim y: w =0, Vk [0: K 1),
3. Square sum of the change of weight is finite: Ei= Ok=o 1
K-1 (1)
w (1) 112 co.
The theorem above shows that cyclic continual learning on the jointly separable data will eventually learn all tasks, or equivalently, find an offline solution without any additional techniques such as regularization. This result matches the recent empirical findings that DNN can mitigate catastrophic forgetting when tasks are given repetitively (Lesort al., 2023). The last part on the sum of squared changes is used for proving the upcoming Theorem 3.2. We note that Theorem 3.1 does not require convexity of f. The proof can be found Appendix E.
Although Theorem 3.1 shows that the joint training loss converges to zero, due to the joint separability
(Assumption 3.1), there are multiple directions in which w (t) could evolve to make the offline training loss decay to zero. That is, the loss convergence only guarantees finding an offline solution, but does not characterize which. Under additional assumptions of non-degeneracy and tight exponential tails, we characterize which direction w. diverges to, and show that the model parameter in fact aligns with the joint & max- max-margin solution r (3).
Theorem 3.2. Let {un) ( 1 be the sequence of GD iterates (2) from any initial point
(0) where tasks are given eyclically. Suppose that Assumptions 3.1, 3.2, 3.3, and 3.4 hold. Then, under the same learning rate condition as Theorem 3.1, w will behave as
(t) In(()( + Pk
(0)
w k
for all sufficiently large I, where ||
(6)
stays bounded L - 50.
The proof is in Appendix F.2. A key implication of Theorem 3.2 is that the weight vector converges in the direction of the joint max- marxin solution while diverging in magnitude at a rate (Inn))
w (1)
i
lim 00
Vk [0 K K-1]. 1].
(5)
( ||
|6
implies that sequential GD without any regularization not only learns every task, but also implicitly biased towards the joint max-margin direction whose corresponding linear classifier separates the all update steps of the classifier
total dataset with the largest margin, even without full access weight. This implication is visually verified in Figure 2.
Remark 3.6 (Asymptotic Convergence Rate Joint Training Loss). Recall that Theorem 3.2 relies on Assumption 3.2 as well the assumptions about the shape of the loss function e(-), namely,
5

---

Published as a conference paper at ICLR 2025
Sinc Anglel Va cossim-)) between Linel Modil vs. joint Man-Mangin
Casti mulli loarmo
Iest
Carthuu Learnin trgedery
Data y- +21
S
Teak Dute
Tast2 Dute Use 9 -11
(a) Data points, training trajectory (heginning-of-stage iterates), and the decision boundaries (dashed).
(b) Sine angles, implying the implicit bias toward joint max-margin direction.
Figure 2: Comparison befween continually learned and jointly trained linear classifier. We generate three jointly separable binary classification tasks (with 2D inputs) and run (1) sequential GD in a cyclic task ordering and (2) full-batch GD. It is well-known that the offlin full-batch GD converges to the offline E2 max-margin solution (Soudry et al., 2018). We verify similar implicit bias of sequential GD iterates (which we proved in Theorem 3.2) by observing the decrease in angle between the model weight and the joint max-mnrgin direction (set as (1, We also observe similar phenomena for a more general experimental setup (e.g., random task ordering): see Appendix C.2.
Assumptions 3.3 and 3.4. Combining these assumptions again with the theorem, we can show that the [(w()) (9) will eventually converge to zero at rate (1/tt), given that is sufficiently large. We prove this claim in Appendix E.3. Moreover, we will compare it with a forthcoming non-asymptotic loss convergence rate (Theorem 3.3) later in Section 3.3.
Remark on Assumption 3.2. As noted earlier, the non-degeneracy assumption (Assumption 3.2) borrowed from Soudry et al. (2018); the purpose of adopting this assumption is to facilitate a more complete analysis of the residual pk In fact, in Soudry et al. (2018), the conclusion on the directional convergence (similar to Equation (5), but for single-task GD training) still holds even under the absence of Assumption 3.2. In light of this, we also believe that directional convergence of sequential GD (5) will hold even without Assumption 3.2, but we did not pursue removing the assumption because it does not offer substantial additional insights.
Additional Experiments. Although we analyze continual learning in setting where each task has fixed dataset, the insight of our analysis extends to general setups. To show this, we conduct experiments in a setting where each task has its own (separable) data distribution and dataset is freshly sampled at every new stage. We observe the same directional convergence behavior of sequential GD toward the true joint max-margin direction. The detailed results are in Appendix C.2.4. In addition, we provide experiments with shallow ReLU networks, verifying analogous insights on implicit bias and loss convergence of continually learned models: see Appendix C.4.
3.3
RESULTS: Loss CONVERGENCE AND FORGETTING BOUNDS
In Section 3.2, we presented asymptotic results characterizing the convergence of total training loss to zero and the directional convergence of sequential GD iterates to the max-margin solutions. We now supplement these results with additional asymptoiiii convergence analysis on total training loss, which we can use to obtain a non- asymptotic analysis of cycle-averaged forgetting as well.
As aforementioned, the main challenge in CL is mitigating catastrophic forgetting. Analyses of continual learning methods aim to show that methods decrease forgetting, theoretically or empirically. In this paper, we interested in how strong forgetting is in our continual linear classification setup.
We start by stating a common definition of forgetting, which quantifies the amount of loss increase at the end of stage t compared to the end of K steps of GD on ((s) executed in stage 8 S t. Definition 3.7 (Forgetting). The forgetting at stage I of the task learned in stage (S f) is the change of the task loss ((s) from the moment the K GD steps were finished in stage That is,
F(o)(() = (()) (1n (2) (!0) (w (8)

---

Published as a conference paper at ICLR 2025
Notice that forgetting is zero by definition when t= s. While it is usually expected that forgetting is a positive quantity, it could also be negative by definition. Such a case can happen when the tasks seen in stages between 8 and f. are well-aligned with [ so that the model improves on the task previously seen in stage This phenomenon is called backward knowledge transfer.
When CL tasks do not necessarily repeat, is common to evaluate the average forgetting that occurred during all past stages, namely & Ex (t). However, since we consider the case where tasks are given eyclically, it is natural to define quantity of interest as below:
Definition 3.8 Aveer--ee Forgetting). The cycle-averaged forgetting at cycle is the average loss change of previous tasks from the stage in which it was learned. That is,
Foyc
1
(M5)mm) (Mjj M 1-
M
M-
1 M
Lm (un) (11++))))) - f. Eum ()))+m)).
By studying cycle-averaged forgetting, we would like to understand how much forgetting happens during the cyclic learning process, and how the amount of forgetting changes as we repeat the cycles.
Although the asymptotic convergence to joint max-margin solution (Theorem 3.2) suggests that the model will suffer a diminishing level of forgetting in the long run, characterizing the amount of forgetting for given cycle count J necessitates a more careful non-asymptotic analysis of the loss convergence. For this purpose, we present an additional theorem characterizing the -sympsymio convergence of offline training loss L; we then build this theorem to prove upper and lower bounds on cyele-averaged forgetting. The new convergence theorem requires the same set of assumptions as Theorem 3.1, except for additional assumption of convex E(u).
Theorem 3.3. Suppose that Assumptions 3.1, 3.3, and 3.5 hold under the cyclic task ordering 6²
setup. Then, if we choose learning rate satisfying 1) aKBo (m
we have for any
m E [0: M - and k E [0: K 1] that
L(w (M)mmm) S
[S]
E i=0
|S + & |mml
e(In + |! In MJI1
D
J
2nKJ
J
EnD (141-155 1 (Sai) + & (14ml 18mml) ((1lnM)
+ [|| |S|
|S|
where 0 > 1 is the second margin defined in Section 3. and D2 is constant independent to J.
The proof, as well as the detailed expression of Dj, can be found in Appendix E.4. One can revisit Section 3.1 to recall the definitions of symbols such as Tmax, 6, and B. The bound in Theorem 3.3 may be a bit difficult to parse. First of all, notice that whenever E(u) S e 1 Combined with other loss (u)) In(1 + "), we have E(In MJ) < MrJ and E(0 In MJ) (MJy"
which is true for logistic
terms, this implies an overall O In upper bound for the offline training loss.
Unlike the asymptotic result, Theorem 3.3 enables capturing the behavior of training for any small J. we can notice for any fixed J, the upper bound in fact grows with and m. This unusual growth of the upper bound reflects the effect of forgetting that can happen within cycles. We demonstrate this mid-cycle increase of joint loss using a toy example in Appendix C.3. Moreover, despite the possible forgetting, Theorem 3.3 indicates that if tasks given cyclically, then the loss bound is guaranteed to decrease at the end of every cycle.
We can now use Theorem 3.3 derive bounds on cycle-averaged forgetting we defined in Defi- nition 3.8. We characterize how fast the cycle-averaged forgetting FJye(J) converges to zero as the cycles replay. For this theorem, we specifically consider logistic loss, which satisfies all the assumptions about loss in the paper.
Theorem 3.4. Suppose Assumption 3.1 and let f(u) In(1 + e be the logistic loss, which
o
satisfies Assumptions 3.3, 3.4, and 3.5. If the learning rate satisfies 17 < IKg0 (Mo+omax) then
7

---

Published as a conference paper at ICLR 2025
0.020
contradicc
Averagee Forgesting 7ox0)
aigned
0.015
0.010
0.000
-1
-1
-0.005
-0.010
0.5
0.0
0.5
1.0
13
-55
0.0
0.5
10
1.5
cycle/
(a) Contradicting case
(b) Aligned case
(c) Cycle-averaged Forgetting
Figure 3: We compare two continual learning scenarios with the same joint dataset D {(1, 2), (1.1, 1.8), (1.2, 1.9), (1, 2), (1.1, 1.8), (1.2, -..9), where labels are all +1 and hence omitted. We mark Task I's data 'o" and Task 2's data as '+', We used M and K 10. Figure 3(a) displays a data composition that makes large A whereas Figure 3(b) displays data composition that makes relatively small A1,2 and large 2 Figure 3(c) plot of cycle-averaged forgetting (Feye), evolving over cycles. For the "contradict" scenario (red), Feye is always positive and diminishing to O. contrast, for the "aligned" scenario (blue), Feye is always negative and rising to O.
the cycle-averaged forgetting (Jy for cycle satisfies the following upper and lower bounds:
Evgg pa
Eptn Apa
[
S FFayo())
Snk (L(J))2
M
M
where I(J)= = 0 (11س2) and A ==
Σ (I,))T,xI m 20
x.1 Mg Aga =
Σ
| ar
(1.))T,xI,
21 my<0
The proof and the detailed expressions are in Appendix E.S. Theorem 3.4 shows nonnegative upper bound and a nonpositive lower bound on the cycle-averaged forgetting at cycle J. Note that both upper and lower bounds decay zero as J grows. Convergence of (J) is of rate O (( which is faster than the convergence rate O ( of joint training loss shown in Theorem 3.3.
The bounds in Theorem 3.4 reflect how positive/negative data alignment between different tasks impact forgetting. The quantities A and Ap.4 capture show how similar and different (respectively) data points are, for pair of tasks (p, q). In particular, if Engt A 0, it is guaranteed that (non-negative) cycle-averaged forgetting will not happen regardless of J. Rather, training on a task will decrease the loss for all previously learned tasks, which can be considered an extreme form of backward knowledge transfer. On the other hand, if Epdy A+ O, it is guaranteed that the model will suffer forgetting at every cycle: however, even in this case, Theorem 3.4 implies that repeating tasks over cycles mitigates catastrophic forgetting.
Even when the joint dataset D is the same, forgetting behavior can differ depending on how the data points are distributed over different tasks. This matches the former theoretical explanation of how distribution affects forgetting. For instance, Lin et al. (2023) show that larger distance between each task's optimal solution leads to larger forgetting. For a straightforward interpretation, consider the following example of two tasks: their cycle-averaged forgetting for two different decompositions of D plotted in Figure 3. We can observe that two tasks contradicting each other (i.e., large AT,2) result in positive forgetting, whereas two tasks aligning better (i.e., large At exhibit negative forgetting. Nevertheless, cycle-averaged forgetting converges to zero both cases.
Remark 3.9. When É(u) is the logistic loss, direct application of an asymptotic loss convergence rate mentioned in Remark 3.6 implies the forgetting convergence of rate 0(+) without any additional logarithmic factors, which can be shown by almost an identical proof Theorem 3.4. However, is guaranteed for sufficiently large number of cycles J. See Appendix E.3 for discussion about it.
8

---

Published as a conference paper at ICLR 2025
4 RANDOM-ORDER LEARNING OF JOINTLY SEPARABLE TASKS
In this section, we consider the scenario where tasks are given in a random order, while still assuming that the tasks are jointly separable. Formally, at the end of the K-th GD iteration of stage t, the next task is sampled independently and uniformly at random. Even in this case, our analysis reveals that the asymptotic results shown Section 3.2 continue to hold almost surely.
We first show that the offline training loss converges to zero almost surely, which is random-order counterpart of Theorem 3.1. The proof Appendix F.I.
GD iterates from any starting point Theorem 4.1. Let {w) ke(o- be the sequence GD
(0)
where lasks are given rundomly. Under Assumptions 3. and 3.3, if the learning rate satisfies
20² then the following statements hold with probability 1:
n
Bo maxx
1. Loss converges zero: lim C(w (0)) - [0: K 1
2. All data points are eventually classified correctly: lim you; w/
(1) 0, Ak 00: K - 11,
3. Square sum of the change of weight is finite: Er 2k==
||
(t)
(1) w 112 xx.
k+1
We derive the same asymptotic loss convergence result, with minor difference that the learning rate can be chosen independently of the number of tasks M and the iteration count K.
We now state the random-order counterpart of Theorem 3.2, which implies that the sequential GD iterates converge to the joint Eg max max-margin solution almost surely. The proof is in Appendix F.2.
Theorem 4.2. Let {m (0)
(kk[(:KK-))ss be the sequence of GD iterates (2) from any starting point w where tasks are given randomly. Suppose that Assumptions 3.1, 3.2, 3.3, and 3.4 hold. Then, under the same learning rate condition as in Theorem 4.1, wo will behave as:
(t) w In (t) i Pk
where ( stays bounded as grows.
BEYOND JOINTLY SEPARABLE TASKS
Now we turn our attention to the CL on a strictly non-separable set of M tasks, where the tasks are presented in cyclic manner. In this section, we assume that the set of all data points spans the whole space &dd without loss of generality. This is a mild assumption hecause every gradient update happens in the span of data points. In this case, if we assume the strict non-separability
the full dataset (see Assumption 5.1), the offline training loss L(w) M-1 L. (. defined with logistic losses becomes strictly convex and coercive (i.e., li L(w) +oo); thus, it has unique minimum w, Rdd We show that, under cyclic task ordering, the iterates of sequential GD converge to w,
with rate O (In which faster than the loss convergence rate of the separable case.
The core idea of the analysis is to identify the local strong convexity of the offline training loss compact set on which every end-of-cycle iterates lie (Freund al., 2018). To this end, we introduce a strict non-separability of the joint dataset defined below.
Assumption 5.1 (Joint Striet Non- Sopaaaarray Condition (Freund et al., 2018)). Assume that the whole collection of data points is of full rank: span( {æ; O..... 1}) = RR. Additionally, assume that there exists > 0 defined
Σ 0= [ e)
b
min
vER ||
where [a] == max -a}.
Note that large b means that the joint data points are highly non-separable: for any classifier vector V. there exist some data points with the incorrect prediction of the label with a large margin. We also remark that individual tasks not necessarily strictly non-separable. Hence, analysis covers the case where all individual tasks are separable but the full dataset is not separable.
We additionally assume some mild properties of the loss function {(-).

---

Published as a conference paper at ICLR 2025
Assumption 5.2. The loss function L R - R4 is strictly convex, f-smooth function with positive second derivative such that E(u) 2 G [a]] for some G > 0.
Note that the logistic loss E(u) = 1n(1 in(1+e"") satisfies the assumption above with 3 = 1/4 and G = From the assumptions, we have that (1) the training loss of m-th task Cm (w) = Eier,,, {y,a w) is convex and mm-oth for 8. == 3dmax (Xm.X,) where X, E [R a data matrix of task m consisting of columns {æ, : E J: (2) due to the strict non-separability, the offline training loss =0 (2w) has unique minimum w. Furthermore, we can prove that the end-of-cycle iterates of the sequential GD stay bounded in compact set W around w.. Consequently, we obtain local strong convexity of the offline training loss on W. The proof is in Appendix G.I.
[(w) = _m= M-1
Lemma 5.1. Consider learning M linear classification tasks cyclically. Suppose that Assumptions 5. and 5.2 hold. Let = Σ -- 8... and V, = 1
Bun [[VLm(w.)ll Take step size rj S 2<2KB' Then, there exists a compact set W C IR containing w. and every Wo (jMM) (j= = 0,1, .). whose radius is independent of J (the number of cycles) but depends on other parameters like b, G, B, and Vz. Also, the offline training loss j--strongly convex on W, where
EM-1
p== (mingg]o:N- 8" (yer,, w)) Amiin (xx 0.
(6)
We remark that the radius of the set W largely depends on the non-separability b b (Assumption 5.1):
loosely speaking, W can be arbitrarily large if goes to zero since || w. = O(1/b) for any w E W. In particular, for the logistic loss f, the local strong convexity coefficient μ can get small if b small, because of the (possibly) large radius of W. With the local strong convexity, we finally have a fast non-asymptotic convergence rate of (J-22) towards the global minimum. The proof can be found in Appendix G.2.
Theorem 5.2. Suppose we learn M tasks cyclically for J > 1 cycles. We adopt the notation from Lemma 5.1. Then, with step size n = O ( min
In(3)) }). sequential GD satisfies
B
(MJ) w
J.J (1 (1
1100
(0) w.
2 BVV,
w.
O exp
J
(7)
Remark on the Loss Convergence Rate, Since the L(wr) is B-smooth, it satisfies that
B 2 |/w 11 2 ||w w.ll?
[(w) - [(w,.) S (V (VW.)), w - w.) +
(8)
Thus, our Theorem 5.2 naturally implics the loss convergence at the same rate (in terms of J).
Experiments a Real-World Dataset. For those interested, we also provide an experiment real-world dataset CIFAR-10 (Krizhevsky, 2009), which is not guaranteed to be linearly separable: Appendix C.5.
CONCLUSION
We considered continual linear classification by running gradient descent for a fixed number of iterations per task. When there exist solutions that can solve every task, we found that even without any regularization or CL methods, the classifier eventually converges to the joint margin direction. This implicit bias was shown to exist in both cyclic/random task ordering. We further presented non-asymptotic analysis on cycle-averaged forgetting with respect to positive/negative alignments of tasks and the number of cycles. Lastly, we showed that if no linear classifier solves all tasks simultaneously, the model converges to the unique minimum of the offline training loss.
We believe the convergence on continual classification can be extended to other model structures, bridging the gap between empirical findings and theoretical understanding of the impact of task repetition. Also, results are restricted to the "small learning rate" regime, and do not cover larger learning rates or even the "edge stability" regime (Wu et al., 2024); relaxing this restriction is left for future work.
Future Works.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was partly supported by the Institute for Information & communications Technology Plan- ning & Evaluation (IITP) grants funded by the Korean government (MSIT) (No. RS-2019-11190055, Artificial Intelligence Graduate School Program (KAIST); No. RS-2022-I1220182 84, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy on Ethics; No. RS- 2019-1119 1906, Artificial Intelligence Graduate School Program (POSTECH)). This research was supported in part by the NAVER-Intel Co-Lab. The work was conducted by KAIST and reviewed by both NAVER and Intel.
REFERENCES
Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Mareus Rohrbach, and Tinne Tuytelaars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 139-154, 2018.
Haruka Asanuma, Shiro Takagi, Yoshihiro Nagano, Yuki Yoshida, Yasuhiko Igarashi, and Masato Okada. Statistical mechanical analysis of catastrophic forgetting in continual learning with teacher and student networks. Journal of the Physical Society of Japan, (0(10))10400) 2021.
Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama. Generalisation guarantees for continual learning with orthogonal gradient descent. arXiv preprint arXiv:2006./1942, 2020. 1, 16
Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puncet K Dokania, Philip HS Torr, and Marc' Aurelio Ranzato. On tiny episodic memories in continual learning. ICML Workshop Multi-Task and Lifelong Reinforcement Learning, 2019. 1
Andrea Cossu, Gabriele Graffieti, Lorenzo Pellegrini, Davide Maltoni, Davide Bacciu, Antonio Carta, and Vincenzo Lomonaco. class-incremental enough for continual learning? Frontiers in Artificial Intelligence, 5:829842, 2022.
Thang Doan, Mehdi Abbana Bennani, Bogdan Mazoure, Guillaume Rabusseau, and Pierre Alquier. A theoretical analysis of catastrophic forgetting through the ntk overlap matrix. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1072-1080. PMLR, 2021. 1, 16
Rick Durrett. Probability theory and examples, volume 49. Cambridge university press, 2019. 56, 57
Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, and Daniel Soudry. How catastrophic can catastrophic forgetting be in linear regression? In Proceedings of Conference on Learning Theory (COLT), pp. 4028 4028-4079. PMLR, 2022. 3.3
Itay Evron, Edward Moroshko, Gon Buzaglo, Maroun Khriesh, Badea Marjieh, Nathan Srebro, and Daniel Soudry. Continual learning in linear classification on separable data. In Proceedings of the International Conference on Machine Learning (ICML), pp. 9440 9484. PMLR, 2023. 1, 2, 3, 14, 16, 17
Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3762-3773. PMLR, 2020. 1, 16
Robert M Freund, Paul Grigas, and Rahul Mazumder. Condition number analysis of logis- tic regression, and its implications for standard first-order solution methods. arXiv preprint arXiv:1810.08727, 2018.
Daniel Goldfarb and Paul Hand. Analysis of catastrophic forgetting for random orthogonal trans- formation tasks in the overparameterized regime. Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2975-2993 PMLR, 2023.
Ian J Goodfellow. Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investi- gation catastrophic forgetting in gradient- gradient-based neural networks. arXiv preprint 13Xiv:1312.60 2013. 1
11

---

Published as a conference paper at ICLR 2025
Mustafa N Gultekin and N Bulent Gultekin. Stock market seasonality: International evidence. Journal of Financial Economics, 12(4))469-49) 481, 1983. 3
Joachim Houyon, Anthony Cioppa, Yasir Ghunaim, Motasem Alfarra, Anaïs Halin, Maxim Henry, Bernard Ghanem, and Marc Van Droogenbroeck, Online distillation with continual learning for cyclic domain shifts, 2023. URL https:://// //aaaiiivv.v wwtp//ss..///////oe//o// 23044 01239.
Khurram Javed and Martha White. Meta-learning representations for continual learning. Advances in Neural Information Processing Systems (NeurlPS), 32, 2019.
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07 070000 2018. 16
Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Proceedings of Algorithmic Learning Theory (ALT), pp. 772-804, PMLR, 2021. 16
Ryo Karakida and Shotaro Akaho. Learning curves for continual learning in neural networks: Self- knowledge transfer and forgetting. In Proceedings of the International Conference on Learning
Representations (ICLR), 2022. 16
Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, Zixuan Ke, and Bing Liu. A theoretical study on solving continual learning. Advances in Neural Information Processing Systems (NeurIPS), 35: 5065-5079, 2022. 1, 16
Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, and Bing Liu. Learnability and algorithm for continual learning. In Proceedings of the International Conference Machine Learning (ICML), pp. 16877-16896. PMLR, 2023.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114 (13):3521-3526, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical re- port, University of Toronto, 2009. URL https://www.c cs http://wwww..tttottteottee/////t fertinngfeettues--2000 pdf. 10,
Sebastian Lee, Sebastian Goldt, and Andrew Saxe. Continual learning in the teacher-student setup: Impact of task similarity. In Proceedings of the International Conference on Machine Learning (ICML), pp. 6109-61 61 19. PMLR, 2021. 1, 16
Timothée Lesort, Oleksiy Ostapenko, Pau Rodríguez, Diganta Misra, Md Rifat Arefin, Laurent Charlin, and Irina Rish. Challenging common assumptions about catastrophic forgetting and knowledge accumulation. In Conference Lifelong Learning Agents, pp. 43 63-65. PMLR, 2023.
Haoran Li, Jingfeng Wu, and Vladimir Braverman. Fixed design analysis of regularization-bn based continual learning. In Conference on Lifelong Learning Agents, pp. 513-533. PMLR, 2023.
Zhizhong Li and Derek Hoiem. Learning without forgetting, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPMAI), 40(12):2933 2947, 2017.
Sen Lin, Peizhong Ju, Yingbin Liang, and Ness Shroff. Theory on forgetting and generalization of continual learning. In Proceedings of the International Conference on Machine Learning (ICML), pp. 21078-22 100. PMLR, 2023. 8, 16
David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pp. 109-165. Elsevier, 1989.
Scyed Iman Mirzadeh, Mehrdad Farajtabar, Razvan Pascanu, and Hassan Ghasemzadeh. Understand- ing the role training regimes in continual learning. Advances in Neural Information Processing Systems (NeurIPS), $3:7308-7320 2020. 1
12

---

Published as a conference paper at ICLR 2025
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. Adaptive Computation and Machine Learning series. MIT Press, edition, 2018. ISBN 9780262351362. 4
URL https://books.. http://ooooooooololooooooo gwwgle.
kr
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent separable data: Exact convergence with fixed learning rate. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), volume 22, pp. 3051-3059. PMLR, 2019. 16,
Binghui Peng and Andrej Risteski. Continual learning: feature extraction formalization, an efficient algorithm, and fundamental obstructions. Advances in Neural Information Processing Systems (NeurIPS), 35:284 14-28427, 2022. 16
Krishnan Raghavan and Prasanna Balaprakash. Formalizing the generalization-frgetie trade- off in continual learning. Advances in Neural Information Processing Systems (NeurIPS), 34: 17284-17297, 2021. 1, 16
Haizhou Shi and Hao Wang. A unified approach to domain incremental learning with memory: Theory and algorithm. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023. 1, 16
Hanul Shin, Jung Kwon Lee, Jachong Kim, and Jiwon Kim. Continual learning with deep generative replay. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. Journal of Machine Learning Research (JMLR), 19(70): 1-57, 2018. 2, 4, 5, 6, 16, 33
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013. 2,
Eli Verwimp, Kuo Yang, Sarah Parisot, Lanqing Hong, Steven McDonagh, Eduardo Pérez-Pellitero, Matthias De Lange, and Tinne Tuytelaars. Clad: A realistic continual learning benchmark for autonomous driving. Neural Networks, 161:659 669, 2023.
Jingfeng Wu, Vladimir Braverman, and Jason D Lee. Implicit bias of gradient descent for logistic regression the edge of stability. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024. 10, 16
Yingxiang Yang, Zhihan Xiong, Tianyi Liu, Taiqing Wang, and Chong Wang. Fourier learning with cyclical data. In Proceedings of the International Conference on Machine Learning (ICML), pp. 25280-25301. PMLR, 2022.
13

---

Published as a conference paper at ICLR 2025
CONTENTS
1
INTRODUCTION
1
1.1 SUMMARY OF CONTRIBUTIONS
2 PROBLEM SETUP
2.1 CONTINUAL LINEAR BINARY CLASSIFICATION
2.2
ALGORITIM:: SEQUENTIAL GRADIENT DESCENT
3
CYCLIC LEARNING OF JOINTLY SEPARABLE TASKS
3.1 DEFINITIONS AND ASSUMPTIONS
3.2 ASYMPTOTIC RESULTS: Loss CONVERGENCE & IMPLICIT BIAS TO JOINT MAX-
MARGIN
3.3 NON-ASYMPTOTIC RESULTS: Loss CONVERGENCE AND FORGETTING BOUNDS
4 RANDOM-ORDER LEARNING OF JOINTLY SEPARABLE TASKS
9
5 BEYOND JOINTLY SEPARABLE TASKS
6 CONCLUSTON
10
A OTHER RELATED WORKS
16
B BRIEF OVERVIEW OF EVRON ET AL. (2023) AND COMPARISONS
17
C EXPERIMENT DETAILS & OMITTED EXPERIMENTAL RESULTS
18
C.I EXPERIMENT DETAILS OF FIGURE
18
C.2 EXPERIMENT DETAILS FIGURE 2 & MORE RESULTS
18
C.2.1 EXPERIMENTAL DETAIL.
18
C.2.2 OMITTED Loss CONVERGENCE RESULT FIGURE 2
19
C.2.3 RANDOM TASK ORDERING
19
C.2.4 BEYOND THEORETICAL SETUP: TOWARDS CONTINUAL LEARNING ON ONLINE DATA
19
C.3 ToY EXAMPLE FOR INCREASING Loss IN CYCLE
20
C.4 EXPERIMENTS WITH NEURAL NETWORKS: BEYOND LINEAR MODEL.
21
C.5 EXPERIMENT ON REAL-WORLD DATASET
23
PROOF SKETCHES
D.1 ASYMPTOTIC Loss CONVERGENCE (PROOF SKETCH OF THEOREM 3.1)
25
D.2 DIRECTIONAL CONVERGENCE (PRoOF SKETCH OF THEOREM 4.2)
25
D.2.1 PROOF SKETCH OF LEMMA E.5
26
D.3 NON-ASYMPOOTIC Loss CONVERGENCE ANALYSIS (PROOF SKETCH OF THEO- REM 3.3)
27
14

---

Published as a conference paper at ICLR 2025
E PROOFS FOR SECTION 3: CYCLIC TASK ORDERING, JOINTLY SEPARABLE
29
E.1 ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PROOF OF THEOREM 3.1)
29
E.1.1 PROOF OF LEMMA E.
31
E.1.2 PROOF OF LEMMA E.2
E.2 DIRECTIONAL CONVERGENCE ANALYSIS (PROOF OF THEOREM 3.2)
33
E.2.1 PROOF OF LEMMA E.4
35
E.2.2 PROOF OF LEMMA E.5
36
E.2.3 CONVERGENCE OF Pk (6)
E.3
ASYMPTOTIC Loss CONVERGENCE RATE AFTER MANY CYCLES
43
E.4
NON-ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PROOF OF THEOREM 3.3)
45
E.4.1 PROOF OF LEMMA E.8
48
E.4.2 PROOF OF LEMMA E.9
49
E.5 FORGETTING ANALYSIS (PROOF OF THEOREM 3.4)
50
PROOFS FOR SECTION 4: RANDOM TASK ORDERING, JOINTLY SEPARABLE
F.1 ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PROOF OF THEOREM 4.1)
53
F.2 DIRECTIONAL CONVERGENCE ANALYSIS (PROOF OF THEOREM 4.2)
54
F.2.1 PROOF OF LEMMA F.I
56
(0)
F.2.2 CONVERGENCE OF Pk
58
G PROOFS FOR SECTION 5: CYCLIC TASK ORDERING, JOINTLY NON-SEPARATHE
60
G. LOCAL STRONG CONVEXITY ANALYSIS (PROOF OF LEMMA 5.1)
G.1.1 PROOF OF LEMMA G.4
62
G.1.2 PROOF OF LEMMA G.5
63
G.2 NON-ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PROOF OF THEOREM 5.2)
65
G.2.1 PROOF OF LEMMA G.6
66
15

---

Published as a conference paper at ICLR 2025
A OTHER RELATED WORKS
Theoretical Results on Continual Learning. Continual regression has been studied under various regimes and algorithms. The work by Lin et al. (2023) analyzes empirical and population risks by drawing Gaussian samples for each task. It also investigates the impact of overparameterization and task similarity on forgetting. Bennani et al. (2020); Doan al. (2021); Karakida & Akaho (2022) study forgetting in NTK regime. Specifically, Bennani et al. (2020); Doan et al. (2021) analyze forgetting of orthogonal GD (OGD, Farajtabar al., 2020), while Karakida & Akaho (2022) studies continual transfer learning. Other settings, such as teacher-student setup (lee et al., 2021), and feature extraction (Peng& Risteski, 2022) have been considered task-incremental learning.
On the other hand, most of the works on continual classification focus on analyzing the performance of the model without assuming its architecture. Instead, they focus on the specific types continual learning (Kim et al., 2022; Shi & Wang, 2023). In class-incremental learning (CIL), Kim et al. (2022) prove that attaining strong within-task prediction (WP) and strong task-id prediction (TP) are neces- sary and sufficient for achieving strong CIL. Furthermore, they relate TP to the out-of of-distribution detection problem. On the other hand, Shi & Wang (2023) consider the domain--ncrennental learning setup. They especially suggest framework with a memory buffer that unifies earlier methods. The work by Raghavan & Balaprakash (2021) studies the generalization-foreee as two-player sequential game. However, the best of our knowledge, other wark--parttt from specific model architectures and analyzes the behavior of specific
trade-off by viewing it
Evron et al. algorithms as in continual regression.
Implicit Bias of GD for Linear Classification. As far know, the work by Soudry al. (2018) the first to prove the implicit bias of GD towards the max-margin direction for separable linear classification problem. Another work by Ji & Telgarsky (2018) also considers the data that are not necessarily (strictly) separable, yet the GD iterate may diverge to infinity. although the convergence rate is slower due to the absence of the non-degeneracy condition. The work by Nacson et al. (2019) shows similar implicit bias result for the stochastic GD. Ji & Telgarsky (2021) show a faster convergence
under decreasing learning rate via primal-dual analysis. Very recently, it has been proved by Wu et al. (2024) that GD on logistic loss eventually converges to the max-marga direction even when the learning rate large, which contrasts with the existing findings requiring small enough learning rates.
16

---

Published as a conference paper at ICLR 2025
B BRIEF OVERVIEW OF EVRON ET AL. (2023) AND COMPARISONS
To highlight how our sequential GD algorithm differs from Evron (2023), we briefly summarize the Sequential Max-Margin (SMM) framework considered in the existing paper and its theoretical results.
Evron et al. (2023) consider minimizing the regularized training loss of each task until convergence, where the loss function is chosen to be the exponential loss f(u) - exp(-u). Let (w be the iterates trained by regularized continual learning with regularization coefficient A. The algorithm can be written follows:
(++1) = arg min wx
Σ
exp (-yar w) + u (8)
(9)
wERd
XET()
Also, let (t)
SMM be the weight trained by the Sequential Max-Margin algorithm. The update rule is USMM
(t+1) p(t) (MMM)) == arg min
w
u
SMM
(0)
subject to y; w 2 1, E r(t)
(10)
weRd
where the operator p(0) is the orthogonal projection onto convex polyhedral set y. w 2 1, 1(0)
w E R
(11)
defined by the margin conditions on the data points %(0, That is, USMM is the same as the sequential projection onto such convex sets. Evron al. (2023) showed the relation of w and WSMM. when the regularization coefficient À + O: Theorem B.1 (Theorem 3.1 of Evron et al. (2023)). For almost all jointly separable dataset. in the limit of -> holds that w u UMM with residual of O( log log (+)). Hence, any log(1/A) t = log (1))))))) ). we get
(t)
(+) SMMM
W
w
lim
|
Based on this equivalence in terms of parameter direction, Evron et al. (2023) expect that the behavior of ( can be analyzed through the lens of wSMM long À is close to 0, since Theorem B. holds for all
(t)
log(1/A) log log(1/A]
Given this background, we now highlight some differences between Evron et al. (2023) and our analysis. First of all, seen in (9), Evron et al. (2023) study regularized exponential loss trained until convergence, whereas we study unregularized logistic loss trained for a fixed number of iterations. Training the weakly regularized loss until convergence, in conjunction with the limit À O, sends each w to infinity. Hence, each stage requires a growing number of iterations, and the grounds for the equivalence between (9) and (10) become weaker, since the solutions become vastly different in terms of magnitude.
Second, thanks to the connection between weakly-regularized continual learning and SMM, Evron et al. (2023) could obtain the exact trajectory of every stage via the projection method. On the other hand, in our sequential GD setting, is very difficult keep track of the exact location of the iterate after a task is trained, since the iterates are updated multiple times, but training stops before convergence. This makes challenging to analyze implicit bias and forgetting by tracking the exact trajectory stage by stage. To overcome this challenge, we use different proof techniques from Evron al. (2023). Rather than pinpointing the exact position of the iterate after each stage, we focus on the direction in which the sequential GD eventually converges.
On top of that, importantly, our analysis of sequential GD reveals that training on unregularized loss using a fixed number of GD iterations results in the joint/ofiline max-margin solution. In contrast, although the convergence to some offline solutions is already shown for SMM (Evron et al., 2023), the converged offline solution can be different from the offline max-margin solution. In fact. in the next section (Appendix C. we demonstrate by toy example that SMM can indeed converge to a point other than the joint max-margin solution.
17

---

Published as a conference paper at ICLR 2025
C EXPERIMENT DETAILS & OMITTED EXPERIMENTAL RESULTS
C.I EXPERIMENT DETAILS OF FIGURE
In this section, we present a simple toy example that demonstrates interesting facts about max-margin solutions in continual linear classification:
The joint max-margin direction of the joint dataset can be quite different from the max-margin solutions of individual tasks. Specifically, the joint solution may not be on the subspace spanned by the individual solutions.
The limit of Sequential Max- Max-Margin (SMM) iterations can be different from the joint max -argin solution, whereas the limit direction of sequential GD does align with it.
We consider the case of M generality, we assume that all the labels are +1, and hence omit them. We let f,1, 1,,,10), (1, (2,12,1) 1)) be the dataset of task and {(1, 1), (1, -2) be the data of task 2. One can verify that:
tasks, where the input points come from R Without loss of
Their joint max-margin direction is (1,
The max-marpe max-margin direction for tasks and 2 are (11 and [II 17). respectively.
Therefore, the joint max-margin solution does not belong the span of individual max-margin solutions.
We ran numerical experiments running the SMM iterations, which are done by solving the constrained minimization problems using fmincon in MATLAB Optimization Toolbox. The code is provided in our supplementary material. We find that SMM converges (11 11): the trajectory for 10 cycles can be seen in Figure 4.
w1
w2
SMM Iterate Values
w3
0.8
0.4
0.2
SMM lterations (10 Cycles)
Figure 4: We run SMM iterations on the toy example by solving the projection problems using an optimization solver.
C.2 EXPERIMENT DETAILS FIGURE & MORE RESULTS
Here present the experimental details of Figure 2. We also provide omitted results related to it. Then, more importantly, we extend our experimental setups beyond the cyclic task ordering and the fixed total offline dataset.
C.2.1 EXPERIMENTAL DETAIL
Data Generation. We carefully design three 2D synthetic datasets. Each dataset (of size 100) is randomly sampled from bounded support. Below, describe the data distribution from which draw samples. Note that the label E (=1} uniformly randomly sampled before sampling the 2D input points.
18

---

Published as a conference paper at ICLR 2025
Task 0, æly +1: Uniform distribution round disk (i.e., inside of circle) with radius 0.9
and centered at (0.6, 4.5).
Task 0, zly = 1: Uniform distribution on rectangle [0, 1.5] |-3.9. -2.7].
Task I, æ 1: Uniform distribution round disk with radius 0.75 and centered (5.1,
Task 1, øly -1: 1: Uniform distribution on rectangle [-4.2, 2211] 1] x [-0.9,0.4 0.9].
Task 2, æly = +1: Uniform distribution on rectangle [0.6, 3] [0.6, 2.7].
Task 2, x = 11: Uniform distribution on disk with radius 1.2 and centered at (-3, 2244.
Among all 300 data points, we randomly choose 3 points (one for each task) and replace them by (æ (1.5,-2.)
-1) (for task 0), (ar (-2.1, 0.9), y -1) (for task 1), and (ar (0.6, 0.6). = +1) (for task 2), which are the points included in the support of the data distribution(s)) These three points play the role of supporting vectors so that the joint max margin direction becomes separable).
where the size of maximum margin (Equation (4)) is ø 0.6v 0 (thus, jointly
[0
/2' V2
Optimization. We rum sequential GD for 300 stages in total. Since there are three tasks, for the cyclic ordering case, it is equivalent to = 100. The step size we used is r) = 0.1. Also, we allow and conduct K = 1,000 updates per stage. For the joint training case, full-batch GD on the union of all datasets for MJK = 300,000 steps.
C.2.2 OMITTED Loss CONVERGENCE RESULT IN FIGURE
Although we only displayed the directional convergence in the main text, we also observed the loss convergence to zero, which proved in Theorems 3.1 and 3.3: see Figure 5. Note that depict the loss values for a jointly trained model (with full- ball-batch GD) every K = 1,000 gradient updates, for a fair comparison with continually learned model (with sequential GD). It is omitted due to space limitations and being relatively more obvious than directional convergence.
Lost:Conkin
Losz:
back
baik1
brkk lons
total lzaa
5ocal loaa
10-1
10-1
12"
(a) Losses of continually learned model
(b) Losses jointly trained model
Figure 5: Loss convergence results for cyclic task ordering. The joint training loss is divided by the number of tasks in order to match the scale.
C.2.3 RANDOM TASK ORDERING
In Section 4, we theoretically showed that loss convergence, as well as the implicit bias result, holds almost surely under the random task ordering- Indeed, observe similar tendency of directional convergence and loss decrease even under the random task ordering. The result is shown in Figure 6.
C.2.4 BEYOND THEORETICAL SETUP: TOWARDS CONTINUAL LEARNING ON ONLINE DATA
Most theoretical analysis in this work exploits a structural assumption on the data points: there is a pre-defined set of offline datasets, which is divided into chunks and accessible one by one at each stage. Thus, exactly the same batch of data is guaranteed to be reused (surely or with high probability). Can go beyond this repetition and apply theoretical intuition more general setups?
19

---

Published as a conference paper at ICLR 2025
Angllst VIL
beloren Linear Model jenn Nas-laarg
Cantin cilly tankddmooi
Taus PaL.BBaaa--
10P
sage
(a) Data points and trajectories
(b) Sine angles (the smaller the more aligned)
Lone: Continusly leamed model
Loss: leamnd model
33"
1axtd tro
1stal 191s
Iotial bose
107
34
10
250
200
220
100
150
300
Stage
2age
(c) Losses of continually learned model
(d) Losses of jointly trained model
Figure 6: Experiments on 2D synthetic data under random task ordering.
Here, we demonstrate that the results of our theoretical findings are not really limited to the task repetition setup. Instead, our insight about jointly separable continual linear classification applies to several general setups. In this section, we showcase an analogous behavior of sequential GD when the total dataset is no longer fixed throughout the continual learning process. We consider the setup where there are M different (jointly separable) data distributions, rather than datasets; every time we encounter task, we have access totally new sample of data points drawn from the task's s distribution. For simplicity of visualization, we still stick to the bounded support cases.
An implementational difference from the previous sections is that we resample the data points from predefined data distribution at every stage. Another minor detail is that we no longer fix the three support vectors mentioned in Appendix C.2.1: thus, at every stage, never reuse the same data psint(s) from the previous stage, almost surely. We test whether a similar trend happens even when we add the resampling process, under the same data distribution described in Appendix C.2.1. The results are shown in Figures 7 and 8 for cyclic task ordering and random task ordering cases, respectively.
C.3 TOY EXAMPLE FOR INCREASING LOSS IN A CYCLE
Here, we give toy example that shows temporarily increasing joint training loss during a cycle, even with small learning rate.
Let the datasets D; (i = 1,...,5) 5) be as follows. We choose all labels as +1 without loss of generality, hence we omitted them.
Di ((1, D2 ((1,)), D3 (1.1, D (111,222)) D; = ((11,2.33))
In this case, the max-margin direction is (1, while most of the task has their individual max- max-margin direction around (1,2). We set K = 10, 17 = 10-6 so that satisfies the learning rate condition.
When task 1 is being trained, joint training loss increases while it decreases when other tasks being trained. This is because most of the tasks have their own max-marge margin direction around (1, 2), dominating the joint training loss.
20

---

Published as a conference paper at ICLR 2025
Anglls VIL
belwwen Linear Model jenn Nas-laarg
Cantin cilly tankddmokk
worrraadde Texe DecoOeeeee
Taas cilioaaaae
Tack Diia
301
sage
(a) Data points and trajectories
(b) Sine angles (the smaller the more aligned)
Lone: Continusly jeamed model
Loss: learned model
1axtd tro
bac Inso
total leve
22-1
Iotual bose
10
3 23-
10
18a
1
250
258
220
100
.20
250
300
Stage
Siggs
(c) Losses of continually learned model
(d) Losses of jointly trained model
Figure 7: 2D synthetic experiments: Cyclic task ordering..jinnt separable online dataset (which is drawn an online/streaming fashion from a task's predefined data distribution).
C.4 EXPERIMENTS WITH NEURAL NETWORKS: BEYOND LINEAR MODELS
We explore the possibility of extending our theoretical insight to nonlinear models, in particular, wide two-layer ReLU networks.
For linear classifier with single linear layer, recall that we already verified that the sequentially trained model (in cyclic/random task ordering) directionally converges to the max-margin direction. However, it is more difficult to analyze and visualize the dynamics of the multi-layer neural net's s parameter values. Moreover, it might be nonsense to discuss the relationship (e.g., aligmment, directional convergence) between the max-margin direction and the parameter matrices of neural net, because the parameter matrices themselves no longer have a semantic meaning in the data space.
Instead of inspecting the parameter values, move our attention to the decision boundary of the model. Observe that the decision boundary of a linear binary classifier is a hyperplane (i.e., d - 1 dimensional subspace) of the data space (of d dimensions), whose orthogonal complement is the span of the classifier's weight vector. Thus, the alignment between the weight vector and the mar-margin direction (i.e., the implicit bias guarantee) is semantically equivalent to the alignment between the classifier's ' decision boundary and hyperplane determined by the max- max-margin solution as a normal vector; this hyperplane can be approximated well by jointly training a single-layer linear classifier. Thus, we can still verify the similar idea of implicit bias even for neural network by observing, not only that a continually learned model (with sequential GD, under task repetition) eventually classifies all the data points correctly, but also that the decision boundary of the continually trained model getting similar to that of a jointly trained model (both starting from an identical initialization). Although cannot exactly characterize to which set of points a two-layer ReLU net's decision boundary should converge only with our theorems, gives an effective and efficient way to confirm findings beyond simple linear model.
To intuitively visualize the decision boundaries, we again use the 2D synthetic datasets. Most of the experimental setting is the same as in Appendix C.2.1, except for the following three differences:
21

---

Published as a conference paper at ICLR 2025
Anglls: belwren Linear Model JarE tanoediook
Jane uPE
wrrrradddr Tau CiLLA
Texe
10:1
10P
367
sage
(a) Data points and trajectories
(b) Sine angles (the smaller the more aligned)
Lene: Continusily jeamed modell
model
1axt0
Total l9re
22-2
Iotial basa
g33
30a
250
208
220
100
250
250
300
Stage
(c) Losses of continually learned model
(d) Losses of jointly trained model
Figure 8: 2D synthetic experiments: Random task ordering, jointly separable online dataset (which is drawn an online/streaming fashion from a task's predefined data distribution).
400
1000
(b)
50000
Figure 9: We take average on total loss(black) for better visualization. The current task switches every 10 iterations. One cycle consists of 5 stages. Figure (a) shows the case where task's loss increases within a cycle. However, it eventually decreases as Figure 9(b) shows.
1. The classifier's architecture is a two-layer neural network Se R= + consisting of dimensional input, 500 hidden ReLU neurons, and scalar output:
fo (x) w RcLU b,) + d2.
where 0 (W1, by W2 b2) R 500x2 x I. 500
T 500
R and ReLU(v); = max(w; 0}.
2. To make the total dataset non-separable by linear classifier with positive margin but still classifiable by a neural net, we translate all data points with positive labels (+1) by a vector (-1.2, In this case, the decision boundary should not be straight but bent in a curly L-shape to effectively distinguish two classes.
3. To prevent the sequential GD from behaving similarly to a mini-batch SGD with small-scale and lazy updates, increase K to 3,000 to guarantee that (1) the jointly trained model can
22

---

Published as a conference paper at ICLR 2025
correctly classify all data points within only stage (i.e., with initial K updates), and (2) the continually learned model gets sufficiently trained on specific task at each stage. As a result, the jointly trained model takes MJK 900,000 iterations. (M 3, J = 100)
As did for linear classifier, we classify the input data as y = +1 if the model output is positive and as -1 otherwise (thus, the decision boundary is a level set (ær E TR? f) = 0}). We again use the usual logistic loss N Ei= ((veJo(x:)).
bed Goandery
turdaa Doundery
Dacoior deandry
die caae
Taxk Data
Task Data
Texk Data
Task Rata
At the end of the first stage.
(b) After running 300 stages.
Loss: Cont muwly leamed model
Loss: joirtly learned model
c2000 lsss
10-1
13540 loss
tank
tand2
16-
30-1
16-1
16-4
20-1
16-4
12.4
10-1
300
152
200
253
300
52
102
110
202
250
300
Stage
Stage
(c) Losses of continually trained model.
(d) Losses of jointly trained model.
Figure 10: Two-layer ReLU network experiment under cyclic task ordering. (Top.) Each subtigure displays the decision boundaries (and other auxiliary level sets) of jointly trained model (dashed red line) and continually trained model (dashed green line). (Bottom.) Figure 10(c) demonstrates the large amounts of forgetting at the initial few cycles and convergence of loss and ayylle-veeraged forgetting to near zero. On the other hand, Figure 10(d) shows that the training loss of the jointly trained model is already small (e.g., less than 10-3) at the initial stages.
The result of the experiment for cyclic task order is visualized in Figure 10, exhibiting decision boundaries of jointly trained model and a continually trained model (with sequential GD). As we expected, the updates are aggressive enough so that even a single stage (i.e., initial K = 3,000 iterations) is sufficient to perfectly classify the total dataset with the jointly trained model, and the same for the dataset of the task 0 with the continually trained model (Figure 10(a)). After some number of stages (Figure 10(b)), both models not only correctly classify every data point, but also have an almost identical decision boundary (note that the other level sets are not necessarily the same), implying that similar phenomenon like implicit bias is happening here. We also observe almost the same tendencies under random task ordering and even for non-repeating dataset cases (Appendix C.2.4). We omit their detailed results from the paper, but one can find them in our supplementary materials.
C.5 EXPERIMENT ON REAL- WORLD DATASET
In this section, we present result of the training linear model with CIFAR-10 (Krizhevsky, 2009).
23

---

Published as a conference paper at ICLR 2025
We choose two classes from the CIFAR-10 10 dataset and design 3 tasks that have 512 data points from the two classes (" f'airplane' and "automobile") ) Our Theorem 5.2 on linearly non-separable data like CIFAR- 10 shows that sequential GD iterates should not diverge and instead converge to the global minimum ur under the properly chosen learning rate. To estimate the distance between sequential first train linear model using joint task data and obtain Woint as a proxy of w"; we do this because offline training is guaranteed to converge to the global minimum. Then, we train sequential GD and measure the distance between iterates and the jointly trained solution Woint at the end of every stage of sequential GD.
GD iterates and the global minimum,
203
2008
1000
(a)
(1) K
(b) Loss of jointly trained model
Figure 11: CIFAR-10 Experiments with linear model. We jointly train model for 200000 iterations to achieve the global minimum. We then train each task with cyclic ordering. We set the number of GD for each stage as 50 (K" 50), and run 1350 cycles (J 1350). Figure 1 (a) shows that sequential GD iterate converges close to Woiit as the training goes on. However, does not fully converge Wointt Joint not equal to w". Figure 11(b) reveals that the loss of the jointly trained model was decreasing after 200000 iterations.
As a result, we observe that the distance between sequential GD iterates and Woint converges close to O, even when we adopt learning rate 7 0.01, which is not as small our theorem requires. Yet, we couldn't i show convergence of distance to exactly 0 since the jointly trained model did not converge all the way to w".
24

---

Published as a conference paper at ICLR 2025
D PROOF SKETCHES
In this appendix, we provide proof sketches of the main theorems of the asymptotic and non- asymptotic convergence under the cyclic task ordering. The proof sketch for the random task ordering is omitted, as the asymptotic loss convergence is straightforward, and the directional convergence can be established in much the same way as for the cyclic task ordering. addition, we include proof sketches for Lemma E.5 whose proof is particularly intricate and challenging to follow.
D.1 ASYMPTOTIC Loss CONVERGENCE (PROOF SKETCH OF THEOREM 3.1)
Since a m function, we get
L(wo L(wb (M)++M) L(wb) (Att))
maxe
(M++M)
(MJ)
Wg
w00
2
I <VL(wb ( (ee)) (Afs+M) - wh (1)))
< VC(2 ( || + V (M3))
(Mj+M)
w ( + 1 ((w
(Mj)
1
for each j-th cycle (j 2 0). Since the term
w
(M++M)
w VKVL(wW) ( is bounded
(Ms)
above by factor (in j) of v V
|||
(Lemma E.2), we have a form of descent lemma,
L(wb L(ww) (Mis)) - -nj (1 nK3) (
(12)
for some B' (0, ) Therefore,
L(wo))) (0) 1)((1 - kK 00.
Σ V V(ww (M3)))
Again by Lemma E.2, the term
v ( (+t)))
is bounded above by a constant factor (in j) of
v vl(w (3)) which leads to the following convergence of an infinite sum of non-negative terms:
20 M-1K-1 ΣΣΣ
VLw Vll Mi+m)) || < co.
1=0
R=0
This implies Vk E [0 K 1] lim
v (ww (1) = 0. Finally, Lemma E.1 leads to
t000
lim (x w = 0 for all l E 10: K-1] Equivalently, x. w + oc.
1-000
D.2 DIRECTIONAL CONVERGENCE (PROOF SKETCH OF THEOREM 4.2)
First, for each & E [0: K-11 1], define Pk (t)
and
r
(*) as
w (t) In (t) w + Pk
(0)
In (t) ④ +
KK
+
M
(t) m,,k + T
M
K
where v is the joint & max-margin solution (defined in Equation (3)), i is the solution of
Vi E S 17 exp
(-z, w) = ag P(w w (0) = 0.
and m,, is a vector defined in Lemma E.4 in detail. Then by definition, the following holds.
1
mn (1)
k
K
M
K
In
M
K
i + my,k
i
(13)
25

---

Published as a conference paper at ICLR 2025
M w K
(t)
Σ
Cg
k
Σ
a,s'
K + zo. (14)
eE
#ES
To show the boundedness of Pk is enough to prove the boundedness of r v is constant vector and My,k converges to zero. From the fact
(8)
K++
rk
(2)
2(r
(1) k+1
rk
T
(0)
rkt - 1/011
(0)
we get
(1) ro
ro
ΣΣ
1- K-1
2
TT
(1)
ΣΣ
[-1
p r/ 11
(15)
According Lemma E.5, the first term of the right-hand side of Equation (15) is bounded. By Equation (13),
T 1
T K
r k+1
(1)
w k+1
w
(4)
M
(mi,k+1
mcN)
K
imt1 0=0
(=11
(1)
M
k+1
wk
K
(m m((,))
t= k=
1= k=0
+ 2
T K
w
(t)
w
2
Σ
T K
(m,,k+1 -ma,k)
K
t=
k=0
k=
We use the Cauchy-Schwarz inequality for the inequality.
E kk=
(0)
k
k+1
and D E || M (m,,++1 m are bounded as consequence of Theorem 3.1 and Lemma E.4, respectively. Therefore, the second term the right-hand side Equation (15) is (0) is bounded.
bounded. It concludes
D.2.1 PROOF SKETCH OF LEMMA E.5
From Theorem 3.1, Vi e 1 w (t)
+ Thus for sufficiently large t, Assumption 3.4 gives re "e-""" "[""(
[x W (1)
Also, since m,, converges to zero, for a sufficiently large L, m
K
M t) + i mi,k rk In( K [0:
( In(
M f) + i +()
M
K
By Equation (14), for all &
K - 1]. get
(1)
(t) (t)
(t)
M
Σ
k = 2 k+1
w
CgIz
Kl
SE
=n Σ
E' { w k
I
Σ
a.E.
Kt
SES(()
= Σ
(a
w
(1) az
Σ
ne (n un
(1) +
Kt
M
0g
Dgg-
Se 800
SES())
Hence,
(rl)) (1) (t) --1
Σ
C( w
(1)
a Tk
(t)
(2 w
(1)
+
M
a2
x, rkk
(1)
Kt
(50)
SE
(16)
26

---

Published as a conference paper at ICLR 2025
The first term of the right-hand side of Equation (16) can be upper bounded as below:
7 E
un
Ja
exp
In(
K
1)a
x.
x. x (0)
n. 1k
M
(() ( g(
2, % 50
K In(
$ 17
Σ exp
t)
xg O(t O)
(17)
M
SE/ a. e_r(0>> >0
where in the last line we use the fact Vo 2 0 x exx((xx) 1, and Vs 1(0) (5000 xx] w 2 0.
Now we examine the second term of the right-hand side of Equation (16),
Σ
1 (a. u
(2)
M
Fg
k
M
exp
(-wn rk - x r
Kt
Kt
SES(S)
#ES())
Set j min 1M_ 0.25). where M4+ p is defined from Assumption 3.4. We analyze each E 5()) by dividing into cases.
0 < x.Tr 0.5p.
M
(1) T(())
x.. T. (1)
0g 0(1-10055))
Kl 0g
exp
2t TK -
2. if 0.5.
< xg rk
(1) 0:
Kt 02
M
exp
x (r(((
T (1)
x
Tk
(1)
M
a2
exp
x r/ (1) }
x r
Kt
M
T (8)
x
rk
Kt
3. if -0.50 xx. TTTT (t).
((())
Kt a,
M
exp
(1)) (-x, rk -1
2g rk
(1)
<
M
[exp (-t (-t-0.51) 11] x, Tk
Kt
<
OAa [1 -0.5
0.5g
+ PP] x. rk
K7.
where in the last line we use the fact Vr I 1 exp x S + x + x.2 Since -t -t-----00 0.5f -055 decreases to zero more slowly than the other term, the last term is negative for sufficiently large l.
4. if x Tk < -t-00.p
x. r(k (1)
Since x rk < 0, exp
> 1 holds. Therefore
M
x. r1
(1) x rk <0. 0.
Kt
0ss
exp
To sum up, there exist C₁, C2 0, 2 max(t_,t_ such that for all t 2
(r - r rk s C1t 0 + Czt --1-1-0-00 1-555 Vk E [0: K K-1).
D.3 NON-ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PROOF SKETCH OF THEOREM 3.3)
The analysis Appendix D.I can be extended similarly arbitrary cycle number. That is,
Vj JJ L(w) (M MM+ S L(w (Mi)) k (1 - k 33) (ang
Thus by applying Lemma E.9, we obtain
2 Σ nk (C(vo) (M)tM)) L(x))
21 Ko Ko
Σ
(C(ub)))) C(wo ((woM)+a)))
- n. 62
K o 8)2
1 - nKB
j-0
5
27

---

Published as a conference paper at ICLR 2025
w - = x|² 1 (M -
(18)
for any 2 E IRd Thus
J (C(wbb - ((x)) + 80 nk (E(uob L(206"))
$ 2
nk -((x) +
8q
nk (C(uef - -((ob)
2
Σ
1-1
TyK (E(u0b -(())
80
n
J-1
L(wnb (22))))1))
5=0
5=0
2
Σ
nk
- -[(z))
M Ko
m 3
nk
(f(wg
(1 nMKo Ko m
8)
nK
1=0
1=0
(0)
12
100
(MJ)
(19)
where in the first and second inequalities we use the fact that L(wn) (M)) min KM 2k }. Re-arranging gives
decreasing and <
(0)
40 max L(wr)))
w
[(w) (MJ) [[(z)+
6²
2nKJ
Let == v IJ)..). Using L(w (n(o)) S 11] ((I((M))). we can obtain O ((m)))) upper bound for the training loss.
28

---

Published as a conference paper at ICLR 2025
E PROOFS FOR SECTION 3: CYCLIC TASK ORDERING, JOINTLY SEPARABLE
For simplicity, we set = 1 for all i E 1 = [1 N] in the proofs, without loss of generality. If not, we can convert every data into (æ Di) (y; +1) by "absorbing" the original label into the input.
E. ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PROOF OF THBOREM 3.1)
Let restate the theorem here for the sake of readability, whose proof sketch is provided in Appendix D.1.
Theorem 3.1. Let {w) 1ke(o-K-1):120 be the sequence of GD iterates (2om any starting point
y where tasks are given cyclically. Under Assumptions 3.1 and 3.3, if the learning rate satisfies o²
(0)
n
2K mus (Mo+)mes) then
1. Loss converges zero: lim (0) ) 10: 1/.
2. All data points eventually classified correctly: lim yau w (1) xc, Vk [0: K 1],iE..
K-1 3. Square sum of the change of weight is finite: Ei= =K= w (2) (0) 11 xx.
Let us recap some notation regarding the dataset and loss function. The training loss task m, C = Eie {y w), is -m-sth for 3m == 3Amax (X)X where Xm E dx Im is a data matrix of task m consisting of columns {æ; : E I. Let 8max = maxme]|uM 1] Am by definition, 8max S 30 S (0:M) Bm holds.
In this proof, we rely on the key property of linearly separable data. Lemma E.1. Suppose that Assumptions 3.1 and 3.3 holds. For any w E Rdd
[L((w] Φ 1
Σ (e w)]
Proof. See Appendix E.1.1.
Also, we use the following lemma, which holds in cyclic continual learning with M tasks.
Lemma E.2. Suppose that Assumptions 3. and 3.3 holds. Let any E N, m 10 M 1]. (0:
K - 1). Then, if we choose the step size as 1) < [mK tk)omaos we have
(14m) w
VC (w (0) L (1+m) (w (0)
we
+1
1=0
17 (mn + K
5
VL(w (2)
11
nmmkk + k)o 31
(o(emm)) - -00
5
VL(w (2)
$11 - nmnk k
(e (tmm)) VC(wo
nKo o
VL(w. |||
$11 7[[nK k)o
Proof. See Appendix E.1.2.
0 3 3-smooth function, we get Since L is
a2 maxx
L w (M))tM)) L (wo())))
(Mj+M)
(M5)
w
2
v C(w (Mi) (20 (M++M)
(0 (MO))
w0
VL (w0 (13)))
T (Mi+M) wi
(M1)
(wb (()))))
-KKV (wo) (M)))
+
29

---

Published as a conference paper at ICLR 2025
< <nnK VL un
+
u0
(
|| L0 (MM wm w + VV (
By Lemma E.2,
[(wb) (( - [((ob
0 max B
(170 K)²
VC((o( 12
2
7 K o maxx33 3)2
< VC(2ub 6
>2M max
VC(eu( ||?
6( - -nMKo
F 3)
o
Given that 17 S 2
[(w0) [(w0) (M)++M)) - L(wb (
M max! 3
max 3
} (((( 12
S S-nk 1 n
Φ(1 17 n KM 2
max 3)
20² - n. K o 3)3
1 (1-nx- nk 2M + m moma
V V (M51) |?
--nK
d2
= =-n (1 - 33 V ((
(
(20)
where we set B = 2 m
Given that 17 < KB L(wb (M < L(un)M)) holds.
Note that KB
< 2MKo max
because, in the proof of Lemma E. we can show that
Φ S
min
Xxll S
max
|| X S max
VE R
2o:10=11
VERS 1ER8o:1o|1=
Also, by Equation (20),
2 [(20b (1)) - liim 00 L(w0) (M5))
[(we) (0)) K1 k)K
Σ
/|²
< 00.
nk(11 1) K (3)
Coupled with Lemma E.2,
M-1K-1 Σ 1= 0 K=
V Vl (Mj- ()-m))| ||
K-1
C/(an ( || + V ( (M)tm)) VL(w6 (15) 2
j=0
nKom 3 mm_KK
( 11?
1
21 811 nmnk + k)) 93
j=0
1) i max
20 MK Σ j=0
V (Mil)
<0.
Φ1 - Ko 2
(1) 1| = 0, Vk E k
The boundedness of infinite sum of nonzero elements means lim V
[0 : K - 1]. This leads lim ('xx] (()" 0, E 1,k E [0 K 1] by Lemma E.I
Since ('(x) + 0 only when - co, we obtain or w 00, Vi E T,k: E [0 K - 1] and
lime L(w = O, Vk E [0: K 1]. Finally, we obtain that En ΣK=1 w a+1 - w
(t) (t)
co followed by
v v( (1)
2 Φ
Σ sel
e C(oTT T w
2
Σ Egr())
((xTTe((1)))
V
Σ
(1) L' (x) w )a,
(t)
w//l|
B..
Bmn"
k+1
where we use Lemma E in the first inequality, while we use the fact VY, E R
||Erer 2 <
Tiax v Ever X2 in the third inequality. The last equality is true by the definition of gradient descent.
30

---

Published as a conference paper at ICLR 2025
E.1.1 PROOF OF LEMMA E.
Let us recall the statement of the lemma for the sake of readability. Lemma E.1. Suppose that Assumptions 3.1 and 3.3 holds. For any R.
[
Σ SET
(2) w)]
Let any E Rd. Observe that if we let o' R.y be vector whose i-th entry is (x, w), then
-V[(w) Xe'. Because of this,
[V[(w)] ||xo111
||001l
min
|Xel
VE 2o-1oll
(x) w)]
min 1e
|Xv|.
RE
Let é == arg vin 111l= bll
X
Then for max-margin direction úi, the following holds.
X
X
6
=
|
We used Cauchy-Schwarz for the first inequality and the definition of i for the second one. This concludes the proof of the lemma.
E.1.2 PROOF OF LEMMA E.2
We restate the lemma here for readability.
Lemma E.2. Suppose that Assumptions 3.1 and 3.3 holds. Let any t E N,m m 00 M - 11, [0:
K 1). Then, if we choose the step size as 1) <. [m [mK+K)ommad
have
Wg
(t+m)
(1)
+1
K
(((+)) (wo (1) AV AV (++m))
(w0 (0)
1=0
2 (mK + KijKo
VL(W (2)
$1 1 n(mk k) 31
w wi
m++m)
(4)
nKomax
VC(w (2)
+11 - 11[k + k)
nk B
v V
((tm))
vL(wo)
VL(Ww
$11 1[[nK k))
To start the proof, observe that
12 Tm-K-1
(t+m)
(t)
Σ
v (10
(((+)))
(wn (w0 (ttm))
w
wi
-1
0=0
for all t 2 0, m E [0 : M]. k [0: : K]. Using this, we can deduce the following with Brax smoothness and triangle incquality.
(w) (t)) + A. ( (((mm)) (w)b)) (1) (wb5))
w (+m)
with + m
K
0=0
(((+))) (t)) v ((( (c
V ((0t-m)(zo(")) - (((+))) (w ((tm)))
+
(w) (20 (++1))
)
v (zo ((((m) (w (2n(tm (0+ml)))
100 hmd
31

---

Published as a conference paper at ICLR 2025
S 1/8mxx
m- 1 K
Σ
w
(1+-)
Σ
R-1
w
maftmmo))
(21)
F=o h=0
h/=0
Moreover, using the fact VYg E R: Eser dot 212 S mmax v Exee N..
m++m)
(A)
10
w
17
K
m
V
(wob
AV AVC (co6")
k=
m-1
10
((mm)
+1 wi
(1)
k
V L
(((+)) (1m) (1)) xV ((+mm) (uob (1))
1=0
K m-
< rj
l' (xx way
yo, )oe
(0)
(xx wo yas
)
1= r(e+1)
((++m)
m-1 K
w
((+m)
w/" +1
(1)
Σ
VC
(20(()))(20)))) AV C (w)b))
1=0
Σ Σ
1=
(c(((()w)))) )
Σ
(e w!))) )²
1//Tmax
== agr(e+*)
m-1
w
((+m)
woy n
K
Σ vc(()))
AV VV (wo
1=0
S TmKx Tmax
Σ (x] 200))))
w/
(+mm)
wa +1 1
K
(10 (3)) + AV c((tm) (wo (
E1
Thus, by Equation (21) and Lemma E.1, we obtain
(++m)
nKomax
vl(w (1) >|| m
Σ
Σ
w
(+++)
10
(0)
+
Σ
k-1
w
(t+m)
Φ
j=0
(22)
Here, we use the following technical lemma.
Lemma E.3 (Nacson et al., 2019). Let e and 0 be positive constants. Suppose 8n 5 Σk-1 6n
holds for all non-negative integers 1. Then
k0
8v < 1- ke
and
8n < 1 k
1=
By applying the lemma to (22), we obtain
ur 20 10
(t+m)
n max
Vi((n! )
111 nmnK + 1 maxx $7
and
(t+m)
(1)
V (20 (t) - VV
(20 (1)
w k
2000 + 17
K
i=0
m- 1 1- Σ
# --1
< 170 2 3
[jj
((+))
wi
(1)
w
(l+m)
-00 (0)
1=0 1=
==
32

---

Published as a conference paper at ICLR 2025
(mK + Ko) max
[[(2o)))
S - o[1-n(mK + k ) 3}
Finally, by smoothness.
( (+tm)) vL(wo('))
S 0 maxe3 / ((+m) (000
nKon mnax 3
0 @11-n(mk + k)o max 3}
which concludes the proof of the lemma.
E.2 DIRECTIONAL CONVERGENCE ANALYSIS (PROOF OF THEOREM 3.2)
In this section, we prove our implicit bias result: Theorem 3.2. Moreover, we further discuss the (t) beyond its boundedness, under some additional assumption convergence of the residual vector Pk: on the dataset (see Appendix E.2.3).
Theorem 3.2. Let {wh 1kE[0:K-1],42 be the sequence of GD iterates (2) from any initial point
" where tasks are given eyclically. Suppose that Assumptions 3.1, 3.2, 3.3, and 3.4 hold. Then, under the same learning rate condition as Theorem 3, wg
(t) will behave as
a (t) = (n( + Pk
(c)
for all sufficiently large t, where || stays bounded as + DC. Note that we use Assumption 3.2, the unique existence of SVM dual variables a that satisfies
S
Ys E S a, 0, Vs This assumption holds for almost all data (Soudry al., 2018).
$ S: 02 O.
When the tasks are given in a cyclic order, the following lemma holds. Note that the lemma does not depend on the algorithm.
Lemma E,4, When tasks are given cyclic, there exists ıb mi,k E IRd the following holds for all teN, [0: K
1).
K
K
K
Σ
ag +
Σ
Og
In
w +
v + mi,k-
M
M
M
um
SE)(s)
SES
m := m4+100
such that | || -0.5++, and | m,,ull O(1-1) for all 10: K -1), > and u only depends on the order of tasks and constant with respect to t.
Proof. See Appendix E.2.1.
We set mi,k and to along Lemma E.4, and define Pk
and r
as
(1) k
= In (t) ib + Pl
K
(23)
= In (t) w + In
i +
1 +
my + (1)
M
K
(++1)
(()
((+1)
PK Pb
K
r
33

---

Published as a conference paper at ICLR 2025
where w is the solution of
vi 8 exxp (-w) w) 0i.
P(ū-wij w 0,
which is unique under Assumption 3.2. Then by the definition,
(t)
(1)
M
K
K
w
ln
+ + m2,k)
v
K
M
M
(1)
M
Σ SES(s)
ag +
Σ SESUO
0
Kw - 1 + t0.
K
w=1
Under these definitions, can get the primary lemma of T Lemma E.5, Under Assumption 3.1, 3.3, 3.4, and Assumption 3.2, if learning rate is n <
6²
min
2M K3 4K (M }. then
1. 3i, C1. C2 > 0 such that Vt > i
(r Tk
(1) T rk < C,t + C2t-1-0.5p Ak E 00: K - -1..
(t)
2. Moreover, for all E1 > 0, 38" C33 > 0 such that if Pr 2 El and S(() + 0,
(1) (1) (0) (r k+1 rk rk -C 1 8' k E [0 K - 1].
Proof. See Appendix E.2.2. The proof sketch is provided in Appendix D.2.1.
By the definition of Pk it is enough to prove
(8)
rx is bounded above in L. We use the fact
(t)
|01
2(r kir ( r (t)
| 1
to show the boundedness of (2)
For all & E 10: K - 2]. let ax
(t)
M (m,,,+1 m,,x). And let
- = In(1 + })u + K
M
(m++1.0
-m, Since w0! (1) = In ( (K w + w + M
K m,,s + kk
r - (0) = w w
(t)
(t)
Also, by Lemma E.4, a (1) = -O(t-)). Thus, 3t
0%
such that VL 2 4, E 00: K - 1]: 0
(1)
<t1
Now we can get the following for all T 2 tl.
K
T K
(1) (8)
k+1
w 0
0=
t=
k=0
K-1
K-1
T
K
w k+1
(1)
urk
(1)
2
k
(t)
w
(1
(1)
a
(1)
a
99
k=
t=) k=
K
K-1
K
(4)
(t)
(4)
(0)
(8)
1 k+
w
+
k
a
1=t1 k=0
1= k=
1=h
k=
K-1
T K-1
T K
W
w
(4)
+
(8)
w
(1)
2
ΣΣ
t-2
2
t=
K=
1= k=0
k=0
t=
k=0
< OC.
(24)
We use Cauchy-Schward inequality for the first inequality and the factor that Et=, 1-2 <
00 and
Eie,, KK
wx
wk+11
(t)
< 0o by Theorem 3.1.
34

---

Published as a conference paper at ICLR 2025
Combined with Lemma E.5 and the fact that Vc 1: Et 21=1 to
D0, we get
| x 11
r
|++
2(r
r/ TT (()
- <00
hence
(0) rk
is bounded.
E.2.
PROOF OF LEMMA E.4
+ k
K XΣ
Σ
Cg
ag
SES(s)
NES(!)
1 JM
K
Σ
ag KK
Σ
1
1 Σ
agıs
+ k
ag
8ES(M)
[ M+1 SES(u)
eES())
m
M
M
K
CgIls + m',
u 8ES(M)
K
Σ
Σ ag
+mii
+ M(u 1)
(ES(v)
M
ar sES(")
Σ
ag
+ +mi
M u - 1)
Note that m i and m¹, - m4, n are both 1t for all & E [0 K -1]. For every e,
Σ a,
#=1 + M(u - 1)
(ES(v)
1- M7
Σ agat (ES(v)
Mu
Mu² (v M)u
((=-11)
) +
1
In
Σ ag
M
M
Mu + (u M)u
(ES(e)
In
[-- +7 +7+0(14) +
1 1 2
Σ
a
M
M
Mu² + (v - M)u
SES
+
1
In
+
M
MM
Mu² + (v - M )m
8ES(e)
where, in the last three equalities, we use the fact
1n
35

---

Published as a conference paper at ICLR 2025
In (t) - In ([(]t) O(+ In (1) ln (1 (4- ((1
where y is the Fuler-Mascheroni constant. Since S S M, the inequality Ma'+(e-M) 1- Mu-+ converges with rate O(L-t).
1-
1-#
holds. Therefore, the series En,
1
V M
1 M
30
M
Mu² + (v M)u
Mu² (v
M)U
Mu
(v
M)u
-
H+1
1- M
+0((1
Mu²
(u M)u
Hence,
K
Σ
U M(u- 1)
(ES(())
K
In
t
+7)
Σ
K
M
1 -
Σ
0,Iis
mmm
M
M
Mu + (v - M)u
WES
(ES(m)
K
In
t
+
K
80
v 1
M
Σ ag
+ m"
M
M
Mu² + (v M)u
v=1u=1
(SES(o)
K
K
In(
i +
ib + m",
M
M
M
where w = γu + M EM v= E Mu Tu (E agts). and || 1(
Finally, for all As E [0: K 11, let
mi,k == K
ag + k
Σ
agts
K
In 1
K
M
M
M
SES(u)
aES(S)
and
My,K == mc+100
Then ||m,,all = |m + mx
= Ot 1), and
|m mm,e
Σ as
=0((1), (k= 0, K - 2)
SE)
m4+100 - mi,k-1ll=
Σ
ag
In(1 + t 1) = ()
t
M
#ES(O
E.2.2 PROOF OF LEMMA E.5
We use Assumption 3.4 here. That is, there exist positive constants (44; p__ and such that Vu > u
(1 exp(-uu < (l((w) < (1 uxp(
By definition,
vk E [0: K
1]: r(()
w (1)
M
K
k u
Σ
a. + k
Σ SE8(0
a,
In KvØ w + +w
K
S
36

---

Published as a conference paper at ICLR 2025
(0)
(t-1)
00
Then for all lo E 00: K 11, we get
(1)
(8)
(t)
(e)
M
kk
w k+1
w
Oxgi2
Kt
SES())
1 Σ
l' (ar 2 DE
(1)
M
0g
Kt
SES())
Σ
(x. T wk
(1)
ax
Σ
(n
w/
+
M
as
Ds.
Kt
SES(
Hence,
(1)
(t)
(8)
TK+1 Tk
rk
=-
Σ
(x w
(t)
x Tk
(t)
Σ
ne
(1 w
+
M
0g
x x(
(8)
Kt
SE sE7(0
SES())
Σ
In
K
M
x. mi,k
+ Iz T
+
I.
T
Tk
(1)
2, Tk
(0)
(25)
K
ne'
In
M
K
M
x.
m
x w x r/
+
Kt
M
a,
x. x.r r.)
(8)
(26)
#ES0
The behavior of each term can be analyzed when stage is large. To achieve this, we first characterize five stages.
t = tt Vt 2 vK 0: K 11,
w a}
46 = min
14 2 VK E 0: K 1],V&
W 2 0}
4 = min [t' 4 14 E [0: K T. exp
K v mi,k
2
is = min 2 2 34 44 00 K 11, expp
K a, m
tg = min (t' 4
44
00 K 11, exp
(-p x w (1)
Such ts ~ tg exist since vs E 1, 44 E 00 : K - 1] lim x. w
(t)
0o by Theorem 3.1, and
vk E [0: K 1] lim | ||l by Lemma E.4.
Then for all f 2 max (ts, to t7, tg to). the first term (25) can be upper bounded as below:
Σ
Eα w Tr rk
< -
Σ
((xx w (t)
j x (t)
8E S00
(0)00
Σ
(1+expl exp(-xx440 _ () exp( x w
(1) (1)
Ja T
In 1
ts
$Erl0) =. (()
I1
2 exp
In
K
x
T i
M
x
mi,
x.. _w xT (1)
t2
M
K
(E)(0)))0))
... (1())) (000
<
Σ
20, exp
(-lm In
K
T 1
M
xx
T
Mirk
xr.T x r
(2)
(27)
M
K
(90) xx. (0)(0)00 >0
37

---

Published as a conference paper at ICLR 2025
S Σ
20x exp
-In
K
w
M
x
mi.k
(28)
M
K
(g) 2, rh >0
K M
4a, exp
(-In In
x
t 4
sE/(t)
(1)50) =.rr 12
(29)
Kt
0
$ 4NNamxxx ax))
(30)
M
where in (27) we use the definition of w. in (28) we use the fact Vu 2 0 x exxp( S 1, and in (30) we use Vs E ((t) (((() 2 w 2 0. Now we examine the second term (26). Given 2 fg. it can
be divided into two cases.
(1) (x, w 2 Tk
+ exp(pxpppppppe 14104 w (1)) [x-expp-H-_0 w0(() (t) exp(- w
exp( exp(-xx x
w
rk
if a Tk >
(1)
S
(1)
Jx
(1)
if o rk <
(1)
For each E S, define A as
+ exp( - M4
w
(0)
x r > 0
(1)
1, ==
exp(
p (-p
x w (0)
if i r/ S
(0)
Then, we can use
(xx T w0
(1)
jar (1)
< A exp(-ar.) w )a rk
(9)
in any s S,
10: K 1]. Therefore the second term (26) is bounded
Σ
Ne' In
K M
M T
xx _. x, xr((
M
(0)
my.k
0ta
K
Kl
$ES()
Σ eES())
7A
b exp
(4)
(-In
In
K
t
M
v2 mi,k -
T
w
x,
T
Th
Kt 0s
M
M
K
Σ
(1))
5.k Kt
Mas
cxp
M
K
x. mi.k x. r/
Kt a2
M
x. rk
(1)
SE
Σ SESIO
M
A exp
(M K σ mr.k
xz T (1) rk
T (t)
Kt
0's
x
r
Now we analyze each E ((() by dividing into cases. Note that
R σ m = o(u5t.5+c) for all
M
e >> O. Therefore if we set j min(p+. p_, 0.253. then x mi,k = aa)
if if0 x
xTT
Th
(1) S
Stt
0.5p.
M
(1) s,k
M
(1)
T (t)
0
exp
x. 8 mi.k - 1 rk
x rk
Kt.
K
M
02
eexp
M
KK x. T m4,k
(1) xx7 rk
x B
(0)
2 to
Kt
M
Oig
cxp
(-xxT rk
T (1)
- xx. x( (1)
2 47
Kt
4MCCT
<
maxx.))
-1100.5
K
The last inequality holds by the case condition 0 - TT rg < C71-0.50
38

---

Published as a conference paper at ICLR 2025
2. if -Cy--0. < xg N.T (1)
k
50:
M
A
M T
Iz xr.r(()) - 1 x.TT r(
0g3
exp
x m
Kt
K
M
03
A s,k exp
(-x
M
T
mi,k
Fg (1)
) [ (0)
Kt
K
Kt
M
as
k
(1)
S
Kt
M
as
Cyt
MCr t -0.5
1 a
K
3. if O-5-0.5 0.5p x. T
Here, we first examine (1)) a,k-
3, = + exp(
2 wk (1)
= 1 + exp
-/+
h
K
M T 2g m,,k + +2, 20 + xx rk
(r(( (1)
M
K
K
M
S 1 + exp
-14
In
x: T m + x. 10)
M
K
K
< 31+ + 2 exp
-44
In
+ x 2
M
S1+ Csl
Therefore,
M Kt
OO'
A e
exp
M T
K F. m
(1)
2g r
(t)
M
as
+ Ost
exp
M
F2 mi,k x Tk
(1)
x rk
T (0
Kt
K
Kl as
M
(1 Ogt exp
M
K F mi,k -0.50
8 rk
(t)
(31)
Since t 2 17.
K æ
M
m S 1. Now by the fact Va S 1: expx S 1 + x x2,
M
M
M
exp
(
K x. m1,k S
K
x
T
m +
K
2. mi,k
exp
(-Crt 0..5))
< Cat
0.5 0.55
+ C7t
Then get
M
(1 + Cst
exp
T.. x. mi,k Cct 0.5ā
K
M
(M
K 2. mi,k ) (1 C7.50. + u++)
1
D. mi, +
K
M
M
2
<
K n. mi,k +
K my mi,k
Crt 0.5ā + o(t R4)
< Cyt 15t-0.5 0.50 + mit
where in the last two inequality, we use Finally, Equation (31) is bounded
M T R x, m = o(t
M 02 (1 + Cst (st exp Kt
M
R u mz,k - Cyt
0.5p
-1
T
rk
39

---

Published as a conference paper at ICLR 2025
M Kt Ct [- 0.5p o(t
o[( x T (0)
Since -C7l-0.5p decrease to zero slower than the other term, 34, 2 max(45, lo, 17, (9, such that for all / 2 1,, the last term is negative.
4. if ag kk < -C
Since x; 2_r rk
(0) 0, it is enough show that A exp (- M [ m1, -x.r for
sufficiently large Note that A.t 1 exp(- supl-M-2t x w
0 since t 2 to. If
exp (-x] 1r.Th (0)
2 4,
A exp
M K
x. mi,k - x w5xh²²)
2 4(1 - exp( - μ 1_ w// )1) exp
"x mi,k
M
K xi
T
21.
The last inequality holds by 2 max Ls (o) Now, if exp
(-x0 r/ < 4,
K M
M
3,6 = =1= 111expp
exp
-
In
f
+
xx mi, + +2, w x, r/
K
4Kt
M
21
exp
-
$: T
Mi.k + x.
M
K
(8Kt)
-M
21
exp (-p |l x.
T t
M
Also, by the fact Vx: : expx 2 1 + 3r
exp (-x mma x aIrl" (1)
2 (
M xz mi.k (1 (1_
Combined with the former inequality.
(-M
M xr mi.1 xz r(
(0) 3,4 exp
2. m,,k) ) (1- r (0)
2 (1 - (--) 1 x²
2 (1 =n) +1 (() (1 + O.5-)
C7C - R(.
Since -75-0.5p decrease zero slower than the other term, 3t_ 2 max to t7, ts, (o such that for all t 2 t., the last equation is larger than 1.
To sum up, there exist C₁, C2 > 0, N max(t_,t_] such that for all t 2
(r(()) (t) TT < Cit- O2t-1-0.5p Vk E |0:K- K-
(8)
Now we consider special cases to finish the lemma. For any ég > 0, the following analysis holds.
1. If x Tk T
(f)
E2 0:
Since lim My,k
there exist li max max 1-} such that VT (i, Vs S, vk E [0 < 0.5cz. Also since lim, xx_ w - co, there exist t 2 t such that
K - 1] R
M T m
Vt 2 fs Vs E S,Vk E [0 K - 1]: exp (-u4=0 w < exp(0.25ez) 1. Therefore for
f 1 t
M
(1)
M
T xr(())
012
a. exp
v m
x3 rx
-
x rk
Kt.
K
40

---

Published as a conference paper at ICLR 2025
Kl as
M
[1++ xxx exp(-0.5e2) -
2 T r/
t2
M
Kt ag (exp(-
1) x r/ (1)
t24
M
1) 62 1 C
S min as K
2. If F rk 62 < 0:
(0)
Again, since lim v. w (t)
+ 0o, there exist 1-_ 2 l such that 11 E S, e (0: 2 exp(-0.2550 -0.25e2). Therefore for t 2 th,
(t)
K 1 1 exp -H- w/
M
(4 s.k exp
M 2 m, x x//²
1 x, rk
02
Kt
Kl (1-eex(--H_22
M 0ss
[ (1- -1 x.= w exp(0.5eg)
x rh
(t)
124
M
0, (exp(0.256z) 1) x. kk
12
Kt
M
S - -iina, (exp(0.256z) - 1) 62 -
K
In conclusion, for any e 0, Pr (t)
2 and 8(0) # 0, then
(0)
(PT xx) (PTx.)
(t)
2
x T pr(
max sES(()
12 1/
max (E((1)
rk
z
S(0)
SES()
x S(1)
Pr
(
o o (X
s(o)
pr 1
|S(0 miin (X )e
|50
(00)
| where X Ssto E | Tmin (X) is non-zero. Therefore, for all > 0, 3F" C3 0 such that if || P 2 e1 and
is a matrix which has far, 8 E { as its columns. By Assumption 3.2,
((t) * 0,
(r - (0) -C VE ke 0
E.2.3 CONVERGENCE OF Pk
Theorem 3.2 only shows boundedness of Ps (t) Yet, if an additional mild assumption on data is given, it can be guaranteed that p converges to the particular vector.
Assumption E. Support vectors span dataset. That is, rank(æ; : i S} rank : E I}. Proposition E.6. Under the same setting as Theorem 3.2 with an additional Assumption E. the "residual" converges lim Pk
(t) w. Vk E [0 K -1.. Here, i is the unique solution of the
following system of equations
Vi E S exxp (- w = 0z, (I (I- P) w (0)) = 0,
where P Rdddd is the orthogonal projection matrix to the space spanned by the joint support vectors indexed by S.
We set P P for the convenience of proof.
Proof. By the definition of P u +
M my,k + rh
(1) it is enough to prove lim rh 0.
First of all, since w0 = In K t) i + w + M mi,k + +r. (M
K
M
Pr (1) = Pw (1) In
Pw
Pr
Pm.k
M
K
41

---

Published as a conference paper at ICLR 2025
(0) - In = PPw
K MM
Pw
Pio
M K
Pm...
-Pu (0) Prù 0.
The first line holds under the Assumption E.1 since VL(w) is a linear combination of the columns of X. that is, Yl PVL (w) = 0. The remaining lines are true by the definition.
Ftt1 x/ =00
Second, we get to show Pr + O. By Equation (24), limy- 0o E Ek=
C1. That means vk E [0: K - 1] 1im
1--- rk
(7) O. Therefore, for any eo, there exists
12 > 0 such that M rk (1)
< K
for all 12 12, k E 10: K I]. As result,
|ro (t)
| (1)
ス |r( (t)
k
60 2
co.
K
For / 2 m4, 12, }, if pr!
26 + 50 and 5 * 0. then Ak E (0: K - -1]: pr( (1)
||]:|pr(])] 2 E1
By Lemma E.5 (2),
K=
Vm E [0: M 1]:
uet1 r(()) (r(() S KKCttt + Km (Cit + C2t-1-0.5ß).
a=t 0=0
Since --1 decrease to zero slower than -- and 0.50 there exists is > max 12, {). C4 > 0
such that - K Km (C1t- + C2t -21-110.54 S -Cpt 11 1, To sum up, for any Eo, 62 > 0, there
exists tg > max(t1, t2, {*} such that Pro Σ cu + 6 and s((()) + 0. then
t+m K-
Vm E [0:M 1]:
(p( r-1 - TT)))) S -Cat
Now, define two sets for each & E [0: K - 1]
To (t > ts: :
|r (1)
< o ta)
Th = ( > 13 | (0)
2 E0 +a)
We will finish our proof by showing Ts is finite.
First, every Ts is neither empty nor finite. If there exists some k' that Th is empty or finite, then 3mmax Tgg Then
Pro (
Pro
(mmax)
ro
(c)
2
2
K
(w)
1+1
rk
u Imax k=0
(w)
r 1001
+
t-1
Σ
(n
(u)
r/ ((u))) (M)
K+1
1+1
moax k=0
C4 +2
Σ
(rif1 k+1 - r/
(u)
)T)) (1)
r + (r((
(w)
- r/ Tk
(n)) T (u)
u=tmax
< C4 + Co +2
#411 rx ) r
(u)
Sust-1
S(u)
42

---

Published as a conference paper at ICLR 2025
S C4 Co 2C3
Σ
fmxx UmaxS SRst-1 5(") o0
The first inequality is true because of Equation (24), while the other inequalities hold due to Lemma E.5. As goes to infinity, the upper bound goes to negative infinity. However, it con-
tradicts the fact that rb (t) is bounded.
Before move to the final step, note that limy- Ei=,, 2k=0
K-1
[k+1
(1)
(t) -k
C4 implies
rk 100 C4 h(t)
u= 0=
where h(t) is a positive function monotonic decreasing to zero.
Now, assume that there exists some k' that Te is infinite. WLOG, we set K' 0. Since To is infinite, for any E To there exists t', r, E To such that t E [t' - -1:t" -1] C Tu. We divide it into two cases: For all & II' +1:+1:4 1" 1].
Pro ( 2 $ Pro + Mco S (M + 1) +
if [[' +1: $|| < M, then
2. if [[e +1 8|| 2 M, let = min E [t' + 1: //: s(w) #0). Then
1- K-1
Pro (8) 2 = Pro 0
Σ
r 1
+
=
=|Pro
Pro pro
+ Σ
1441 -h
(w)
+ + k+1
xxx kk
TT (u)
umt kmo
+ h(tt) -|pr!t>
h2 Σ
+2
(1)
(T))TT (w)
u=
I (Mc + c0 + +1) + - 2Cs
co
Mu
==1
I (Mco + co +e) h(t).
Since h(() is monotonic decreasing function, for any e2 > there exists 4 such that V/ 2 4 h(t)= < 62.
|rro0l < (Meo + eo + =1)² e2. Since it holds for any 6o, 61, E2,
Therefore, Vt 2 max 44
it contradicts with the assumption that To is infinite.
E.3 ASYMPTOTIC Loss CONVERGENCE RATE AFTER MANY CYCLES
Here we discuss and prove an asymptotic convergence rate of sequential GD, in terms the joint training loss, after large enough number of cycles J. This convergence rate is derived from the implicit bias result in Thcorem 3.2, so relies on a different set of assumptions from those used in the proof of Theorem 3.3. Namely, in this section, we rely on the the shape of the loss function E(-) described in Assumptions 3.3 and 3.4, thereby having ((1/J) rate without any logarithmic factor in J in it, while the convexity of e is not necessity. On the other hand, in Theorem 3.3 having (In (J)/J) convergence rate, the loss function é is (non-strongly) convex (Assumption 3.5) and has shape described in Assumption 3.3, but it does not have to satisfy the tight exponential tail assumption (Assumption 3.4).
43

---

Published as a conference paper at ICLR 2025
We start the proof of the asymptotic rate by obtaining upper bound of E(u) based Assump- tions 3.3 and 3.4. Recall that, for any v > U,
(v) I (1+ exp( exp(-1++))e
Taking the integration
00) for it we have
1
((u) - 1 1+ exp( exp(-144) E
(32)
$ u4 e (where Cy_ = =1+ 1+#
-4i < 2)
since {()) + 0 as xc. We move attention Equation (23), appeared in the proof of Theorem 3.2:
W
(t)
in
Kt
i +
M (8)
M +
Tk
M
K
P
(33)
Kt
(1)
Pk
M
Recall that Theorem 3.2 proves the equation above for all sufficiently large t, well as the bounded- ness of Pk ((t) as tends infinity.
In addition, from Theorem 3.1.2, we deduce that the inner products x wo ū for all sufficiently
M oo) be a time step such that x. un > ūt and Equation (33) hold for all t T. By definition of the joint training loss, for all > T..
large f. Now, let T, E K
(0)
l
x
(1) w
(32)
C
Σ
exp
x w
(t)
iEl
33)
Cμ.
exp
-
T
Pk
(1)
exp
-
Kt
x; i
M
iE!
x )
M
Cp-
exp
Ktt
iET
Cp- Σ exp
(xx) T Pk
(()
M
2.T
+ +
Σ exp
-x,;
(11)
M Kt
xx_ ab
Kt
iES
iET18
S Cp
Σ exp LEE
(-x pk
M
+Cp+
Σ iElis
exp
(-xx ((1)
p(9))
M 0 Kt
Kt
This leading
The last inequality above holds because x. u0 if w; is support vector (i.e., E S) but (t) is bounded above by constant independent
2. á 2 1 otherwise. Since the magnitude of P t, we can summarize the bound above L(w (t)) = (1/tt;; we plug in t MJ where J the
number of cycles, we yield ((w)) ((A))) (11J)).
noteworthy implication of the asymptotic loss convergence bound above about the vanishing rate of cycle-averaged forgetting (Definition 3.8) under the same setting of cyclic task occurrence. That is, we can obtain an asymptotic vanishing rate of the (absolute value of) vycle-averages forgetting in terms of the cycle count J as (1/ without any logarithmic factor in its leading term. The proof effectively identical to that of our Theorem 3.4. In essence, we use the loss convergence upper bound T.(J) in the middle of the proof: see Equation (45). Thus, letting I(J) (11/J) and
44

---

Published as a conference paper at ICLR 2025
following the same logic as the rest of the proof leads to the desired result: (Fcyc(J) ((1/J))
Although this bound seems better than that Theorem 3,4 in terms of the vanishing speed, it inherits the same problem that the asymptotic (11/J) loss convergence bound has: holds only when J is sufficiently large, thereby may fail to capture the dynamics in early (observable) cycles.
E.4 NON-ASYMPTONES LOss CONVERGENCE ANALYSIS (PROOF OF THEOREM 3.3)
In this section, we show non-asymptotic loss convergence, as stated below:
Theorem 3.3. Suppose that Assumptions 3.1, 3.3, and 3.5 hold under the cyclic task ordering setup. Then, if we choose learning rate satisfying < 4K max maa)) we have for any m E [0: M - 111]aadd and [0: K that
L(w (M)tmm x
[S|+ Σ
|S + [mml
E(In (InMM) + 1/00 (0) In MJI2
D1
J
2n
j
+ +(11- - |S|
Ei= (14 -(al) + R (14ml - 11mml) e(01n MJ),
where 8 the second margin defined in Section 3.1, and D2 constant independent J.
We first present three main lemmas prove Theorem 3.3. The first one is an extension of Lemma E.2. When M tasks are given in a cyclic order, the following lemma holds.
Lemma E.7. Let any t E N. 1 E [0 : K - 1]. m E [0 : M - 1] and E [0 : - such that I 2 m = 0 but 1 k iff M. Then, for any L, k) satisfying these conditions,
m
wi (++m) w + (K- 1)
(1)
K
10 (0)) + IV L (++m)
(w (e)
i=1
172 (mn +
ko max
V 2(20 (2)
$1 7mmK + 1 k) 3
((+m)
o
VC (4)
w
5
0 7mmk +1 k) k) max maax
V ((ww/ ((mm))
vL((n
VL(20 (0) )
Φ{1 - nmnnmmmm + k)) 3}
Proof. We omitted the proof since there are only a few changes from the proof of Appendix E.1.2.
The second and third lemmas represent two similar versions with respect to the common Gradient Descent setting, and the Continual Learning setting.
Lemma E.8. Let L be convex function. Suppose that there exists 3 2 0 satisfying that, if
n E (0, t)) the iterates (w,...., w;)) defined with an update rule wj+1 := w, T)W,(w,, satisfy
((w++1) s L(wn)) n13) VL[
for all j [0: [0-]] 1). Then, for any 2 E Rdd
2 Σ (C(w,) L(x))
Σ
(C(w,) - [(w)+1)) |wo =|2-1|w, x1|2.
1=0
1=
Proof. See Appendix E.4.1.
Lemma E.9. Consider the jointly separable continual linear classification problem with cyclic
task ordering. Assume that E(-) convex and 8-smooth, there by the total training loss L convex & 3 function. Assume that there exists 3' O satisfying that: if
45

---

Published as a conference paper at ICLR 2025
7 - min 2M "Mioinms" 3: 2 h. the iterates w w
(0)
K-1: w
(0)
(2)
w k-1
(L)+
defined with
the update rules w 9+1 = w
(p)
=w -nVC(e (n) and w
((rt1)) w
"x
(p)
satisfy
Llunk (M)+ S f(unk ( nk (1 -n]Ki'))) V (
for each j E [0: - 11, m E {0: M -011,, 11, and A E 10: K - 11. Then, for any 2 E IR.
J-1
2
Σ nk (Cluo
- [(x))
j=0
2nMKo Ko max
Σ 1 - nK
J-1
nn
(C(w) - ((wo% (M)t-++mm))))
d2 - -1MM Ko o max 3)2
5=0
(m)
- x 1| - |1 (1)++m)
1
k
Proof. See Appendix E.4.2.
Note that Lemma E.9 holds only when jointly separable tasks are given cyclic, while Lemma E.8 always holds.
We follow the process of Appendix E.1 show that it satisfies the condition in Lemma E.9, Since L is a T function, For all j E [0: : J - 1], m E [0 M - 11, k E [0: K - 1}, we get
[(w
k
(M5+ M)+ - k C(w (M)+m))
o maxx
3
(M)+N+m)
w0k
(Mi+m)]
2
vLww ((ww (M)+m)) T (w0 (M)+M+m)
(M)+m))
w/
VL(wn (M))m)) TT (ueg (M)+DS+m)
um (M)+m)
k vyK (A1)+m) (2)+mm)m)) + kKVLLW (M)+m))))
-n VL(ukk ( (i++m)/ /|? + (V ())+))]
(Mj+ M+m) w
(Mi+m) nK L mm (M)+m))
By Lemma R.7,
L(wbk (M)+ - -L(w -(( (M)+mm)
0 maxe 3
VL(20) (M)+m)
2
MMK 2 3)3
s <nn (T J||
M²2
03
V VLW (M)+m)) 122
Φ(1 nM K 02
max
Given that 17 S 1K maa MM (oo+)
2M
((w0M)+M++))
L(up (1)+))))
Mo nax3 3
4 maxx
[ (Mitmi)
S snnK(1 [K
6(1 - -MM- K 2 3)
20 nMMK Ko o 3)2
S S-nK (1_nx²
2 + Faax Jo maxx 3
( J|?
2
=-nk (1 101-nhs n)B
( (M)+m))
(34)
where we set (et/3'== := 2 Jo Since Equation (34) holds for all j E JJ 11,m E [0: M - 11, & E [0: : K [-1] -1] and < 1/2K3' given, by Lemma E.9, we get
2²
J-1
> nk (E(u (M)-)+))) -((2))
2
1=0
46

---

Published as a conference paper at ICLR 2025
21 K of
max
J-1
nk
(E(w
0² nMM
max 3)2
1=0
(m) - =|?
k
(MJ+m)
=1|
(35)
and L(w ((wg (M)tm)) is decreasing.
Given that 17 2KT IMKDON
M K o max
3
1 K' (C(ro(a - L(1ok C(
n
2
n K o
m)x
3)2
80 max
n (C(w) - (
(36)
df
Also,
80 max
n ( (M++m)) + +2nKJL((v ((
(M)+m))
80
nk L(w (m))
Φ²
0²
<
80 max
n L(w
f (MJ+m)) + 2nk
C(wb (M)+m))
80 max
n L(2 (m)
0²
j=1
80 2
2n C(ub (Mj++M))))))))))
max
n
L(20) (jtt) (37)
3=0
Combining Equations (35), (36), and (37), we obtain
2 (C(w (
- -(()) + 80 max
(
(dJ+m)) ((wo(m)))
nk
0²
2 nk (C(wg
Σ
J-1
- ((x)) (ll
8o max
nK
Σ
J-1
(C(ep
L(10/ ((w0M)+tt++m)))
1=0
1=0
(m) w &
=
1|
- 2
(MJ+m)
2 |
(38)
Now we examine the loss change in cycle. For any E (0: : M - 1 (0: 1-11,
(, () S ()) - n(1
no max 3
(w(
2
Since 1) 2MK Ly(10 (7) decreases. Therefore for any p [0: M 11, q [0: K 1).
1 (p) 9+1) ( Cz(2)) $ Σ 1
-Cp())))))((())
1=1
9-1
Σ (0)) - Lp(z)) ) +2
(
Σ
1 (p) - -cp(
=
1=0
1=0
--
Σ 17 (o) -px(z))
(0))
Σ 1 133 (Co(wo(o)) (cp(((
$ 2
1=0
(p)
||2
(o(p) 2
where in the third line, we use I-n3 < 2, and in the last line, we use Lemma E.8.
By summing up, we obtain
m
Σ 2n (Cp( (p(z)) + 2nk (fm((n))") (m))))) - Cm(2)) S mn -z)
m (m)
0
(39)
47

---

Published as a conference paper at ICLR 2025
At last, (( (m)) is bounded by L(we)) as follows:
[(w (m)) L(wbo) - V ((w)))) T
(m)
-w
w
(0)
+
max
2
3
(m))
w
(0)
|L((()) (0) //
maxx
8
(m)
(0)
(0)
w
-20
nK 0 max
3
n max
VL((r) 00)
||²
6(1 7, Ko? R 3)
Φ(1 n K
max
Do
V VL(w
(0)
(40)
where we use the smoothness in the first inequality, we use Cauchy-Schward the second inequal- ity, and in the last line, we use the fact
mm)
(0)
held by
p(1 nM--MMR K m)x
Lemma E.7. We set Do (1 @01 n
nk B
nk 01 7, B.
Combining Equations (38), (39), and (40), we obtain
1 m-1
k (MW))m)) S [(z)+
Cz) +
q
(z)
K
p=0
L(wb (0) + Do V (0)) ||
(0)
2
4 max
W - 2
2
Now let us choose = w In MJ. Using the fact Ly In MJ) S | MJ) +
(14 - [S,1) (since is monotonically decreasing), we can finish the proof with
2
(0) + I+
KKo max
no max
V (3)) 11)
10))
D1
60(1 1/ Ko 3)x @11 7 K Ko Ko
E,4.1 PROOF OF LEMMA E.8
Here is the restatement of the lemma. Lemma E.8. Let L be a convex function. Suppose that there exists 2 0 satisfying that, if
7 E (0, (..)) the iterates (wo...., defined with an update rule w := wy 17V [(w,) satisfy
[(wf+1)= S C(w,, m (1-n3) V\,,,)
for all jE [0:t- - 1). Then, for any z E Rd.
2 Σ (f(w,) -[())===)-)))))))))()))) Σ 1 nB (C(w;) L(wj+1)) |w0 =1|²-|
- -1 =||²
This is a well-known property of gradient descent iterates applied to smooth convex objective function. However, we contain the proof for completeness.
For any j 2 0 and E Rd
[10+1 - =| = |0 - 211 + 2n((V - + 1/ [[W((1)))
I 11 (n(((2) [(w;)) + | ( [V
< ||, + 2n(((z) L(w,)) + (E(w,) L(w,+1)),
n
where the first line comes from convexity and the second line comes from the condition of our lemma. Summing up the inequality over all j E [0 : t 1]. we eventually get the desired result:
1
2 Σ (C(w,) ((x)) Σ n (C(w,) ((w)+1)) S Ww =1| - || lw; =1|
48

---

Published as a conference paper at ICLR 2025
E.4.2 PROOF OF LEMMA E.9
Here is the restatement of the lemma.
Lemma E.9. Consider the jointly separable continual linear classification problem with cyclic task ordering. Assume that {(-) is convex and 3-smooth, there by the total training loss L
is convex & max 3-smooth function. Assume that there exists 3² z 0 satisfying that: if
S min 2MK 2K b. the iterates
(wo K-1: w0 ..... uK1 ( defined with
(0)
(1)
the update rules w 9+1 = w - (VC( (P) and w (o+1) == w (n)
k satisfy
[(w) (MW(+++++M) S f(w) (M)tm)) .7 (1 - 3)
( (m) ||?
for each j E 20: - 11, m E 10: M - 1), and k E [0: K - 11. Then, for any 2 E IRd
J-1 1
n (E(ug (() - (()))
2
j=0
AmMKo
max
J-1
nk
(C(wp) (l)tmm)) - ((ubk (1
(2 - -n/ K o
3)2
1 K1 3'
1=0
(m)
2 1|
2
(DJ++m)
x|?
Without loss of generality, let assume m 0, k For any j and = E Rd,
M-1K-1
2
(Mj+M) 1
12
(Mj)
V (e (M(()))))) -2
2
10
1j
4=0
M-1K- K-1
M M-1K-- K-1
(MJ)
2
12
+ 21)
Σ
Σ
V (w) (M5+t)) (10 -020
wo (M2))
+ 17²
Σ
Σ
V L (u0
F=0 7=0
p=0 q=0
M- K-11--1
(M5)
2
+ 2n
Σ
V ( (wft))t)))+ x- g
aof2rs+D)
p=U 9=0
M- K-1
M K
+ 2n
Σ
(w) (M)(t))))))))))..)))))))))))))) u0! (Mttt) - w0 ((6))))) + +1²
Σ
Σ
V (2 (u)
(41)
0= 9=0
p=0
9=0
By convexity,
M-1K
M-1K-1
ΣΣ
(Cp((((M(tt))) -wo(a(tp))) < MKL(z))
Σ
Σ
Cp(wf
(42)
p= Q=0
p= 9=0
Combined with Equations (41) and (42), we get
(M)+af) 200 0
- 2/ 2 - 100 - =1 S 2n)(((z) - 2n1 Σ
||
(M1)
M- 1-1
Σ
Cp (u (Mtti)
p=0
9=0
M- 1-1K- K-1 Σ
A
K-1
+ 2n
V (m no (M((+)))
Σ
Σ
V
(n
(43)
0= 0=0
By 2 maxx
3 8-smoothness,
M-IK-1
Σ
Σ
(w(((t) = w (M)+p)
1=0
0=
49

---

Published as a conference paper at ICLR 2025
M K-1
M
K
2 KL(2)
Σ
max
Σ
m (M++p)
2
p=0
-=0
p=0
9=0
(Mr++M) then we get
Apply smoothness on Equation (41), and let == w
0 2
w
0
(M1))
w
w
| + 2n ((wp L( (
M
K-1
M-1K-1
2m
Σ
no
Σ
(M5+M)
(M++))
(Mj+
p=0
p=0
M-1K-1 (VLp(u((aitt)) u0 (()++t)))
M-1K-1
+ 2n
Σ
Σ
w0
+ +1²
Σ P=O g=0
Σ
p=0
9=
(44)
Combined with Equations (43) and (44),
(MJ+M) 1/
(M5)
2
S 22)
2n) 6 ((10)((t)) (M5+40)
- 110 (M15 w0
10 (M
1|
(M)+AA)
20 (a5)tt))
+ oll max
w
g=0
s <2nK((z) 2 (M)+MM)
2006 (M))
MM++
w
+ +2nMKo max /umm1: (M5) w00 w (A
2 +
2n10 2
max
3
M
M-16 K-1
w0
(M15)
m (M+t
p=0
K-1K-1
S (2) - 2 ((w0 (Mi++00))
+ ((u max
2 2
Σ
(MJ)
20
(M)+ ?
D=0
9=0
where in the last line we use S 2M
Finally, by Lemma E.7,
(M - =1? u
(M))
-= -z
< kn (E(x) - L(wb ((mo)))t-M)))
2n²² MK3
04
max!
3
VL (M5)) 1
+
0 (1 nMK K 02
MAx 3)2
< 2nn (E(z) L(wo ((16M))tMM)))
2n Mr max
nnK
nK (C(10)
L(1b) ((1m)))))))
62(1 7 2 max
1 3)2
By adding all j E (0,,.... JJ 1}. we can finish the proof.
E.5 FORGETTING ANALYSIS (PROOF OF THEOREM 3.4)
We prove Theorem 3.4 here, which is restated below for readability. Theorem 3.4. Suppose Assumption 3.1 and let E(u) = In(1 + + be the logistic loss, which satisfies Assumptions 3.3, 3.4, and 3.5. If the learning rate satisfies 17 < AKBeassMMooon (a then the cycle-averaged forgetting Feye(J)) [J')for for cycle satisfies the
the following upper and lower bounds:
-nkK ([()) Epty Ata
Epto Apa
< {Feyc(J)
(J) Sn (T(())2
M
M
where L(J)= = (mx2) and Atg :=
Σ
xJ_ x Ap.g :
Σ
[ [1,22]1 x
(15) " my>0
(
2, my<0
By Theorem 3.3, the joint training loss cycle J is bounded as L( (M (MJ+m)) < T(J)
(45)
50

---

Published as a conference paper at ICLR 2025
where
L(J) = j ((s1+
[ |1|-11 |S|
) (1+ 1 | (0) w In MJ
+ +Di =0 (nn
(M
MJ
27K
D1 40 max
[(wb)) Do VL( (0)) /1(²
Φ²
Therefore, the following holds:
As I, Vm E [0: M 11, vk E [0: K 1]:
x._ w
(M++m) 2 20 (T(()).
Now, we analyze the change of each task in one cycle. For the upper bound, (1b
Lm(uv) (MJ+M)
L. (wx (1xx (J+m))
M
S リ
Σ
Vm (wo
(46)
p= -=0
M-1 K-1
s 1 Σ
Σ
(x wh
MM w(M)++))xx? x
p=++1 9=0
(A.))emxxl xIp
ax k0<0
M-1 K-1
- Σ
Σ
Le' (5 (L(J)))
Σ
x x3j
(47)
p=++1 q=0
(k.))E xI,
2. <,
M-1
{ーnK(L(J)3
Σ
Σ
x.. Bjj
(48)
P=
(IJ)El x
2. 2,
where in (46) we use convexity, in (47) we use the condition that E is negative function monoton-
ically increasing to zero. Equation (48) holds by the fact Væ (xx) = llog (æx 2 - exp(-xx) and
yo (xx) = b1og -(x)) 2 log(z). Likewise, we can get a lower bound as follows:
Cm(w)) (MJ+N)) Lm (w (M))))))
M
K
2 1 Σ
Lm mm (w
(MJ++)) T v (p (MNM)tD)
p=m+1 g=0
M-1 K-1
2 1 Σ
Σ (i.)) XI
(ax w
( (xr un (M(J+))))a) x.
p=m+1 q=0
a. Φ, >0
M-1 K-1
2 n
Σ
Σ
le' (L())))
Σ
x æj
p=++1 0=0
(1.)) xlp 2. 23>0
M-1
2 h
Σ
x aj.
p=m+1 (i.))emm XI,
xi my>0
Define
At A+ =
Σ
x. 2. 2 and A Ap4 =
Σ
|o: æτ
2 0.
(,,
(I,j)E,,XI,
2, a,>>
2, æ5<0
Since
M-1 M-1
Σ
Σ
x xz =
Σ
A p.g
m=0 p=m+1 (K.))TT xI,
p#g
2, æ,>0
51

---

Published as a conference paper at ICLR 2025
M-1
Σ
Σ
Σ
a. x. =
Σ A
m= p=m++
(k.)) xI,
2, <0
we can conclude
-n)(((J))3
Σ ppy
At
p.q
<
1
M-1
Σ
(MM M) S
Eppa App M
M
M
m=0
52

---

Published as a conference paper at ICLR 2025
F PROOFS FOR SECTION 4: RANDOM TASK ORDERING, JOINTLY SEPARABLE
F.1 ASYMPTOTIC Loss CONVERGENCE ANALYSIS (PRoOF OF THEOREM 4.1)
Let us restate the theorem here for the sake of readability.
Theorem 4.1. Let {w (5) =E(00--11,,120 be the sequence of GD iterates (2) from any starting point
0 where tasks are given randomly. Under Assumptions 3.1 and 3.3, if the learning rate satisfies 20²
(0)
n < So
then the following statements hold with probability 1:
Loss converges to zero: lim L(w ( - 10: O 1].
(-000
2. All data points are eventually classified correctly: lim yoor w0 0, Ak [0: K 1
(1)
2-000
3. Square sum of the change of weight is finite: Et= EKS 11 w 10 oc.
Since L a o 3-smooth function, we get
E ((w (0)
k+1 ) - E [(
< E
VL VL(W (1) T (w k+1 -x
o
max
2
E
Wk+1
K++
W
(t)
E
E VL( (1) T (w0f11 (t)
w
(2)
k
(1)
3
E
w
R+1
(1)
w
(1)
E
E
v (2) (w [0)
(2)
0 muce
3
2
Σ
l' (xx_
20 k
(1)
)xx;,
SE
"1 m M
V ((0 11)
3
2
(1) (ar w0 )ar
(1)
2
7 E s M
V
100 (2))
0 max
"
E
(1) ll (xx 28
T (00)) 12)
2
SET
7 E M
max
3
11
E
(z()))] E e w [1)
2
sEl
7 (1)
|
max
"
E
Σ
8' (x. 20 (0))
M
2M
SET
where 2 is a variable which is 1 when is in the task on stage t, or 0 otherwise. The second inequality comes from the fact VY, E IR: ||E.er >, l| S maax VE X2
By applying Lemma 1, which only depends the total dataset (but the task ordering), obtain
(4) (21) E [(w]))
E [<(
17 (
othx
s
M 17
E
20
17 (1 T
(49)
where 3" = 3 20
Given that
<
go.
(ww (0) liim E ((ww))) [0)
K-1
M M(ww (0)
v( (2)
111 113") < co.
37 (1 31
t=0
53

---

Published as a conference paper at ICLR 2025
Thus, by Sabini-Tonelli theorem, we have E Ek=
VL
(4)
oc. Since a non-
negative random variable with finite mean is finite almost surely (because of Markov inequality), we have that E== -
I|² [ is bounded with probability 1. The boundedness infinite
V
sum of nonzero elements implies vk E [0: K 1] lim V L [ 0. Combined with
Lemma E.I, we obtain time-o0((x)) w/ (1) 0, vi 1 E [0 K 1]. Since (u( only when u - co, I. ( - >00, E I E [0 - 1/. And lim C(w (t) = 0, vk E [0 K 1]. Finally, followed by
VL |))
20,
(o w (3))
2
Σ tEI(C)
(x) T w )
IE1
Σ iET(1)
(xx
w )x:
(0)
(1)
"
mmax
mmax
We obtain that Eie 2k
[k+1
(t)
(4)
oc with probability 1.
F.2 DIRECTIONAL CONVERGENCE ANALYSIS (PROOF OF THEOREM 4.2)
In this section, we prove Theorem 4.2 and further discuss the convergence of Pk (0) beyond bounded- ness.
Theorem 4.2. Let {w] T ]ke[o: be the sequence of GD iterates (2) from any starting point w)) (0) where tasks are given randomly. Suppose that Assumptions 3.1, 3.2, 3.3, and 3.4 hold, Then, under the same learning rate condition as in Theorem 4.1, Wy will behave as:
w = In (t) 2 + P (t)
where ( stays bounded as grows.
We only need to prove that the two following lemmas still hold in random order.
Lemma F.1. When tasks are given randomly, there exists w Mi, E IRd the following almost surely holds for all E N, k E 10 K 1]:
[-1
Σ SES()
ax
K
log( no +
K
i + my,
(50)
W
M
M
M
==1
SCS(w)
mr,K
m
such that |m o(t-0.5++g and | - mI,1l ((-11) for all 10: K- 1-11c > and in only depends on the order of tasks and constant with respect to t.
Proof. See Appendix F.2.1.
Using Lemma F.1, we my,k and io and define p and (t)
as we did in cyclic order. That is,
w (t) In (1) vb Pk
(4)
K
M
In (t) vb In
i
1
my + r
M
K
and
(++1)
(()
((+1)
PK
Pb
TK
r
54

---

Tr (0) Published as a conference paper at ICLR 2025
where w is the solution of
Vi E S mxxp (-x; w) Oi; P(w w (0)) 0.
which is unique under Assumption 3.2. Then by the definition,
M
K
K
(1)
=
log
l + m2.k
K
M
M
M
K
t-1
Σ &ES
Ug
+ h
Σ
a,t's
logg Kw - 2 + w.
K
==1
SE8(0
Then we can get the second primary lemma of rk
Lemma F.2 Under Assumption 3.1, 3.2, 3.3, and 3.4, if learning rate is n < 30 then
20
1. 3i, C2. C2 such that vt i,
(1) T (1) (T Tk rk S Ctt + C2t 1-0.5p C2t--10000
Ak E 10: K - -].
2. Moreover, for all 61 0, 38 C3 such that if
PT (1)
2 c and S(t) + 0,
(r - r r S -Ct &
(1)
k K -I.
Proof. Only the learning rate is different from the cyclic case. Therefore see Appendix E.2.2.
The remaining step is the same as the proof of Theorem 3.2. To sum up, we can set a as
(6)
(t)
w ( (0) (0)) Then by Lemma F.I, 36 such that Vt t,, Ak [0 a
|k41
T
w
K 1]:
ax
(2)
<t
For all T 2 I1
K
T
(1)
(1)
(8)
rk
14111
wk
.0k
tmti k=0
K
T
w
w
(4)
2 -
(1)
(0)
a
(1)
a
(
tmti k=
k=U
K-1
(1)
(1)
(8)
(1)
(1)
(8)
w k+1
w
+
w w
k+1
a
t=h
4= k=0
1= k=0
1=
K-1
w k+1
w
+ (
(1)
w
(8)
w 2
2-
[=1
1= k=0
4= k=0
< oc.
(51)
We use Cauchy-Schward inequality for the first inequality and the fact that Ei=, 1-2 <
xo and
ETe ΣK-1
w x++ < oo by Theorem 4.1.
Combined with Lemma F.2 and the fact that Vc > 1: Eee t- < co, we almost surely get
11)
(ktl |r 11)
(1) 2
| r (4) 12) < 00.
((r(()) (w)
r TT (1)
55

---

Published as a conference paper at ICLR 2025
F.2.1 PROOF OF LEMMA F.1
Here we restate the lemma for the sake of readability.
Lemma F.1. When tasks given randomly, there exists w mi,k IR the following almost surely holds for all E N, k E 10 K - 1]:
K
h Og
Σ
Og
K
log( t
yi +
K
in + ma,k.
(50)
M
M
M
SES
SES()
mA,K := m4+100
such that | || = ) and | m.,ull = 0(1 for all ls E 10: K -K11,, > 0, and only depends on the order of tasks and constant with respect
We define an (i.i.d.) random variable(s) 2/ == 1sx E }. Note that B[2 = M and Var(z!")
= M-1 M22 due to uniform sampling of the task index in [0 M 1]. Then, we can write a
sum on the right-hand side of Equation (50) as follows:
(a)
K =
<En u (ES(u)
a
= KK
Og
f-1
(8)
E
K
a,
8ES
1m
1
(-1
(w)
Ele
E
(w)
K
ag
M
u
u
Since
t-1 Σ = log t + + q(t)
==1
where y is the MascherMac constant and g(t) 1)t ), we have
K
K
a, = M
(logt + + g(t)) w.
M ==1
SES
Now we are going to deal with the sum
E
23 (w)
in two aspects: (1) it converges with probability 1 as t + oo and (2) the almost-sure vanishing rate of the "residual" (a sum from to oc) is ott -0.5+c) for any e O. Let us look at its almost-sure convergence. To this end, we utilize the following useful proposition.
Proposition F.3 (Theorem 5.2.6 of Durrett (2019)), Suppose X2,X2 are zero-mean independent random variables. If D Var(X,) oo, then Ens Xn converges almost surely (i.e., with probability 1).
Observe that X,, = all u. but also the sum of their variances is convergent:
is zero-mean random variables, Not only are they independent for
Var(X.)= M-
1
20
<
00.
M
u
56

---

Published as a conference paper at ICLR 2025
Thus, by Proposition F.3, the sum Ex=1 Xu converges with probability 1. Next, want show the vanishing rate
Σ Xu o(t 0.5+t)
with probability I, where choose any 0. Observe that it is equivalent to show, for any 0
P
0.5-c
Σ X > for infinitely many f
Here we bring renowned Borel-Cantelli Lemma.
Proposition F.4 (Borel-Cantelli lemma; Theorem 2.3.1 of Durrett (2019)). Consider a sequence of If Ef= P(An) then
events A1, A2,
Pllimsup An) = P(A, happens for infinitely many n) = 0.
By Proposition E4, it suffices to show
Ag O, p
8..-c.
X > 8
<0.
u=
Let us recall Hoeffding inequality here:
Proposition F5 (Hoeffding inequality). Consider collection of independent random variables X1, Xn, satisfying a, S X, S for each i =1,-.. n (a, < b:). Then,
2r
IP
Σ
X
2r
2exp
2i=1 (b; 0.)
Since the sum Eane X,, converges almost surely, is well-defined random variable with probability and
T
P
Σ Xu
> 8.. 5.11 -.54e 1.55t = =
Σ
Xn
> 8. 0.5+ for all but finitely many T
16
> 8 . -..5te ))
=:P P
in T-x
Σ Xn
u=t
< lim inf T-
Σ X
8 2 0.3+c
(52)
25 1+2c
< lim inf 2 exp T-000
(53)
Σ uuzt 4²
1
28 1+26
2exp
(54)
Ene 12
< 2 exp (-82(20..
(55)
We use the fact "Ii inf,, A.) < lim inf,, P(A,,) )" in Equation (52); we apply Hoeffding inequality (Proposition F.5) and the fact Mu < X, < M-1 in Equation (53); and we utilize the fact Ma
D Ne < 2 in Equation (55). Since exp(-82 = ot-22) for any > and large enough t, sum E, exp(- 2 (2(2 converges. Therefore, we have desired almost-sure convergence guarantees.
From now let us proceed with the proof. Using the almost-sure convergence results, let
8c Σ
i == (log M + 7 M
Σ
X₂
ag
SES
N=1
57

---

Published as a conference paper at ICLR 2025
00 Σ
mi.k = M (() in
K
Xu
a +
Σ
Σ
ag..s.
SES
SESO)
Then with probability the statement of the lemma holds: Equation (50) holds, where w is constant vector in terms of I, ||m S o(t-0.5+e) for any c <> 0, and
m m = Ot )
(k= -K...K.K K-2 -2 2)
7,+00 m = O)t
This concludes the proof of the lemma.
(0) F.2.2 CONVERGENCE OF Pk
We can also prove a characterization of the limit of Pk as done in Appendix E.2.3. However, when (8)
tasks are given randomly, we need an additional assumption guarantee the convergence of Pk to the particular point.
Assumption F.1. Every task has at least one support vector. That is, Vm E [0: M 1] Sm + 0. Proposition F6. Under the same setting of Theorem 4.2 with additional Assumptions E. and F.I,
(t) the "residual" converges lim, Pk w Vk [0 K 1). Here, the vector defined in Proposition E.
Proof. First, Pr (1) Pwo (0) Pw 0 holds as in eyclic case. See Appendix E.2.3.
Second, we get to show (r(()) + 0. By Equation (51), limy Ete, 2k=0 k+1
(0
C4. That means vk E [0: K- - 1] lim
0. Therefore, for any en. there exists r k++ rk
(2)
t2 > 0 such that | rk
(t)
for all t t2, E 10: K 1]. As result,
K
Pro (t)
(t) co- (r (1) 2 pr(
c
K
Fort 2 maxfti, t2, }" }. if By Lemma F.2 (2),
2 c + cu and ((t) # 0. then Ak E (0 K 1]:
--1]:
Pr 2 e1
(1)
Σ
(ro41 u+1
(1)) (())) r (w) < KKGt K (Cit C2t-1-0,50),
u=-
Since -ー decrease to zero slower than -ー and to 1100.5 there exists to > maxfft,, 77 C2 > such that -KCst-1 + K (Cit + 11t-1-0000 0.5p) I -Cst Also ((t) # @ is given by As- sumption F.I. To sum up, for any 60 > 0, there exists to > max(tı, t2, 8*) such that Pro 2 cp + 61 then
K
Σ
Σ (1 - ( ((a)) S -C
v=0
Now, define two sets for each & E [0: K - 1]
T = {t > 1::
Pr (t)
< E0 +e
T = (t >
P (1)
2 c +a]
58

---

Published as a conference paper at ICLR 2025
We will finish proof by showing that Tx is finite. Here, the fact that every Tg is infinite.
The proof is the same as in the cyclic case. Since lim Eis, Σk=o Pht1 (1 2 get
= C4, we
K
(1)) Th = C4 - -h(t),
u=t1
where ht(t) is a positive function monotonic decreasing Now, assume that there exists some k' that Ts is infinite. WLOG, we set k 0. Since To is infinite, for any & To there exists I', l" To such that & [I' +1, - 1] To. We divide it into two cases: For all E [1' + +1,1" - 1].
Pro 10)
S >r
Prb
i 1, then
t S Zen + 61.
2. ift 2 t' + 1, then
Pro (t) 2
Pro 1|
t-1
1841 || - (1) 2
+
w=t' k=
Pro
[ r 1001
2 rk ( (a)
(1)
0=0
6-1 K-1
+ +h(1)= 1((() +
Σ
Σ
(n(1)
- (()
TT)
[())
k+1
a= k=
[-1
S (eo + +2) + +(1) 2C3
20
Σ
11 +1
k=#42
(eo + ) + h(t).
Since h(t) is monotonic decreasing function, for any Eg > 0, there exists 44 such that Vt 2 h(t) < 62-
| s (co e1) + e2. Since it holds for any ED, E1, 62
Therefore, Vt 2 max t4 contradicts with the assumption that To is infinite.
59

---

Published as a conference paper at ICLR 2025
G PROOFS FOR SECTION 5: CYCLIC TASK ORDERING, JOINTLY NON-SEPARABLE
Review Bregman Divergence. Before start the proofs, we briefly overview some basic properties Bregman divergence.
Given a differentiable convex function f S + I defined on closed convex set S C R.. the Bregman divergence between two points (x. y) E x S with respect to f defined as
Dy(2, y) = f(x) - f (V)(y), x y)
Note that Dy (æ, y) 2 0 for any æ, y E S because of the definition of convexity; when f is strictly convex, (x, y) 0 if and only if y. Also. if is 8-smooth, D y) I
8 || yll holds. 2
We often use the following useful identity that links three different points æ; y E S and E int
(Vf(z), x y) = [f()) f(v) (m, - (1,
(56)
Here is another useful fact: for convex 3-smooth function on Rd the Bregman divergence is bound below by the squared distance between gradients. Proposition G.1. Let Fd IR be convex, B- 3-smooth function. For any x, y R
[V V (())) < 23D,(
Proof. Observe that Dy(: y) is also 3-smooth function for any y. Let = - [v) - v E Rd. Then by 3-smoothness and the non-negativity of Df(: y). we have 0 S D (2,y)
B ||= az12
< (y( + (V.D)(z,
1
1
(x,
3 (Vf(x) Vfy), v
Vf(x)) v(y)]
23
= D y)
[V/(2)) \
2B
This proves the proposition.
Useful Inequalities. There are two other crucial inequalities for the proof's in this appendix. One is a variant of Jensen's 's inequality applied to a squared norm.
Proposition G.2. For any positive numbers \1," An > any vectors u1," ".. Un E Rdd. and an integer m E [0= : n).
S
A
Σ
Juall
A
Proof. Let Am = Emm dj. Then by convexity of the squared norm,
X;
Am
U
A
Am
ut
A
m
Am
|u,
A
An
| 11
60

---

Published as a conference paper at ICLR 2025
Another is about solving recurrent inequality.
Proposition G.3. Consider O < μ. S 3, V > 0, T Suppose the following inequality holds for any positive a S 3 and 00: 1]:
0 -00=0mm)1))))) and Ap 2 0.
1
A+t1 S
A, + a.
1 1t
If we take
c+1 1
max (1, 11 Aope
min
in
Tm
we have
AT = 0 0-0eee (expp
V V-In"(T)
(c++1)8+ 1)88))
Do + um+1Tm
(ct
Proof. Since op S $ S c, we have
Itap $
ou ctl
By unrolling the recurrent inequality, we
have
)² Do aatamtly
T-1
)
AT S 1 c+1)
of
ap V
Σ
c c+1
(- al T Do
S cxp
(Tc+1")
1
With the choice of a, the first exponential term is bounded as
(-
exp (-o+17) )
c (
cp
() Do:
Do S max
exp
(ct 1)3
p m
(- qu
exp
([c+ 1)8"")
Do
um+1pm
Also, the second term is bounded
2a T
2(c+1) V In mm
1, Aou
(TH "m" max
Combining these two and ignoring some constant factors and polylogarithmic terms, we have the desired bound.
G.1 LOCAL STRONG CONVEXITY ANALYSIS (PROOF OF LEMMA 5.1)
Recall that we consider cyclic continual learning on M jointly strictly non-separable classification tasks. Let us restate the lemma here for the sake of readability.
Lemma 5.1. Consider learning M linear classification tasks cyclically. Suppose that Assumptions 5. and 5.2 hold. Let B == EM-1 -1 9m. and V. EM=1 Bm [VLL Take step size <
2/2KB' Then, there exists compact W IRd containing w. and every w (o (j = 0, 1, whose radius independent of J (the number of cycles) but depends on other parameters like b, G, B, and V.. Also, the offline training loss L is p-stroogly convex W, where
p (unin::(p:N-11.eee L" (y:ar) w)) -Amin (XX) > 0.
(6)
To prove the boundedness of end-of-cycla iterates and the local strong convexity, we first establish per-cycle recurrent inequality terms of squared distance to an arbitrary comparator Rd and the risk values. We put u w. later.
Lemma G.4 (Backward recurrent inequality). Consider learning M linear classification tasks cyclically. Suppose that Assumption 5.2 holds. Let B = EM- 8m- If we take any step size satisfying S 2/2KB' the iterates of sequential GD satisfies
(U+1)M)
61

---

Published as a conference paper at ICLR 2025
M-1
$ 11000
(1))
u
2g (C (wm ( [(u)] + k2
Σ m==0
[VLmm(u))
Pm
for any vector Rd for all j 0, 1,
Proof. We defer the proof to Appendix G.I.1. We remark that this lemma holds even without assuming the non-separability.
Observe that the following holds special case:
(++1)M) w.
(M)
w. 2n [ (w) (20binn) [(w,)) +
(57)
where V. >m 3m
|VLm (w.)l²
The next step is to construct a compact ball W centered at w. containing every end-of-cycle iterate of sequential GD. The crucial step is to apply the -on-separability coefficient (Assumption 5.1).
Lemma G.5 (Boundedness of the end-of-cycle iterates). Consider learning M linear classification tasks cyclically. Suppose thut Assumptions 5.1 and 5.2 holds. Let B Em-D Bm and V. we we take any step size satisfying 1) S 2/2KB'' the end-of-cycle iterates of sequential GD are contained in a compact set which is fixed in terms of the number of the cycle: for all j = 0, ,,..,
EM-I 5m || [V=L(( If
72 + 2
(JM) w
E EW = un E Rd ||w w.
Gb (E(u))) + V2nKBVV.
+ +||w,|||
V.
2
V
S w E Rd w w.1l²s
[(w.)
+
+ +||w,11
+
Gb
2
2V2B
Proof. The proof is done by induction based on Equation (57). We defer the proof to Appendix G.1.2.
The last part of the proof is to compute the strong convexity coefficient of L on W. Since C is twice differentiable, can be directly done by computing lower bound the minimum Hessian eigenvalue on W: for any w E W.
N-1
V VOC(w) = Σ (x (.:w)aa w 2=
min
(I w) xxT 2 uI.
iEl0:N-1 wEW
This concludes the proof Lemma 5.1.
G.1.1 PROOF OF LEMMA G.4
For the sake of readability, restate the lemma.
Lemma G.4 (Backward recurrent inequality). Consider learning M linear classification tasks cyclically. Suppose that Assumption 5.2 holds. Let B ΣM-1 Bm. If take any step size the iterates of sequential GD satisfies
satisfying 2/2KB'
(6+1)M) - ul
w
M-1 2n [c (M)) - [(w) + K22
(M
uel"
Σ Am=0
for any vector Rdd and for all j 0.1.....
62

---

Published as a conference paper at ICLR 2025
We start the proof by bounding the squared distance between two iterates in the same cycle of continual learning. For [0 []] and m E [0: [0:M- M- -1], 1].
(jM)
(iM+m)
w0 ook
K
12
Σ
V mm f ( (i)+m))
M-1K-
M K-1
(1M 12
1/
B
Σ
Bi
h=0
1=0
h=0
$ KB
M
( (1M++))
Ve((w))]
+ +1(
31
1=0
h=0
M-1K-1
M-1
S <B
Σ
De. (u, wh
(2M+D) + K K
Σ [
(58)
3
We (modified) Jensen's inequality (e.g., Proposition G.2) in the first two inequalities above; the last inequality is due to Proposition G.I.
Next, we decompose the (j 1)-th squared distance into j-th squared distance and more:
(0+1)M) w
u
M- 1-1
-1w0
(JM)
u) + 100 VLilun ( (M+m)) ) w00 wooo))
GM) (G- (G1-1)a))1
2n1
K=
Using Equation (56) and 8m -moothhnesssss
(G+1)M) w
2
w
(JM) -ul 10|²
M-
K-1
21
Σ
Σ
L.
Lm (m)) Dr...
(wog .00k (m) - D (us, w (m)))
m=0 k=0
+ 100 (ja)
M-1K-1
< <2nn [ (o) (((b)))) C(us)
+
Σ
Σ
8m
2w
(jM)
wwx
m=0
k=0
M- K-1
2n Σ
Σ
Dem (ze, 20 20 ((M
2000
(101)
w
(
m== k=D
M-1 Σ m=0
<22nK [c (x)git)) - C(u)) +
[mm]ll)
Bm
(59)
M-1K-1
- 22n(1 - 2nKB - 2n² K22
Σ
Σ
Dem (zi, w
(jat 4ma)+m))
m=0
k=0
M Σ m=0
5-2nK ( (wobiM) C(u)
+ +2
[V
3
In Equation (59), the result from Equation (58) multiple times. The last inequality is due to
our choice of step size: 1) B < This is the end the proof.
v3-1
2 - 1 (:: 2g 2q² 2 0f
0, / 3-11
2/2
1.1.2 PROOF OF LEMMA G.5
For the sake of readability, restate the lemma.
63

---

Published as a conference paper at ICLR 2025
Lemma G.5 (Boundedness of the end-of-cycle iterates). Consider learning M linear classification tasks eyclically. Suppose that Assumptions 5.1 and 5.2 holds. Let B Em=o Bm and V. Em=o I Vm (w.))l²- If we take any step size satisfying S 2/2KB' the end-of-cycle iterates Fm of sequential GD are contained in compact set which is fixed in terms of the number of the cycle: for all j = 0, ,,
-2 + +2v21 K2 BV
(JM) wi
E W =
w E Id ||-- - w.11
(C(w.) + /VBKBV.)) (17KKBV,)+(,.....1
Gb
5 w Rdd ||w0 w. 111125 Gb [((w.) + //² + +||2,|1| ||
V,
+
2v2B
Also, recall the backward recurrent inequality, which we write here again:
w (+1)M0)
w. I|= w (MM)
2n [c (00 (wof [(wc.) +2V2n2 2=2,,,
w.
(60)
(0) as we want: if wh (0) 0, since We choose wo
w
(0)
w.
|| = || it is clear that wo (0)
E W.
Now assume w
(jM) W and proceed with induction on j: we aim show w ((++)) E W.
The proof is divided into two parts:
1. If the current total risk is too high, then we can show that the squared distance to w, will decrease.
2. The other case means that the current iterate is close enough to w, (due to the strict non- separability of the full dataset). Thus, the squared distance w, at the next cycle will not grow that much.
Suppose L (( (w)) - [(w.) 2 V2 Then Equation (60)
Part 1: High-Risk Case.
implies
w (G++))
w. l| - 1w
(jM)
w.
Thus, ww ((++))M E W.
Part 2: Low-Risk Case. We first show that L (w)())) L(w.)) S 22n implies an upper
bound on the current squared distance to w. Because of Assumptions 5.1 and 5.2, for any w e Rd
L(w)=
8 (x.. w)
1=
N-1 2
[ T w
i=U
N-1
= G ||w||
[
==0
2 G || b,
by the definition of the non-separability
b > 0. Thus, we have
mn
(jM)
w.
< 100 (mb + +11ez=1
(jM)
(wo (() + ||wa|ll
<
Gb
1
[(()) + V2nKBV, + +||
Gb
(MM lies a strict subset of W. Also, Equation (60) implies Thus, wo
(G+1)M) w.]" < m w
(M)
w.
|| + K²²
64

---

Published as a conference paper at ICLR 2025
1 Gb
((u) VV, + +|ww|||
+ 22222
(G++))
Thus, by the definition of W, w
E W. This concludes the proof of the lemma.
G.2 NON-ASYMPTOTIC LOSS CONVERGENCE ANALYSIS (PROOF OF THEOREM 5.2)
Recall that write Em=o B. and V. = Em=O [V.((w.)l" Also, in the previous Fm
sub-section, discovered local strong convexity (with coefficient je > of the total risk function satisfied on compact ball W containing w, and every end-of-cycle iterate of the sequential GD.
Let us restate the theorem for the sake of readability.
Theorem 5.2. Suppose we learn M tasks cyclically for J > 1 cycles. We adopt the notation from Lemma 5.1. Then, with step size rj O min In(J) J
sequential GD satisfies
1 (MJ) w+
2 < O
exp
(1 + 2/2)
JJJ
20
(0) w.
B²V,In 1
10.
(7)
Remark G.1. In fact, the full expression of our step size choice is:
1 1+2 In _ max {1. 1, 11100
(U)
w. 113100
n= min 2/2KB' 2/2KJ
B
which is omitted in the theorem statement above.
The theorem states fast (()-3) rate of convergence. One could try to prove it with the backward recurrent inequality (Equation (57)), but is difficult due to the 17² dependency of the so-called "noise" term. We only succeeded in proving slower (J- rate with the backward recurrent inequality, whose proof is pretty much similar to that in this sub-section. To take a step further towards faster rate, we should use a different way of writing the recurrent inequality, with higher exponent for in the "noise" term. Here how goes:
Lemma G.6 (Forward recurrent inequality). Consider learning M linear classification tasks cycli- cally. Suppose that Assumption 5.2 holds. If we take any step size satisfying 1) S VIKB' the iterates of sequential GD satisfies
((+1)MM)
1
M-1 Σ m==
(MM) W
ul
2n/ [c m (o(6t))an) - - [(w)]
+ 2m K32
Bm
for any vector E Rdd and for all 0, 1,
Proof. We defer the proof to Appendix G.2.1. We remark that this lemma holds even without assuming the senaarabra.
In particular, we have
w (0+1)M) w.
1|2 s 20 GM
12 -2nK ( (o((++))))) [(wx))
w.
(61)
Applying p-strong convexity, i.e.
C (w - -(w.)
11 ((+1))M)
w
w.
2
we eventually have recurrent inequality purely on the squared distance to w.:
w (1-1)M w.
(jM)
w.||
||
+ 21 K B
(62)
KN K
We now conclude the proof by applying Proposition G.3: plugging < ,, 3 + B. - J, + 2/2' V <- 2B²V, m 2, and A, + mm
()
to the proposition, we have desired result.
65

---

Published as a conference paper at ICLR 2025
G.2.1 PROOF OF LEMMA G.6
For the sake of readability, we restate the lemma, whose proof is very similar that of Lemma G.4. Lemma G.6 (Forward recurrent incquality). Consider learning M linear classification tasks cycli- cally. Suppose that Assumption 5.2 holds. If we take any step size satisfying n S VIKB' the iterates of sequential GD satisfiss
100 1 (0+1)M)
M-1
10 (MM)
ul 2nk [c wm (ott))))) [(w)] 2n 2nn"K B2
Σ m==
1
<
Bi
for any vector E Id and for all j = 0, 1.
We start the proof by bounding the squared distance between two iterates in the same eycle of continual learning. For & [0: K 1] and m E [0: M 1].
(G+1)M)
w +mM++)
w
M
K-
K
=
V V
(M+H))
V V (wh (M)+m))
|==+11
h=0
M K
M-1K-1
11
Bt
Σ
h=0
1=0 h=0
M K-1
Vi - -Ve((u) +IVC(()))))
< 2BBBBB KB
31
h=0
M-1 K-1
M-1
S KB
Σ
Σ
De, (u, w
+ + (MM+D)
Σ
(63)
3
1=0
We use (modified) Jensen's 's inequality (e.g., Proposition G.2) in the first two inequalities above; the last inequality due to Proposition G.I.
Next, we decompose the j-th squared distance into (j + 1)-th squared distance and more:
M
K-1
w (1M) - ull 2 w
((+1)MM
ul] + 27
Σ
Σ
(MM+m))) ((+1))M) u
w
m== K=0
Using Equation (56) and Bm -mooooothnessss,
1 ((+1)M)
mo (jM) ual
M
- Σ Σ
(mm( (2m (1++1))00)
Cm
Cm((u) Dem (w
(0+1)M))
GM++m)) + De... (u, w (1M+m)))
M-1K-1
$ ~nn [c (wo
[(w]
+
Σ
3m w
((+1)M))
w (m))
m==
k=
M-1K K-1
2n
Σ
De... (u, ro (o(gamm))
m=0 k=0
M-1 1
s <22nK [c (m(((+)))m) c(w)]
K
Σ
||
Bm
(64)
M-1K-
- -27(1 2²²
Σ
Σ
Dem, (us, wi (1))
0=
66

---

Published as a conference paper at ICLR 2025
M Σ m=0
S -
[2 ( w ( - [(wi] + 2 B²
K
| Lm (u)l
3m
In Equation (64), we use the result from Equation (63) multiple times. The last inequality due to choice of step size: nKB V2"
This is the end of the proof.
67


Reviews:
[{"review_id": "gp5KY4dLfb", "reviewer": "Reviewer_sGag", "summary": "The paper considers continual learning setting in which a linear classifier is trained for a fixed number of iterations on tasks (either cyclic or random). In the separable case, the papers shows (directional) convergence to the offline (i.e., combined) max-margin classifier for cyclic and randomised ordering of tasks. In the separable, the paper also characterises (i) forgetting and (ii) backward transfer (for aligned tasks). The paper also shows convergence to overall minimum in the non-separable case.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Clarity : The paper is clearly written.\nSoundness : The theorems are stated clearly with proofs.\nOriginality : Shows results under fixed budget of iterations at every stage. This is an improvement over the Sequential Max-Margin.", "weaknesses": "The main weakness is in the novelty and significance.\n\n1) No experiment with real world dataset.\n\n2) No experiments with realistic synthetic dataset : The paper presents only one experiment on a synthetic dataset with 6 points. Experiments should be detailed in such a way to bring out all the important results.\n\n3) Setting may not be novel: Given that there is an overall linear classifier, the protocols of cycling training or randomised training seem superfluous. To elaborate, we are not in the online learning setting, so we have all the training data of all the tasks apriori. We also know that there is a single linear classifier. So what is wrong if we combine the datasets of all the tasks into one and train using SGD with batches of data (batches either cycled or random) as it is done always? \n\n4) Are batches Tasks? : It is a standard practice to use SGD with batches of data (either cyclic or random). And it is not surprising/novel to know that SGD with batch converges. Is the paper just fancily calling batches as tasks?\n\n5) No Connection to realistic/standard settings : The paper mentions that \"cyclic task ordering covers search engines influenced by periodic events. Random task ordering bears resemblance to Autonomous driving in randomly recurring environments\". These instances do convey meaning of cyclic, and randomised tasks for a reader who is looking at these the first time. However, the paper has to be specific in terms of specific set of standard datasets and standard real world scenarios. \n\n6) No recommendations for practice : Theoretical results are very important and sometimes can be obtained under even restrictive assumptions. However, the results should also give rise to some recommendation in realistic scenarios. This paper fails in this aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PV2x8pVus2", "reviewer": "Reviewer_1DCj", "summary": "This paper investigates how gradient descent (GD) converges to the joint max-margin solution for multiple tasks that are jointly linearly separable. The authors present loss and forgetting bounds under both cyclic and random task presentation orders. Theoretical results are provided for both asymptotic and non-asymptotic settings. Overall, this is a highly novel and interesting paper that offers promising insights for continual learning.", "questions": "I have the following questions:\n1. Can you provide the intuition about Assumption 3.4 Tight Exponential Tail?\n\n2. Figure 1 present a toy example to help us to understand the motivation, but all the tasks with labels 1. It seems not realistic, so I am curious whether this setting is necessary, can you make it more general.  \n\n3. What is the definition of task similarity in continual learning? Do $N_{p, q}$ and $\\bar{N}_{p, q}$ in Theorem 3.4 measure the task similarity? I hope the author can give the clear definition of task similarity. Intuitively, task similarity will affect the forgetting as well as training loss. For example, there are two tasks with significant different optimized directions and a model is trained to learn two tasks, I think it's usually harder than learning two similar tasks, so it probably has larger training loss. So it is reasonable that task similarity would affect the training loss either, do author agree with me?\n\n4. This paper gives a new definition about cycle-averaged forgetting $\\mathcal{CF}(J)$, and also show the upper and lower bound of $\\mathcal{CF}(J)$ in Theorem 3.4. I think this definition somehow restricts the forgetting measure within the current cycle. The problem is that can you guarantee the model performs better on task $m$ in the current cycle $J$ than before? If not, even if $\\mathcal{CF}(J) \\rightarrow 0$, we can not say the forgetting performance is good. Is it possible to change the baseline as $\\min_j\\mathcal{L}_{m}(w_K^{Mj+m})$, which considers the best performance of model on task $m$. Then the cycle-averaged forgetting $\\mathcal{CF}(J) = \\frac{1}{M}\\sum\\_{m=1}^{M-1}\\mathcal{L}\\_{m}(w_0^{MJ+M}) - \\mathcal{L}\\_{m}(w_K^{Mj+m})$\nwhich is consistent with conventional definition of forgetting.\n\n5. Line 412: $\\lim_{t\\rightarrow \\infty} x_i^T w_k^{(t)}=\\infty$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel analysis of continual learning: The paper contributes to the understanding of continual learning by offering new insights into the convergence behavior of gradient descent on multiple tasks.\n\n2. The presentation is clear and easy to follow.", "weaknesses": "This is a very novel and interesting paper, but I have the following concerns,\n\n1. The logistic loss function and linear model are somehow limited. We usually use large foundation model and cross entropy loss nowadays. So can this theorem be generalized to more practical cases. \n\n2. No convincing experiments and compared baselines are provided, such as deep learning experiments for continual learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7YX7FWTrNY", "reviewer": "Reviewer_uaBW", "summary": "This paper studies continual linear classification tasks by sequentially running gradient descent (GD) on the unregularized (logistic) loss for a fixed budget of iterations per each given task. When all tasks are jointly linearly separable and are presented in a cyclic/random order, the full training loss asymptotically converges to zero and the trained linear classifier converges to the joint (offline) max-margin solution (i.e., directional convergence). Additionally, when tasks are given in a cyclic order, non-asymptotic analysis on cycle-averaged forgetting and loss convergence at cycle $J$ are provided, which are $O(\\frac{\\ln^4J}{J^2})$ and $O(\\frac{\\ln^2J}{J})$ respectively. Lastly, when the tasks are no longer jointly separable and presented cyclically, a fast non-asymptotic convergence rate of $\\tilde{O}(J^{-2})$ towards the global minimum of the joint training loss is established.", "questions": "1. Could you provide a geometric interpretation or intuition of the theoretical results, just as what [Goldfarb et al. (2024)](https://arxiv.org/pdf/2401.12617), [Evron et al. (2023)](https://arxiv.org/pdf/2306.03534) and [Evron et al. (2022)](https://arxiv.org/pdf/2205.09588) did? \n\n2. Could you provide proof sketches and a technical overview of the theoretical analysis? In particular, it would be helpful to understand more about the connections and distinctions from prior works, such as [Evron et al. (2023)](https://arxiv.org/pdf/2306.03534) and [Evron et al. (2022)](https://arxiv.org/pdf/2205.09588), as well as what new technical contributions this work presents. Appendix A.1 provides a brief overview and comparisons with [Evron et al. (2023)](https://arxiv.org/pdf/2306.03534), but it lacks an in-depth discussion of the technical and theoretical challenges and contributions.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is easy to follow and clearly demonstrates the contribution of the theoretical results.\n\n2. When all tasks are jointly linearly separable, standard GD without any regularization not only learns every task but also converges to the joint max-margin direction eventually. The implicit bias happens on both cyclic/random task ordering, which is new to my knowledge.\n\n3. When tasks are presented in a cyclic order, non-asymptotic convergence rates are established: $O\\left(\\frac{\\ln^4 J}{J^2}\\right)$ if the tasks are jointly linearly separable, and $\\tilde{O}(J^{-2})$ if they are not.", "weaknesses": "1. The theoretical framework for continual learning in this paper does not fully align with practical settings in deep learning; for example, tasks are assumed to follow a cyclic order, although this is a common setup in theoretical studies on continual learning.\n\n2. The experimental setup of the paper is quite limited. While the toy example in Figure 1 effectively illustrates the motivation, additional empirical results under more practical continual learning scenarios—or at least beyond the simplest toy example—are necessary to validate the theoretical findings, e.g., the implicit bias phenomenon for both cyclic/random order, cycled average forgetting converges faster than the joint training loss.\n\n3. The proofs in the Appendix are involved. Although the remark paragraphs following each theorem provide brief explanations, proof sketches or high-level technical overviews for all of the theoretical results are lacking. Specifically, it is unclear what technical novelties are introduced from a high-level perspective and how the current analysis improves upon [Evron et al. (2023)](https://arxiv.org/pdf/2306.03534).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nCMR1IhzYx", "reviewer": "Reviewer_a4PQ", "summary": "The paper analyses continual learning in a linear classification setting.  \nThe analysis focuses on a simple unregularized setting with a fixed number of gradient steps per task (in contrast to a previous paper that studied the regularized setting when learnt to convergence).\nBoth asymptotic and non-asymptotic results are derived, showing that when task recur cyclically or randomly, the iterates converge to the global offline max-margin solution across all tasks.  \nThis paper advances the theoretical CL field by clearly showing a different behavior than the one of the weakly regularized case studied in a previous paper.", "questions": "I have no questions but rather some minor remarks that I suggest that the authors address in their revisioned version. I do not expect an author response on these bullets.\n\n- Line 62: I wouldn't say SMM *\"cannot be shown to converge to the offline max-margin solution\"*, but rather that it *does not always* converge to that solution (as shown in Figure 1c of Evron et al. 2023). Also, I'm not sure that it should be considered a *\"limitation\"* of SMM, since this is merely the behavior of the weakly-regularized setup. I wouldn't even say that it's an advantage of the unregularized setup on the weakly-regularized setup, but rather that we see here two different behaviors that can describe continual classification to some extent.\n- Figure 1 could be clearer. Maybe a 2d example would be more suitable for a paper? \n- Line 105: the sentence negates the forgetting and the loss but at this point it's still unclear what the difference is.\n- Line 112: is \"symptotic\" a word? That part of the sentence might need to be rephrased.\n- Line 143: \"be a set of\" => \"be the set of\"?\n- Line 212: not sure \"generic\" is a good choice here.\n- Theorems 3.1 & 4.1: \n    - In the second result, *\"Every data point is classified correctly\"*; perhaps say \".. is **eventually** classified correctly\"?\n    - The third result seems like an auxiliary result (proposition?) that is not of any practical interest (unlike the first two). I would reconsider its current location in the main results. \n- Figure 2: not very clear. Maybe add a subfigure with the actual 2d parameter space?\n- Line 432: do you really need to span the *whole* space? In linear regression we can usually ignore unused directions due to the rotation invariance. Maybe I am missing something, but please reverify this.\n- Line 434: strictly or strongly?\n- Line 436: *\"faster rate\"*, faster than what?\n- Theorem 5.2: authors should explain the differences from the separable case. And also explicitly explain how the bound on the iterate gap yields a bound on the loss and forgetting.\n- Line 506: \"implicit bias on\" => \"of\"?\n- Line 523 say *\"are no solution\"* instead of \"is\".\n\n- Many formulas in the Appendices exceed the page margins (e.g., Pages 19-20).\n- Some citations are incomplete or inaccurate. For instance, *\"Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate\"* was published at AISTATS 2019; and *\"Continual Learning with Tiny Episodic Memories\"* was published at ICML 2019.\n\n- Line 806-809: Evron et al. (2023) already showed it (see their aforementioned Figure 1c).\n- Line 828: might need rephrasing.\n- Line 831 say *\"contrained\"*.\n\n- Line 918: *\"proposed by indicates\"*, rephrase?\n- Line 1152: Missing whitespace.\n- Equations (74,75): It's not common to use the $O(\\cdot)$ notation for negative quantities. I think the authors need instead $\\log(t)-\\log(t-1)=O(t^{-1})$.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- **The paper is well written**.\n- **The contributions are clear and significant to the theoretical CL field**.  \nThe main results show the implicit bias of continual linear classification when learned in a practical setup with a fixed number of gradient steps, given that tasks recur in the sequence. Consequently, they show a separation between that setup and a previously-studied weakly-regularized setup which can be considered as less practical.", "weaknesses": "- **Results are not especially insightful**.  \nThe previous paper by Evron et al. (ICML 2023) proved a clear projection-like behavior (\"SMM\") under the weakly-regularized continual linear classification setup. Their results showed an iterative behavior that is somewhat insightful even for \"arbitrary\" task sequences.   \nHowever, the paper reviewed here proves a behavior that is only informative in the presence of task repetitions.  \n(This is not strictly a weakness since it might be the only behavior that one could possibly prove; but still it is only insightful given task recurrence.)\n\n- **The appendices are hard to follow and verify.** Many steps are insufficiently explained (e.g., it's not very clear how Eq. (20) stems from (19); the steps in Eq. (26) are also unclear).  \nThis prevented me from quickly validating a random subset of the proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)