Optimal Rates in Continual Linear Regression via Increasing Regularization
Authors: Ran Levinstein
Amit Attia
Matan Schliserman
Uri Sherman
Daniel Soudry
Tomer Koren
Itay Evron
Venue: NeurIPS 2025 poster ()
Keywords: continual learning
lifelong learning
last iterate
forgetting
task ordering
regularization
Primary area: theory
TL;DR: We prove that using regularization with either fixed or increasing strength yields near-optimal and optimal worst-case expected loss rates in realizable continual regression under random task orderings.

Abstract: We study realizable continual linear regression under random task orderings, a common setting for developing continual learning theory.
In this setup, the worst-case expected loss after $k$ learning iterations admits a lower bound of $\Omega(1/k)$. 
However, prior work using an unregularized scheme has only established an upper bound of $O(1/k^{1/4})$, leaving a significant gap.
Our paper proves that this gap can be narrowed, or even closed, using two frequently used regularization schemes:
(1) explicit isotropic $\ell_2$ regularization, and (2) implicit regularization via finite step budgets.
We show that these approaches, which are used in practice to mitigate forgetting, reduce to stochastic gradient descent (SGD) on carefully defined surrogate losses. 
Through this lens, we identify a fixed regularization strength that yields a near-optimal rate of $O(\log k / k)$.
Formalizing and analyzing a generalized variant of SGD for time-varying functions, we derive an increasing regularization strength schedule that provably achieves an optimal rate of $O(1/k)$.
This suggests that schedules that increase the regularization coefficient or decrease the number of steps per task are beneficial, at least in the worst case.

Optimal Rates in Continual Linear Regression via Increasing Regularization
Ran Levinstein" +
Amit Attia*
Matan Schliserman
Uri Sherman"
Tomer Koren
Daniel Soudry?
Itay Evron 4
Abstract
We study realizable continual linear regression under random task orderings, common setting for developing continual learning theory. In this setup, the worst- case expected loss after k learning iterations admits lower bound of (11/k). However, prior work using an unregularized scheme has only established an upper bound of O(1/1=/4), leaving a significant gap. Our paper proves that this gap can be narrowed, even closed, using two frequently used regularization schemes: (1) explicit isotropic &g regularization, and (2) implicit regularization via finite step budgets. We show that these approaches, which are used in practice to mitigate forgetting, reduce to stochastic gradient descent (SGD) on carefully defined sur- rogate losses. Through this lens, identify fixed regularization strength that yields a near-optimal rate of Ollog k/k). Moreover, formalizing and analyzing a generalized variant of SGD for vire-ng functions, derive increasing regularization strength schedule that provably achieves an optimal rate of (1/kk) This suggests that schedules that increase the regularization coefficient decrease the number of steps per task are beneficial, at least in the worst case.
Introduction
In continual learning, learner encounters a sequence of tasks and aims acquire new knowledge without "forgetting" what was learned in earlier tasks. Many algorithmic approaches have been pro- posed to address this challenge [see surveys in 45| 42]. However, a deeper theoretical understanding is still needed to clarify the principles governing continual learning and is essential for the practical and reliable deployment of such methods.
We study standard regularization-bass schemes in setting with random task orderings. Both the setting mndd-espccially--tee schemes play central role in the practical and theoretical continual learning literature, as discussed below. We find this combination mutually beneficial: (1) regulariza- tion improves the best known upper bound under random orderings, achieving optimal rate; and (2) randomness facilitates analysis that motivates heuristics for setting the regularization strength.
We focus two forms of regularization: a well-known explicit isotropic l2 regularization, and implicit regularization induced by a finite number of gradient steps on the unregularized loss each task. Prior work studied such schemes in restricted settings- -ie., two tasks (8 29), simplified data models (28, [48 (29), weak regularization
[3 23], or cyclic orderings [5]. contrast, we consider
any number of regression tasks drawn from any collection, under random orderings.
Equal contribution.
1 Department of Computer Science, Technion.
$ Blavatnik School Computer Science and AI, Tel Aviv University.
Blavatnik School of Computer Science and AI, Tel Aviv University, and Google Research. Department of Electrical and Computer Engincering, Technion.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Random task orderings are both theoretically motivated and empirically relevant: they closely characterize con-adversarial-aan and often realistic- task sequences; can be induced algorithmically via random sampling to actively mitigate forgetting; and are implicitly present in standard randomly generated continual learning benchmarks (e.g., split or permuted datasets). These orderings were found to have remedying effect on forgetting in continual learning, both empirically [27] 20) and
loss rate for linear regression with jointly realizable tasks is ((1/k//4) (14), leaving significant gap from the kk) lower bound that holds for any continual learning scheme.
theoretically [3 23 [14]. Under such orderings, the best known
In this work, we analytically reduce both the explicit and implicit regularization schemes incre- mental gradient descent, which aligns with SGD under random orderings. We prove that, under jointly realizable tasks, specific choices of fixed and increasing regularization strength schedules yield nearly-optimal and optimal rates of (log k/ and (11kk) respectively.
Summary of contributions. Summarized more technically, our main contributions are:
We reduce continual linear regression with either explicit l2 regularization or finite-step budget to incremental gradient descent surrogate losses. These reductions enable unified analysis, even under arbitrary task orderings and non-realizable settings. Figure ! visualizes our analytical flow.
In the realizable case under random task orderings, where the best known bound of (1/k2/1) is obtained via an unregularized continual scheme:
We prove that a carefully fixed regularization strength yields a near-optimal worst-case expected loss of Ollog k/k).
We introduce and analyze generalized form of SGD for time-varying objectives and use it to propose an increasing regularization schedule that achieves the optimal rate of O1/kk) closing the existing gap between upper and lower bounds. See Table T for a summary.
Table 1: Loss rates in realizable continual linear regression (based Table 1 of Evron 12 Upper bounds apply to any M jointly realizable tasks. Lower bounds indicate worst cases attained by specific constructions, Bounds for random orderings apply to the expected loss. We omit unavoidable scaling terms and constant multiplicative factors (which are mild).
Notation: iteration; d dimensions; F, Tmax
average/maxinum data matrix ranks; a A min(a, b).
Random with Replacement
Bound
Regularization
Paper/ / Ordering
Cyclic
M Vk
2
Tmax
Evron al. 12
k
M
Unregularized
Kong al.
26
k
Vd -
MF
Upper
Evron et al.
M / /og (k/M)
Fixed (explicit)
C&D
k
log k
Fixed
Ours
Inereasing
Ours
1
Ar2
Unregularized
Evron et al.
(+) k
k
Lower
Any
Ours
(++)
(*) They did not explicitly present such lower bounds, but the 2-task construction from their proof of Theorem 10, can yield @11kk) random behavior by cloning those 2 tasks [M/2] times for any general M. (*+) While the proof is standard, aware of an explicit statement in the literature.

---

2 Setting: Continual linear regression with explicit or implicit regularization
We focus the widely studied continual linear regression setting, which, despite its simplicity, often reveals key phenomena and interactions in continual learning (e.g.. 1.. 12 16 36
28
48
Notation. Bold symbols are reserved for matrices and vectors. Denote the Euclidean (vectors) or
spectral (matrices) norm by II-II, and the Moore-Penrose inverse by X+, Finally, denote [v]] 1, .
Throughout the paper, the learner is given access to a task collection of M linear regression tasks, that is, (X1, y1). (XM, M. YM), where X. E R and ym. E _ We define the data "radius" as task ordering 7: [k] M). The learner aims accumulate expertise, quantified by the objective below.
R _ max X 12-- Over & iterations, tasks are presented sequentially according
Definition 2.1 (Average loss). The average- population-loss is defined the mean training loss across all individual tasks m E M. That is,
M
[(w)
Σ
L(W; m)
Σ
X
ym
M
2M
Remark 2.2 (Forgetting and seen-task loss). Prior work analyzed not only the loss over all tasks but also the forgetting, or loss on seen tasks. Under the random orderings considered here, all these quantities are typically close. We thus focus average loss and discuss the others in Section
Explicit regularization. A large body of practical continual learning research focuses on mitigating forgetting by explicitly penalizing changes in parameter space [e.g.. 25 47 6 Many employ
regularization terms based on Fisher information 4), though others have found empirically that & (isotropic) regularization often performs comparably well [32 40). Following recent theoretical work
[e.g.. 28 13 5),
we also focus on isotropic regularizers but discuss alternatives in Section 4.3
Scheme Regularized continual linear regression
M Input: Regression tasks (Xm, ym) m= task ordering т, regularization coefficients (Ae)
Initialize Wo Ogd For each iteration 1,...,k::
Wt + arg min X Vr. 11 Output Wy
2/ ||w 3
Remark 2.3 (Unregularized first task). Our analysis is also valid for the common choice A1 + O.
While the continual update step above admits closed-form solution-useful for theoretical analysis [e.g., 288 -our paper does not directly leverage it. Instead, in Section 3 we reduce this step-which solves entire task-to a single gradient step, thus enabling last-iterate SGD analysis of the scheme.
Implicit regularization. Practically, it is common to minimize the current task's unregularized loss with gradient algorithm for a finite number of steps (e.g., (24); contrast to theoretically learning to convergence [12 [4)). This implicitly regularizes the model, even in stationary settings 1 41
Recently, it has attracted theoretical interest in continual setups [23 48
Scheme Continual linear regression with finite step budgets
Input: Regression tasks {(Xm. Xm) vm) m task ordering т, inner step counts and sizes (Ne, 7e) )
Initialize Wo = 0₂
For each task /. = k; Initialize (0) <- W,-1
For 1....,N; Ny: # Perform N2 gradient steps on the current task's unregularized loss.
(+) w(s-1) - v X, w(--1) - -yr
Wr t (N.)
Output Wt
Regularization strength. The coefficients X, and step counts N₂ in Schemes and control the "regularization strength" and determine how well the current loss minimized ooten seen as tuning the stability trade-off [18 45). Our paper identifies choices that yield improved bounds.

---

3 Regularized continual linear regression reduces to Incremental GD
Evron al. [14] proved reduction from unregularized continual linear regression to "stepwise- optimal" SGD scheme, where a single SGD step corresponds to solving an entire task. This has allowed them to use last-iterate SGD analysis to study continual learning, as we do in Section
We define the Incremental Gradient Descent (IGD) scheme to cast both Schemes] [ and 2 within a unified framework, enabling a common analysis. The reductions and the flow in which we employ them are illustrated in Figure |
At each iteration 6, the algorithm performs a gradient step on the tire-varying smooth convex function (t: Te), selected by the ordering т, using step size Tt--
Scheme 3 Incremental Gradient Descent for smooth, convex, time-varying functions M
Input: Smooth, convex, time-varying functions (:mm) m=r- ordering т, step sizes (nt)
Initialize Wo E Id
For each iteration t 1, I,...,k: k:
Wt 4 W Output Wy
# Perform a single gradient step on the current objective.
We present two reductions that cast regularized and budgeted continual regression special cases of incremental gradient descent. Proofs for this section are provided in Appendix C
Reduction 1 (Regularized Continual Regression + Incremental GD), Consider M regression tasks {(Xm, Ym ) m= seen in any ordering Then, each iteration i [k] of regularized continual linear regression with coefficient d > O is equivalent to an IGD step on (:5() with step size πu >> O, where f( (w; m)
1 (w - - x for some ( depending on Xe, TJ. That is, the iterates of Schemes 7 aad coinniie.. coincide.
Reduction (Budgeted Continual Regression = Incremental GD). Consider M regression tasks {(Xm y mm) m=1 seen in any ordering Then, each iteration E [k] of budgeted continual linear regression with N₂ E N inner steps of size nt E (0, 1/R2) is equivalent to an IGD step on f(.)) (:; Te) with step size Tt > O, where f(()) (w; m) A V (w- x tm)) for some Am depending on No, Tt: Th. That is, the iterates of Schemes 2 land 3 coincide.
(1)
Proof idea. The updates (Wt-1-w/ in Schemes I and are affine in W and thus correspond to gradients of quadratic functions. By setting A
Y (Le X [x]x,, Xela) in Reduction
(t) 1 (Ia (Ia - 7t X Xm) Mi in Reduction each of those updates coincides with an and Am
IGD step on the quadratic surrogate (w; = =ll 0 (w X xm)
Next, we establish key properties of the surrogate objectives ,,"), which hold regurdless of task ordering or realizability. Importantly, they enable last-iterate GD analysis for continual regression.
Lemma 3.1 (Properties of the IGD objectives). For t E [kc], define f( 110 and recall the data radius R A maxme[Jx] |Xmll2
((0)) as in Reductions and
(i) f( (5()) are both convex and (-smoout D Ffor 2640) A 1 n2a
A 1 (1 n. N...
ne R+
Th
(ii) Both functions bound the "excess" loss from both sides, i.e., Vw Rd Vt E 1k),mm Vm E [mm]
R2
dep: f(()) (1:::: m) [(w; min L(w': <
f(t)
(w; m),
B(9))
R²
1 (w; S [(w; min L(w':m) S NNe
The
f
(w;m).
w'
8
(iii) Finally, when the tasks are jointly realizable (see Assumption 4.1 the same w, minimizes all surrogate objectives simultaneously. That is,
L(w 4: m) = f(()) (w.: m) = f(() (w.; m) = 0, Vt [k)] Vm E [M] 'A function h; 1 E. is 8-smooth when [y) Vh(x)) - 9 [ly x1| for all 2. E Edd

---

Continual I Linear Regression: unregularized, learned convergence
Continual Linear Regression: explicit, isotropic, E regularization
Continual
Linear Regression: implicit regulum regularization via finite step size budgets
Incremental GD:
Incremental GD:
B-smooth functions, fixed, "step-wise optimal" step size of 1/B
Smooth functions, tunable smoothness & step size (fixed or scheduled)
1 -
Random Task Orderings
Last-Iterate SGD Analysis
Last-Iterate SGD Analysis for Time-Varying Varying Functions
Loss Forgetting Rate:
Loss Forgetting Rate: near optimal 0 klogk/k) via fixed regularization
Loss Forgetting Rate:
111/k1/)
optimal (11/k) via increasing regularization
for unregularized CL
(a) Previous Results (Evron [14])
(b) New Results (Ours [2025))
Figure 1: Schematic overview of our contributions compared to prior results. Evron et al. 14 reduce unregularized continual linear regression to incremental gradient descent on surrogate objective with fixed smoothness. They then analyze the last iterate of SGD to derive loss rate of O(1/k!/4) under random task orderings. In contrast, we show that adding explicit or implicit regularization enables tuning the smoothness of the corresponding surrogate objective. Importantly, this added flexibility allows a more nuanced last-iterate analysis: a well-tuned fixed regularization strength yields near-optimal Oloo k/k: rate, while specific increasing schedule achieves the first O(1/k) rate for continual linear regression under random orderings.
Rates for realizable continual linear regression in random orderings
Jointly realizable regression. In this section, focus setting in which the training data of all tasks can be perfectly fit by a single predictor-a common assumptior in theoretical continual 17 23 [1]. This assumption simplifies analysis by allowing all iterates to be compared to a fixed predictor, ruling out task collections with inherent contradictions. Such realizability often holds in highly overparameterized deep networks, which typically be optimized to arbitrarily low training loss. In the neural tangent kernel (NTK) regime [22) 71. such networks exhibit effectively linear dynamics that closely align with our analysis.
learning [e.g.. 12 [3 26
Assumption 4.1 (Joint realizability of training data). There exists an offline solution w, E Rd s.t.,
X Yms
Vm
[M].
We note in passing that even under this assumption, models still suffer from forgetting prior expertise- sometimes catastrophically. as thoroughly discussed Evron al. 12
Random task orderings. We study random orderings natural model of adversaraal task sequences (38). Such orderings avoid worst-case pathologies and allow reductions to standard stochastic tools. They are implicitly used when generating common random benchmarks (e.g., permuted or split datasets), and can also be induced a algorithmically by random sampling. These
settings have been studied empirically [27 (20 and theoretically 12 known rates under random and cyclic orderings.
K 23 14
Table compares
Definition 4.2 (Random task ordering). A random task ordering samples tasks uniformly from the collection [M]. That is, Ti...., Unif ([M]), with or without replacement.
'Other theoretical works similarly assume an underlying linear model, but allow additive label noise.
This. however, almost invariably requires assuming either i.i.d. features [66 3 or commutable covariance
matrices across tasks (28 29 48 whereas allow arbitrary data matrices, enabling worst-case analysis.
5

---

An immediate lower bound. Under random ordering with replacement, no algorithm can achieve a worst-case expected loss convergence rate faster than ((1/k). This result, which stems from the uncertainty over unseen tasks, is formally established in Theorem B. and serves as baseline for evaluating the tightness of our upper bounds.
Lastly, throughout the section, use the data radius R - [MX [m
4.1 Near optimal rates via fixed, horizon-dependent regularization strength
We apply last-iterate convergence results for SGD to the surrogate losses used by IGD under random orderings. Our analysis first considers the fixed-regularization setting, which is common in practice and-unlike our result with increasing regularization- -xteads cleanly to random orderings without replacement (see Remark 4.5). Specifically, using the results of Evron et al. [14] together with the smoothness and upper bound from our Lemma 3.1 we establish the following.
Lemma 4.3 (Rates for fixed regularization strength). Assume random weph-repl ordering over jointly realizable tasks. Then, for each of Schemes 7 and 2 iterations upper bounded as:
the expected loss after k
(i) Fixed coefficient: For Scheme with regularization coefficient X > O,
[Wo
W
112 R2
E L (Wx)= S
2
Ra
Ra
R
R²+X
(ii) Fixed budget: For Scheme 2 with step size y E (0, 1/2) and budger N
||wo 100-,,1 1 122
E, (Wx)
2 (1 - RR2)2N) (1-11-11- 1-01-181
All proofs for this subsection are provided in App. D
The rates established in Lemma 4.3 raise natural question: What choice of the regularization
strength-i.e., the regularization coefficient À or step count Nuuchieves the tightest bound?
Corollary 4.4 (Near-optimal rates via fixed regularization strength). Assume a random with- replacement ordering over jointly realizable tasks. When the regularization strengths in Lemma 4.3 are set as follows:
(i) Fixed coefficient: For Scheme set regularization coefficient X A R 1);
(ii) Fixed budget: For Scheme choose step size E 10,1/R²) and set budget N & In(1-12)
REy
Then, under either Scheme or Scheme 2 the expected loss after l 2 iterations bounded as:
5 5|/wo -
w.ll -.,ll
R ln
Remark 4.5 (Extension to without replacement orderings). The rates in Lemma 4.3 and Corollary 4.4
extend to random orderings without replacement; see App. D for details.
This marks a significant improvement over the (1//k1/4) rate established by Evron et al. [4] for the unregularized scheme. By tuning the regularization strength, gain control over the smoothness of the surrogate losses f(()) and f( in Reductions and allowing us to attain the Olog k k/k) rate that optimal within the SGD framework used in their analysis. In contrast, their unregularized scheme lacked this flexibility, which made achieving such rates considerably more difficult and potentially of reach. A similar rate also be derived from the last-iterate bounds of Varre al. [43], the smoothness induced by our choice of regularization falls within the applicable regime of their results.
While the rate we obtained in the corollary is closer to the lower bound of ((1/k), gap remains. This leaves an open question: can regularization be used to match the known lower bound? In the next section, develop techniques to answer this question.

---

4.2 Optimal rates via increasing regularization
We present the first result in continual linear regression that achieves the optimal rate for the last iterate, matching the known lower bound. This is obtained by employing schedule in which the regularization strength increases over time. We discuss these findings and their connections to prior work in Section 6
All proofs for this subsection are provided in App. H
Theorem 4.6 (Optimal rates for increasing regularization). Assume a random with-replacement
ordering over jointly realizable tasks. Consider either Scheme or Scheme 2 dependenn schedules:
with the following
13R²
k+
(i) Scheduled coefficient: For Scheme set regularization coefficient A
3
t 2 k -
(ii) Scheduled budget:
k t +
For Scheme choose step sizes " E 10.1 and set budget N; 13
k+1
Then, under either Scheme 7 or Scheme 2 the expected loss after ls 2 2 iterations is bounded as:
20 wwo
w. R²
E,((we) <
k+1
Proof technique: Last-iterate analysis for time-varying objectives. Establishing the theorem requires novel last-iterate bound in stochastic optimization, as no existing analysis yields a (11/k) guarantee for last-iterate convergence in the realizable setting. A standard path to such rates is to use decreasing step-size size schedule. However, our setting is more nuanced: the quantities we control are the regularization strengths-iae the regularization coefficient or step budget in Scheme I - which inherently modify the surrogate objectives fK²) and f((²) in Reductions and
To handle this, we analyze SGD applied to time-varying objectives a generalization of standard SGD, For this analysis to yield meaningful guarantees, the evolving surrogates must closely approximate the original loss. Indeed, this condition holds, as verified by Lemma 3.1 thus enabling the application
of the next lemma Fl
Lemma 4.7 (SGD bound for time-varying distributions). Assume t is a random with--relaacment ordering over M jointly realizable convex and 3-smooth loss functions f(; m): Rd + R. Define the
average loss f(w) & (m: m). Let 2 2, and suppose (:(m) t [kb], m E [M] are time-varying surrogate losses that satisfy:
(i) Smoothness and convexity: (-:m) are B-smooth and convex for all E [M], [k]]
(ii) There exists a weight sequence V/,,..,, Vy such that for all m E [M,t E [k), w E Rd:
(w) m)) (w)) & f(w;:) - ( (F+ - ((0((w);
(ii) Joint realizability:
w. E OsE(M) [m][M] arg min (w;;;; Vm E [M], [k], fk), (w.::) = f(w.:m).
Then, IGD (Scheme
3 with diminishing step size that satisfies V S = k-l+2
Vt E for
some S 3/333), guarantees the following expected loss bound:
Ef(ws) f(w.) 27 +
|wo w.ll?
In particular, for 133
3 obtain,
20,3 |o -w.ll w
Ef(we) - f(w.) <
k+1
'While Lemma 4.7 serves Theorem i. our least beast-squares setting, it is stated more generally to apply to broader family of objectives.
7

---

4.3 Do not forget forgetting: Extension to seen-task loss
We now take the opportunity briefly revisit our results through the lens of other quantities of interest beyond the average (training) loss defined in Definition 2.1
Continual (or lifelong) learning aims develop systems that accumulate expertise over time- learning from new experiences without forgetting previous ones [33 15 While mitigating forgetting
has long been central goal in continual learning, practitioners often monitor it indirectly using
"positive" metrics, such as average accuracy or performance 25 25]
In theoretical work, however, it is essential to define such quantities explicitly. Doan al. [ defined forgetting at time k as the drift in model oulpuls, e-g., R >i= Xx, (Wx w:)ll Nevertheless, this can be large even if the model improves between times / and that is, in the presence of positive backward transfer.
An alternative forgetting definition, used, e.g., by Evron et al. 12 Lin et al. [31]. is loss degrada- XX, W. yr, Commonly, such works 112 [7] assume joint realizability (as we do). and also that the model is trained to convergence at each step, achieving zero loss on the current task. In that case, forgetting reduces to:
tion: I Σ t= ((WK;:)) () D6 t=1 XX, Wa Yr,
Σ
Σ
- Xx, Wk -r,ll" which is always non-negative and can be meaningfully upper bounded.
25
However. in schemes like our regularized approaches (Schemes [ and 2) where convergence is not achieved despite realizability, loss degradation can be negative due to backward transfer. As result, is sensitive to worst-case analytical "manipulations" and difficult analyze theoretically.
We introduce more suitable alternative: the seen-task loss, which quantifies performance on previously encountered tasks. Importantly, this quantity is always non-negative and decreases in the presence of desirable backward transfer.
[M] be the task ordering, and let Wμ. be the iterate (parameters) after lt steps. The seen-task loss at step le is defined as
Definition 4.8 (Seen-task loss). Let [k] -
k
1 7:
(
((wesT))
In App. we extend Theorem 4.6 from the average loss to the seen-task loss. Specifically, we show that increasing regularization also achieves an O(1/k) rate for the expected seen-task loss. But, is this the optimal rate for seen-task loss?
The next lemma shows that, at least under explicit isotropic regularization (Scheme I.. it is optimal. Proof in App. B More precisely, under random task orderings, no regularization schedule yields rate faster than (1/kk) for the expected seen-task loss. In Section we discuss how non-isotropic regularization
the cost of additional space complexity-
ensure seen-task loss of zero.
Lemma 4.9 (Lower bound for seen-task loss of the isotropic Scheme I Junder any coefficient sequence). For any d 2 initialization Wo Rd. and regularization coefficient sequence A1...., A 2 O. )
there exists a set of jointly realizable linear regression tasks {(Xm Ym) I== such that, under with-reelacemmnt random task ordering, Scheme 7 iinuus seen-task loss L1s = [((1k)) with probability least 1/10.
5 Related work
Explicit regularization. Recent theoretical work on continual learning has studied the explicitly regularized scheme (Scheme I1 in continual linear regression settings [28 48, 29), with several key differences from our work. Like we do, these papers focused on settings where labels stem from an underlying linear model. However, they analyzed the generalization loss given noisy data, while we analyze the training loss given noiseless data. Theirs may sound like a "stronger", more permissive setup, but comes the price of very restrictive assumption: the expected task covariances ЕX X,,..., T X, XM are assumed to commute. This commutativity removes forgetting due to misaligned feature subspaces across tasks, leaving noise as the sole culprit behind any degradation.
To minimize the expected risk under this assumption, Zhao et 48 proposed regularization weight matrix proportional to the sum of observed task covariances, which-like our proposed

---

schedule increases over time. However, their approach is conceptually distinct from ours: the mechanism driving their schedule exploits the commutativity assumption, which eliminates task misalignment, whereas our schedule explicitly mitigates degradation caused by such misalignment. As result, the motivations and quarantees-behing the two schedules are fundamentally different.
Li et al. [2 29 focused exclusively on sequences of M = 2 tasks. Li et al. (28) derived risk bounds for isotropic regularization (Scheme D and highlight trade-off between forgetting and intransigence. Li et al. [29] demonstrated that, under additional restrictions on the data matrices, there is a trade-off' between increased memory usage and the performance of regularized continual linear regression. In all these works, performance degradation is attributed solely to label noise. In contrast, we analyzed interference that arises even the absence of noise. Accordingly. their focus lies complementary regime that does not capture the challenges we address.
Finite step budgets. Two main theoretical works studied the finite budget setting (Scheme 2 Jung et al. [2 analyzed continual linear classification under cyclic and random orderings. For cyclic orderings, they provided convergence rate for the loss; and, for random orderings, they only proved asymptotic convergence. Moreover, classification settings can yield different results and conclusions compared to regression settings [see 13). Zhao et al. [48] analyzed both regularized and budgeted continual linear regression schemes under restrictive assumptions, showing that a carefully constructed, task-dependen regularization matrix can force the iterates of the regularized scheme to match those of the budgeted one. This alignment, however, requires precise knowledge of task covariances and breaks under standard isotropic l2 regularization. In contrast, our unified reduction of both schemes IGD (Section B) avoids this limitation entirely.
Proximal method. Cai and Diakonikolas S analyzed the Incremental Proximal Method (IPM), corresponding to isotropic l2 regularization, under cyclic orderings. They provided convergence rates for convex smooth convex Lipschitz losses with bounded noise, but their guarantees only become meaningful after multiple full sweeps (or epochs) over the task sequence. In contrast, we analyze the random orderings and establish nontrivial-and even optimul--uuranteer without requiring repeated passes, See Section 6 for a comparison with our regularization schedules.
6 Discussion
Our work reduces regularized continual linear pegression-hhttiee using explicit or implicit regularization-tte to incremental gradient descent on smooth surrogate losses. This reduction enables last-iterate SGD analysis under random task orderings and yields significantly improved convergence rates. Specifically, we show that a suitable fixed regularization strength achieves a near-optimal rate of Ollog k/k), while a carefully chosen increasing strength schedule achieves, for the first time, an O(1/k) rate, matching the known lower bound. See Figure and Table for a summary of the reductions and improved rates.
Regularization strength scheduling. In Section 4.2 we derived an optimal regularization schedule in which the regularization strength increases with each task. This implies that the parameters change progressively less over time. Interestingly, such an attenuation in "synaptic plasticity" is also observed in biological systems: the rate which synapses grow or shrink response to sensory stimulation or motor learning [21] significantly decreases over time as the brain matures 35)
In continual learning, many papers practically set fixed regularization coefficient À through simple hyperparameter tuning. However, non-isotropic weighting schemes often encode an implicit scale in the weighting matrices they compute. Methods such as EWC (55 and Path Integral 47] are particularly sensitive to X, as their weighting matrices tend to have low magnitude early in training and may increase over time [O]. This initially low regularization strength was considered problematic by some [e.g..G. d and was even canceled algorithmically. as it allows excessive plasticity in early tasks. Yet, one may argue that high plasticity desirable in the beginning of long task sequences, where substantial expertise remains to be acquired. Our analysis in Theorem 4.6 supports this intuition, showing that in such cases, an increasing regularization schedule yields optimal upper bounds under random task orderings. See also the findings and discussion in Mirzadeh et al. R4 on the effects of a decaying step size, which as noted in our Section 2 corresponds to an increasing regularization strength.

---

Analytically, Evron et al. [13] showed that in continual linear models for binary classification, increas- ing the regularization coefficient can be harmful to convergence guarantees (see their Example 3). However, their analysis applies only to weakly regularized schemes (where A - 0 for all (), and the problematic schedule they presented increases the coefficient at a
rate-in con- trast to our Theorem 4.6 which utilizes finite, and relatively large, coefficients that increase linearly. Under cyclic orderings over linear regression tasks, solved with explicit regularization (Scheme D. the analysis of Cai and Diakonikolas [5] dictates a fixed coefficient = 2M It2 v /lu(k//M In contrast, under random orderings, our fixed variant in Section 4.1 sets À = R k- - 1). While both choices grow at most logarithmically with k theirs grows with the number of tasks M, making it less suitable for "singlc-epoch"
thoughh effective in the multi-epoch regime that they studied.
To complement our analysis, App. A empirically examines a simple two-task setup trained under the sppliit-regularization scheme with random task ordering. Interestingly, in this -on-worst- setting, the optimal fixed regularization, obtained by minimizing the expected loss after l steps, exhibits an approximately linear dependence on k in contrast the logarithmic scaling we predicted for the worst case.
Non-isotropic explicit regularization. Throughout the paper, we assumed Scheme uses isotropic Eg regularization. Such regularization often performs competitively with weighted schemes practice The latter, widely used in the literature, typically rely on weight matrices derived from Fisher information, often approximated by their diagonal [25] 47 2 Theoretically, using the full Fisher matrix from previous tasks requires (dd) memory in the worst case, but guarantees zero seen-task loss (Definition (4.) that is, complete retention of past expertise (see Proposition 5.5 of Evron et al. [33 and Proposition 5 of Peng et al. (36)). Closed-form alternatives include Recursive Least Squares (Chapter 12.2 in () and its block variant BRMP [49], which likewise maintain an explicit second-order memory to prevent forgetting, More generally, the rank of the regularization weight matrix can offer a trade-off between memory and forgetting (29).
[32 40
Last-iterate convergence of SGD in the realizable smooth setting. Our Lemma 4.7 originally proved to leverage the reductions from continual learning to the incremental gradient descent method, also establishes a last-iterate convergence guarantee for a variant of SGD that may be of independent interest. By setting the surrogate functions equal to the original functions, this result yields (1/k) convergence guarantee for convex smooth optimization in the realizable regime, using a linear decay schedule [9. To our knowledge, this is the first fast-rate guarantee for the last-iterate convergence of SGD in the realizable setting. It not only generalizes prior results specific to least-squares problems 43 but also improves the convergence rate from Ollog T/T) to the optimal (1//T).
Future work. While establish optimal rates for realizable continual linear regression with regularization under random task orderings, several directions remain open. First, empirical validation on standard continual learning benchmarks would test the practical impact of our regularization strength schedules, Second, extending our reduction- based analysis to simple nonlinear models could reveal whether similar schedules yield optimal convergence in more expressive settings.
Perhaps more fundamentally, it remains an open question whether comparable bounds can be achieved without regularization that is, whether the gap between the upper bound of Evron et al. [14] and the lower boundoboo shown in Table []] can be closed. Clarifying this would shed light on whether regularization is essential for achieving optimal rates, or if it simply serves role convenient analytical device. Addressing these questions may help close the gap between theoretical guarantees and practical continual learning systems. Finally, fully understanding the role of regularization in typical (non mon--worst-case settings remains an open question for future work.
Acknowledgments and Disclosure of Funding
We thank Edward Moroshko (University of Edinburgh) for insightful discussions.
The research of TK has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the
10

---

granting authority can be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant number 3174/23), from the Israeli Council for Higher Education, and grant from the Tel Aviv University Center for Al and Data Science (TAD).
The research of DS was funded by the European Union (ERC, A-B-C-Deep. 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair AL.
References
[1] A. Ali, J. Z. Kolter, and R. J. Tibshirani. A continuous-ting view of early stopping for least squares regression. In The 22nd international conference on artificial intelligence and statistics, pages 1370-1378. PMLR, 2019. (cited on p.
[2] R. Aljundi, F. Babiloni, M. Elhoseiny, M. Rohrbach, and T. Tuytelaars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pages 139-154, 2018. (cited on p.
[3] M. Banayeeanzade, M. Soltanolkotabi, and M. Rostami. Theoretical insights into overparam- eterized models in multi-task and replay-based continual learning. Transactions Machine Learning Research, 2025. ISSN 2835-8856. (cited on p. 5
[4] Benzing. Unifying regularisation methods for continual learning. AISTATS, 2022. (cited on TOp
[5] X. Cai and J. Diakonikolas. Last iterate convergence of incremental methods and applications in continual learning. In The Thirteenth International Conference on Learning Representations, 2025. (cited on p. 9 [0]
[6] A. Chaudhry, P. K. Dokania, T. Ajanthan, and H. Torr. Riemannian walk for incremental learn- ing: Understanding forgetting and intransigence. In Proceedings of the European conference on computer vision (ECCV), pages 532-547, 2018. (cited on p.
[7] L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buce E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. (cited on p.
[8] E. Chong and S. Zak. An Introduction to Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimi. Wiley, 2004. ISBN 9780471654001. (cited on 10
[9] A. Defazio, A. Cutkosky, H. Mchta, and K. Mishchenko. Optimal linear decay learning rate schedules and further refinements. arXiv preprint arXiv:2310.07831, 2024. (cited on p. 10)
[10] M. Delange, R. Aljundi, M. Masana, S. Parisot, X. Jia, Leonardis, G. Slabaugh, and
T. Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. (cited on p. 9
[11] T. Doan, M. Abbana Bennani, B. Mazoure, G. Rabusseau, and Alquier. A theoretical analysis of catastrophic forgetting through the ntk overlap matrix. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 1072-1080, 2021. (cited on p.
[12] Evron, E. Moroshko, R. Ward, N. Srebro, and D. Soudry. How catastrophic can catastrophic forgetting be in linear regression? In Conference on Learning Theory (COLT), pages 4028-4077 PMLR, 2022. (cited on p.
[13] I. Evron, E. Moroshko, G. Buzaglo, M. Khriesh, Marjieh, Srebro, and D. Soudry. Continual learning in linear classification on separable data. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 9440-9484 PMLR, 23-29 Jul 2023. (cited p.
10
11

---

[14] I. Evron, R. Levinstein, M. Schliserman, U. Sherman, T. Koren, D. Soudry, and N. Srebro. From continual learning sgd and back: Better rates for continual linear models. arXiv preprint urXiv:2504.04579 2025. (cited on p. 2
6
15
23
24
[15] R. M. French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, 3(4):128-135, 1999. (cited on p. 8
[16] D. Goldfarb and P. Hand. Analysis of catastrophic forgetting for random orthogonal trans- formation tasks in the overparameterized regime. In International Conference on Artificial Intelligence and Statistics, pages 2975-2993, PMLR, 2023. (cited on
[17] D. Goldfarb, I. Evron, N. Weinberger, D. Soudry, and P. Hand. The joint effect of task similarity and overparamettrization on catastrophic forgetting an analytical model. In The Twelfth International Conference on Learning Reprexentations, 2024. (cited on p.
[18] Grossberg. Processing of expected and unexpected events during conditioning and attention: a psychophysiological theory. Psychological review, 89(5):529, 1982. (cited on p.
[19] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234. PMLR, 2016.
(cited on p. .113)
[20] H. Hemati, L.. Pellegrini, Duan, Z. Zhao F. Xia, M. Masana, B. Tscheschner, E. Veas, Y. Zheng, S. Zhao, al. Continual learning in the presence of repetition. In CVPR Workshop on Continual Learning in Computer Vision, 2024, (cited on p.
[21] I.. Huang, H. Zhou, K. Chen, X. Chen, and G. Yang. Learning-dependent dendritic spine plasticity is reduced in the aged mouse cortex. Frontiers in Neural Circuits, 14:581435, Nov. 2020. doi: 10.3389//ncir.2220558 14355 (cited on p. (
[22] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. BesaaBBiacchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. (cited on p.
[23] H. Jung, H. Cho. and C. Yun. Convergence and implicit bias of gradient descent on continual linear classification. In The Thirteenth International Conference on Learning Representations, 2025. (cited on p- 5
[24] R. Kemker, M. McClure, A. Abitino, T. Hayes, and C. Kanan. Measuring catastrophic forgetting in neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. (cited p. 3)
[25] Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins. A. A. Rusu, K. Milan, et al. Overcoming catastrophic forgetting in
J. Quan, T. Ramalho. A. neural networks. Proceedings of the national academy of sciences, 114(13):3521-3526 2017. (cited on p. 3 10)
[26] M. Kong, W. Swartwotth, H. Jeong, D. Needell, and R. Ward. Nearly optimal bounds for cyclic forgetting. In Thirry-seentth Conference on Neural Information Processing Systems, 2023. (cited on p.
[27] T. Lesort, O. Ostapenko, Rodríguez, Misra, M. R. Arefin, L. Charlin, and I. Rish. Chal- lenging common assumptions about catastrophic forgetting and knowledge accumulation. In Conference on Lifelong Learning Agents, pages 43-65. PMLR, 2023. (cited on p. 2
[28) H. Li, J. Wu, and V. Braverman. Fixed design analysis of regularization-basel continual learning. In S. Chandar, R. Pascanu, H. Sedghi, and D. Precup, editors, Proceedings of The 2nd Conference on Lifelong Learning Agents, volume 232 of Proceedings of Machine Learning Research, pages 513-533. PMLR, 22-25 Aug 2023. (cited on p.
[29] H. Li, J. Wu, and V. Braverman. Memory-statistics tradeoff continual learning with structural regularization. arXiv preprint
2025. (cited on p. 5 9 10)
12

---

[30] Z. Li and D. Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40(11))22335 2947, 2017. (cited on p.p.l
[31] S. Lin, P. Ju, Y. Liang, and N. Shroff. Theory on forgetting and generalization of continual learning. In Proceedings of the 40th International Conference Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 21078-21100, PMLR, 23-29 Jul 2023. (cited p-
[32] E. S. Lubana, Trivedi, D. Koutra, and R. P. Dick. How do quadratie regularizers prevent catastrophic forgetting: The role of interpolation. In ICML Workshop Theory and Foundations of Continual Learning, 2021. (cited on 10
[33] M. McCloskey and N. J. Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989. (cited on p.
[34] S. I. Mirzadeh, M. Farajtabar, R. Pascanu, and H. Ghasemzadeh. Understanding the role of training regimes in continual learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. E. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7308-7320. Curran Associates, Inc., 2020. (cited on
[35] S. Navakkode and B. K. Kennedy. Neural ageing and synaptic plasticity: prioritizing brain health in healthy longevity. Frontiers in Aging Neuroscience, 16: 16:1428244, Aug. 2024. doi: 1..3889finagi.20244 1222244. (cited on P. P.
[36] L. Peng, P. Giampouras, and R. Vidal. The ideal continual learner: An agent that never forgets.
In International Conference on Machine Learning, 2023. (cited on 10
[37] S. Rebuffi, A. Kolesnikov, G. Sperl, and C. H. Lampert. icarl: Incremental classifier and representation learning. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5533-5542, Los Alamitos, CA, USA, jul 2017. IEEE Computer Society. doi: 10.1 P411009/CVR..2017... (cited on
[38] T. Roughgarden. Beyond worst-case analysis. Communications of the ACM, 62()):88-96, 2019. (cited on 5)
[39] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 112663-26770 2010. (cited on p. 31
[40] J. Smith, J. Tian, Y.-C. Hsu, and Z. Kira. A closer look at rehearsal- continual learning. In CVPR Workshop on Continual Learning in Computer Vision, 2023. (cited p.
[41] D. Soudry, E. Hoffer, M. Shpigel Nacson, Gunasekar, and N. Srebro. The implicit bias of gradient descent on separable data. JMLR, 2018. (cited on
[42] G. M. van de Ven, N. Soures, and D. Kudithipudi, Continual learning and catastrophic forgetting. arXiv preprint arXiv:2403.05/775 2024. (cited on P
[43] A. V. Varre, I.. Pillaud- Vivien, and N. Flammarion. Last iterate convergence of SGD for least-squares in the interpolation regime. In A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. (cited on p. 6 10
[44] R. L. Voglewede, K. M. Vandemark, A. M. Davidson, A. DeWitt, M. D. Heffler, E. H. Trimmer. and R. Mostany. Reduced sensory-evoked structural plasticity in the aging barrel cortex. Neurobiology of Aging, 81:222-233, Sept. 2019. doi: www.biijeuroiiiigiig..00000 06.006. (cited on
[45] I.. Wang, X. Zhang, H. Su, and J. Zhu. A comprehensive survey of continual learning: Theory, method and application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024. (cited p. 1
[46] M. Zamani and Glineur. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint arXiv:2307.11134 2023, (cited on p. 28
13

---

[47] F. Zenke, B. Poole, and S. Ganguli. Continual learning through synaptic intelligence. In
International Conference on Machine Learning, pages 3987-3995, PMLR, 2017. (cited on p.
9 TTp
[48] X. Zhao, H. Wang, W. Huang, and W. Lin. A statistical theory of regularization-base continual
learning. In Forty-first International Conference on Machine Learning, 2024. (cited on p.
3
5
[49] H. Zhuang. Z. Lin, and K.-A. Toh. Blockwise recursive moore-pennonn inverse for network learning. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52(5):3277-3250, 2021. (cited p. 10
14

---

A Empirical Illustration
In this section, illustrate the dependence of the optimal fixed regularization coefficient À the horizon & and task angle & in a simple two-task setup. Two single sample tasks are defined as X1 (1,0) 0) and X2 (cos 0, sin 0), trained under the explicit-regularizatio with random with-replacement ordering (Definition 4.2). For each (k, 0) we numerically determine the fixed coefficient X (k; 0) that minimizes the expected loss after steps. As shown in Figure 2 the optimal regularization grows roughly linearly with k, and its magnitude increases with A i-indicattnn that longer horizons and more misaligned tasks benefit from stronger regularization.
scheme (Scheme [
&
40
Angles between tasks
Optimal regularization A
0 = 1
θ = 0.01
e = 0.1
0 = 0.001
30
20
10
0
0
25
50
75
100
125
150
175
200
Iterations k
Figure 2: Optimal fixed regularization grows with horizon and task angle. Each curve shows X (k;; 8) obtained by minimizing the expected loss after it steps of the explicitrregularizztion scheme with constant A. We observe an approximately linear growth in & and higher optimal regularization for larger
Discussion. The qualitative behavior in Figure 2 aliign with the general principles established the paper, but the quantitative trend differs. Section 4 we prove an optimal time-varying regularization schedule and a near-optimal fixed coefficient for the worst-case analysis over arbitrary task distributions. Here, by contrast, we examine a simple two-task setting, where the empirically optimal fixed regularization X (k:; 0) grows approximately linearly with k, rather than logarithmically as predicted by Corollary 44.4 A plausible explanation that the worst-case distribution inducing the log(A (k) scaling is more complex than the two-task setup considered here, optimizing for this simple distribution yields an inherently different solution from the true worst-case behavior across all distributions.
Computation. compute the expected loss in closed form using an operator formulation similar to that of Evron et al. [14, originally developed to establish their fast ciimensionalliy-dpeendee rate. At each step Scheme
w: X,,,, + AI) 'XT.,, (X + AWw-1)), A 0.
15

---

Under realizabilitty (ym = X w.). defining Z, W. gives
2z (X,, + A1)
+ AW:-1) W.
-,, AI) X W. + AW:-1) W.
= =X,,X,, + +XI) (X,, X,, + AI)w. + A(W(-1--W -w.) W.
-w.+ X + XI) (wr-1 -w,) - W. -
=,(X;,X, X - 14-1-
Since is sampled independently each step, taking expectations the randomness of r gives E 2 ] E Xx, + +AI=
Elz I- A(X Xr, AI)-11
Starting from Wo = 0, the initial error is Zo = -W. so E/2020 = w.w.. Define the linear operator
Ωx Rdd dddd
2x [A] = E. XX AXX
By independence of T3 and Bt-1,
E Z 1
2^ [B 14
El = 2 [. [ww.
By Definition 2.1 the population loss after lo steps is the expected training loss across tasks:
1 ( Fl|x, - y-113]-
[[[((:)] =
Under realizability (y+ X, w.), this equals
B[[(w*)]] - - BlIIX. w.)ll]] Bl x, x
Taking the expectation inside the trace gives
[[[[w:)] TT E X X
E Bl222T)) 1 (E 2f(w.
To move 2 from w. ! onto E[X X, expand O along an i.i.d. sequence Ti,..., Th and apply linearity of expectation and the cyclic property of the trace:
TXX, @x(w.w..)
E E..... Th TEX X. A Ar, W.W. A, Arr) Ar, BXX [|X An, ... A. w.w.)
EEr,...
TIAA
THe X, w.W.).
where A, = A(XX + AI) Hence,
B[[(w+)] = T [
=
x+]] w.w.) = w, E x,] w.-
Taking the maximum over all unit teachers ||w.|| = gives the worst-case expected loss
L worst Amaxy OX
This formulation allows us to compute the expected worst-case loss for Scheme entirely in closed form. All stochastic effects of task ordering captured analytically through expectations, eliminating the need for Monte-Carlo sampling or repeated randomized experiments.
16

---

B Proofs of lower bounds
Theorem B.1. Let d and 2 2. Then for any algorithm A which receives k. functions fú, f......... fk. and a set k 1-smooth convex quadratic functions which are minimized at Wa. h hg IR_ - IR such that
Rd - I. and outputs a point in Ie, there exists a point w. E IR such that ||w/ll S 1
(00)),....(0)))))MM00)))0) (F((()))))) ((0))))))...,,,((00))))) F(w.) 2(1/k))
where F(w) 2 EEs
Proof. In the following proof we denote with w[i] the i'th coordinate of a vector w. Given an algorithm A, let hy (w) = w(12,. h, = h1 for i = ...... h 1, and EB (Vi E [M] r(() / k)
be the bad event where last index is not sampled. Note that x 2 4- for all E [0, z..
Pr(FB) (1
Let w be the (stochastic) output of A(hi ,.,..,, h1) (when A is presented with l: copies of h1), and let
Pr 2 L if Pr w 2 S
Let hx (w) ] (w[2] a)2. Note that all functions are 1-smooth, convex, quadratic, and minimized at w. = (0,a, .......). where /wwl || < 1. Hence, as w. is a minimizer of F(w),
([F(A(())))) hh ([F h1,..., - F(w.) Eg]
Pr(EE) (.(()))) F(w.) EB]
(Conditioned on EB. h (1) = (1)) for all i)
-P((E))EFF(ACC,, h.).. EB]
(h, (w.) = 0 for all i)
I Pr(EB Ehk (A(b,, hi,..., h1)) EB..
(F(w) 2 h4 (w) for any i, w)
k
Conditioned on En, with probability at least 1. w A(hi, hi,..., ,,1) satisfies (w [2] - a)² 2 1. Thus,
Pr(En)
(IF(A((T))....... - F((w)) 2
2 = ((1/k))
4k
16k
Our next lemma makes use of the Sherman-Morisee formula, stated below for completeness. Suppose X E dddd is invertible, and u, Rd. Then X + uv is invertible iff 1 + v x #0, 0, in which case is holds that:
Lemma B.2 (Sherman-Morisonn
X xv = = -X--
X uv X
1+v
17

---

Recall Lemma 4.9 lower bound for seen-task loss under Scheme 1. For any d 2 2. initialization Wo E R2 and regularization coefficient sequence , Ax 2 0, there exists set of jointly realizable linear regression tasks {(Xm )m) such that, under a with-replacement random task ordering, Scheme incurs seen-task loss LI (Wi)) (wk) (11/k) with probability at least 1/10.
Proof. Let 2 9, and let A1...., As 2 be any regularization sequence. For simplicity. we set M k. but the proof can be easily extended to M k. Let fi(w) 2 (e w)?, where
e2 (0, 1,......,00)) 0) and f2(w) = [x w)², where x - (VI a² a, U, .). for some [0. Note that these can be represented as tasks {(e2, 0), 0)) with R 1.
.))
Consider the uniform distribution over the {f1.... fi. f2} of size k, such that fi is sampled with probability &/ and f2 is sampled with probability K. Let EB be the "bad" event where f2 is sampled exactly once, and note that using the inequality - 2 4- which holds for all x E [0, 1
Pr(EB) = (1 (1- ) k-1
(1-
k 2
4
The of the analysis will be conditioned on the "bad" event. Let 0. and note that for any w.
arg min (f1 (w') + l|w' wll (e2e + AT) (Aw) = (w Te2) w'
X+1 62.
where the second equality follows from Lemma B.2 The case of À = 0 is treated as the update above with x = 0, and similarly,
arg min ( (f2(((()))))) + I|w w w/l =
(w x) A
X.
Starting at wo = (1, T) the iterates will not move until encountered with fz. Denote with ty this step. Thus,
Wio = -1-1102
1- a²
avi a²
Ata +1'
Ato +
From now on, we only observe f1. so the first coordinate of we for h > to. which we denote as wr[1], is
( (wa-) e2
w&[1] = W
[4] w = .... = ww,
++
If k = lo then wx[1] = [1] trivially holds. Thus,
1-
Wk
Jea
for some Ç E R. Hence, setting a = 11/2.
f2(wk) 2 (1
1 1-a V1 a2 + ac) )²
1
2(2to 1] + +c)²
1
Ato
4
and f((w)) 2 If If 2
we done fi is observed k times (conditioned on EB) and
VR"
C1:k(Wa) k k fi (wx)
k - 5² ((1/k).
2k Otherwise, as 2 2 -1 1/3, and (conditioned on ER)
1 fa(wx) > 1 (1/6)) 144"
Therefore, in this case,
C1. (Wx) 2
T. f2(w)) ((1kk)
So with probability at least Pr(EB) 1/4 > 1/10, it holds that Lia (Wx) (1)/))
18

---

C Proofs of the reductions and their properties
Recall Reduction -- Regularized Continual Regression = Incremental GD. Consider M
regression tasks ((xm; ym)Jm= seen any ordering т. Then, each iteration [A:] of regularized continual linear regression with coefficient X 0 is equivalent to IGD step on ft (1; Te) with step size do > O, where f/(²) (w; m
Am (w- ym) ||
for some Am
(t) depending on X Tt-
That is, the iterates of Schemes andd
coincide.
Proof of Reduction Each iterate of regularized continual regression is defined as
(2
Wy = arg min
X w Yr, yr.
+ 2 l| ww-1l²)
which admits the closed-form update:
(X, Ael) - (X,Tym + A.w.-1).
We define:
A -- X X X (xr )))
1 (w; m) - 1 $
VA (w X m))
TJt
(For notational simplicity, we write Am in place of the more precise A Observe that:
T/t A. I de (X Xm AoI)
[X],,,m Ax) (X IX X A11 - de (X, +2I)
-XXX, (x X ArI)
When we run IGD on f with learning rate Tr. we get:
W
V (w,-1;7) = Wi-1 - AA (We-1 x
= XX, 1x1) -1 Wi- X X (x + +AI1) -1 xxty
= AX, Xx1) -1 W + (x X + Ax1) X
XX, + Xx)) (A:W1-1 + X.YyT.) wi
Recall Reduction 2 Budgeted Continual Regression Incremental GD. Consider M re-
gression tasks {(Xms Mm)) m= seen in any ordering Then, each iteration E [b] of budgeted continual linear regression with N₂ E N inner steps of size Y) (0, 1/R²) is equivalent an IGD
step p( (:) with step size π) 0, where f((0) (w; m) | A (w- x mm) for some (1) Am depending on No, Th, Tht That is, the iterates of Schemes 2 and 3 coincide.
Proof of Reduction In budgeted continual regression, we apply Nr steps of gradient descent with step size 7/, to the loss 2 [,,, w yr. 12. Let (0) & w,-1. The inner iterates evolve as:
(+) 7/ x X.,) (o-1)) x N
N W; = (N)) (I Nx x,) No W + 76
(I - x. x,,) XTTY
We define:
Am 4
(1- (1 (x-
( m) 2
V Am (w x
T
19

---

(For notational simplicity, write Am in place of the more precise A mm)) To simplify the expression for the sum, consider the SVD X, = UEV and observe:
N
N
[1 71 x x,,) X V
Σ =
Te (1 (1-7) (1-1)2)) " Yr.
7
==0
= V (I M x Mi
U Yn. = I (I (I- nx xx,) Mi) xtyyr.
Geometric sum]
AT. X Y.
When we run IGD 1/ with learning rate Th- We have:
W nh V. (wa-li7)) = wr-1 Ar, (wr-i y.)
=[I- mAAT)) We-1 AA
N1-1
(I X xT,) N1 W 7
7 x xx)) X. Wi
- 2 | w ymal? and R² A Lemma C.1 (General reduction properties), Recall & (w;
maxm! mm 12 Let
1 m)
A
V Am (w x v with
Am (XTx,, X,):
where : - R is applied spectrally (i.e., each eigenvalue of X Xm). Assume that is concave, non-decreasing on [0, R2), with g(0) = and g' g((0) > O. Then:
(i) f(() (w; m) is (ii) and the following inequality holds:
((t) (w;m) S C (w; min L (w's m) g(())
1
R²
p(() (w;
w"
9 (R2)
Proof. Let E, denote the i-th eigenvalue of X Xm. and let &
- g(E) the corresponding
eigenvalue of Am. By the concavity of g, for every & [0, R?..
g(Ea) S (0) &
g S.
Hence, Alo Am & X X m- By concavity and g(0) O, the chord from to R2 lies below g:
RR
R²
g(E))
&
R²
g
so we obtain the matrix inequality: X Xm
R
R
Moreover, since is non-decreasing, & S g( gPR)) and therefore all eigenvalues of A. are upper bounded by g(R²), Am & g((22),, implying that the Hessian V p(t) (w; m) Am satisfies smoothness with parameter g(122).
Next, decompose the squared loss:
[m -mmll 1 Xm (w X (Xmxt 1) ym
L(w; m)
(IXm (w x m)) 112 (Xm - 1) mmml1))
[rthogonality]]
where the two terms orthogonal since Xm (w X Xm)) range(X and (X,X I) ym ker(X]]))
20

---

The minimum loss is attained at Nn. yielding: minw L(w':m) = l1 I) Thus, the excess loss becomes:
L(w;m)-min m(w::) w' m)) = - Xmm (w - x xmh)mm) =1 (w xm)m) X Xm (w mm)m)
Meanwhile, (w; = (w- Xtt Am (w- X m
By the sandwich inequality ক A. & Xm
n²
Am, conclude:
a(R2)
R² g(
g' g'( f(0 (w; - [(w:m) min L(w';m)
f(t) (w;
Recall Lemma 3.1 properties of the IGD objectives. For t E [kt] define , as in Reductions and and recall the data radius R a maxme([]] |Xm ml1-
Jbb are both convex and f-smooth for a A
n² R
(1 -1- (
(ii) Both functions bound the "excess" loss from both sides, i.e., Vw Rd, Vt E [K], Vm E [m],
R2
Xen ft (w: (w:m) S L(w; m) - min L(w'; m) s
f
(w;
T/ 1 (w: NN
< [(w; m)) - min ((w'[(m) I
R22
((
(w;
86
w'
(iii) Finally, when the tasks are jointly realizable (see Assumption 4.1p. the same w. minimizes all surrogate objectives simultaneously. That is,
L C(w.:m) = f (w.; :)) = f: (w.:m) = O, Vt [k], Vm E [M]
Proof of Lemma
3.1
Recall the definitions of the IGD objectives:
{ m) &
2 gr (, (w X
110) (w; A
V 9b (x (w X
where the functions gr, 96 IR + R are applied spectrally (i.e., to the eigenvalues of X X,). and defined as:
g (E)
4
1 1
A )= 9o(E) & 1 Th
(1-(1176)))
5 + Ae
17t
Note that both y and f/ are standard quadratic forms and hence convex in
We verify that and gb satisfy the assumptions of Lemma C.1 on the domain & E [0, [83]
gr differentiable with
2de 9"(E) = mo(E Ae) S 0,
g. (E) = TI + x,) 20,
so 9r is non-decreasing and concave.
To differentiable with
NeTt (1 111--E)---11- 0,
N,(N, 1)m? (1 (1)7 N 500 N1-2
gb(E)
gE(()
1/
Thus, 9b is also non-decreasing and concave.
21

---

In addition, we note:
1
No 0,
g- 0,
(0)
> 0,
96(0) 0, $((0)
7
1
and we compute the smoothness constants:
R²
(x
(1 (1 (1- n113)
1/e (R
Xx)
$
T/e
Hence, by Lemma C.I. both f and f/ are smoohh with the claimed parameters 3,5 .8) and they satisfy the two-sided bounds:
1
R²
(w;m) [(w; min [(w';m) 5 1 (w;
(0)
w
9r
1
1/) (w; m) & [(w;
min L(w'; m) < gb (R2)
R²
5b (w: (w; m).
g6(
w
Substituting in of (0) and (0) yields the bounds stated in part (ii).
Finally, for part (iii), assume the tasks satisfy joint realizability (Assumption 4.1 meaning that for some common minimizer w..
L(w.;m) min L(w'; Vm.
Then by the lower bounds in part (ii), both (w.i = and p/ (w.;m) = for all 6, m, completing the proof.
22

---

D Proofs for fixed regularization strength
Recall Lemma 4.3
rates for fixed regularization strength. Assume random with-replacement ordering over jointly realizable tasks. Then, for each of Schemes [ 2 iterations is upper bounded
and the expected loss after
Fixed coefficient: For Scheme
with a regularization coefficient 0,
|W
w
R²
E2 C (W*)=
S
n2
n2
2
R2a
k
x²
4(24+3)
R
+x
(ii) Fixed budget: For Scheme
2 with step size
(0, 1/2) and budget N E N.
e Ww - R²
E., L (wx) <
2 2. - 7R - -1-
Proof of Lemma 4.3 From Reductions [ and the iterates of Schemes and are equivalent to
those of IGD (Scheme 3) applied to the respective surrogate objectives f!()) and fu When 7), X, N fixed, the functions ft (((h) do not depend
and under random ordering with replacement,
the update rule becomes standard SGD.
By Lemma 3.1 the surrogates f(() and (()) are jointly realizable whenever the original losses are, and hence satisty the assumptions of the following result from Evron et 14]
Rephrased Theorem 5.1 of Evron et al. 14 Let f(w)
EM= f(w:m), M
1
where each f(w; m) e Am 6, is 8-smooth, and assume realizability:
f(w.) = for some w.. Then for any initialization wo and step size 1i E (0, 33 SGD with replacement satisfies:
e e||wo wx
E, f-f(w)) S 27y(2 78) k -08(1 (8/44)
We now instantiate this result for each setting:
(i) Fixed Regularization. For Scheme
I the surrogate f! is 3,-smooth with
R
1 R² 2
3, A
X
which implies
n
Br
R2 +
3,
The loss is upper bounded by the surrogate:
R² [(w*) - fr(ws),
Br
which gives:
R² E. [..J((w)) S 2n,, (2 mB,) k2 118, (1
e I/Wo w.ll 112 R²
E.(((k)) S 3r
Substituting 3, 1.
R² +T gives:
e||woo w.l? R2
E.L(wk)
2
R (2
Ra k'
R²
22
4
82
n2 +x
+x
(ii) Fixed Budget. For Scheme
2 the surrogate p!()) is Bb-smooth with
BB 7
- (1-(1-110))) (1- so that 7 Br
-1-(1171111)
-
<
3r
23

---

As before, we have:
R²2
e wwo w+| R22
E, ((ws) - 5b
Ey (o(w)) -
21/3r 1156) k. - -n (16644))
Substituting 3. = " (1-11-RR3 yields:
Wo w. w.ll2
E, E,[(wx) S
2. (1 (1 (2)222)2 2²- (1- 224))
(1-11(11-)
This completes the proof.
To extend this result the without-replacement case (see Remark 4.5 we can simply invoke the without-replacement extension of Theorem 5.1 in Eyron et al. 14
Recall Corollary 4.4 near-optimal rates via fixed regularization strength. Assume ran- dom with-replacement ordering over jointly realizable tasks. When the regularization strengths in Lemma 4 are follows:
Fixed coefficient: For Scheme
set regularization coefficient À - Rº 1);
choose step size 7 10,1/R²) and budget N In m
(ii)
Fixed budget: For Scheme
Then, under either Scheme or Scheme 2 the expected loss after k 2 2 iterations is bounded as: W. R In
5 Wo
(w
Proof of Corollary 4.4
We apply the general loss bound from Lemma 4.3 which holds for both ired-regularizzttoon and fixed-budge red-ettdett variants:
e||wo w N2
E2 ((w&) S
2nB (2 n1) k -- 98/4)
Now plug in the parameter settings from the statement of the lemma. (i) Fixed Regularization. Set À A R2 (In k 1).
Then:
R²
1
R²
1
By
nB,
71 R
+
11
R² Rl - 1) Ink
In k
In(1- m
(ii) Fixed Budget. Set N
Then:
In(1 714)
BB L. (1-
(1 (1-718)
+
T/BB
In l
1
In
In both cases, we have n/3- ln Substituting into the loss bound:
||o w. 1| 122
E,L(w)) <
Ink (2 kn) - T F
Ilnk
=I|wo w.ll2 n² 2 1n
kmnk
40m 83
|wo w.l' 11 122 In knk
2² Thm
k
2 2 l
Since c²- ThE (2 lnk) < for all &s 2 2, we conclude:
5 |||wo- w.ll R² In k:
E, L(wx)
<
24

---

E Proofs for scheduled regularization strength
optimal rates for inereasing regularization. Assume a random with- replacement ordering over jointly realizable tasks. Consider either Scheme D or Scheme 2 with the following deeedeepedentt schedules:
Recall Theorem 4.6
13R²
k +
Scheduled coefficient: For Scheme
set regularization coefficient X
l 4 2
(ii)
Scheduled budget:
3
k - + 2 +
For Scheme 2 choose step sizes "/e E 10.1/R²) and set budget N₂ 13
Then, under either Scheme I or Scheme 2 the expected loss after t: 2 2 iterations is bounded as:
20 wo w. w.1²RR" R2
E, C(wx)
k+1
Proof of ThThheeem 4.6 We apply Lemma 4.7 with the original loss ((w; m) L(w; and surro-
gates f (w; ft ( (w;m) or fb m). defined in Reductions and 2
Smoothness and convexity. From Lemma
3.1
both surrogates are convex. Their smoothness constants
are:
8(1)
1
R²
(1))
(1 (1 - -2))
R
+
Regularized:
Setting
1/1l gives
R²
8
1it R2 + S R??
Budgeted: With N₂ = 1n/71 we get
RR N,
= RR R2 E (0,1) 1). Using (1 x)) 2 1 - nır, we obtain:
b S 1}
(1 (1 R2) = R
Thus, both surrogates are R2 smooth, matching the smoothness of the loss ((: and satisfying condition (i) of Lemma 4.7
Joint realizability. From Lemma surrogates;
3.1 if the original tasks are jointly realizable, then so are the
f(0) (w.: m) (w.: m) [(w.:m) O, Vt E [k], m E [M],
condition (ii) of Lemma 4.7 is satisfied.
Two-sided bounds. We verify condition (ii) of Lemma 4.7 using the two-sided inequalities from Lemma 3.1
R²
Aene (w; m)) L(w:m) min L(w': (wwmm)) m)
< (w;
B(1)
R²
17t
f/ (w; I L(w;m) min L(w';m) x
1b
(w;m).
NN
g
By our choice X₂ 1/1 and N₂ = mt/res we have den
n n, 1, so the lower bounds reduce
to
p( (w; m) S m(w;,),
f(()) (w; m) S L(w;
Now set 14 A th. To satisfy the upper bound L(w; m) W (1 + v,3) (w; m), it suffices to show
R²
E 1 t R2
300
25

---

Regularized:
8500
R
R
R $
1 1/1 R2
11
+x;
Budgeted: With y
E (0, 1), and using (1 - ) 2 5
I Tt
for x E (0, 1), we get:
No
R
R
R
1 nR
(
71
1
1
Th 122
1/
1
R
Hence, both the lower and upper bounds hold, and condition (ii) is satisfied. Setting the learning rate schedule to:
13 and 1): = 11 1 + 2
Applying Lemma
4.7 yields:
20 || Ww - w R2
E, E,L(wx) = (.-((*)) 5
k: +
26

---

E.1 Proof of Lemma 4.7
In this section, we provide the proof of our main lemma establishing the guarantees of time varying SGD, In order to better align with conventions in the optimization literature from which our techniques draw upon, we adopt different indexing for the SGD iterates throughout this section. Below, we restate the lemma with the alternative indexing scheme; the original Lemma 4.7 follows immediately by a simple shift of k + - and 0 in the indexes the iterates Wt.
Lemma E.1 (Restatement of Lemma 4.7 with alternative indexing). Assume is ran- dom wethereptacement ordering over M jointly realizable convex and B-smooth loss functions f): Rd + RR. Define the average loss f(w) & (w) Let k 2 2, and suppose { (5)m) I [k], E [M] for L E [ki are time-varying surrogate losses that satisfy:
(i) Smoothness and convexity: (::m) are B-smooth and convex for all E [M], [k];
(i) There exists weight sequence " Pi such that for all m [M] E [k], w R9:
(1) m)) 1 (w.; E ((w; - [(w.;m) <
- ( (w.;
(iii) Joint realizability:
w. E [bE(A) MmE[M) arg min ( (w; vm E [M], E [k], (w.,))) = f((w;m)) w
Then, for any initialization E Rd, the SGD updates:
t=1...,k: W4+1 W. T1 (wiiT))
with a step size schedule that satisfies us S T): = 1 guarantees the following expected loss bound:
(k+1)-++1
14 E [k] for some v S 3/(133).
k+1
9
Ef Ef(wx-1) f(w.) S 2n(k + +)
|| w.
In particular, for 135 we obtain
3
[f((++1)- f(w.) 203 [W 1.
+
Furthermore, we also obtain the following seen-task loss bound:
&
20
E
f f(W++1:) (fai:it)-((waaaa ((w+:T))
S (/c 1)
|/w: w-ll2
k
1=1
In particular, for obtain
3
133
87, [[ -w.ll
w.ll?
E
f(Wa+1i f(w.iT))
<
k
27

---

To prove the lemma above, we begin with a number of preliminary results. The next theorem provides an extension of [46] for our "relaxed SGD" setting that accommodates time varying distributions of functions.
Theorem E.2. Let J 2 2, and assume T: [J] + [M] is a random wiph-replaeement ordering over M jointly realizable convex and 3-smooth loss functions f(:m); R + R. and suppose
(f(0(;)) I E [J].m E [M]] for i E [J] are time-varying surrogate losses for which there exists Uy that satisfies, for all m E [M]]. 1 E [J], w E R.d:
a weight sequence ,
f(r) (w; - (w.: m) S f(w - f(w.: m) - (1 + v/3) (f:) - ((.)
Then, for any initialization w E IRd and step size sequence T],, TJ,, as long as Vt E [J] m 2 Pb. the SGD updates:
W(41 Wt TI V (Weite): Te):
guarantee that for any w E Rd, and weight sequence 0 << 00 S.n Us S... Us:
Σ ((o - f(o s
J
0/ ||w w.
1
V p(() ((l) (w); 77) ||
the
2
2
where Co - nun - (1 (1 11-1) E 2 and (w) A E Em- (w:;
Proof. Define 2i,..., ZJ recursively by 2o = w. and for t 2 1:
1/-1 2 + (1
U/-1
Z,
We.
U1
Denote g: 2 ()((t) (Wei Tr) and observe.
| Z 2|
|i+1 1011
U/+1
v/
|| - 1/188t - 22111
U/+1
(l/wa- 20l1 27t (gt. We 21) + n/ (1
22+1
thus, rearranging we obtain
2uî (gr, W. 2.) = 0² ||w, = oZt -0-1 ||
Ze41 12++ ||g.11
Summing over 1. = 1, I,....,J yields
J +
Σ o (gc. We 2i) S 1 "/ ||w w.
of ||g:11
2
2 1=1
where we used that,
10
20
|| z
|| zoll
w -w.l.
Next, by convexity of f(() and the fact that w., 2, are independent of tr. conditioned on TI...., 1t-1
Ey, (g: We z,) (E,, (we: Tc)], W. - -z.)
= (VF We w.www=z) -z) 2 - [())(w.) - (z:)
Therefore,
T
2 E.
f(O..) - (()())
- 3 ww - w.ll
1
+ 2
1 Σ o lg:.
t=1
t=1
28

---

On the other hand, Z, can be written directly as convex combination of Wi.... W. and w., as follows:
Up
Ux
U/-1
W
W..
11
Jensen's inequality then implies, using convexity of f();
2 F.
f(o - (z))
((,) - v0 p((t) (w+)
U/ U--1 F(() ((()(w.)) (w.))
2f E
21
[m]
B
1/ f10) (w:)) - 200(t)) (w))
(Us - -0' -0--1) 1)F())
t=1
s=1
Σ B
(w.) f()(w.))
(1/- 1 (ws))wss) 810 (w-))
14
Combining the two bounds and denoting 5. (()) - (w.), we conclude that
Σ (Us U--1) (F()(w.)) - (w.))
E E
ur
l| w=11
Σ u 2 ||g:
Now, by assumption, for any s S f, m [M]:
Vw: : p( (w; m) (w m) S f (w;m)- S (1+11,3)
hence, taking expectations over m ~ T, we obtain (w.p. w.r.t. randomness of w.):
- (1 + n.8),, = - (1+ (w)) (( s -- (())(w))
- - (w.))
Combining with the previous display, we now have
v 2
B E
vy - (v. - -1- - s |[ w. 12
Σ
0
E ||
2
s=1
1=1
which leads the following after changing the order of summation;
J Σ
Σ nop - (1 - 11.3 - vz-1) Σ NoVs EZ, S
|| w.
of E |grl
2
2
t=1
and completes the proof.
29

---

Next, we prove a technical lemma which we employ in conjunction with the above in the proof of Lemma E.
Lemma E.3. Let k E N, 3 > 0,a > 0,02 > 0, 11 (0, (8a, to02]p T/2 1) -- for
t E f1,2...., k), 2 k-
2 + 2 for E f0.1..... 1 and U Uk-1 = =1+ 1.- Denote
C: = 7 3m 13 (1 + (v 1 Ex=o U. Then all t E .1, .k.. ct 2 0,
and in particular, ck 2 k.
Proof. As Uk- = UK- and 1 S (8o, +5w2)01
Ck n - a1 Bui
nxuk
1
01
01
1
1
1
(1 (1- a1,3n
k
K
k
k:
7 ス k (1+ xt 1
3
17
5
3
1 +
8k)
k
8k
81.2
We proceed to lower bound Gz. for L < k. Focusing on the first terms, A,
_ mpre - a1 (11111 vt.
17(K 1)+1)
2
1
A mcep (1 a133k)
+ k
(1 a1 BT))
k
k k-t+1
1
4
4
--1+1
=1
+
+
(1-a1817))
-1-1a
k(k- - t + 1)
12
33
4
4
2 17 k(k - t + 1)
+
(1
01 B18)
122
Moving to the last term, B₁ _ (1 + 02 32 (v: 84-1) Σx U/
2
1 1
1
k-1
2
k-s + k-s+1)
B, = (1 + a233))7
E Σ
k +
k-t+1 k - t +
k
12
s=t
1 k-1
(1 + +=23m))
21
1+ k
+ 2(k +)+ + Σ (k (k- ++1)
k(kk t + 1)(k ++
k ==1
21
(k: - 1 + 3) - t)
(1 + a23m1)
1+ k
+ 2(k: f) +
k(k t + 1) t + 2)
2k
12k + 2 + 4k<k - t) + (k - t 3) - t))
(1 + (1)
12 - 1+ 1)(k (+
-6
4
1
(1 + a23m))m
kik - t + 1)(k: - +t+2 2) + k(k - t 1)
+
k
4
< (1 + a2
1(k-1+1) 11 +
1.2
Thus, for < k.
C1
4
122 3)(1
o133)) (1-0)37)) (1 + 3n))
(1
4
1
kik t+ 1)
k(k - t 1)
12
4ay + 4az
4aj + 02
BT
12
kiAh 1++1
12
3
4aa + 402
(Aar
a2) (k- ++1)
Bn
+
422
k2
33
3
Bn
(8a1
50z).
k2
ka
Thus, for 1) 5 (8aj
3
b C 2 0.
30

---

The next lemma provides the stability property, which we leverage to translate our loss guarantees to the seen-task loss defined in Definition 4.8
Lemma E.A. Assume the conditions of Lemma E.I and consider the algorithm defined in Eq.
!
with non-increasing step sizes T)t S 1/23. In addition, define for every S h, fis(()
Ei=1 [(W;T(). For all S k, the following holds:
Efi S 2B 2W 8 [|1 w-
k+1
Proof. First, any 8-smooth h: Rd + R holds that
3
(h(w) h(w)l Vh(w) (w- ww +
w w/1
2
1
|| w/ 1 + 3
< Vh(w)) 2| +
|| - w|
(Young's ineq.)
23
2
< h(w) + 3 - ww|?
Denote fm A fm) for all m E [M]. Now, similarly the standard stability *
generalization
argument 39 19]. and denoting by w. (8) the iterate after s steps on the training set where the i'th
example, my was resampled (we denote the new example by m²):
E [(WW++)) - [La((WH))]] =
Emarrt [((x=iim.) - f(w (ww.tiim) m.))
f(W*+1;m.) + w W 12)
E
h 1=1
Bf(w++1) +
8
R
10) k+1
wx+
Next, we bound w k+1 by the non-expansiveness of gradient steps in the convex and 33-smooth regime when for every 1, S 2/3 [see Lemma 3.6 in 19]:
Wk+1 Since by Lemma E.1 for every t, (() is convex and 3-smooth,
i
w(() w. 0,
i <<8
w
6+1
(1)
S
wi+1 2
In addition, denoting by Jm; the function that sampled after replacing fm, and its corresponding time varying objective by f(m)), by the conditions in Lemma E.1 we have that,
w (6) V (mm²) (mm)((((()) (9) W: 17s V (ms) (:)) |1
w 1+ W
m v (mb)) (mm))( (-) v)(mm)(w.)))
s 2n / (w( (3) || 2nF fi (w:) 2
< 48 p(m))
(m))(w(()) (w) + 487/ f(mi))
< 43 fm (w.")) + 43 fm,(w:)) (wi).
and, taking expectations,
[ Wi+1 2 < 88 (w:s),
31

---

Now,
8 k
k
E
w
k+1
Wa+1
I 8882 E
k i=1
ns fmr (w:)
1=1
88E
Tn (w;)
K
Summarizing, we have shown that:
E [[(Wa+)) Pax (wx+t))
< <BS((*+1))
8
Σ
E Wx+ 1 -w++1l
7:
S <Ef(w++1) + 8,3
Σ ThSms (wi)
Now, by Theorem E.2 with = 1 for every 1, we have, since neB S 4. I+m
Te ReEss (wi)
5
1=1
k
B. (w;)
Σ
7 ((() - (w.)
n v (()))) 2
$ 2
||w1
-w +
Σ
2 i=1
1
$ 2 || w. + Σ
Brs f (()))
$ 2/ ||11 - 12 +
Σ
1.E.f.m (wi),
1=1
this implies,
I. (0fmm.(w)) (wi) S [| -w.ll?
Then we can conclude,
88 |w1 w.l
E [(Wa+1) - FLl((W)] s <Ef(w++1) +
k
and the result follows.
32

---

We are now ready to prove our main lemma for this section.
Proof of Lemma
To begin, note that we are after guarantee for Wk+1, which is the SGD iterate that was produced by taking l steps over k losses. To that end, we are going to apply Theorem E.2
with J = k + 1, hence we are obligated to supply random ordering т: [k + 1] - [M], f f((+1)
and
M++1, which are not supplied in the statement of our lemma. Therefore, we define
( (+41) k++1
(k: 1) (A: 1) )
Vm E [M] (; - f(:m), and Mh+11 - "n 1:
k+1
We additionally define f (w) A Em--Unit[M]] / (w; It is immediate to verify f(++1)
satisfies the properties required from f(t) for E [K] and 7 is the next step size in the sequence
",..... Th defined in the statement. Finally, we simply define the extra sampled index Tk+1 to be uniform over [M], exactly like Ti for L [k].
Now, the conditions for Theorem E.2 are immediately satisfied with J = k + 1 by our assumptions and augmentation described above, leading
1+1
neol -(1 111mm:0 --m:)((u 01-1) Σ
E B
fco (w()
Uo
k+1
un [w - w.ll2 +
Σ
of
((()(
2
Now, by the joint realizability assumption, conditioning on all randomness up to round t,
B
< (f (W
||
- f( (w.: (w.: 23 (F(()))) f(t f(t)(w.))
Combining with the previous display and rearranging, this yields
k+1
n Bui (1 (v v2-1) Σ us
E
t=1
2g
|| w. (2)
Now, by Lemma E.3 the step size sequence 7)t 1y( (k+1))+41) with 7 S 133
and {urkel
k+1 as
k-]
specified by the lemma, guarantee that c&+1 2 n1 Combining these properties with Eq. (2) we obtain,
E+I 0p S 3/
(k+ + 1). and ot 2 for E [ 1].
[f((++11) f(w.)
F(h-1) 1) (W++1) f(k+)((w.))
2g
|| w.ll
||w w.ll?
20
21)(k + 1)
which completes the proof for the first part. For the seen-task guarantee, by Lemma E.4
we have
* -[WW::) s 2Ef(ww+1) + 8,32 || w
E
((W++17T))
Te
k+1
which gives, after combining with the population loss guarantee:
18
|| w. 8,3 ||w, w.
f( -
< (1 + 11
k +
20 ||wi -w.l
(n $ 1/(23))
< 1)
which completes the proof.
33

---

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

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
assume joint linear Every lemma and theorem in the main body explicitly states its assumptions and includes reference the appendix containing its complete proof. The proof techniques are briefly discussed in the main text.
Justification: The setting is clearly stated in Section 2 In Section 4
realizabilitty (Assumption [. which is further discussed in Footnote 2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
35

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc
wwt.ssicinnooooooioooooooooooili for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppcccguuiiieeaeeec /otpa///ggiieee/eocuuubbiiii wtttdd//e/ooeeeeaeiiiiiimoo
assionPoicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
36

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative етхог rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: This is a strictly theoretical paper, intended to improve convergence rates of continual optimization algorithms.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
37

---

10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is strictly theoretical paper, intended to improve convergence rates of continual optimization algorithms.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
38

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
39

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs only used for writing and editing.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy htttss//hourips..c///fffeerrr for what should or should be described.
40


Reviews:
[{"review_id": "85pPMaq53f", "reviewer": "Reviewer_ZBRc", "summary": "This paper proves new worst-case bounds on linear regression problems in a continual learning setting, specifically focusing on the regularized case.\n\nI should note that this paper is far out of my field of expertise, and thus my assessment is just an educated guess. I hope the other reviewers are more qualified to review the paper.", "questions": "- As someone working on other varieties of ML, such as large language models, what is the significance of this work?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Clarity: The paper is dense, but to me it seemed clearly written.\n- Originality: Analyzing learning dynamics under regularization seems like an important topic to be covering, and if this has indeed not been covered in previous work then I think it is worth examining.\n\nWeaknesses:\n- Significance: I mostly work in more applied varieties of machine learning, and to me it was not very clear what the significance of this work would be. (Somewhat facetiously but also somewhat not,) we are approaching AGI and it's not clear that knowing this tighter bound will get us closer to that (although purchasing more GPUs likely will). It would be nice to have a little more grounding in what the practical implications of the work would be, and how they might eventually lead into new optimization algorithms, etc. That being said, this is not the variety of paper I typically read in the first place, so it might be that this is much more interesting to people for whom this is a central research interest.", "was_revised": true, "final_justification": "I would like to follow the prevailing sentiment about this paper, as I am not very qualified to review it myself.", "rebuttal": "We thank the reviewer for their feedback. We are happy that they find our paper **clear** and **original** within the scope of theoretical continual learning.\n\nThe reviewer mostly doubted the significance of an analytical work like ours—somewhat calling for a broader discussion on the importance of theoretical ML research while the community seems to be *“approaching AGI”*. While we do not feel this is the most appropriate platform for such a broad discussion, we would like to note that:\n\n1. **Generally**, the rapid progress towards AGI might “hit a wall” which will require a better theoretical understanding to cross—perhaps in the sense that optical theory has helped develop better telescopes (which were first designed empirically, without theory). Better theory in ML should eventually be able to provide scaling laws, help devise better algorithms, and also explain the behavior of existing algorithms.\n\n1. **Relevance to LLMs.**\nContinual learning is considered essential for general-purpose AI systems \\[\\*1 below]. Recent work \\[e.g., \\*2, \\*3] shows that fine-tuning LLMs often leads to catastrophic forgetting, especially during domain adaptation.\nThese works already use quadratic regularization like the one we study. While our results apply to linear models, they offer theoretically-grounded rule-of-thumbs into regularization schedules which may be useful in practical continual learning systems, perhaps especially in large models.\n\n1. **Our work is important to the theoretical continual learning community.**  \nAs our Table 1 shows, our rate directly improves upon and/or relates to prior work from recent important conferences: Evron et al. (COLT 22), Kong et al. (NeurIPS 23), and Cai and Diakonikolas (ICLR 25). More broadly, the continual **linear** regression setting is a central setting, studied theoretically in many papers from notable conferences (e.g., [10, 11, 30, 15, 35, 27, 46, 16] cited in Line 58). Furthermore, the reviewer’s summary seemingly ignores a central, novel contribution of our paper: our work not only “proves new worst-case bounds in a continual learning setting”, but also shows how to achieve these optimal rates using explicit and implicit regularization.  \n\nWe respectfully ask the reviewer to reconsider their assessment of the significance of our work, taking into account the standards and interests of the theoretical continual learning community.\n\n---\nAdditional references:  \n\\[\\*1] Hadsell, R., Rao, D., Rusu, A. A., & Pascanu, R. (2020). Embracing change: Continual learning in deep neural networks. Trends in Cognitive Sciences, 24(12), 1028–1040.  \n\\[\\*2] Song, S. et al. (2025). How to alleviate catastrophic forgetting in LLM fine-tuning: Hierarchical layer-wise and element-wise regularization. arXiv preprint 2501.13669.  \n\\[\\*3] Xiang, J. et al. (2023). Language models meet world models: Embodied experiences enhance language models. NeurIPS 2023."}, {"review_id": "88qs5iKFQG", "reviewer": "Reviewer_7nbE", "summary": "This paper studies continual linear regression under random task orderings, wherein the learner faces a collection of randomly-ordered linear regression tasks and seeks to minimize the average error across them. A $\\log{k}/k$ last-iterate convergence rate is derived using a fixed regularizer, and the result is improved to a $1/k$ rate using increasing regularization; both results significantly improve the best-known rate of $1/k^{1/4}$. A lower bound of $1/k$ is also shown, demonstrating that the $1/k$ rate is optimal.", "questions": "- The comment before Lemma 4.9 was unclear to me; how can we simultaneously have a 1/k lower bound and non-isotropic regularization ensuring seen-task loss of zero? The elaboration of this comment in Section 6 did not resolve this question for me either.\n\n- I don't really understand the point of presenting both the fixed and increasing regularization scheme; the former seems to be strictly worse, so why not just present the optimal algorithm? It feels like this could have been included in the appendix rather than being featured prominently in the main text.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\nThere are two common approaches to the problem studied: applying explicit regularization on each step (to penalize moving too far from the current iterate, thus \"forgetting\" much about previous tasks), and implicitly regularizing by applying only a limited amount of updates in each task. Section three shows that both of these options can be analyzed in terms of SGD on a particular surrogate losses, leading to a more unified analysis. Very clean.\n\n## Weaknesses\n\n- The lower bound is not particularly novel; it is standard but technically hasn't been explicitly stated in the literature (the paper is up front about this)\n\n- The writing and paper structure is not very polished. Generally the writing comes across as rushed.\n  -  e.g. Section 2 introduces the setting but only partially, with key assumptions (realizability and random task ordering) not being introduced until later, in Section 4.\n  - Section 4 introduces the 1/k lower bound, and then follows up with an algorithm which fails to achieve it, only to fix it with a separate algorithm afterwards. It seems redundant to present the sub-optimal algorithm if an optimal one is obtained at seemingly no compromise.\n  - Lemma 4.7 re-introduces all the assumptions in the lemma statement. This one lemma take up more than a third of a page", "was_revised": true, "final_justification": "The paper has some novel results, but relatively weak writing which is left unaddressed by unconvincing justifications in the rebuttal. After reading the response and the other reviews, I've retained my original score.", "rebuttal": "We thank the reviewer for their positive feedback. We are happy that they find our analysis clean and that they appreciate how we **unified two common continual learning practical algorithms** under an analytical framework that has ties to the rich literature on SGD.\n\nAs **weaknesses**, the reviewer mostly pointed out **places where the paper could be clearer**. We would like to clarify these issues here—and later in our manuscript’s next version:\n1. **Lower bound is “not particularly novel” (but it is also not presented as a main contribution).**  \nThis bound is indeed standard (and like the reviewer acknowledged, we were explicit about it).\nHowever, we do not consider it a 'weakness' of our paper, as it was not presented as a primary contribution but rather included for completeness to facilitate the discussion of the optimality of our novel *upper* bounds.\n\n\n1. **Reservations regarding the paper’s structure.**  \nWe gave careful consideration to the appropriate structure—and particularly to the issues that the reviewer raised. Below, we explain our rationale. Still, following the reviewer’s remarks we will try to improve the flow—especially when transitioning between sections and/or around key results.\n    - **Setting “partially” introduced in Section 2.**  \nWhile the reviewer proposed a valid alternative, we believe that our structure offers certain advantages: the reductions in Section 3 apply **without assuming realizability or random task ordering**. By introducing those assumptions only later—in Section 4—we kept Section 3 broadly applicable. For example, future work on adversarial/structured task sequences can use our reductions directly without modification.\n    - **Length and placement of Lemma 4.7.**  \nLemma 4.7 offers a result of independent interest: the **first optimal last-iterate convergence rate for SGD** in a realizable setting. To make it accessible to readers from an SGD/optimization background, we chose to state it fully, in a self-contained version that is more *general* than the rest of the paper (e.g., it applies to all smooth and convex functions).\nWe will clarify this when presenting the lemma.\n\n\nRegarding the reviewer’s **questions**:\n1. **Lemma 4.9’s preamble (isotropic vs non-isotropic):** \nPlease note that Lemma 4.9 states a lower bound for Scheme 1 which employs *isotropic* regularization. In Section 6 (lines 282-288) we discuss how non-isotropic regularization (requiring additional $d^2$ memory) achieves a seen-task loss of $0$.\nThere is no contradiction between the two claims, because they deal with distinct regularization schemes. This is also what we tried to convey in Lemma 4.9’s preamble.\nFollowing the reviewer’s question, we will ensure that the word 'isotropic' explicitly accompanies 'Scheme 1' within Lemma 4.9 itself, and not just in its preamble.\n\n\n1. **Why present the fixed-regularization scheme?** \nFixed regularization is widely used in practice and merits theoretical analysis in its own right. Furthermore, our fixed-schedule results **extend to random task orderings without replacement** (see Remark 4.5), which the increasing schedule does not currently cover. \nWe will emphasize this in Section 4.1.\n\nWe again thank the reviewer for their thorough feedback, which we have used to improve the clarity of our paper."}, {"review_id": "sACtLzZGGG", "reviewer": "Reviewer_6cuU", "summary": "This paper addresses the problem of realizable continual linear regression under random task orderings, a setting that is important for understanding and advancing continual learning. Previous work has established only suboptimal learning rates, achieving an upper bound of \\$O(1/k^{1/4})\\$ despite the existence of a lower bound of \\$\\Omega(1/k)\\$. The authors show that incorporating regularization—either explicit L2 regularization or implicit regularization via a finite number of gradient steps—significantly improves convergence. By reducing these schemes to stochastic gradient descent (SGD) on appropriately defined surrogate losses, they demonstrate that a fixed regularization strength leads to a near-optimal rate of \\$O(\\log k / k)\\$, while an increasing regularization schedule achieves the optimal rate of \\$O(1/k)\\$. These results close the theoretical gap and highlight the practical and theoretical importance of tuning regularization in continual learning.", "questions": "See Weaknesses above", "limitations": "See Weaknesses above", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper tackles an important and fundamental problem in continual learning—the learning bounds of continual linear regression.\n\n2. The writing is clear, well-structured, and easy to follow.\n\n3. The theoretical results appear sound and provide tighter bounds compared to existing work.\n\n**Weaknesses:**\n\n1. The primary concern lies in the parameter setting of the algorithm. The data radius \\$R\\$ must be known in advance to determine the regularization coefficient. Is this assumption realistic in practical scenarios?\n\n2. In Figure 1, the loss and forgetting rate are combined into a single quantity. However, continual learning is typically evaluated using two separate metrics: average accuracy across all tasks and forgetting rate on previous tasks. Why do the authors merge these two metrics into one?\n\n3. Could the authors include synthetic experiments to further validate the effectiveness of the proposed method?", "was_revised": true, "final_justification": "I recommend accepting this paper because it tries to tackle a fundamental theoretical problem, and makes notable advances.", "rebuttal": "We thank the reviewer for their positive feedback. We are happy that they find our paper **clear**, providing **sound results** on a **fundamental problem**.\n\nWe wish to resolve the reviewer’s “primary concern” (1) and clarify the analyzed metrics (2).\n1. **Knowledge of the data radius R:**  \nThe required knowledge of problem parameters for optimal tuning is a common issue in virtually *any* stochastic optimization method, perhaps most notoriously in SGD, where the choice of step size crucially depends on unknown parameters, such as the Lipschitz constant and the initial distance from a minimizer (see, e.g., elaborate discussion in [\\*1]).  \nIn our continual learning case, the schedules require knowledge only about the data radius—a quantity that could be easily inferred from unlabeled training data in many real-world problems. \n1. **“Single” loss metric in Figure 1:**  \nThe reviewer is correct in noting that loss and forgetting are distinct quantities. However, in the random orderings we study, these quantities are closely related—as explicitly discussed in Remark 2.2. While most of the paper focuses on the *loss* convergence, we discuss forgetting in length in Section 4.3 (titled: *“Do not forget forgetting: Extension to seen-task loss”*) and explain that the optimal rate we derived extends to it as well.\n\nFurthermore, regarding the reviewer’s third remark (3),\n\n3. **Synthetic Experiments:**  \nOur paper is theoretical, focused on establishing formal convergence guarantees in continual linear regression. That said, we agree that simple illustrative experiments can help clarify the behavior of our regularization schedules and support the intuition behind our results. \nWe will work on such experiments, but due to the short rebuttal period (which doesn't allow any figures), we will only be able to do so for the final version.\n\n\nWe will be happy to answer any additional questions during the discussion period.\n\n---\n**Additional references:**  \n[*1] Y. Carmon and O. Hinder. The price of adaptivity in stochastic convex optimization. COLT 2024."}, {"review_id": "hEmHjNaWtp", "reviewer": "Reviewer_ahtS", "summary": "This paper derives two convergence rates for continual linear regression with regularization: for fixed regularization, they achieve $O(log k/k)$ convergence rate, whereas for scheduled regularization they achieve $O(1/k)$. As $O(1/k)$ is the optimal rate one can achieve for continual learning, they have achieved optimal convergence rate for continual learning for the first time. The proof is followed by first understanding the problem as Incremental Gradient Descent, and then applying the bound in [1].\n\n[1] Evron, Itay, et al. \"Better rates for random task orderings in continual linear models.\" arXiv preprint arXiv:2504.04579 (2025).", "questions": "A general question I have is \"is joint realizability a reasonable assumption to study continual learning?\" I get that for continual learning, both learning from new tasks and remembering previous tasks are important. To me joint realizability feels like the framework doesn't have the notion of forgetting - because naively trying to do better for every given task naturally leads to better performance for all past tasks. Are there different setups in continual learning theory that can reflect such issues? Is your theory applicable in those cases too?", "limitations": "One limitation is that the result is purely theoretical.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: A novel scheme that has optimal convergence rate is very valuable. The fact that continual learning can be understood as incremental gradient descent is also important I believe, as it enables continual learning to be studied by tools from SGD. They also consider many diverse settings, such as considering seen-task loss, different regularizations, etc.\n\nWeaknesses: One weakness I find is that there is no experimental results. I understand that this is a purely theoretical paper: of course showing that increasing regularization strength for isotropic regularization would have been ideal, but at least showing that the lower bounds / upper bounds make sense for certain continual linear regression problems could have been good.", "was_revised": true, "final_justification": "There was basically no issue in this paper: the contributions were solid and to me they could potentially be very influential in continual learning community. A question I had was is the joint realization assumption reasonable, and the authors pointed out to an interesting phenomena which shows that it is indeed the case. So I did not change my initial assessment.", "rebuttal": "We thank the reviewer for their positive feedback. We are happy that they find our schedules **novel** and **“very valuable”**, and that they appreciate the SGD perspective that we derive.\n\nWe like to highlight that—as the review summary mentions—we did employ the bound from Evron et al. [13] while proving the nearly-optimal rate for fixed regularization strengths (Lemma 4.3); however, the proof of the optimal rate for increasing strengths required novel analytic techniques (Lemma 4.7), not covered by the previous analysis of [13].\n\nThe reviewer mentioned as a **weakness** that we do not have **experimental results**:  \nAs the reviewer mentioned, this is a purely theoretical paper focused on establishing convergence guarantees. That said, we agree that simple experiments can help illustrate the behavior of our regularization schedules and highlight the practical implications of our theoretical results. We will work on such experiments, but due to the short rebuttal period (which doesn't allow any figures), we will only be able to do so for the final version.\n\n---\n\nWe now answer the reviewer's important **question** about the *joint realizability assumption*:\n\n- First, please note that we assume joint realizability solely for the training data. This assumption is quite **common in theoretical work** [e.g., 11,12,13,16,25,35] and is **practically reasonable in overparameterized models**. In particular, it was shown empirically [\\*1] and theoretically [\\*2; Theorem 1] that a sufficiently overparameterized neural network can perfectly fit data, even with random labels.\nThis holds also to linearized approximations of such networks (e.g., using the Neural Tangent Kernel).\n\n- The reviewer also mentioned that “joint realizability feels like the framework doesn't have the notion of forgetting”. However, this intuition is misleading. For example, a prior prominent work (Evron et al. [11]) illustrated geometrically how even under joint realizability, solving a task would often lead to forgetting the previous one (i.e., leaving its solution space; see their Figure 1).\nOn the other hand, they showed that learning any single task 'contracts' the learner toward the offline (joint) solution, agreeing more with the reviewer's intuition.  \nEven so, they presented adversarial task sequences under which the learner learns *virtually nothing*—i.e., forgets everything—even after observing an *infinitely long sequence of jointly realizable tasks*.\n\n- Moreover, like our Table 1 shows, prior work has proved that the lower and upper bounds on the convergence of continual learning schemes may differ (quite significantly), even under the joint realizability assumption. Our work shows that regularization, widely used in practice, theoretically achieves optimal rates under that assumption.\n\nWe will use the discussion here to illuminate these aspects in the revised manuscript.\n\n---\n\n**Additional references:**  \n[\\*1] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.  \n[\\*2] E. B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity, 1988."}]

Author rebuttal:

Meta-review: The paper studies overparameterized linear regression in the continual learning setting with repeated tasks, under random task ordering. It is motivated by a gap left from prior work: the lower bound on the convergence rate was $\Omega(1/k)$, while the upper bound was $O(1/k^{1/4})$. This paper closes this gap. The main idea is in using increasing regularization strength between the task adaptation procedures, either via explicit regularization (i.e., by adding a quadratic term to the objective) or via implicit regularization (early stopping). All reviewers were in agreement that the paper presents solid theoretical contributions and is a good fit for NeurIPS.
Decision: Accept (poster)