Are Greedy Task Orderings Better Than Random in Continual Linear Regression?
Authors: Matan Tsipory
Ran Levinstein
Itay Evron
Mark Kong
Deanna Needell
Daniel Soudry
Venue: NeurIPS 2025 poster ()
Keywords: continual learning
lifelong learning
task ordering
curriculum learning
forgetting
kaczmarz
Primary area: theory
TL;DR: We study greedy task orderings in continual learning that maximize dissimilarity between consecutive tasks, and compare their performance to random orderings both analytically and empirically.

Abstract: We analyze task orderings in continual learning for linear regression, assuming joint realizability of training data.
We focus on orderings that greedily maximize dissimilarity between consecutive tasks, a concept briefly explored in prior work but still surrounded by open questions.
Using tools from the Kaczmarz method literature, we formalize such orderings and develop geometric and algebraic intuitions around them.
Empirically, we demonstrate that greedy orderings converge faster than random ones in terms of the average loss across tasks, both for linear regression with random data and for linear probing on CIFAR-100 classification tasks.
Analytically, in a high-rank regression setting, we prove a loss bound for greedy orderings analogous to that of random ones.
However, under general rank, we establish a repetition-dependent separation.
Specifically, while prior work showed that for random orderings, with or without replacement, the average loss after $k$ iterations is bounded by $\\mathcal{O}(1/\\sqrt{k})$—we prove that single-pass greedy orderings may fail catastrophically, whereas those allowing repetition converge at rate $\\mathcal{O}(1/\\sqrt[3]{k})$.
Overall, we reveal nuances within and between greedy and random orderings.

Are Greedy Task Orderings Better Than Random in Continual Linear Regression?
Matan Tsipory *
Ran Levinstein *f
Itay Evron *f
Mark Kong
Deanna Needell
Daniel Soudry
Abstract
We analyze task orderings in continual learning for linear regression, assuming joint realizability training data. We focus on orderings that greedily maximize dissimilarity between consecutive tasks, concept briefly explored in prior work but still surrounded by open questions. Using tools from the Kaczmarz method liter- ature, we formalize such orderings and develop geometric and algebraic intuitions around them. Empirically, we demonstrate that greedy orderings converge faster than random ones in terms of the average loss across tasks. both for linear regres- sion with random data and for linear probing Analytically, in high-rank regression setting, we prove a loss bound for greedy orderings analogous to that of random ones. However, under general rank, we establish snpetition-dependen separation. Specifically, while prior work showed that for random orderings, with or without replacement, the average loss after k it- erations is bounded by ((1/V)) we prove that single-pass greedy orderings may fail catastrophically, whereas those allowing repetition converge at rate (11 VK). Overall, we reveal nuances within and between greedy and random orderings.
SIFAR-100 classification tasks.
Introduction
Continual learning is subfield of machine learning in which learner exposed to tasks or datasets sequentially. In such setups, only single task is fully accessible at any given time, due to, for instance, computational limitations, data retention or privacy constraints, or the temporal nature of the environment. While much of the continual learning research focuses mitigating forgetting improving transfer, the role of task ordering is not yet fully understood.
Understanding how task order affects learning and what characterizes optimal orderings is important for both theoretical and practical reasons. Such understanding can illuminate failure modes, clarify the interplay between forgetting and transfer, and guide the design of continual environments and algorithms. Furthermore, it can inform active control over task sequences settings that permit (e.g., robotic environments), situating the problem at the intersection of continual learning, multitask learning, currieulum learning, and active learning. This line of inquiry raises impactful computational and financial questions in the era of large language models and foundation models:
Can task ordering by itself mitigate forgettin even under vanilla continual training?
What constitutes "optimul" task ordering?
Is it better to learn when adjacent tasks are similar or dissimilar?
Can greedy strategies systematically outperform random task orderings?
"Equal contribution.
Techhnoo,, Haifa.
1 University of California, Los Angeles.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

One compelling direction in the continual learning literature is the design of task orderings informed by task similarity. This idea appears in several earlier works, with varying degrees of emphasis and
differing motivations [e.g., 56 79 90
Most closely related to our work is Bell and Lawrence [4], who were among the first to explicitly and systematically examine such orderings in continual learning. They hypothesized that optimal performance would arise when adjacent tasks are similar. Surprisingly, they empirically found the opposite- opposie--orderings with dissimilar adjacent tasks led to better performance. More recently, Li and Hiratani (62) reached similar conclusion and further proposed arranging tasks from the least to the most "typical". While these studies are thought-
89
71
44
63
72
provoking, they are either empirical [7T] 14 72), based restrictive data assumptions [63] 62), or focused solely on incremeentl settings (79). with some of their findings appearing inconclusive or contradictory. This underscores the need for more rigorous theoretical understanding.
To this end, we formalize "similarity-guidee orderings through greedy task selection, leveraging tools from related fields. Building on projection-based perspective of continual learning [K] 34 we introduce two greedy orderings-Maximunn -aximum Distance and Maximum
studied in the Kaczmarz 775 73 and projection methods literatures [2] 41] Using these orderings, we build a geometric intuition for greediness, as illustrated in Figure I We then develop both analytical and empirical insights-e.g. by experimenting random and CT tasks and proving optimality
cesidual-commene
results for high-rank tasks.
Surprisingly, under general tasks, although without- replacmeett random orderings are known to converge 355 IO], we show that single-pass greedy orderings may fail catastrophically. We further prove that this drawback is resolved under greedy orderings with repetition, for which we establish a dimensionality -ineit--iddeeeneent convergence bound. Finally, we propose a hybrid scheme combining greedy and random orderings, highlighting its empirical and analytical benefits.
We hope that the theoretical (oundations-perspeeet will inspire future work on task orderings and their potential to mitigate catastrophic forgetting.
tools, and findings-laid out in this paper
Summary of our contributions.
We formalize similarity guided orderings in continual linear regression via greedy strategies, drawing on tools and intuitions from the Kaczmarz and projection literature (Section 33.
suuided
2. We empirically demonstrate that greedy orderings converge faster than random orderings, both on synthetic regression tasks and on SEFARR-10-bbar classification tasks (Section
3. We prove optimality and convergence guarantees for high-rank tasks (Section 4.2
4. For general-rank data, we design adversarial task collections in which single-pass greedy orderings provably induce catastrophic forgetting, i.e., yield an 22(1) loss even as T - oo (Section 5.1
5. In contrast, we prove an (11 (T) upper bound for greedy orderings with repetition (Section 5.2)
6. We combine greedy and random orderings into hybrid strategy that performs well empirically and inherits the bounds of random orderings, avoiding greedy failure modes (Section 5.3)
TaskA solutions
A
Task B solutions
B
Task C solutions
CC
W3
Task D solutions
(a) A greedy ordering with dissimilar adjacent tasks.
(b) A greedy ordering with similar adjacent tasks.
Figure 1: Intuition. Consider a collection of jooontly-raalizablll linear regression tasks (e.g., A,B, C) Each task has an affine solution space (e.g., where X,W = ya), and w, is an "offline" joint solution at the intersection of all tasks. Employing projection perspective on learning in continual models 33 34 we see that transitions between dissimilar tasks (A (A->D- BB +B+C) intuitively lead to faster convergence toward the intersection compared to transitions between similar tasks (A (A-+B CB.

---

2 Setting and Background: Continual linear regression
We focus on continual linear regression, common in theoretical continual learning [e.g.. 29
33 35
63 78 38 46]. This setting, though simple, already gives rise to key continual learning phenomena, such as complex interactions between forgetting, task similarity, and overparameterization [see (3)]
Notation. We reserve bold symbols for matrices and vectors, e.g., X, w. We use ||||| to denote the Euclidean norm of vectors and the spectral (L.2) norm of matrices. X denotes the Penroee pseudoinverse of matrix. Finally, we denote [n] = I.....
Formally, the learner is given access to a task collection of T linear regression tasks, i.e. (X1.y))..... (Xr.yr) yr) where Xm Raaxd Ym R== We denote the data "radius" by R A maxme [T] [xm]|= For k iterations, the learner sequentially learns the tasks according to task ordering T [K] + [2], which-as this paper chows-can be crucial in continual learning.
Scheme Continual linear regression (to convergence)
Initialize Wo O₂d For each iteration / = ....., k:
.....,,.
W, Start from W,-1 and minimize the current task's loss (i(()) (w) - [ y-ool with (S)GD to convergence
Output W
We assume throughout the paper that there exist offline joint solutions that perfectly solve all T tasks jointly. This assumption is commor
el in many theoretical continual learning papers and facilitates the analysis [e.g.. [33] 34 35 [4 39 [1]. Moreover, it naturally holds in highly overparameterizee models and is thus linked to the linear dynamics deep networks in the neural tangent kernel (NTK)
regime [see 49 23
Assumption 2.1 (Joint Linear Realizability of Training Data). Assume the intersection of all task
solution subspaces is non-empty, i.e., W, å n Wm _ Nmm= Rd
X w = ym # Ø.
We focus the joint solution with the minimum norm, often linked to improved generalization. Definition 2.2 (Minimum-noon -oommmmmm-oommmmmm joint solution). Denote specifically w. - argmin /w/].
weW.
39 351 and study the model's ability to not "forget" previously seen data, and accumulate expertise on the training data (of all tasks). This focus isolates continual dynamics from statistical generalization effects that also arise in non-continual, stationary settings.
We follow prominent theoretical work [e.g.. 29
Definition 2.3 (Average loss). The (training) loss of an individual task m [T] defined as L. & ||X w ym 112 The loss we analyze is the average across all T tasks, which in our realizable setting takes the following form:
((wx)
Σ
(wi) = 1w.
Σ Imm (W w.)ll? m=1
T
T
m=1
where we also normalize by the generally unavoidable scaling factors ||w.|| and R & max
| ||-
me(2"
Remark 2.4 (Forgetting loss). An alternative quantity considered in continual learning 20 33 the forgetting, defined as the loss degradation at iteration & across previously seen tasks only, i.e., T - (Wx)) (r) (w:)). simply & Σ ||x+() Wi yr(1) || in our realizable setting. Since we mostly focus on single-pase orderings where each task is seen once, the forgetting ultimately coincides with the average loss. Thus, we presentation and study the average loss.
'A different trend continual learning theory assume underlying linear model, like do, but allow additive label noise [e.g.. 38 63 109
28 60) 61]. However, this comes at cost strong assumptions on the features e.g., commutable covariance matrices or i.i.d. features across tasks. To some extent, the analysis in Section 5.1 of Evron et al. (38) suggests that, under such assumptions, task ordering has limited impact. Thus. it may not be suitable starting point for studying similarity guided orderings, in contrast assumption.
3

---

Another insightful quantity is the distance to w.. Definition 2.5 (Distance to the joint solution). After & iterations, the (squared) distance is,
(7(wk)
[w.]] |w -w.ll
This distance upper bounds the loss, as can be shown using simple norm inequalities.
Proposition 2.6 (Linking the quantities). After iterations of Scheme / on jointly realizable tasks, the loss is upper bounded by the distance the joint solution.
((w*)
Σ m=1
Xm (We -W.]l
w.]l
w. [W -.. w.
D2 (wwx).
w. FR
T
In some cases, the distance remains large while the loss vanishes, showing that converging to w, not
mandatory for continual learning [33]. Focusing on the loss paves the way to universal convergence,
independent of the problem's 's complexity, e.g., condition number 85
Geometric interpretation to learning. In each iteration of Scheme | the learner minimizes the squared loss of the current task to convergence 5 Each iterate w, of this scheme above is known (33 to implicitly follow the following closed-form update rule,
X
+ ((()) +
x-x T(A) x(()
W
Conveniently, in our realizable setting, this update rule admits an intuitive geometric interpretation. Evron et al. (33 identified an orthogonal projection operator,
Wr(e-1)
m X Xm Rddd
which use for analysis only (Scheme computes pseudoinverses or SVDs).
I never explicitly
Under the realizability assumption, Vr()) X.)) plug it into Eq. ①T and obtain:
Pr(e)
W. X 7(2) X W. + (I- Xt (()) XT0)
W
Wxto)
W:
W. w. = Pr()) (Wi-1-W.) w.).
Figure 2: Projection dynamics.
Geometrically, Wr-1 is projected by an affine projection onto the solution space task (t). In paper, we adopt this projection-based perspective-provee proven useful in theoretical work on to build intuition about greedy orderings.
continual learning 33 34
Greedy task orderings: A formal approach and intuition
As discussed in Section I the learning order plays crucial role in the dynamics of many machine learning settings. This phenomenon has also been observed continual learning, both analytically and empirically. Several works have proposed leveraging "similarity- Aimilarity-guided guided" task orderings pplacing dissimilar tasks consecutively. However, the existing literature still lacks the rigor and analytical tools needed to fully understand such orderings. To address this gap, this section draws on connections between continual linear regression and other research areas to formalize greedy task orderings and develop the mathematical tools necessary to study them.
Geometric intuition. As illustrated in Figure 2 the projection perspective allows to decompose ||w, w.|l using projection properties and the Pythagorean theorem as:
I| w.ll ||w:-1 1 w, 1| || w
(3)
= || || w. [I P (wa))(w=-1 - w.)l
-w.]]
Thus, to try and minimize l|w; -wr-w.ll"" one could greedily maximize [|(I- (wo-))
"This simplifies the analysis; other choices exist well, e.g. fixed number of steps per task [1]
59

---

This has inspired a myriad of studies on Kaczmarz and projection methods [e.g., 2...2110 75 16 which employed ordering schemes that greedily maximize |[ wall". "e in the following spirit.
Definition 3.1 (Maximum Distance Ordering). Greedily maximize the distance between iterates, i.e.
(MD(t) = argmax (ra
X W ym)ll (x-
argmax me([T))/xo(1Z) (I:tt]
[| ([I-PA Pm. (W;-1 - w+)ll
at each iteration E (7), where TMD (1 :::. 1) {TMD (1),..., TMD (t 1)}
Our earlier Figure Ta illustrates the MD ordering and how it leads to faster convergence to w..
Distance and task similarity. The distance between iterates (t- and (()) reflects some angle between the affine solution subspaces of their corresponding tasks, and more generally, relates the principal angles between these subspaces [33]. These angles can be used to quantify task similarity. as illustrated in the setting of Section 4.2 and Figure] [
alternative greedy ordering found in the literature is the Maximum Residual ordering [e.g.. 2, 40 75 [06]. This rule is easier to compute in full, or to estimate using a small validation set.
Definition 3.2 (Maximum Residual Ordering). Greedily select the task exhibiting the greatest error:
MR (t)
argmaxx [m,, W ymll?,
vt E (T).
Notice that the MD and MR orderings related since X., Xx, X X X, (I Pm),, and,
X W yml 11
Xm (W:-1 - w.)ll Xm 1 | [[II P (W(11 -w.-l- w.)ll
Single-pass orderings. Our paper mostly focuses on "single-pase songle-pass" greedy orderings, where each task is encountered exactly once. Although disallowing repetitions departs slightly from the motivat- ing literature on projection methods, is the more common- and arguably more natural-setup in continual learning [see [4 62). Even in curriculum multitask learning, limiting tasks a single pass can reduce training costs. Nonetheless, in Section 5.2
we examine the effect of repetitions.
Computational tractability of greedy policies. As explained above, the benefits of greedy order- ings are intuitive, The cost of computing the greedy rules in Definition 3.1 and Eq. (4), of course, introduces tradeoff between convergence rate and overall computational cost. Before continuing our investigation of these orderings, we briefly address their computational feasibility.
(i) Estimation: Greedy rules can often be estimated efficiently in practical scenarios. For example, the maximum residual rule (Definition 3.2) requires the current loss of each available task. This quantity can be approximated using a small subset of samples or via dimensionality reduction techniques [e.g., see 31]. I. In App-Cc
C we show empirically that the maximum residual rule performs comparably to the maximum distance rule, and that its performance remains unharmed even when approximated using only 1% of the data. In deep networks, computing that rule requires only forward passes and may reduce the number of gradient steps thereby lowering overall time and memory costs by limiting costly backward passes 47
(ii) Heuristies:
Our greedy rules rely residuals to quantify the similarity between the current task and the remaining ones. This approach exemplified in Figure I and Fq. (5) of Section and is related to principal angles between subspaces [see 33] Alternatively, one could utilize
heuristic notions of task similarity-ee e.g. predefined [56] or computed metrics that use Hessians
14], zero-shot performance 622 or task embeddings [1]
(iii) Structured tasks: If each step updates relatively few residuals (e.g., in a Kaczmarz setting with sparse columns and rows), only few residuals must be recomputed [75]
"The Kaczmarz method 52 22
further explained in App. iteratively solves linear system of equations.
In practice, the MD rule is easy compute for rank-1 tasks, since it reduces to [x ||x W ymm In higher ranks, this rule is harder to compute exactly but can be estimated, e.g., with subsample of the task.
5

---

Benefits of greedy orderings
natural competitor greedy strategies is the random strategy, uniformly sampling tasks (rows blocks in the Kaczmarz context) from the task collection (7). That is,
TUait (1), ..... Uunr Uniform ([T))
As mentioned earlier, greedy strategies have long-standing history in the Kaczmarz method [75] 76
106 102 employing either deterministic 75 or probabilistic selection rules. In this context, greedy orderings often achieve better provable bounds on distance to w+ (Definition 2.3 compared to random orderings. In contrast, our focus-and that of related continual learning literature (..g..33. 34 51p-eeterss of the loss (Definition 2.3). While the loss is upper bounded by the distance to w. (Proposition ...6.. the existing Kaczmarz rates fall short in two ways: (i) they rely on repeating rows/blocks and do not apply in the single-pass regime central to continual learning; and (ii) even when repetition is allowed, their rates depend data eigenvalues, potentially making them much slower than data-inder inteeinneeenddnt (1/ Vk) guarantee of Theorem 5.3
and block variants 73
68
108
11 12
107 95
convergence
In this section, we examine how well the advantages of greedy over random orderings carry over to the loss in continual settings first empirically, then analytically.
4.1 Motivating experiments: Greedy outperforms random ordering
Here, test different task ordering strategies synthetic regression tasks and more complex classification setup using linear probing in a comain-incrementte CIFAR-100 setting
Regression tasks: Random data. The feature matrices X Xy are drawn from a Gaussian distribution. We compare the two random ordering (Eq. 4 and complementary minimum distance strategy (defined as in Defini tion 3.1 replacing argmax with argmin). Full details, including more combinations of task count T, dimension d, and rank r, well as experiments anisotropic data, are provided in App. B
greedy strategies (MD, MR) to the
Classification tasks: CIFAR-100. We randomly partition classes into continual binary classification tasks, similarly to Li and Hiratani (62). We train a linear probe on top of ResNet-20 embedder, pretrained on the original CIFAR 100 multiclass task 45 55 We optimize the cross-entropy loss of each task while employing L2 regularization towards the previous parameters [65]. We compare the performance 'joint' baseline, trained on all tasks together (not continually). See App. C [[oo full details. There, we conduct further experiments on continual CIFAR- 100 tasks as before, but using embeddings pretrained on (i) CIFAR-10 and (ii) CIFAR- 100 with only half of the samples from each class (in this case, continual learning is performed on tasks formed from the other half). We also examine more computationally efficient greedy orderings, determined from only a fraction of the dowa- to 1 %% (5 samples per class in CIFAR-100).
70
10
Test accuracy
Greedy MD
Greedy MR Random
Loss
10
Grendy Min. Dist.
60
Random
10
Greedy MR
Greedy MD
10
20
30
40
50
10
20
30
40
50
Seen tasks
Seen tasks
(a) Regression (random data): Average loss over T' 50 regression tasks of rank 10 in d 100 dimensions, sampled from an isotropic Gaussian distribution. Details in App.
(b) Classification (CIFAR-100) Average test accu- racy over T' = 50 binary classification tasks, gener- ated by randomly partitioning CIFAR- 100 classes (a iomain-incremental setting). Details in App.
Figure 3: Task ordering comparison. Transitioning between dissimilar tasks consistently outper- forms random transitions, with Greedy MR and MD achieving comparable performance.
'We provide code snippet for the regression experiments in App. The code for the classification experiments is accessible atthtps::/// http:/hhww..oo/mmttttt/teeeeeeee wtweaanntttteeeeeeeeeeeeeeeeeeee orderingg

---

4.2 Provable benefits for high-rank, "nearly determined" tasks
To further motivate greedy orderings, we analyze a simple setup where each task's matrix is of nearly full rank, i.e., rank rank(Xm) = d - 1, Vm E [T). Even in such setup, it has been shown that arbitrary orderings of T 20 may lead to catastrophic forgetting and maximal losses [33].
In this setup, each projector can be expressed as a rank-1 operator, i.e., Pm = X -V V for unit vector Vm E IR Distance (Definition
that spans the solution space of task m. Then, we can rewrite the Maximum rule to explicitly maximize dissimilarity between consecutive tasks, i.e.,
(f) = argmin ( (v (V (+(t-1)) 1))
(0-- (5)
where we define V+(0)
(Wo w.): see Eq. (6) in App. D
Optimality of greedy orderings in terms of distance to w.. Earlier in Eq. (3). we motivated the MD ordering as greedily maximizing the decrease in ||w: w.ll. Does this guarantee a minimal distance ||Wr- w at the end of the sequence? Here, we prove that the MD ordering yields square-root approximation of the optimal distance at the end of learning
Lemma 4.1 (Optimality guarantee when r = d-1). 1). Let wite and w be the iterates after learning T jointly realizable tasks of rank d - 1 under the Maximum Distance ordering TMD and an optimal ordering T, that leads to a minimal distance to the joint solution w.. Then, their distances hold,
|
TMD
w.
1[ -w.ll D(w?)= S1
0 S (w < (W
1
w+1
The full proofs for this section are given in App.
What about the loss? The optimality of the distance does not imply optimality of the average loss, exemplified in Fn Section 6 Instead, now derive an upper bound for the loss.
Lemma 4.2 (Loss bound when r = - 1). Under the Maximum Distance greedy ordering over T jointly-realizabee tasks of rank d- 1, the loss of Scheme [after T iterations is upper bounded as,
((WT)
1 T
Σ
[X - eT
1
w. RR
This rate matches a recent O - bound for random orderings without replacement 335 whereas the best known rate for such orderings with general-rant tasks is O(/vT) [10]. This raises the question: for general-rant rank tasks, can single-pas, greedy orderings still compete with random ones, or even outperform them, in worst-case analysis? Next, we show that they cannot.
Failure modes and surprises in greedy orderings
Under random orderings, with without replacement, Attia et al. 110 proved universal, dimenssonallit--ndeeeeeen rate of Brear ((w < 13/Vk. Surprisingly, we prove a clear separation in our setup: while Lingle-pas: greedy orderings can fail catastrophically, i.e., not decrease with the number of iterations k = T, greedy orderings with repetition enjoy a bound of (1/V/))
5.1 Greedy orderings can fail where random ones do not
We now present cases where the single-pass greedy ordering forgets catastrophically, i.e., suffers an ?((1) loss, even after fitting a collection of 7' + oo tasks. Specifically, we present an example in d = 3 dimensions where the loss does not diminish, and a construction in d = T + dimensions that exploits dimensionality to yield maximal forgetting. Full details and proofs are given in App.
9 Our optimality result related to optimal Hamiltonian path a predefined similarity graph, as studied related work [14 (2]. Specifically, in this section's 's high-rank case, similarity can statically defined as 8m,m. = cos² (0 (0m,m.) Then, the greedy MD ordering approximates the Hamiltonian path that maximizes I| (t-1t))).... [see 37 70). However, under general tasks, our greedy rules (Def. 3.1 and 3.2) are computed online at each iteration and depend not only on the previous task r(t - 1) but also on the previous iterate W:-1. Consequently, these rules do correspond to Hamiltonian path any predefined graph.
7

---

Example 5.1 (Adversarial 3d construction). For all T E {4- -0'-001- 1.2..,, there exists a task collection of reintly-relizable tasks in d = 3, such that [(w f( L( (m)) >> 2.78 10-5
Theorem 5.2 (Greedy lower bound). For any d 2 30, there exists an adversarial task collection with tasks (of different ranks) such that both greedy orderings (MD, MR)
T = d- - 1 forget catastrophically. That is, the loss at the end of the sequence is, L(w (TT) ((w,
We demonstrate the behavior of adversarial task collection using T = 999 tasks in d = 1000 di- mensions. Our constructed collection "tricks" the 0.075
0.125
0.100
greedy orderings: slowly increasing not only the loss on all tasks, but also the forgetting of previ- ous tasks. The model is thus unable to accumulate knowledge and practically forgets everything learns.
0.050
Loss (all tasks)
0.025
Forgetting (seen tasks)
0.000
50
100
Seen tasks (%)
Figure Learning an adversarial collection.
5.2 Single-pass vs. repetition in greedy orderings
So far, we have focused on single-pass greedy orderings, in which each task is learned exactly once. These are conceptually related without-replacemmnt sampling and (re)shuffling techniques in SGD and the Kaczmarz method, where repetition-fiee free strategies often converge faster than with-
replacement sampling, both empirically [7. 76 96) and theory (69 42 15 50 43
but see 84 26
We ask: Does the advantage of orderings without repetition exlend to greedy orderings?
Now, we show that repetition in greedy orderings avoids the failure mode of single-pass ones.
Theorem 5.3
paarsiionaait-indeeeedeeee bound for greedy orderings with repetition). Under Maximum Distance greedy ordering with repetition (TMD-R) over T reiltal-r tasks, the loss of Scheme after ks iterations is upper bounded as L (w--) (L)
App. provides the proof, comparison to prior rates (Table and details for the experiment below.
We evaluate the effect of repetition across orderings under random data. As in prior work, random sam- pling without replacement outperforms with replace- ment. In contrast, repetition benefits greedy orderings, likely due to larger updates and faster convergence to w.. The slowdown in the single- pass case likely reflects the exhaustion of high dissimilarities.
10-2
10-3
rapi.
10-4
Random, without repl.
Greedy, single pass
10.5
Greedy, with repetition
10
30
Iterations (seen tasks incl. repetitions)
Intuitively, repetition in random orderings exposes the learner to less data, while greedy selection allows considering all tasks at each step.
Figure 5: The effect of repetitions.
However, these findings do not always hold, seen in our classification example (App- C.5
5.3 Extension: Hybrid task orderings
To leverage both the fast empirical convergence of greedy orderings and the analytical convergence guarantees of random ones, we introduce a "hybrid" strategy: begin with greedy selection and switch to random once the decrements [w,-1- - w fall below a threshold. Analytically, using a suitable threshold, we prove in Lemma G.T that any bound for without-replacemmet random orderings. e.g.,
O(I/VT) 10 extends our hybrid scheme, showing it avoids the failure mode of Section 5.1
Empirically, the hybrid ordering performs better than random but worse than greedy. This matches our in- tuition from Eq. (3) and Figure La greedy selection takes larger "steps" (or projections), particularly early on, when most tasks are still available. Once these projections diminish, ing, mhnich-uniiee the greedy approach cannot be adversarially "tricked" into failure.
10--
Random Hybrid MD
switch the random order-
Greedy MD
10
20
30
40
50
Seen tasks
Further details and experiments appear in App. G
Figure 6: Hybrid ordering experiment.
8

---

Discussion and related work
So far, we have studied greedy task orderings, demonstrating empirical and analytical benefits of tran- sitioning between dissimilar tasks. Here, we expand connections and ideas not yet fully covered to better situate our work within the existing literature. In App. A we discuss further links to Kaczmarz methods, curriculum and active learning, coordinate descent, and example selection in SGD.
Task orderings in continual learning theory. Continual learning theory often treats task orderings as arbitrary. However, several analytical works [e.g.. 33 Snderings-ttpically
54 51 19] show that certain cyclic or random-cui can mitigate forgetting (matching empirical findings (58)). While some works downplay ordering arguing they are often minor-and defer their study to future work [92), others design continual learning algorithms specifically for evolving sequences with very similar adjacent tasks [6]. We follow a different line of work that studies how pairwise task similarities, or dissimilarities, influence continual schemes.
particularly relevant work by Bell and Lawrence [4]] advocates pairwise task dissimilarity as a guiding principle and was among the first to empirically investigate similarity-uuided task orderings. Tasks are represented as vertices a complete graph, where edge weights correspond to predefined distance between tasks, and Hamiltonian paths represent full task orderings. They hypothesized that a minimum- weight path (favoring similar tasks in succession) would yield the best continual performance. Yet their experiments on simple neural networks indicated the opposite: maximum- weight paths, placing dissimilar tasks adjacently, often led to improved performance. Still, these results were not always statistically significant (see their Figure 5) moomviivgiing us to revisit similarity- guided task orderings from a more analytical perspective.
Li and Hiratani [22 conduct a deeper investigation into similarity- task orderings, obtaining more statistically robust empirical results. They likewise find that adjacent tasks should be dissimilar, and further explore task "typicality" (discussed below). While deriving results for a linear regression model to support their empirical observations (on neural networks). they rely on a restrictive analytical data model in which features are randomly drawn from simplified distribution across tasks. In contrast, our analysis accommodates arbitrary feature matrices, allowing richer and more realistic forms of task similarity. Like Bell and Lawrence 114, their goal is to characterize optimal orderings in general, whereas we formalize and analyze greedy orderings specifically, both as a practical strategy and as a proxy for optimal ones.
Ruvolo and Eaton 88 propose an "information maximization" approach to task ordering, using a diversity-basee based heuristic related to our maximum residual strategy (Definition 3.2). However, their complex model limits rigorous theoretical analysis of the kind we provide.
Lin et al. 63 examine the role of task similarity and reach conclusions broadly aligned with ours. While influential, their work differs from ours in several ways. First, their analysis relies on restric- tive i.i.d. feature assumption across tasks. They also assume a distinct teacher model per task, unlike our setting, where all tasks share a single overparameterized model-as common in modern deep learning. Consequently, their notion of task similarity relies on teacher similarity. rather than more practical measures such as residuals (as in Definition 3.2) or feature similarity. Although they note ordering effects in their expressions and briefly support them with classification experiments, task or- dering is not their primary focus. In contrast, we offer comprehensive treatment of similarity-guin orderings specifcally-providing providing formal definitions, geometric intuitions, greedy strategies, optimal- ity results, empirical validation, failure modes, and repetition analysis.
Can similarity-guided task orderings alone mitigate forgetting? Methods such as replay, reg- ularization, and parameter isolation are widely used to mitigate forgetting in continual learning 87 27 However, they depart somewhat from standard ("vanilla") deep learning practices that apply plain gradient methods to the (current) loss. Interestingly, both our work and prior studies show that even without such mechanisms, task ordering alone strongly affects forgetting. For instance, simply randomizing the task order-wind or without replacement- is known to alleviate forgetting [33
53
59 8
21
35 10, 58). In contrast, we show that single-pass -aaseeppsssssse greedy ordering can exacerbate forgetting (Section 5.1 while allowing task repetitions mitigates this effect (Section (52)). Moreover, ordering strategies can be combined with other approaches; for example, in our classification experi- ments we also employ regularization (Section 4.1 This underscores the importance of studying task ordering as a simple, complementary way to mitigate forgetting, while potentially keeping continual learning closer standard deep learning practice.

---

Task typicality at the end of learning. Li and Hiratani [62] suggest that tasks should be arranged from least to most "typical". While we did not focus on this aspect of orderings, our geometrie interpretation can illustrate it.
W/
Our motivation was to minimize the distance www--wll." which upper bounds the loss & Em= [[ (W wr.-- How- ever, this bound can be loose, and minimizing the distance does not guarantee the lowest loss. For example, in Fig- ure [ although ||wa - w.
||wc w.ll the point We is a better ending point than Wa. inducing a lower loss (the arrows represent the residuals). This happens because task C is more typical-i.e. more similar to other tasks than task A. The empirical advantage of greedy ordering may stem from a tendency to postpone typical tasks, perhaps causing its benefits to emerge only in later stages of training (see Figure 3b)
C
WC
D
Figure 7: Task typicality.
Regret today or loss tomorrow? In Section 3 we motivated the use of greedy orderings to minimize the distance to the joint solution ||w w. which in turn upper-bounds the average loss over all tasks: + >-' || (Wa- - w.)ll This objective is related, but not identical, to the notion of regret, which quantifies the loss along the optimization path on consecutive tasks, ie., Σ (xx,()) (W--1- - w-)ll². From this definition and Figure we observe that regret-
though also upper-bounded by the distances |w--- w- = can often benefit from transitions between similar tasks rather than dissimilar ones. In other words, to make accurate predictions during learning-egg. in decision-making transtioitnn between similar tasks may be preferable. Conversely, to minimize average loss across aaskseeg.. in curriculum or multitask learning- our findings suggest that transitioning between dissimilar tasks is preferable.
Other continual setups. The majority of studies support our conclusion that sequential task dissimilarity is beneficial [e.g.. 88 [4 71 33
63 66 9I). Still, the specific continual setup can
dramatically influence the behavior of task orderings. We consider a "dommin--incrementaa" setting: learning the same problem across different domains, i.e., PXX) changes but XY is fixed [99 (5). Alternatively, "rask-incrementa"" setups involve distinct tasks- with task identity known at both train and test time. There, prior work 779 72 trained a separate model per task and found that ammilaiit-maximmzan findings. However, in such scenarios, the focus shifts from forgetting inter-task transfer, benefiting from similar consecutive tasks (see discussion regret). Hence, their results complement ours.
with different P(YIX)
orderings prevail, seemingly contradicting our
Others have studied caaassiincrmmental learning (CIL), where each task introduces new objects or classes, aiming for strong overall performance (e.g.. in split benchmarks (97). While some CIL papers suggest that consecutive task similarity is preferable [44] 677, a closer look reveals that they modify the class composition within each task, inducing high intra-task heterogeneity [4]] g This likely
leads to wider minima and stronger "transferability" to other tasks, thus explaining their improved results. Such configurations resemble curriculum more than continual learning 10 To our knowl- edge, only Yang and Li [104] report contradictory results, possibly due to their empirical design |T Finally, we note that the effects discussed here are related to the interleaving effect in educational psychology 777 86
Future work. One could extend our findings to other settings- such as class- and task-ineremental, discussed earlier-ande and to more complex continual learning methods, such as replay and regularization. Moreover, our linear realizability assumption could be relaxed to accommodate label noise or even extend to nonlinear models, possibly borrowing tools from Kaczmarz literature [13] 106). would also be interesting to combine our approach with common wisdom in curriculum learning -ie., to design orderings that account for both task similarity and difficulty.
Finally, a promising direction for achieving tighter upper bounds in continual linear regression (see Table Th lies in probabilistic selection rules, inspired by randomized greedy Kaczmarz methods [2 107 95), which could combine the strengths of greedy orderings with the robustness of randomness, akin to our proposed bybrid scheme.
10 learner controls the internal task composition to create "easier" tasks, as in curriculum learning [00] "They construct the first task using random half of the classes. This strong "pretraining" leads to low initial loss, the model already learns half the classes. This resembles the failure modes discussed in Section 5.1
10

---

Acknowledgments and Disclosure of Funding
We thank Joseph (Seffi) Naor (Technion) for fruitful discussions. We thank Timothée Lesort (Univer- sité de Montréal, MILA-Quebec AI Institute) for fruitful discussions and valuable feedback.
The research of DS 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 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 in Al.
DN was partially supported by NSF DMS 2408912.
References
[1] A. Achille, M. Lam, R. Tewari, A. Ravichandran, S. Maji, C. C. Fowlkes, S. Soatto, and
P. Perona. Task2vee: Task embedding for meta-learning. In Proceedings of the IEEE/CVF international conference on computer vision, pages 6430-6439, 2019. (cited on P.
[2] S. Agmon. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6:382-392, 1954. (cited on p.
[3] G. Alain and Y. Bengio. Understanding intermediate layers using linear classifier probes. In ICLR 2017 Workshop Track, 2016. (cited on p.
[4] Alain, A. Lamb, C. Sankar, A. Courville, and Y. Bengio. Variance reduction in sgd by distributed importance sampling, arXiv preprint arXiv: 1.0681, 2015. (cited on p.50
[5] R. Aljundi, F. Babiloni, M. Elhoseiny, M. Rohrbach, and T. Tuytelaars. Memory aware synapses: Learning what (not) to forget. Proceedings of the European Conference on Computer Vision (ECCV), pages 139-154, 2018. (cited p. 27
[6] V. Alvarez, S. Mazuelas, and J. A. Lozano. Supervised learning with evolving tasks and performance guarantees. Journal of Machine Learning Research, 26(17):1-59, 2025. (cited
p. 9
[7] H. Asanuma, S. Takagi, Y. Nagano, Y. Yoshida, Y. Igarashi, and M. Okada. Statistical mechanical analysis of catastrophic forgetting in continual learning with teacher and student networks. Journal of the Physical Society of Japan, 10410), Oct 2021. (cited p
[8] N. Ashtekar, J. Zhu, and V. G. Honavar. Class incremental learning from first principles: A review. Transactions on Machine Learning Research, 2025. (cited on 10
[9] K. Atkinson. An Introduction to Numerical Analysis, 2nd Ed. Wiley India Pvt. Limited, 2008 ISBN
URL. https://booke: www.se.oooogg......... wttp.//oooooooieddoeeeee---
(cited on p. 94
[10] A. Attia, M. Schliserman, U. Sherman, and T. Koren. Fast last-iterate convergence of sgd the smooth interpolation regime. In The Thirty-Ninth Ninth Annual Conference on Neural Information Processing Systems, 2025. (cited on 2
40 50)
[11] Z.-Z. Bai and W.-T. Wu. On greedy randomized kaczmarz method for solving large sparse linear systems. SIAM Journal on Scientific Computing, 40(1):A592-A600) 2018. (cited on
10
[12] Z.-Z. Bai and T. Wu. On relaxed greedy randomized kaezmarz methods for solving large sparse linear systems. Applied Mathematics Letters, 83:21-26, 2018. (cited on p. 6
[13] Z.-Z.. Bai and W.-T. Wu. On greedy randomized augmented kaezmarz method for solving large sparse inconsistent linear systems. SIAM Journal on Scientific Computing, 43(6):33822 A3911. 11911, 2021. (cited on p. [0)
[14] J. Bell and N. D. Lawrence. The effect of task ordering in continual learning. arXiv preprint arXiv:2205.1333 2022. (cited on p.
5
10
19)
11

---

[15] P. Beneventano. On the trajectories of sgd without replacement. arXiv:2312.16143, 2023. (cited on p.
arXiv preprint
[16] P. A. Borodin and E. Kopecká. Alternating projections, remotest projections, and greedy approximation. Journal of Approximation Theory, 260: 105486, 2020. ISSN 0021-9045. (cited on p. 5
[17] L. Bottou, Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Puris, volume 8, pages 2624-2633.
Citeseer, 2009. (cited p. [18] W. Cai, Y. Zhang, and Zhou. Maximizing expected model change for active learning in regression. In 2013 JEEE 13th international conference on data mining, pages 51-60. IEEE, 2013. (cited on p. 19
[19] X. Cai and Diakonikolas. Last iterate convergence of incremental methods and applications in continual learning. In The Thirteenth International Conference Learning Representations, 2025. (cited on
[20] A. Chaudhry, P. K. Dokania, T. Ajanthan, and P. H. Torr. Riemannian walk for incremen- tal learning: Understanding forgetting and intransigence. Proceedings of the European conference computer vision (ECCV), pages 532-547, 2018. (cited p.
[21] A. Chaudhry, M. Ranzato, M. Rohrbach, and M. Elhoseiny. Efficient lifelong learning with a- a-GEM. In International Conference on Learning Representations, 2019. (cited on p.
[22] Y. Chen.
Pytorch cifar models.
https://github.coo hww.:////cccccoo/o/////o
pytorch-cifar- models, 2021. (cited on 25 101
[23] L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, Beygelzimer, F. d'Alché-Buce Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. (cited on p. 3
[24] R. Das, X. Chen, B. Ieong, P. Bansal, and sujay sanghavi. Understanding the training speedup from sampling with approximate losses. In Forty-first International Conference on Machine Learning, 2024. (cited on p.
[25] J. A. De Loera, J. Haddock, and D. Needell. A sampling kaczmarz-motzkin algorithm for linear feasibility. SIAM Journal on Scientific Computing, 39(5):566-887, 2017. (cited on
p. 5.
[26] M. De Sa. Random reshuffling not always better. Advances in Neural Information Processing Systems, 33, 2020. (cited on p.
[27] M. Delange, R. Aljundi, M. Masana, S. Parisot, X. Jia, A. 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
[28] M. Ding, K. Ji, D. Wang, and J. Xu. Understanding forgetting in continual learning with linear regression. In Forty-first International Conference on Machine Learning, 2024. (cited p.
[29] T. Doan, M. Abbana Bennani. B. Mazoure, G. Rabusseau. and P. 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.
[30] J. Donahue, Y. Jia, O. Vinyals, J. Hoffman, N. Zhang, F. Tzeng, and T. Darrell. Decaf: deep convolutional activation feature for generic visual recognition. In International conference on machine learning, pages 647-655. PMLR, 2014. (cited p. 25
[31] C. Eldar and Needell. Acceleration of randomized kaczmarz method via the johnson- lindenstrauss lemma. Numerical Algorithms, 58:163-177, 2011. (cited on p.
12

---

[32] T. Elfving. Block-iterative methods for consistent and inconsistent linear equations. Nu- merische Mathematik, 35(1):1-12, 1980. (cited on p. 19
[33] I. 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- 4079. PMLR, 2022. (cited on p. 2 3
40 49
[34] I. Evron, Moroshko, G. Buzaglo, M. Khriesh, B. Marjich, N. 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 on p.
25
27
[35] I. Evron, R. Levinstein, M. Schliserman, U. Sherman, T. Koren, D. Soudry, and N. Srebro. Bet- ter rates for random task orderings continual linear models. arXiv preprint arXiv:2504.04579 2025. (cited on
40 50 54)
[36] Fang, G. Fang, Yu, and Li. Efficient greedy coordinate descent via variable partitioning. In C. de Campos and M. H. Maathuis, editors, Proceedings of the l'hirty Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 547-557. PMLR, 27-30 Jul 2021. (cited on p. 19 50
[37] M. L. Fisher, G. Nemhauser, and L. A. Wolsey. An analysis of approximations for finding a maximum weight hamiltonian circuit. Operations Research, 27(4):799-80) 1979. (cited on p.
7
[38] D. Goldfarb and P. Hand. Analysis of catastrophic forgetting for random orthogonal trans- formation tasks the overparameterized regime. In International Conference on Artificial Intelligence and Statistics, pages 2975-2993, PMLR, 2023. (cited p. 3
[39] D. Goldfarb, Evron, N. Weinberger, D. Soudry, and Hand. The joint effect of task similarity and overparameterrizatoo on catastrophic forgetting an analytical model. In The Twelfth International Conference on Leurning Representationss 2024. (cited on p.
[40] M. Griebel and P. Oswald. Greedy and randomized versions of the multiplicative schwarz method. Linear Algebra and its Applications, 139(7):1596-1610, 2012. (cited on p. 5 50)
[41] L. Gubin, B. T. Polyak, and E. Raik. The method of projections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics, 7(6): 1967. (cited on p.
[42] M. Gürbüizbalaaan, A. Ozdaglar, and P. A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, (66(1):4-58)) Mar 2021. ISSN 1436-4646. doi: 10. 10000//111107-01--04440000000000
(cited on p. 19
[43] D. Han and J. Xie. A simple linear convergence analysis of the reshuffling kaczmarz method. arXiv preprint arXiv:2410.01 140, 2024. (cited on p. S
[44] C. He, R. Wang, and X. Chen. Rethinking class orders and transferabilitty in class incremental learning. Pattern Recognition Letters, 161:67-73, 2022. ISSN 0167-8655. (cited on p. 2
[45] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016. (cited on p. 25
[46] Hiratani. Disentangling and mitigating the impact of task similarity for continual learning. In The Thirty-Fightn Annual Conference on Neural Information Processing Systems, 2024. (cited on p.
[47] E. Hoffer, B. Weinstein, I. Hubara, S. Gofman, and D. Soudry. Infer2train: leveraging inference for better training of deep networks. In NeurlPS 2018 Workshop on Systems for MI., page 40, 2018. (cited on p.
13

---

[48] F. Hucht. Solving specific difference equation. MathOverflow, 2024. URL https: // mathoverflow net/ net/o/47433 474430 UKC.hhggg//maabbbeer.oo..eee///s (version: 2024-07- 04). (cited on
59
[49] Jacot, F. Gabriel, and Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. (cited on
[50] Jeong and Needell. Linear convergence of reshuffling kaczmarz. methods with sparse constraints. SIAM Journal on Scientific Computing, 2025. to appear. (cited on p.
[51] 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.
[52] S. Kaczmarz. Angenäherte auflösung von systemen linearer gleichungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat., pages 355-357, 1937. (cited on p. 19
[53] J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, Ctrabsk--Bawinnkkee et al. Overcoming catastrophic forgetting in
J. Quan, T. Ramalho, neural networks. Proceedings of the national academy of sciences, 114(13):3521-352 2017. (cited on p.
9 27
[54] M. Kong, W. Swartworth, H. Jeong, D. Needell, and R. Ward. Nearly optimal bounds for cyclic forgetting. In "hirty-Seventl Conference on Neural Information Processing Systems, 2023. (cited on
6 9
[55] Krizhevsky, Hinton, et al. Learning multiple layers of features from tiny images, 2009. (cited on p. 6 25 101
[56] Lad, Ghani, Y. Yang, and B. Kisiel. Toward optimal ordering of prediction tasks. In Proceedings of the 2009 SIAM International Conference on Data Mining, pages 884
SIAM, 2009. (cited on p. 5
[57] T. Lesort, M. Caccia, and I. Rish. Understanding continual learning settings with data distribution drift analysis. arXiv preprint arXiv:2104.0167. 2021. (cited on p. (00)
[58] T. Lesort, O. Ostapenko, P. Rodríguez, D. Misra, M. R. Arefin, L. Charlin, and I. Rish. Challenging common assumptions about catastrophic forgetting and knowledge accumulation. In Conference on Lifelong Learning Agents, pages 43-65. PMLR, 2023. (cited on p.
[59] Levinstein, A. Attia, M. Schliserman, U. Sherman, Koren, Soudry, and I. Evron. Optimal rates in continual linear regression via increasing regularization. In The Phirty-Ninth Annual Conference on Neural Information Processing Systems, 2025. (cited on p. 27
[60] H. Li, J. Wu, and V. Braverman. Fixed design analysis of regularization-base 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.3)
[61] H. J. Wu, and V. Braverman. Memory-statisties tradeoff in continual learning with structural regularization. arXiv preprint arXiv:2504.0400 2025. (cited on p.
[62] Z. Li and N. Hiratani. Optimal task order for continual learning of multiple tasks. In Forty- second International Conference on Machine Learning, 2025. (cited on p.
27
[63] S. Lin, P. Ju, Y. Liang, and Shroff. Theory on forgetting and generalization of continual learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 21078-21100 PMLR, 23-29 Jul
2023. (cited on p. 10
14

---

[64] Y. Lu, S. Y. Meng, and C. De Sa. A general analysis of seample-selectiin for stochastic gradient descent. International Conference on Learning Representations (ICLR), volume 10, 2022. (cited on 19
[65] E. S. Lubana, P. Trivedi, D. Koutra, and R. P. Dick. How do quadratic regularizers pre- vent catastrophic forgetting: The role of interpolation. In ICML Workshop on Theory and Foundations of Continual Learning, 2021. (cited on p.
[66] G. Honntione-Holmess J. Leo, and Kalita, Utilizing priming to identify optimal class ordering to alleviate catastrophic forgetting. In 2023 IEEE 17th International Conference Semantic Computing (ICSC), pages 64.64. IEEE, 2023. (cited on p. 10
[67] M. Masana, B. Twardowski, and J. Van de Weijer. On class orderings for incremental learning. arXiv preprint arXiv:2007.02145. 2020. (cited on p. [Tp
[68] C.-Q. Miao and W.-T. Wu. On greedy randomized average block kaczmarz method for solving large linear systems. Journal of Computational and Applied Mathematics, 413:1 14372, 2022. (cited on p. 6
[69] K. Mishchenko, A. Khaled, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances Neural Information Processing Systems, 13:1790--,7320, 2020.
(cited on p. g 19
[70] J. Monnot. Approximation algorithms for the maximum hamiltonian path problem with specified endpoint (s). European Journal of Operational Research, 161(3):721-735, 2005. (cited on p.
[71] C. V. Nguyen, A. Achille, M. Lam, T. Hassner, V. Mahadevan, and S. Soatto. Toward understanding catastrophic forgetting in continual learning. arXiv preprint arXiv: 1900:01008.0101,, 2019. (cited on p.
5 10)
[72] T. Nguyen, C. N. Nguyen, Q. Pham, B. T. Nguyen, S. Ramasamy, X. Li, and C. V. Nguyen. Sequence transferability and task order selection in continual learning. arXiv preprint arXiv:2502.06544 065444 2025. (cited on p.
10
[73] Y.QQ Niu and B. Zheng. A greedy block kaczmarz algorithm for solving large-scale linear systems. Applied Mathematics Letters, 104: 106294, 2020. (cited on 2
[74] J. Nutini, M. Schmidt, I. Laradji, M. Friedlander, and H. Koepke. Coordinate descent converges faster with the gauss-southwell rule than random selection. In International Conference on Machine Learning, pages 1632- 1641. PMLR, 2015. (cited on p. 19
[75] J. Nutini, B. Sepehry, I. Laradji, M. Schmidt, H. Koepke, and Virani. Convergence rates for greedy kaczmarz algorithms, and faster randomized kaczmarz rules using the orthogonality graph. In Proceedings the Thirty-Second Conference on Uncertainty Artificial Intelligence UAI'16, page 547-556, Arlington, Virginia, USA, 2016. AUAI Press. ISBN 9780996643115.
(cited on p. 2 6 50)
[76] P. Oswald and W. Zhou. Convergence analysis for kaczmarz-type methods in a hilbert space framework. Linear Algebra and its Applications, 478:131-161, 2015. (cited on p. 6
[77] S. C. Pan. The interleaving effect: mixing it up boosts learning. Scientific American, 313(2), 2015. (cited on p. 10
[78] L. Peng, Giampouras, and R. Vidal. The ideal continual learner; An agent that never forgets. In International Conference on Machine Learning, 2023. (cited on p.
[79] A. Pentina, V. Sharmanska, and C. H. Lampert. Curriculum learning of multiple tasks. In
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5492-5500, 2015. (cited on p. 10 19
[80] S. Rajput, Lee, and D. Papailiopoulos. Permutation- SGD: Is random optimal? In International Conference on Learning Representations, 2022. (cited on p. 19
15

---

[81] V. V. Ramasesh, E. Dyer, and M. Raghu. Anatomy of catastrophic forgetting: Hidden representations and task semanties. In International Conference on Learning Representations, 2020. (cited on p. TT
[82] A. Ramdas. Rows vs columns for linear systems of equations-randomized kaczmarz or coordinate descent? arXiv preprint arXiv:14006 440..5295 2014. (cited on p. 19
[83] S. Rebuffi, A. Kolesnikov, G. Sperl, and C. H. Lamperr. 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.1109/CVPR.2011
(cited on p.
[84] B. Recht and C. Ré. Beneath the valley of the noncommutative saatheeii--eommeti mean inequality: conjectures, case-studies, and consequences. Conference on Learning Theory (COLT), 2012. (cited on p. 8
[85] S. Reich and R. Zalas. Polynomial estimates for the method of cyclic projections in hilbert spaces. Numerical Algorithms, pages 1-26, 2023. (cited on p.
[86] D. Rohrer, R. F. Dedrick, and S. Stershic. Interleaved practice improves mathematics learning. Journal of Educational Psychology, 107(3):900, 2015. (cited on 10)
[87] A. A. Rusu, N. C. Rabinowitz, G. Desjardins, H. Soyer, J. Kirkpatrick, K. Kavukcuoglu, Pascanu, and R. Hadsell. Progressive neural networks. arXiv preprint arXiv: 1606. 660614671, 2016. (cited on p. (.
[88] P. Ruvolo and F., Eaton. Active task selection for lifelong machine learning. In Twenty-seventh AAAI conference on artificial intelligence, 2013. (cited on p. 10P
[89] H. Sajjad, N. Durrani, F. Dalvi, Y. Belinkov, and S. Vogel. Neural machine translation training in a multi-domain scenario. arXiv preprint arXiv: / 700000000000 087/2, 2017. (cited on p. 2
[90] N. Sarafianos, T. Giannakopoulos, C. Nikou, and I. A. Kakadiaris. Curriculum learning for multi-task classification of visual attributes. In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 2608-2615, 2017. (cited on p. 2
[91] C. Schouten. Investigating task order in online class-incrementae learning. Master's thesis, Department of Mathematics and Computer Science, AutoML Group, Eindhoven University of Technology, Netherlands, 2024. (cited on p. 10
[92] H. Shan, Q. Li, and H. Sompolinsky. Order parameters and phase transitions of continual learning in deep neural networks. arXiv preprint arXiv:2407.103115 2024. (cited on p. 9
[93] A. Shrivastava, A. K. Gupta, and R. B. Girshick. Training region-based object detectors with online hard example mining. 2016 IEEE Conference Computer Vision and Puttern Recognition (CVPR), pages 761-769, 2016. (cited on p. [9]
[94] P. Soviany, R. T. Ionescu, Rota, and N. Sebe, Curriculum learning: A survey. International Journal of Computer Vision, pages 1-40, 2022. (cited on p. 19
[95] Y. Su, D. Han, Y. Zeng, and J. Xie. On the convergence analysis of the greedy randomized kaczmarz method. arXiv preprint arXiv:2307.00 01988, 2023. (cited on p. 6 10
[96] R.-Y. Sun. Optimization for deep learning: An overview. Journal of the Operations Research Society of China, ((2):249-294, 2020. (cited on p. 8.
[97] S. Swaroop, C. V. Nguyen, T. D. Bui, and R. E. Turner. Improving and understanding variational continual learning. arXiv preprint arXiv: 09099, 2019. (cited on p. 10)
[98] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2818 18882886, 2016. (cited on 25)
[99] G. M. Van de Ven, T. Tuytelaars, and A. S. Tolias. Three types of incremental learning. Nature Machine Intelligence, 4(12): 2022. (cited on p. 10)
16

---

[100] J. T. Wang, T. Wu, D. Song, P. Mittal, and R. Jia. GREATS: Online selection of high-qualig, data for LLM training every iteration. The Thirty-Eighth Annual Conference on Neural Information Processing Systems, 2024. (cited on 19
[101] X. Wang, Y. Chen, and W. Zhu. A survey curriculum learning. JEEE transactions pattern analysis and machine intelligence, 44(9):4555 4576, 2021. (cited on p. 10 19
[102] A.-Q. Xiao, J.-F. Yin, and N. Zheng. On fast greedy block kaczmarz methods for solving large consistent linear systems. Computational and Applied Mathematics, 42(3):119, 2023. (cited
on p. 6
[103] Y. Xu and B. Mirzasoleiman. arXiv:2306. 15848, 2023. (cited on p. 19
Ordering for non-replacement sgd.
arXiv preprint
[104] 7. Yang and H. Li. Task ordering matters for incremental learning. In 2021 International Symposium on Networks, Computers and Communications (ISNCC), pages 1 1-6, 2021. (cited on p. 10
[105] Y. Zeng, D. Han, Y. Su, and J. Xie. Fast stochastic dual coordinate descent algorithms for linearly constrained convex optimization. arXiv preprint drXIv:2307.16702, 2023. (cited on p. 1.
[106] J. Zhang, Y. Wang, and J. Zhao. On maximum residual nonlinear kaczmarz-type algorithms for large nonlinear systems of equations. Journal of Computational and Applied Mathematics, 425:1 15065, 2023. (cited on 5 TOp
[107] J.-J. Zhang. A new greedy kaczmarz algorithm for the solution of very large linear systems. Applied Mathematics Letters, 91:207-212, 2019. (cited on p.
T0P
[108] Y. Zhang and H. Li. Greedy motzkin-kaczmarz methods for solving linear systems. Numerical Linear Algebra with Applications, 29(4):2242, 2022. (cited on 6
[109] X. Zhao, H. Wang, W. Huang, and W. Lin. A statistical theory of regularization- continual learning. In Forty-first International Conference on Machine Learning, 2024. (cited on p. 3
17

---

Appendix contents
Further related work
19
Appendix to Section 4.1: Regression experiments
21
B.1
Isotropic data
B.2
Anisotropic data
22
B.3
on statistical significance
24
Appendix to Section 4.1: Classification experiments
25
C.1
Code
25
C.2
Experiment details
25
C.3
Out-of-domain feature extractors
26
C.4
Regularization ablation study
27
C.5
Allowing task repetition
27
C.6
Rule calculation with partial data
Appendix to Section 4.2: Proofs for "nearly determined" t..k............................
D.1
Optimality guarantee when r
D.2
Loss bound when r d
30
E
Appendix to Section 5.1: Lower bound's "adversarial" constructions
31
E.1
General dimension construction and proof (Theorem 5.2)
E.2
Adversarial 3d construction (Example 5.1)
36
Appendix to Section 5.2: Single-pass vs. repetition
40
F.1
Appendix to the upper bound for greedy orderings with repetition (Theorem 5.3)
40
F.2
Regression experiments single-pass vs. repetition
48
Appendix to Section 5.3: Hybrid task ordering
50
G.1
Hybrid ordering scheme
50
G.2
Hybrid ordering upper bound
51
G.3
Hybrid ordering experiments
H
Appendix to Section 4.1: Code snippet for regression experiments
55
Lower bound technical appendix: Delta positivity proof
59
I.1
Proof outline
59
1.2
Auxiliary: Algebraic inequalities
59
1.3
Proof body
61
I.4
Conclusion
79
J
Lower bound technical appendix: Properties of the recursive construction
J.1
Proof outline
81
J.2
Full proof
83
NeurIPS Paper Checklist
96
18

---

A Further related work
Here, we elaborate on additional connections not fully addressed in Section
Alternative viewpoint: The Kaczmarz method. Our continual linear regression scheme maps
directly to the Kaczmarz method [2 32 classical iterative projection algorithm for solving linear systems of equations. In our context, the solved system is, Xw y, where
Y1
NRd y
ER.
where N
Rem-
VT
m=1
Evron et al. [3] pointed out that Kaczmarz methods iteratively solve the "block" systems of the form ( w (e)))) using an update rule equivalent to our continual update in Eq. (i) As a result, the observations and results in our paper extend naturally the greedy Kaczmarz method. However, whereas Kaczmarz studies typically analyze convergence in terms of the distance to the intersection W., we focus on the loss, i.e., the residuals (Definitions 2.3 and 2.3 respectively). For example, in the r r= = d- case of Section 4.2 this distinction allowed proving an upper bound on the loss and an " "approximation" result on the optimal distance (Lemmas and 4.1 respectively).
is worth noting that, via its connection to the Kaczmarz method, our continual linear regression scheme is also related to coordinate descent methods [82]. While prior work in this area shows that greedy selection can outperform random sampling, these results often rely on strong convexity assumptions [74 [3), and typically apply to the Kaczmarz method through primal-dual lens again, yielding only convergence to the intersection point w..
33 105
Curriculum learning. Broadly, curriculum learning enhances training by controlling the order in which data are presented, to accelerate convergence or improve accuracy. The prevailing view is that examples should be ordered from easy hard by their "difficulty" [101 94). In contrast, we study similarity-guider orderings, aligning with recent findings in continual learning [14 46).
A key distinction between curriculum and continual learning lies in the unit of ordering: while curriculum learning typically orders individual samples or batches, we focus on orderings of entire tasks. Moreover, curriculum learning often takes single gradient step per sample, whereas continual learning optimizes each task to a low loss before proceeding. Nonetheless, given the maturity of curriculum learning and the interdisciplinary nature of our work, some curriculum studies that operate at the task level are directly relevant [e.g., [7] and were discussed in Section 6
Example selection in SGD. Evron al. 35 show that learning entire (continual) linear regression task in our Scheme reduces to taking a single large gradient step on a modified objective. While they use this reduction analyze random orderings via iast-iterate SGD analysis, we leverage it here to draw connections between greedy task orderings and greedy example selection in SGD.
Most of the example selection literature considers multi-epoch settings, where each sample is seen multiple times. In such regimes, it common to randomly shuffle the dataset once or at the start of each epoch [e.g.. 69 42 but this is not necessarily optimal [80]. For instance, Lu et al. [64] show that greedy permutations connutatiooss-omppteed at the beginning of each epoch-can yield faster convergence than random ones. However, their analysis requires (1) multiple epochs and (2) very small step sizes, making it inapplicable to our single-pass continual setting.
Das et al. 24 show that a selection rule akin to our maximum residual rule (Definition 3 accelerates early convergence but may underperform random orderings asymptotically cemptooicallyy-llininng with our findings on the hybrid approach in Section 5.3 They also analyze an approximate rule, supporting our observations on computational tractability Section 3 Others select greedily by gradient magnitude instead of loss [103], or "mine" examples at the mini-batch level selecting "hard" samples with
high loss or ones that lead to a significant decrease loss 93 100
Active Learning. Active learning aims to reduce labeling cost by querying the most informative samples for labeling, typically from large unlabeled pool. This setting resembles ours, where the learner may apply greedy maximum distance rule (Definition 3.1) to select the task or sample expected to induce the greatest model update. For example, related idea explored in Cai et al. 188, who propose greedy maximum distance variant for regression. Since labels are unknown
19

---

at selection time in their active learning setup, they approximate the expected model change using bootstrap method. Empirically. this approach identifies informative examples and consistently improves generalization across datasets.
20

---

B Appendix to Section 4.1: Regression experiments
All figures report averages over 10 runs. In each run, we randomly sample task collection to evaluate the different ordering strategies. Shaded regions (see App.
F.2 and G.3) indicate =1 standard
error intervals, even when not visually discemible.. App. B.3 we further discuss the statistical significance of our experiments.
Computational resources. All regression experiments ieses-inccliiiig those shown were com- pleted within 4 hours on home PC equipped with an Intel 15-9400F CPU and 16GB of RAM.
B.1 Isotropic data
Figures and 9 extend the previous experiment isotropic data (Figure 3a to varying dimensions ranks r and task counts T' Results confirm consistent patterns: greedy (dissimilarity maximizing) methods outperform random, and MD better than MR across all settings (sometimes only slightly).
d=20, r/d=0.1
d=20, r/d=
d=20, r/d=0.9
10
10
10
10-2
10-1
10-9
Lo55
10
10-11
10-13
10
11
10-10
10
10-4
-2
10-29
20
30
50
20
30
50
10
20
40
50
d==0,
r/d=0.1
d=60,
r/d=0.5
d=60,
r//=0.9
10-1
10
10-1
10-9
Los5
10-13
10
10
10
10-25
10-21
10-20
30
20
50
40
d=100, r/d=0.1 0.1
d=100,
r/d= 0.5
d=100, r/d 00.9
10
10-1
10-3
10
10-1.
10-0
Loss
10-3
11.
10
10-15
Greedy Min. Dist.
10-18
Random
10-23
10-23
Greedy
10-5
24
Greedy
78
0
20
30
40
50
10
30 Seen tasks
20
40
50
10
20
40
50
Seen tasks
Seen tasks
Figure 8: Comparing orderings for varying dimensions d and ranks r of the data matrices, for isotropic data. T' 50. We observe that, for such isotropic data, the random ordering performance determined solely by the ratio r/d. In contrast, greedy orderings that prioritize dissimilarity benefit from lower dimension when r/d is fixed (to see that, focus on single columns in the grid). We hypothesize that this because an increased task "density" in lower dimensions: when r is fixed, increasing d increases d - r, expanding the set of possible task projections (see Eq. ) As result, fixed number of tasks T covers this space more sparsely in higher dimensions. lower dimensions, the same 7 tasks yield denser coverage, increasing the likelihood that greedy dissimilarity-basee selection identifies tasks with large projections.
In all strategies, higher task rank consistently yields improved performance (focus on single rows). This is because the solution subspaces are of rank r, so increasing (with fixed d) lowers the subspace rank, increasing the distances between them and resulting in larger projections.
21

---

T=50
T=100
T=500
10:4
10
0 10
Greedy
10-4
Random
Greedy MR
10-1
Greedy MD
10-
0
30 Seen tasks
20
40
50
10
20
30
40
50
10 20
30
40
Seen tasks
Seen tasks
Figure 9: Comparing orderings for varying task count T, for isotropic data. d = 100, r= 10. Dissimilarity-bann -aseed greedy strategies become more effective as the number tasks increases. This is since in isotropic setting, where task directions tasks increases coverage of unit sphere. This results a higher probability of encountering task pairs with large angular separation between their solution subspaces, which greedy ordering utilizes.
sampled uniformly, increasing the number of
B.2 Anisotropic data
The following experiments were were performed with anisotropic data, sampled from a Gaussian distribution with exponentially decaying eigenvalues, detailed in Scheme 2 resulting in high task correlation. This arises because tasks tend to align with the dominant eigen- leading to strong pairwise similarity.
Scheme Generating tasks with high correlation
Require: Input dimension task rank r. number tasks T, edge eigenvalues \₁ = 10-3 3 Ad = 10 1: Sample A (N, 1)axd and symmetrize: Asym <- 2 (A A
2: Compute SVD: Asy USUT
3: Define diagonal spectrum: A < diag exp (In A1) ---7 1=
4: Construct covariance: +- UAUT
5: for t = to 7 do
6: Sample Z; N (0, 1)mxd
7: Set X, 2//1
8: end for
9: Output: ( 1
Figures 10 and 11
below reveal some interesting trends compared to the isotropic case.
22

---

d=20, r/d=0.1
d=20. m05
d= r/d=0.9
10"
10
10-2
10a2
10:4
10
10
10
Loss
10
10
10-1
10"5
10-21
10
10-*
10-2
10
30
40
50
10
20
30
40
50
10
20
30
40
50
d=60,
r/d=0.1 0.1
d=
r/d=0.5
d=60,
r/d=0.9
10"1
10-1
10
10
10-
Lo55
10
10"3
10-11
10-4
10
10-5
10
10
10-24
10
30
40
20
50
10
30
40
d=100,
r/d=0.1
d=100, r/d=0.5
d=100,
r/d=0.9
10a4
10-1
Greedy Min. Dist.
10
10-1
Random
10-1
Greedy MR
Loss
Greedy
10-1
10
10-1
10
10
10-2
10"5
10
20
50
10
40
Seen tasks
Seen tasks
Seen tasks
Figure 10: Comparing orderings for varying dimensions d and ranks of the data matrices, for anisotropic data. T 50. Compared to the isotropic case (Figure (8), we observe slower rates for all strategies. This easily explained by all pairwise distances between task solution subspaces becoming smaller, due to the higher correlation in the anisotropic case.
Interestingly, as rank increases (focusing on a single row the grid), the Maximum Residual (MR: Definition 3.2) ordering underperforms and seemingly aligns with the random This may stem from the combination of high rank and strong intra-task correlation, which leads to ill-conditioned data matrices (for each task). In such case, small perturbations, steps, in the solution space may cause disproportionately large changes residuals. As result, MR is misled into selecting tasks with large residuals that advance the iterate only marginally toward the intersection (w.).
T=50
T 1000
T=500
Greedy Min. Dist.
Random
Greedy MR
Loss
Greedy MD
10
20
30
40
50
50
Seen tasks
Seen tasks
Seen tasks
Figure 11: Comparing orderings for varying task count T,, for anisotropic data. d 100, 10. Unlike in the isotropic case (Figure greedy orderings do not significantly benefit from increasing the number of tasks T. This likely since, in the anisotropic case, a large number of tasks must be added to induce the substantial "angles" that greedy orderings can exploit. Put differently, under our anisotropic distribution, the probability that any of 50 tasks are mutually orthogonal and thus beneficial to greedy orderings is extremely small for any reasonable number of tasks T.
23

---

B.3 A note on statistical significance
All appendix figures include confidence intervals of =1 standard error, although these are often too narrow to be visible. While different task collections introduce slight variations in outcomes, the overall trends are highly consistent. This is illustrated the following figure, where we replicate the plot from Figure 3a overlaying individual runs from all 10 repeated experiments. Despite some run-to-run variability, the standard error remains small, reinforcing the robustness of our qualitative conclusions.
10-2
Loss
10-3
Greedy Min. Dist.
Random
10
Greedy MR
Greedy MD
10 5
10
20 Seen tasks
50
Figure Showing variations across different experiments. Same as Figure 3a we have T = 50, r 10, d = 100, with random isotropic data. Shaded plots represent each individual experiment. While minor variations exist across experiments, the low standard error confirms the consistency of the results.
24

---

C
Appendix to Section 4.1:
Classification experiments
C.1
Code
The code for the classification experiments with CIFAR-100 available at htttps://gittub....... com/ matants//geeedy_oree ordering
Computational resources. All classification experiments were completed within a month's work on 4 NVIDIA GeForce GTX 1080 Ti GPUs.
C.2 Experiment details
C.2.1 Model: Linear probing on pretrained ResNet-20
Our experiments employ frozen pretrained ResNet-20 classifier 45 where the final classification
head was removed and replaced with the binary classification head that we train 30
C.2.2 Tasks and benchmarks
We employ three benchmarks of domain innemmnnnnremettlll CIFAR- binary classification:
(A) Using a model pretrained on CIFAR- 110AR-100 [55], taken from Chen 22 which achieves 68.83%
top-1 classification accuracy CIFAR- 100 multiclass classification according to Chen [22]. The continual learning tasks are composed of CIFAR-100 classes randomly split to 50 pairs of binary classification tasks, such that all classes from the same superclass share label. This is the setting used in all experiments unless stated otherwise, including the results presented in Figure 3h
(B)
We partition the 500 training samples each CIFAR-100 class to two distinct groups of 250 samples, and use of the groups train the ResNet-20 embedder on the original CIFAR-100 multiclass task, using the same training recipe as Chen [22] and achieving 61.57% top-1 classification accuracy the CIFAR-100 test set after 200 training epochs. The partitioning and training code included in our provided repository. We then employ linear probe on top of the resulting model (with the classification head removed), and construct the continual learning tasks using the 250 samples per class that weren's used for training the embedder. The classes that compose each task are the same in the previous benchmarks.
(C) Using model pretrained on CIFAR- 10, taken from Chen 22 with the same CIFAR-100-ban tasks as (A).
All presented results were composed by experimenting with 25 randomly generated task sets.
C.2.3 Training
Training was performed with cross-entropy loss on the softmax of the classifier's output with label smoothing of 0.05 1981, with additive L2 regularization towards the previous parameters controlled by the hyperparameter X, which is common in continual learning and is necessary to facilitate the
projections view, as shown in Evron et al. 34] In Figure 3bl X 5. and present ablation study
for À in App. C.4 to address how it affects the performance different ordering rules.
For each task we used the SGD optimizer with learning rate of ir = 0.01 and MaatteeeROOnPPaatann on epoch losses, trained for 40 epochs with a batch size of 64. baseline, we jointly trained classifier all tasks together, without regularization.
C.2.4 Evaluation
We evaluate the performance of each ordering by calculating the average test (generalization) loss of all tasks after each seen task. Results are presented with 95% confidence intervals, calculated over the different randomly generated task sets, and over the permutations well for random ordering.
25

---

C.2.5 Ordering computation
For the Random rule (Eq. (.) we use random sampling without replacement from the task set, unless stated otherwise. When presenting results for it, we use 4 random task permutations per task set. The Greedy MR rule (Definition 3.2) requires calculating the loss (without regularization) of all tasks after each task training, and choosing the task with the maximal loss. In App. C.6 we show its performance doesn't degrade when the losses are evaluated as 1 of the data-5 samples per class in CIFAR-100. The Greedy MD rule (Definition 3.1 was calculated by performing full training each task, as elaborated above (App. CC..3) choosing the task that resulted in model parameters farthest from the current model parameters in terms of Euclidean distance. While the MD rule may seem impractical-we show that, in fact, the much simpler Greedy MR rule, that requires a single forward pass, achieves identical performance.
fraction of the dataset, as small
C.3 Out-of-domain feature extractors
To evaluate how our proposed method extends to more general transfer learning settings, we employ multiple benchmarks elaborated in App. C.2.2
70
(A) Figure 3a is the same figure Fig-
Test accuracy (%)
Joint
ure shown here for completeness.
65
Greedy
Greedy MR
Random
55
10
30
Seen tasks
(a) Pretraining: Full CIFAR-100; Continual learning: Full CIFAR-100.
(B)
As shown in Figure 13b this transfer- learning setting behaves similarly to the case where tasks drawn from the training data (Figure (3)), though with
65
Joint
Test accuracy
Greedy
Greedy MR
60
Random
slightly weaker performance for both the joint baseline and all orderings.
50
20 Seen tasks
50
(b) Pretraining: Partitioned CIFAR-1000 Continual lear-
ing: Remaining CIFAR-100
(C)
As shown Figure 13c dissimilarity- guided orderings still outperform ran- dom orderings, though less prominently than in other experiments. We hypoth-
58
Joint
Test accuracy
56
Greedy MD
Greedy MR
54
Random
esize that this stems from the model's 's weak joint interpolation ability (indi- cated by the dashed curve), which more strongly violates joint-realizability assumption (Assumption 2.1)
52
50
20
50
Seen tasks
(c) Pretraining:
CIFAR-100 10;
Continual
lcarning:
CIFAR-100.
Figure 13: Comparison of orderings under different pretraining setups.
26

---

C.4 Regularization ablation study
Regularization toward previous model parameters is a standard method mitigate catastrophic forgetting [53] (5), and is crucial for a projections view to emerge in continual classification [34]. Because of its central role, we perform an ablation study on the effect of regularization strength for completeness. As shown in Figure 14] without regularization our continual learning scheme collapses across orderings, and greedy methods consistently outperform random ordering across all strengths examined. Interestingly, the optimal performance for greedy orderings occurs at smaller regularization strengths (A) than for random ordering. This makes sense: greedy methods deliberately select tasks that push parameters further from their current values, so the regularization term has stronger influence on the loss, requiring smaller for optimal effect.
Test accuracy (%)
62.5
60.0
57.5
Greedy MD
55.0
Greedy MR Random
52.5
10
20
30
40
50
Figure 14: Regularization strength ablation study.
C,5 Allowing task repetition
As discussed in Section 5.2 in continual linear regression, allowing repetitions helps greedy orderings avoid failure modes and guarantees provable convergence. In our classification experiments, however, repetitions do not improve performance: as shown in Figure 15] where each scheme could select from all tasks for 100 iterations (instead of 50), repetitions actually harm the performance of greedy orderings, effectively canceling their advantage over random orderings. We observe similar phenomenon in linear regression with anisotropic low-rank data, as detailed in App. F2
In the classification case, which departs substantially from jointly realizable linear regression, multiple factors could underlie this behavior. It would be interesting to examine how this relates to the connection between greedy ordering and "periphery-to-cont when repetitions are allowed, or to the distance-to-ten to-tccher perspective explored in App. F2 (Figure) As this lies beyond the scope of our paper, we leave it for future work.
ordering [62]. which may break down
70
Test accuracy (%))
Joint
65
Greedy single pass
Greedy MR, single pass
60
Random, without replacement
Random, with replacement
Greedy MD, with repetition
55
Greedy MR, with repetition
50
0
20
40
80
100
Iterations (seen tasks incl. repetitions)
Figure 15: The effect of task repetition on 100 continual classification.
27

---

C.6 Rule calculation with partial data
To assess practicality, we evaluate the more efficient Greedy MR method which requires only forward passes uuiinggguiingg fractions of the data and compute. Even with just 1% of the data (5 samples per CIFAR-100 class, ie., 10 per binary task) to compute each task's 's loss, Greedy MR maintains its performance and remains stronger than random ordering.
65
Test accuracy (%)
60
MR All data
55
MR 10%
MR 1%
Random
50
0
10
20
30
40
50
Seen tasks
Figure 16: Greedy MR rule calculation using partial data.
28

---

D Appendix to Section 4.2: Proofs for "nearly determined" tasks
D.1 Optimality guarantee when d
Recall Lemma 4.1 Let wT and w the iterates after learning 7 jointly realizable tasks of rank d - under the Maximum Distance ordering 7MD and optimal ordering that leads to minimal distance to the joint solution W.. Then, their distances hold,
[TT
w.ll
[w w. & (( S 1.
0 s D2(())) S D2
(w (ua)
W. 1
[.
Proof. The distance at the end of an ordering is
D2 (WF)
|W w.ll
Ve(TT .. --())) (wo - w')l'
w. 1
|w+ll
|w, (Yra) (wo (wo- w II
(vT (vToo=a=)))
t=1
Let 7 TMD; be the greedy MD ordering and an optimal ordering leading to the minimal distance
(respectively). Denote for simplicity e c(i.j) = || (vJ (wo -w.))² i i= E [T]
(v.Tv,)
i E [T]
Then, have,
T-1
D² (wF)) = ||w=|1 (T.. (wo ww.) -w.))
II
v
T-1
=c(0, (1))
II
c(T... (T), (t 1))
1=1
=0 T. (1))
II
(T (T. (f))) To (t (t+1))
c (t), (t), (Tx
LEC
Iec
where we define the index set C { 15555
- - (T (T) < r (t++
Employing greediness, we get
2
(7- (Tx (1)) - +1+ (Tx (1)))
IEC
bere, (r. (1)
II (o(TT(1 (T. (t+ 1))) (7 (Tx (1 111) EEc
here, (t+())))
Then, since 7- (T. (.)) "covers" [T] and e (i.j) S 1, iterating over the entire I....,T T simply add elements to the product and make smaller. That is,
will
T-1
T-1
D2 (w 2 (0, (1)) II (() 0) II (()(L))))=
T-1 c(T (1+
2
c(0 (1))
2 T-1
Vi( (oo vrrcai))) = =(D² (w7)))
||w.|1 2 (Vr(1) (wo w.)
II [=1
+ 12D((7)) > 2 (w ) > 2² (w:t) ) > 0.
29

---

D.2 Loss bound when r = d-1
Recall Lemma 4.2 Under the Maximum Distance greedy ordering over T jointly- tasks of rank d 1, the loss of Scheme ① after T iterations is upper bounded as,
T
[(Wr) w. FRE
x WT ymll
T
eT
Proof. We aim to bound the average loss using projection matrices,
Lino (WT) Tw. TTT
WT ymll lw.. 1| 1
X (WT - w.) 11?
m=l
T
X X m
Xm (WT w.) 12
w. TT
m=l
X
(WT w.) 1
[w.
RTT
m=
P (())
P (wo (wo-
w.
Since each task matrix X, has rank d - 1, each projection P, is rank and can written as P. v.v. for unit vector v,. Substituting this and Vr(0) w.
1 (wo- w.). the bound becomes:
T
LO (WT) < T
((1)
T
v (a(
V=(
vow vim
II
v (i(et))V>())
1 Σ 1 (1-7
VT (TT VT()) )² II s=1
T-1
[projection properties]
Then, algebraic and projection properties to rewrite the greedy ordering
(MD
argmax
|[ - (I-Pm) (w:-1
-w
argmax [|W w.1l2- |P (w.-1 w.)l
argmin
Pmm (w,-1- (w.11-
me(TT)
argmnin m
Vm v V=((-1) Vr((-1)
argmin m
(v ()())))))
(6)
Then, employing greediness as reformulated above and incquality of arithmetic and geometric mean, we obtain:
T-1
II (VTooHD)-())
2 < II (vTan))c)) <
T
T Σ
T
(V
)(s)))))))))
am1
Substituting back into the forgetting, it is now bounded as,
| 1 1 (vio
1
Com (wT)
T Σ
eT
s=1
where we invoked an algebraic property that (1 - 2)xx <
1
Vx E [0.
ET
30

---

E Appendix to Section 5.1: Lower bound's "adversarial" constructions
E.1 General dimension construction and proof (Theorem 5.2
Recall Theorem 5.2 For any d 2 30, there exists adversarial task collection with I = d - 1 jointlyreelizable tasks of different rank such that both greedy orderings (MD, MR) forget catastroph- ically. That is, the loss the end of the sequence is, L(wT [(w77M))
1
4d
Proof outline. For given dimension d, we construct sequence of d iterates (w.))=1- correspond- tasks (X,) of decreasing rank, which are jointly-realizable with w. (i.e., Vt E {2...T). y: = 0), and show that:
ing T
1. Bottom line. Given this specific choice of tasks and matching iterates, the loss (or forgetting) is catastrophic mentioned in the theorem.
2. The chosen iterates valid-i.e. they can be obtained from specific selection rule given the constructed task collection.
3. The chosen ordering adheres to greedy selection rules, both MD and MR, under the chosen tasks. This part is quite lengthy.
In the construction, we start the iterates from / = 1 and tasks from / 2, contrary to other parts of the paper, for no particular reason other than ease notation. For this same reason we chose w. = O, e1. The same construction holds for shifted frame of reference
and the iterates starting with where all iterates (and w.) are shifted by -e1-
E.1.1 Construction details
We first construct the iterates as follows:
W1 = c1
=
1. 0
d times
(wi-1); + v (w
-
-43;
2-2 1
V E (2...d] Wt
d-2
0, ...,0.00
2
vd
vd
t- 1 times
where c - 2-1/d and Be ((-1))-((-2)))2
We denote Iz A (W:),. defined recursively by
Tt + v 1 48g
It
Vt E {2..d)
2
Since w. * W,-1, we are free define the unit vector
W. W,-1
u,
E span (e)......
w. w.
We now construct the tasks:
X;
1++
u
p (dd+++1ixd Vt (2...d.
L+id
Then, is easy to see that P, A I
XtX, = I.41dd insu u.u.
31

---

E.1.2 Lower bounding the loss
For each task Xms its individual loss at time t d is given by:
fm (wa) - m wall?
11 m
T
2
wa)² 2 + [m
Wd
Im+1id
2 I Imal:
(wa)²
j=m-1 1
2d
1 2 2 (d m)
(1 - d
m71
2dd4
(1
m (2d-2)/4 43/d
d
1 1 d
24/d
d
So the average loss after all iterates, which coincides with the forgetting (see Remark 2.4 is:
d Lm (Wa)
L ((w))
Σ
Lm (Wa)
T
d
mc (2...)
m 2
2
4(d
1)
1
Σ
d
1
m
d
=
(dd - 1)
d
Σm= m
d
m=
d 2
4 8d
4d
E.1.3 Proving that the iterates and tasks exist
In Lemma J.I we prove that for all d 30, .2...., d). we have x²-1 43, 2 so the square root in the recursive definition of x, (Eq. 7 exists.
E.1.4 Proving that the iterates can be formed from projections of the given tasks
As sanity check, we notice that P. is real symmetric matrix, and assert its idempotence,
P² (I, uuu ))² = I uuu I, - Iuuu + u.u. u I u.u. u.u. + u.u. I, -.u, = P..
First, we show that w (w, - wi-1) = 0. as expected from orthogonality in projections:
w, (w: w.-1)= =
(w:)?
wi), (w,-1), = =(w:)² +
(w:)?
(wx); (w--1);
1=1 1=1
2=
2014
2-200-3
=(w1) 3 - (Wa)1 (w/-1); +
i=2
(t - 1) 2t
(t - 2) 2-
(wr) (w:), (wi-1)1
= =(wi) - (wi), (w,-1),+ + ((t - 1) (t 2)) 20
d
=bt
=(w)) (w:)2 (w,-1), + Be,
and it is readily seen that our construction choice of (Wr), (we-1) / (w:-) -4,
implies
2
w T (w, W.-1) 0.
32

---

Finally, we show that the iterates are indeed sequence the corresponding projections:
P,W-11 = (I, u.u.)
Wt-1 I.
iui Wt-1
(W; w:-1)
(w, w:-1) Wx-1 (wr - -
W
Wt-1
11 Wi-1
|w - wil
|wo we-1ll
We w(-1) W:-1 W Wi-1) Wi
W
|/w, Wz-1 |
(wr - wi-1)
Wi-1 (Wr W
(W, -W-1) (We W1-1)
W; W
W + (Wr W.-1) Wt.
E.1.5 Proving that the iterates adhere to greedy ordering rules
Maximum Distance (MD). We wish to prove that the greedy MD rule agrees with the ordering we chose. That is, A v - -P) Pe)):=1l2=
By induction on the validity of the greediness for 72, 72,...,7 T1-1, the step is (and the induction base for | 2 is shown exactly the same):
1) ||[I - Ptt) w.-1l? [ Pr) wr-1l 2
induction assumption] = argmaxye(t.....7
[Ia - I + u. w,-1 1|
argmaxye (t...... T)
It' > t - 1] argmax/e
(L= + ur up w:-1
| 1 argmaxy'e(t...." (t......
(n (u=)==
(ww--w-1)
ert.a
||w-- - Wi-1
Maximum Residual (MR). We wish to prove that the greedy MR rule agrees with the ordering we chose. That is,
Te A argmaxyeeTTNt......111 / ||
By induction the validity of the greediness for 72,-..; T1-1, the step is (and the induction base for t = 2 is shown exactly the same):
Tr e argmax, (MTT 1) [
||[
-u
2
Finduction ussumption]
argmax, (((.....TT [ argmax, (t.....
W
Ie41d
F'' > t 1-11 argmax r TT
11 W: 11=) 1²²² [ettawi-T11
2
(we' (wa-- - wr- wr- - W+-1
argmax X ((tt....)
We get that the MR and MD rules coincide in this case.
33

---

How we prove greediness holds: Delta positivity. We wish to show monotonous decrease (w.I.t
2 of (ww, 1 (-wa) w. 1) .)²²
which will prove that the iterates we defined are valid under the
Iwa-1-wa greedy MD and MR orderings (i.e., adhere the rules in Def. 3.1 and 3.2
The difference between consecutive iterates
Wk-1 W/: Ik-1 Tb. ck (1
(1 c)
2-2
0,
0
vd
vd
k 2 times
We notice that wk 2 t the term (Wk-1 wk)
W is positive since,
TR) x1 + (t 2) k- (1 c) c¹
(Wk-1 wx) Wi-1 (IK-1
0.
Vd vd
20, From
L6
>0
This means that we can alternatively show monotonous decrease Vk 2 for
(WI-1- - -w)) (N W
well
To this end, we wish show that the next quantity positive Vi .2....,d-1 (we are reminded that the first step is at t = 2 due to our choice, and that at the last step there is only one choice), wk E (t.....d d 1}:
(Wa-1 wh)) Wi-1 (W: wk+1) Wi-1
|| W
|W Wx+1/l
x [W We+1/l (Wk-1- - wx) W -| (wx WW+1) W & A..
Next, we will show this holds numerically for low dimensions (d 25,000), and prove it analytically Ad 2 25,000.
Showing delta positivity numerically for low dimensions. We use the following facts write code that verifies Ar, >> 0 Vd < 25,000, Vt E ( 1}, vk E (t....,d 1}:
ck- (1 -c) c)
ct-3
[ - = (ox-1 - =²)²² + (k - 2)
+
Vd
vd
( =2x)² k - 2
1
2k-6 - -c)²
222000
d
d
ck- (1 - c) cl-
(Wk-1 - wk) W.-1 = (x 1x)
x4-1 + (t - 2)
vd Vd
For each value of dimension d, we calculated the sequence (4), using its recursive definition, and calculated (dd - min. AE(t...... 4r, using these formulas. As shown in Figure I7 we found A(d) remains positive for all d E 730...47,000) (for completeness, any dimension above 25,000 is redundant here). In addition, will be seen analytically (Eq. (13)). we
have that (d) should correlate with d d²,, and for completeness we show this holds numerically for the lower dimensions as well, by showing A(d) d2 is approximately constant.
Computational resources. This numerical validation took days to run on a home PC with i5-9400F CPU and 16GB RAM.
34

---

0.1100
10
0.1075
A(d) d
10-4
0.1050
0.1025
10
0.1000
10-14
0.0975
10
10
10
102
10
10a
d
(a) (d) Positivity
(b) Correlation with d
Figure 17: Numerical positivity of (d) A min tE (2..... 1), KE (e 13] De.k
Showing delta positivity analytically for high dimensions. Due to the length of this part, defer it to App. where we prove that Vd 2 25,000, VI E 1 d - 1}, Ak E {l,..., d 1},
L
|W Wi+1ll (Wx-1- w&) w || W (w& Wa+1) Wi-1 0.
Conclusion. Together with the numerical verification, we have established that Ar,: > 0 for all 2 f. and all 30. This completes the proof of the iterates' adherence the greedy ordering rules, and thereby concludes the overall proof of the adversarial construction that yields a lower bound on the loss under single-pass greedy orderings.
35

---

E.2
Adversarial 3d construction (Example 5.1
Recall Example 5.1 For all T {4. 10 - 1.2.... 77. there exists a task collection of jointly-relizable tasks in d 3, such that L(wTp ((
) 2.78 10-5.
E.2.1
Construction details
For simplicity employ the joint solution w. 0, which means that for all tasks E [T], Ym 0. For some K E N+, we construct = 4K 1 tasks by defining their solution subspaces as follows:
K copies of Span ((0,sin VK cos
(vR)
K copies of Span
((0,-sin sin
VK! ) Co8
0, 1/2 ) (vR)
copies of Span (0o,sin 22K cos (22)) )
[
v2
. K copies of Span
(0, (0,-sin
COs
(
0, v2
2
For given solution subspace of rank d r, task feature matrix X E Rrxd of rank r (i.e, with linearly independent rows) is defined such that each row of X is orthogonal to the solution subspace.
We initialize Wa
(0. sin (vRR cos (vR))
E.2.2 Lower bound explanation
This is not a formal proof, but explanation of why the construction works. We stick using greedy MD for the intuition.
While learning tasks consecutively using greedy MD ordering, we start by alternating be- tween projecting onto the 1-D subspaces, since each 2-D subspace contains a line (either Span (0.- (2 cos 1 ))) between them and
Span (0. sin ) (2 hence cannot be the farthest away. Once those are used up, we' re left with the 2-D subspaces, which we alternate between.
Morally, the angle between the 1-D subspaces is O
so K grows large, these first 2K 1 VK
steps should bring us about (0, 0, (()). The 2-D subspaces intersect in Span (( V22 v2
and the angle between them is also θ
so they move us constant fraction of the way toward
VK
which (e(1), o, 0(1)). Since the first half of the tasks are projections onto 1-D subspaces near (0, 0, 1). the z-coordinate contributes @(1) loss due to these tasks.
the closest point on Span ( 0, 1
v2
Quantifying the asymptotic loss. time, giving
the first 2K- steps we multiply ||w|| by cos(2/VK)) KK) each
2K-1 =11-2/K + +(K 2) = o(1).
COS (2/VK)
The direction (0. sin (I/VK), cos (1/VK)). so we end at (0, o(1), o(1))
Next we project onto a 2-D subspace; this is (11) movement, so w becomes
((),), o()) (0.0,e o())
Let be the closest point on Span ( (11 0, +
to (0.0,e-t) + o(). Then
== (e 122 0, /2) + (1,)0)
36

---

All remaining 2-D subspaces contain the line Span ((1z lines through v perpendicular to L.
J v2 ) so the projections are onto
The angle between these lines equals the angle between the planes. Let u be the closest point on Span(1,0, to (0, (1/vR), oos (1/VK)): then angle is
(2 o()) (1,0, Thus the plane
sin(1/(2VK)) 1/v2+ + o(1) (1 (1+)(1)) v2
2 tan
VK
Each of the remaining 2K projections multiplies dist(w, v) by cos + ( overall it is scaled by e-2 + o(1) Originally,
dist (00,0, (e (2-1/2,0, "'3 +o(1,
so afterwards distance = + o(1)
The direction from v is parallel to
(11) + (0,0,e - +/2,0, 2 = = o(1) ( = o(1) + (- 0, )
(1/
so the final position of Wr
(11) + (6 + ( + o(1)) (o(1) + (-1)))(12111)) ..))
= o(1) + (2 0, +/2 12 8/2).
Hence, the r-coordinate contributes the following approximate loss due to the first half the tasks:
1 1 (e e -2) 2 3.135 10 2
L (WT)
(8)
E.2.3 Experimental results
Constructing the tasks as explained in App. E.2 using QR decomposition to acquire X for each solution subspace, we observe that the task ord orderings for greedy MD (Definition 3.1 and greedy MR (Definition 3.2) coincide. as explained in App. E.2.2 for all T E {4 10 - observed in Figure 18a greedy ordering results in alternating between the first two task groups until these are depleted, then switching to the other two task groups. Loss is is diminishing in linear rate during learning the first half of the tasks, then increases the predicted value (Eq. (8) during learning the second half.
1.2..... 7] As
Chosen task index
10-1
MD, MR
Theory
3-
10
Loss
10-5
2-
10
500
1000
1500
2500 3000 3500 Seen tasks
2000
4000
1000
2000
3000
4000
Seen tasks
(a) Chosen task group under greedy ordering.
(b) Average loss during continual learning under greedy ordering.
Figure 18: Example of continual learning the 3d adversarial construction with greedy ordering. Chosen tasks coincide for MD and MR greedy orderings. K 1000, T = 3999.
37

---

In Figure 19
we show Example 5.1 holds, and the validity of the theoretical value (Eq.
Final Loss (x 1100
3.1
3.0
2.9
MD, MR
Theory
2.8
10
102
103
104 K
10s
106
107
Figure 19: Final average loss after greedy ordering for the 3d adversarial construction, for different task counts. T = 4K + 1.
38

---

E.2.4 Code for reproducibility
import numpy as np
2
def orth orth_compl ement [moeettrrowWW, *, rtol=le-12):
Given V in (dd(rr)xd) (full row rank), return X in & (rxd)
whose form orthonormal basis of the orthogonal comp lement of the row-space of #. ***
5
as.aaaary (M, dtype=float)
a W.ahape[1]
Full QR of N.r 4 is dxd and orthogonal The ferst rank colums of Q span the rows of the remasning colums span their orthogonal complement. mode=' completee)
9, np sinalg.qr((k Berlg..arrixx_aan (W, tol=rtol)
# Q in (dxd]
rank mp. ap.linalg.e
Take the last d rank colums of Q, transpose to get
x q[:, rank:].
# I in (rxd)
return
16
ORDERING 'MD' # 'MR'
'HD'
K 1000
np. array ([[O, up- np.sin sp.sin(1/np.sqq (K)) np cos(1/n/)))) (ptcos(t/p..qrtt (K)) ]]
sqrt
20
w2 mp. ar..rrry ([[o, -np (pppe(((....qrr(( (K)), up- cppccool//pp.ee. sqrt (K) }]])
w3 array
sin (in(0..5mp.eqrt(())
np. co.cos 5/mp. sqrt (K) )]
h//np..srrt()) 0, 1/np. (2)))
w4 np aarra([[[) spp.sin(.55 (g)) up. cos(0. 5/mp sqrt (K))],
- (g/),, 0, 1/mp.sgrt(2)1))
23
ws [w1, w2, w3, w4] tasks forth_complemett (ww for in ws]
projections [n).eye(3) np linalinlggg. pinv (X) for x in tasks] cotal_collection_comm
[K-1, K, ,K]
T mp. app.umttotaal.ccleeiio...comm collection_count count = col.ecciooccccoouttttt.......
28
w np aIray([o, np sim(1/np (k))t// np (1/pp/pp sqrt sqrt(K)))) (K))])
residual
niralg.norm(X hap.linalg mX @ w)++2 for X in tasks]
total_loss (1/T) np- asarray (residual.por__prjjccttolll
4 np. aasarrayytotal.... ctt.ocaall_ollletioooooooc
32
losses (total_loss)
for i in range(T):
chosen_tase None distance -np.int new_w, nex_x_candidate None, None
36
for task_index in ra)ge(4):
if collection_count [task_inden
if ORDERING 'MD':
40
new_w_candidat
projections [task_index] w
new nev_distance np.linalg norm (new @ee____canddddtt w) ++2
elif ORDERING = 'MR':
nev_distance np. np. appainalg. norm (taaks [task_inder] index] w)**2
if new_distance distance:
45
chosen_tass task task_index
distance new_distance
new_w new_w_candidate
if new_w None: new_w projections [chosen_tasee task] w new_w
collection_count [chosen_taskk -
seaddual_per_ppojeccte
Inp limalg (X 0 #)++2 for in tasks]
total_loss (1/T) np asarray (erreiddaalppr..ppjeeiiiol
+ np appaasaray (ow.aalllolllectoooncooooo count))
losses append(total_los:
Listing 1: Code for 3d adversarial construction.
39

---

Appendix to Section 5.2 Single-pass vs. repetition
F.1 Appendix to the upper bound for greedy orderings with repetition (Theorem 5.3
Recall Theorem 5.3 Under a Maximum Distance greedy ordering with repetition (TMD-R) over T jointly-realizale lasks, the loss of Scheme [ater iterations upper bounded as,
1 Vk
L [ T O
The main propositions leading to the proof of Theorem 5.3 are in App. F.1.2. with auxiliary claims in App. F.1.3 We use geometric analysis derive an upper bound on how fast iterates can grow, and then bound the iterates relative to the original distance to the teacher w,. Finally, we upper-bound the loss by the greedy iterate size when repetitions are allowed.
F1.1 Comparison to convergence rates of other task orderings
Table 1: Loss bounds continual linear regression over jointly realizable tasks (based on Table I Evron al. (35). The presented bounds are "worst case": upper bounds apply collection of I' jointly realizable tasks, while lower bounds achieved by specific constructions. Bounds for random orderings apply to the expected loss. We omit scaling terms [[]w.]] 2| H²))
and constant multiplicative factors (which are mild).
Notation:
iteration;; d dimensions; F, Tmax average/maximum data matrix ranks; o, a min(a, b).
Single-pass Greedy
Greedy with Repetition
Random w/o Replacement
Random with Replacement
Bound
Paper / Ordering
Evron
33
k
d-F
d TT
F
Evron et al. 35
VT
T
k
Upper
1
Attia et al. 10
VT
VE
1
Ours
None
VE
1
Evron et al. 33
(+)
T
T
Lower
Ours
2(1)
(+) Although Evron et al. [33] not state these lower bounds explicitly, their proof of Theorem provides 2-task construction which, when replicated [T/2] times, produces @(1/k) bound for both random and greedy orderings with any general 7'.
40

---

F.1.2 Deriving the bound
Proposition F.1. Let Wo, E Rd and let P: R2 + Bdd be an orthogonal projection, then
Wo Pw1l
11
Wo W1 1 II P) w1ll + -I w1 I[I woll
Proof. Let us denote
(I - P)wo: v _ (I-P)w1 Then u, ker(P) and are orthogonal Pwo, Pw1 im(P). respectively.
Now decompose:
Wo W =PWo Pw1) + (u v), Wo Pw1 = -Pwo - Pw1) +u.
Using orthogonality:
(wo- will2
[Ww Pwill + ||u vll?,
(9)
[Wo Pwil 2
PWo Pwil + -|lu]]
(10)
Subtracting Eq.
I0) from Eq.
we get
Wo W1
Wo
Pw 112 = | - vI |||| ||v]2
2u Tv v.
So.
WW Pw/ 1| = |W - w1ll - ||v| + +2 TuTv
[CuuchySSchwar)] S WW will -1((I ([[-PP)) ([W:)) 21 +
P)w1 || |I- [Iwol
Corollary E2. Consider the case in Eq. ② iee, (we) are iterates such that wo 0 and Vt [k]. (W; w.) = P P7(1) (W,-1 w.). then wk: 2,
|| wxll S l|wo will
|ws 1|
k
+ 2
w. - w ||ll|[[[1 P PT(0) (wo w.)ll
Proof. We repeatedly apply the above proposition:
|| Wo - wall? = |l(wo w.) - (wx - -w.)ll
||(wo- w.) -P (Wk-1 -w
< !l(wa ww)) (We-I-Wwi -I((I 1/1li=11(11 P P.(()) (WE-I- (w.-1-w.)ll
continue inductively
+ 2 (I - -P(()) - ([[[) (wo w.)ll
< |l(wo w.. - (WI--W. w.) Σ -I- (W-11-
2=2
+
- -1-P((() (w--1-w.)lll(( PT(0) (wo - w.)ll
2=
b: w - w +2 Σ
= =/woo w1 2
|w - w w--ill P+(0) (wo w.)
t=2
t=2
41

---

Corollary F.3. If the first step is MD greedy, i.e,, Vm E [T], II(T - Pmm) (wo w..ll - wo -wil then Vk 2,
Wo wxll llw will
W. 11- will Σ -
Proposition E4. Under greedy MD ordering, either single-pass or with repetition, we have Ak 2 1,
|| wkll 1 l|wo will 2/a
Proof. Notice that
|| wx |(W W.) P PT(++1) (Wk w+)
[orth. proj.] - || (W: W.) PT(++1) - (W--w.)
[triangle inequality] < [l( W.) -WW -w.ll + || -w.) - -P P-(k+1)(W) w.)
greediness] S |oo wxll + [W - will
||+++ W& ||wo wi| S |wo wxll
where we used the fact that the orthogonal projection of given point on subspace is the closest point in this subspace to the given point the Euclidean-norm sense.
If [|W wx|l < |w will. the proposition follows immediately. Otherwise || Wkll 2
[wo will. and thus
([| Wx
- || will)² - 1|wo - w
-wxl'
Plugging this into Corollary
F3 we get
(Il W
wxll
l|wo will)² S Wo - wxll
& Σ lw w + will Σ
1 s/wo will?
|w, w,-1ll
t=2
t=2
will (I w
||++1 w [w, w,1111 S
||,, Wi-1ll
x++1 We 1/-1
wwo will > 2=
|| - W
Using the same derivation, when all steps are greedy, we see ||2 will 2
>i 2
w. w. ww 1ll
W Wa- 2 2
w. ww 1/|2
[ wwlll
| wxll. acquiring lower
w. we-ill
2| -
bound Vt E [k:] I|w w.-1/ 2
2 [Iw; wllll" Hence, we define the sequence (C:) k+1 by
s++1
Σt#1 C the backward recurrence Ck+1 = |/ wull and VE [b]. C. 2 3 C,' By applying
Claim F7
using the sequences
|| wl b; A Ck+1-5 for all i E (o...., k), we
observe that Wo will 2 C1.
We investigate the sequence (C2) in Corollary F.10 where we prove that if Ck+1 = || Wxll > this sequence maintains Vk 1,
C 2 Ck41 2
1/3 k/13
(and indeed if ||a++ Wxll = 0, the proposition follows immediately). and thus we get that
1 k 1/3
I| - wil 2 C 2 || w
2/3
///wk41 w < |wo- will 2e 4/3 2/3
42

---

Lemma F.. Under greedy MD ordering, either single pass or with repetition, we have 4k 2 1,
4 8/
Wo w.ll
Wk-1 -
3
k2/3
Proof. Applying the above proposition for a starting index (instead of 0), we see that Ak > t, | w&ll 1 | well 4/3 (A: - t)
W wall?
8/3 (k: t)2/3 ||- well2. -w.l?
From the Pythagorean theorem have
h W w
[w w. W - w.ll || w |wo w.ll
1=1
Plugging in the above proposition, get
0 E [w w.l 1 |/ w.11 Σ
| w
1=1
Wk w
||wo w.ll? || -w&l?
8/3 (k: t)2/3
k-1
1
wo w.112 || wwxl
1
Σ
8/3
12/3
2/3 2 3 2//3 -1) 11
3 (k2/3
1 1)
Σ
$ || 1/--/|wx-1 -wal
1+
4/8/3
Wo w.ll
4/
||
w ||
Wk-1
wxll
3(61/311) +
1/3
4/3/3
408/3
8/3
|wo- w.ll?
k1/3
where we used Σ
22/3 2
k
dx = 3 11:1/3 - 1).
2/a
We are now ready to prove Theorem 5.3
Proof of Theorem
5.3 Under greedy MD ordering with repetitions we have:
T
C (Wx)
XmmW We
-ymll2 1w. PRT
Xm (Wa - wl)l
[w.
FTT
m==
m==1
T
X 2 PI(II- - Pm) (Wk w. )1
RRT
m==1
[[I P (W&+ -w))
[w,
m=1
(greedy-repetitions)
[w
Wk+1 |
Iw.
8/3
|w 1,
8/8/3
1
labove, wo 0
Tw.1
1z
3
(k + 1) 1/3
(k + 1)
0 (A- (1-3/))
43

---

F.1.3 Auxiliary claims
Claim F6. For 8, > 0 and 2 define
(a,((a) - 8 8 a2r a²r
+
(a) For 8, O, we have (a.
20 a E [ xo): hence I non-decreasing in a. (b) For all a 2 and > O, we have 0Sa,(()) 0; hence (a) strictly increasing in r. Or
do
(c) For all a E [ 1] and r > O, we have @far(a) 2 0, hence sa) non-decreasing on that o-range.
Ös
Proof. Below, we prove each statement separately, in order.
(a) Derivative with respect
0fsr da
(2ar) + ar) - (s (rr) (s + ar)
Expanding the numerator:
(2ar) + ar) 2ars 20?r? (s + a²rrr = 18 + 22
difference = (2a - 1)rs - a 222
Thus
0f.
221 - 1)s + a²r
20. 0.
do
(8 ar)
(b)
Derivative with respect to
SS.r
(8 + 20²r) (x+ + ar) - a(rs + a2r2)
Ör
+ ar)
Expand the numerator term-by-term:
(s 22²r) ar) = sar 2a2rs 203
a(rs + a²r?) ars + 3,3
difference 52 +2 23,2 0.
Hence 0fa,r/Or > 0. (c) Derivative with respect
0f.r 0s
(s + ar) (s+
72a(1-a) (s + ar)
r
ar)
For a E 12 1] the factor a(1 a: 2 0, yiclding non-negative derivative.
44

---

Claim F.7. Let n 2 1 and let (a:) ==0 be sequence of strictly positive numbers such that
Σ 0
1A 111,
a 2
j=0 Dj
Define second sequence (b:) n == recursively by
bo ao > 0, 6;
(i 1).
2 E by
Then an 2 bn-
Proof. For either sequence I E {a, by and each k 2 1 set
k
Q
R((0)
T
((2) 0.
==
j=U
k
For we can express the defining relations
R
R(a)
R (b)
R
2
by
2
2
and, using -/-1 = R(()
R
1x + k-1
(x)
2x +
k- k- R!
((a))
((a))
k-
R
R
k-
(8)
((2)
Tk + 2-1
Ik 8
5 k-1
1
+
ak
Rlat)
k-1
Tk (
where fer (a) is defined in Claim F.6
We now prove by induction that Ak E n1.
ag 2 by
5(
2 k.
(b)
R((0) *
2 R((b]
Base case k = 0. All equalities ag bo. R1dd R ao. s6at 50 ao hold.
(b)
Induction step i Assume the inequalities hold for k.
Comparing ax+1 and bx+1. By the recursion and the inductive hypothesis,
R
R
a&+1
b
2
2
(ii)
Comparing s(2), and s(()) From the above and the inductive hypothesis,
gla)
s(() ak+1 2 (b) bb+1 = Sk+1
(b))
k+1
(iii) Comparing and R From (*) we have
R(o) k+1
R,0) (g( R( {1)
R44 S R(
as++1
R((a)
where RK_1 2 7- By the inductive hypothesis s(a) 2 k
and k
N R and by Claim F.6
R!! the function (a) is (a) increasing in a, (b) increasing in r for all a > 2 and (c) increasing
in s when a 2- Therefore
R(00) = SStu), ra(a)
aK++ R!(a)
2 gg n(o)
f (0(
R
2
R2
2
Hence the inequalities hold for A + 1, concluding the proof by induction. Taking = n. yields a, 2 by, proving the claim.
45

---

Claim F8. Vx >>>= -1, log 2
2
ltx
Proof. For x > -1, define f(x) = In(1 + z)
I42 then
1 1+r-r
(z(x)
1+ æ
(1 (1+
(1 + x)²
Since f2( < 0 for x < 0 and (x) > 0 for x > 0, the point x = O, where f(0) = 0. is the global
x
minimum of f. Hence In(1 + x) 2 1+a x
for all -.
Claim F.9. Let > μ 0, R > 0. Define the sequences (An) (Br) (cn) 20 by
n=o
Bu, Ao > 0, Bn > 0, Co = n Ao
and for n 2 1.
B
Ba-1 2
Bu An
An - An-1
Bn A Bn-1 + p
On A K
An-
An-1
then Vn 2 1, Cn 2 Co
yn
where
exp (- (=m(2>-p)
Proof. It is readily seen that Vn 0, An, and B, > immediately by induction. Define the helper sequence Vn 2 0, fn
A² B
> 0, then An VBJn and Vn 2 1,
(An-1 + X
Bn-1
2
(VBn-Ifn-1 + X
B
An-1
VBn 1fn
fn
Bn-1 +
An-1
Br
Bn-1+
Bn-1
VBn-ita-
2
Bn-1 VIn-1t Vin-1
B 1+
In-1
1 2A + X2
Jn-1
[Bn-1 > 0]
1 Tn-1
p
fa- +
(A A-pi 2))
= fn-1 + 2X /1 4
fn-1
2 Sa- + 2) ,,,
then fn 2 fa-1 +2 2A
fo + (2X- 14)
A2 Ba
n (2X- 11)
Now, observe Vn 2 1,
C =
B
Ba-1 + fI
An-1
Bu-1
2
Ba-1 1+ |1
A2
Bn-1
Õ n
1+ #
fn-1
A
An +
Bn
K
An 1 + X
Br
1
An-1
xz
7n-1
n-1
f. + fz + X -
n-1
1 2 --
= C
= Co
II
+
ft +
1=0
==
46

---

and note that vi 0, 0 <
Ji+X
A-
<
1. Taking the log we get,
n-
X 1
log Cn = log Co +
log
$3 )
1=0
n-
1=1
n-
Claim g 2 log Co +
1:
= log Co=
-
A-p
fi +
i=0
Ji+A
i=0
X
A- / (2X 1 +
>>> 1 2 log Co-
2 log Co
fo i (2)-
[1] +
==0
i=0
Jssuming n 2 2 = log Co
X 1
i(2 11) + 2 log Co
X- 1
A- |
Σ
n-1 X- 1
1
i2x (4)
1=1
i=1
A-
X 11 (1 + log (n 10-11 1))
Ee 51+ 2 log Co-
11
2X- /b
2 log Co
A- H
X A-
A-M log n
P
2A - p 2X - P
2A 11)
+ C, 2 Co n
2 exp
11 1))
When n = 1, we have log Ō2 2
log Co
A-1 >
log Co d- d-p 2d-x"
hence Ō 2
Co exp 2A(A-H) concluding the proof for all n 2 1.
Corollary F.10. For (C+) desined by the backwards recurrence Ck+1 > 0 and V1 E [k),, C. =
EtiL C3 2 C3'
we have that Vk 2 1,
C1 2 Ck+1 204/3
k-133
k+1
k+1
Proof. By defining Vn E (O.....k)
k}. An
Cj Bn Σ
Σ
CJ. we note that Ag
j=k+1-n
j=b+1-n
CR+1 > 0, Bo C2++1 > 0, and for all 1 S n S k,
Σ S+t
Dj=ktl-nt n+1 C3
1 Bnn1
A, An-1 + Ck+I-n An-1+
A +
2 2 -ー==--1-n4> Cj
An
Bn-1
1 Bn-1
B, = Bn- + C2+ Ch+1-n BB-1+ +
B, B
AAn11)
1
An-1
Defining the sequence Č₂ - n A.,
with 2. we have from the above claim Vn 2 1,
Ö₂ 2 Co y
where \= 3: /1 4, 7 exp
2 カ(
4/3
and Co = 2 Ao
1B
CC++I Thus, have,
4/3
Cn 2 Ck+1
2 n
1/3
Vn 1.
Finally, observe that Ö, 2 1 Bn
E
02
C
2 for all 0 S 1, and plugging in
2 An
2 - C,
n = 12 1, when k 2 2, we get
4/3 -4/3
44/3
C 2 C++1
2 (k - 1) -1/3 > C241
2 k 1/3 -1133
Specifically, when is we get C₁ for all k 2 1.
Cx41 1/2 2 Cx+1
1/3
11/3 concluding the proof
2
2
47

---

F.2 Regression experiments on single-pass vs. repetition
Here, we extend the experiment on the effect of repetition (Figure to additional data regimes.
Figure was produced using the same data as Figure 3a i.e. d = 100, 10, T = 50. Throughout this sectio, the Maximum Distance ordering (Definition 3.1 is denoted by "Greedy" for brevity.
Isotropic data. We find that the conclusions of Section 5.2 extend to more regimes: repetitions are
beneficial in greedy ordering while replacement harms random ordering.
d=20,
r/ r/d=0.1
d=20, r/d=0.5
d=20, r/d=0.9
10
10
10
10
10
10
Loss
10
10
10
10
19
10-24
10:24
10-29
10-29
20
d=60, r/d= 0.1
d=60, r/d 0.5
d=60, r/d=0.9
10
10a1
10a
10-3
10-9
Loss
10-14
10-14
10
10-19
10-7
10
10
26
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
d=100,
0/
d=100,
r/d=0.5
d=100,
=/d=0.9
10
10-1
10 9
10
Lo5s
10-14
10-16
10-0
10-10
Random, with repl.
10-10
Random, without repl.
10-7
10-24
Greedy, single pass
10-4
10-1
Greedy, repetition
10-29
10
20
30
10
20
20
30
Seen tasks
Seen tasks
Seen tasks
Figure 20: The effect of repetitions for varying dimensions d and ranks r of the data matrices, for isotropic data. T = 50. Random orderings without-replacement consistently outperform their with-replacement counterparts In contrast, greedy orderings with repetition outperform the single- pass variant. As explained in Scction 5.2 repetition greedy orderings is beneficial because enables larger steps (and converging faster to the joint solution w.).
T=50
T=100
T=500
10-1
10
Lo5s
Random, with repl.
10.
Random, without repl.
Greedy, single
10-7
Greedy, with repetition
10
20
50
20 30 Seen tasks
40
50
10
20
50
Seen tasks
Seen tasks
Figure 21: The effect of repetitions for varying task count T, for isotropic data, d = 100, r y= 10. As task count increases, the differences between with and without repetition diminish. Notice, however, that all subplots we only learn the first 50 tasks. It is readily observed in the left subplot that the effect of repetition becomes pronounced in the latter parts of the task sequences. As can be expected, repetition offers less benefit when many diverse, unexplored tasks remain.
48

---

Anisotropic data. Next, we observe that the effect of repetitions diminishes for correlated data.
20,
r/d=0.1
d 8200, r/d=0.5
d= 0.9
10-1
10
10-2
10
10-12
Loss
10-11
10
10
10-2
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
d=60,
r/d= 0.1
d d=
60,
r/d
r/d=0.5
d=60,
r/d=
10a1
10-1
10-5
Lo5s
10-1
10-3.
10-12
10-17
10-3
10
10
20
50
10
40
d=100,
r/d=0.1
d=100,
r/d=0.5
d=100, r/d=0.9
10-1
10
Random, repl.
10
Random, without repl. Greedy, single pass
Loss
10-3
10-2
10-12
Greedy, with repetition
10
10-3
10-5
10-21
0
10
30 Seen tasks
20
40
50
10
20
30
40
50
10
20
30
40
50
Seen tasks
Seen tasks
Figure 22: The effect of repetitions for varying dimensions d and ranks r of the data matrices, for anisotropic data. T 50. Previously in App. (Figure IO), we explained that the performance of all ordering strategies deteriorates when the pairwise distances between task solution subspaces are small. This effect even more pronounced for low-rank tasks (left columns), where the complementary high-rank solution subspaces overlap substantially. We also observe that in those low-rank regimes, different orderings exhibit more similar performance, and consequently, repetitions become less impactful. While we cannot fully explain the small performance degradation observed when allowing repetitions in greedy ordering for low-dimension, low-rank settings (top-left subfigure), it may be related to the slower convergence to the joint solution nullifying the effect of the loss upper bound induced by the distance to w. (Proposition 2.6 see also Figure 23 below).
Below, we observe another aspect related to the "diminished" effect of repetitions in this setting.
r/d=0.1
r/d=0.9
Loss & Sq. distance
10a
Single pass distance Repetition sq, distance
10
10:
10
Single pass puss-Mo loss Repetition loss
10-2
10-26
10-3
10-22
10
10-4
10
20 30
40
50
0
10
20
30
40
50
Seen tasks
Seen tasks
Figure 23: The distance to w., a loose upper bound on the loss for high similarity tasks. Greedy ordering with d = 60, T = 50. While repetitions do lead to slightly faster decrease in the squared distance to w., this decrease remains slow when tasks are highly similar (as the low-rank setting on the left). Consequently, the upper bound of Proposition 2roposition2_oboomes looser, as the loss itself decreases more rapidly. This discrepancy makes it difficult to draw firm conclusions about the convergence of the loss, including the exact impact of repetitions. A similar gap between the loss and the distance to the joint solution w, in highly similar tasks was also noted by Evron et al. 33 Section 5.1 therein].
2.6becomes
We omit the figure for the corresponding experiment with varying number of tasks T, as it offers no additional insights beyond those shown in Figure
Remark.
49

---

G Appendix to Section 5.3: Hybrid task ordering
G.1 Hybrid ordering scheme
Motivated by the success of greedy Kaczmarz and importance sampling methods 77 4] as well
as recent convergence bounds for random orderings in continual learning (35 TO], we introduce "hybrid" strategy in Section 5.3] Hybrid schemes have also been explored in the contexts of Kaczmarz
methods 75 25
coordinate descent [36]. and multiplicative Schwarz methods 40
In this approach, tasks are selected greedily as long as the decrements |[w---ww w. |
(see Eq. remain above threshold; afterward, selection switches to random sampling. The proposed hybrid method can be used with either the greedy Maximum Distance rule (Definition) 3.1). p). as in Scheme or the greedy Maximum Residual rule (Definition 3.2) as in Scheme
Scheme MD hybrid ordering (TH-MD)
Input: BMD E [0, Wo w.
For each iteration 1, I....,T: T:
Use greedy selection as long as the threshold is met |( Pm Pm) (w.-1 w.)ll # Compute greedy selection
mn' +- mrgmmaxxmf?]))mamm
[|(I - Pm)))(w:-)) w.)ll 2 3MD Then TH-MD(!) + m' Else Break
TH-MD (t: Unif((2) \ TH-MD 1)) Choose remaining tasks randomly w/o replacement
Scheme 4 MR hybrid ordering (TH-MR)
Input: BAR E [o, R² Wo w For each iteration T: m
# Reminder: R - maxme(T) [Xmm]] # Use greedy selection as long as the threshold is met (1- [Xm X ymll
# Compute greedy selection
If
[mm W ym 2 BAR Then TH-MR(() < m Else Break
TH-MR( T) ~ Unif ([7) TH-MM (1:tt)))))))) Choose remaining tasks randomly w/o replacement
While our analysis sets the threshold 3 using || - w.| and R, the hybrid methods remain useful, egg, with a heuristic B.
Analytically, using suitable threshold B, any upper bound for without--relaacmmet random orderings, egg., an (l1vk) bound [10], can extend our hybrid schemes, showing again that they avoid the failure mode of Section 5.I as shown in the following Lemma G.T. Moreover, we show that the upper bound that we derive for hybrid orderings continues improve as long as the stopping criterion
is not triggered. Put more simply, it is beneficial to follow the greedy ordering as long as the resulting iterates "large enough" (however, the actual stopping time will depend on the data).
50

---

G.2 Hybrid ordering upper bound
Lemma G.1 (Hybrid ordering bound). Consider any known upper bound for the expected normalized
loss (Definition 2.3 in random ordering without replacement over I jointly-realizble tasks, of the
form Er
[[( (aait)) S T
C. with C and 0 < S such that fa S 2-a Then, defining
Bmnn T -C(1-)
the following holds:
CT
When BMD
wwo -w+ll Amin (or BMR 2 R² Wo w-ll Bmin). the loss under Scheme
3
for Scheme 4) is upper bounded as EuH [[(wT)) S
C Furthermore, choosing BMD
I Amin (or BMR = R2² || -w-, w.ll Bmin), i.e., postponing the stopping time as much as our (data-dependent) condition allows, leads to the lightest upper bound (in our derivations).
llwo w.
Proof. For MD and MR hybrid orderings, we denote AMD = wwo -w.l w.ll and BAR 3R wa w.ll respectively. Note the following holds for all m [T]. Rd:
X m2 W- mml X (w w. w.)ll X Xm (w w, w.)]l² R² II(I Pm) (ww-w)). w.)l
So, when |X W - yml 2 3R l|wo w.ll immediately | (w,- w. 1| z
l/wo- w. i.e. if the condition for continuing with greedy MR steps in Scheme 4 holds, then II P (w,-1 -w.]l wl 2 l|wo w. (this holds by definition for Scheme 3
The last step / for which (
P() (w,-1 w.)ll 2 l|wo w.ll? consecu-
rively holds is some = s, where S S T. The following holds:
W. w.l w= = l| w.ll
1I
||, wi-1 < Wo w. (1
We are reminded of the definition for the (normalized) loss for a solution vector w with a task collection T, starting from some starting point Wo and having minimum norm joint solution w,:
(T,,we wo) w A
1
Σ
|mm wwwwa (w-w.)l?? w
Woo w. R2
T
MET
Running the hybrid scheme on the task collection [T]] yields the following expected loss:
E, w()) [WT]
E
[mm (WT wo)ll
|wo - w.ll -w.l'
m=1
1
E
X (e) (WT - w.)ll
E
Xm (WT w. |[]]
|Wo - wall R22 T
me (T) (1:e)
1
R2
E
||
w-ll
E
Xmm (WT (WT- -ww)
(Wo- w= R?
me (T)
(1)
R22
E
Iw - w-1l 2
Σ (e(T)((((:s))
+
E X (WT w. w.))1
|wo w-ll
R22
1=1
R2s [w w.112
Xm (WT-W.I. wP)IPP]
|wo w-ll R22 T
(r
|w w
st (T -s)
|| w. R Σ
E Xm (WT w. -w.)l
T |woo- w.ll
mE(TTTr(1:s)
|w w.ll
8 (T - (e E, (( (wrl)
WW w.ll 1
1 Bs
(T
8) E, (TT (( (wrl)
T
51

---

where (1) is since s I T, and (2) is since w, is deterministic. This means we can plug in any upper bound for the expected normalized loss of the random ordering, for the collection of T tasks (7) T (1 : s) with the starting point w., replacing dependence on 7 with T - If we have an upper bound for the expected normalized loss of random ordering of f (T) tasks, which a positive and decreasing function of T, we obtain the following upper bound for hybrid ordering:
1 -3s
E, E,
[w]]
S
(s
(11)
T
As a sanity check, setting s 0 removes the greedy iterates, and the bound reduces to that of random ordering. For the rest of the proof, we work with bounds of the following form:
C
C
1
((T)
T
T
(12)
1
else
such that (T) 1 VC, a, T. This only means that we ignore the cases where the bound on random orderings entirely vacuous, i.e. is larger than 1.
We want a condition on | for which continuing with greedy iterates long as [I Pm) (w,-1 w.)l 2 l|wo w. necessarily improves the bound. This means we want
the bound to decrease with Thus, we demand Vs E [T] a (f)
-T s) (T ((T)))) s))} s 0:
1 8s (8 + (T () - s)))
ds
T
(-3 (s + (T - s8) - 5)) + (1 31-) 3o) (1 +
(T- a)))
T (-3s - f (T - 5)+ fsf (T - 5) +1 - (T--)) f (T -s) -Bs .s
1
+ßsf (T s) BBs - 5) f (T (T-s)) -))
T (1-23s 1 -1-3s---111
1
(1+ 2Bs f [TT - 5) - -)
(T (I
When demanding this expression to be 5 0, we get:
3 (-22- - - 2s) f (7 - + l' s)) - -1 () (T
1- --
sT -s) f') (T s) B2 Tf (T +) 21 (T - -s)
As a sanity check, note that since and the denominator is positive.
(T- < and f (T - s) S 0, the numerator is non-negative
Continuing:
1- 1-
B B2
-T00------001-----0---------1111 8)
-(- (T -8)
- -1)) 8 (T(T 8) + [T
(T-
s+ 1- (T- (T
(T-
8 Sst [T - (T (T
We demand this holds Vs [T]. We assume, for now, that (T- $ 1. We will later examine the
C
other case. Thus, plugging in f (T - s) --
52

---

(T - 8) (T-s)
CTT 8)²=a
3-1 18t
(7= + (T 5) aC
C
(T-
=8
1- (T-s)
C aC
(T-s)a
=s+ C(T -8)
C(T - 8)
=8+ - - 8)" - 0 a)
- g
(T 5) (1 C(1-a) [T-}}²
We are reminded that we assumed (T-s)a S 1, thus (T s) 2 C dt), so the denominator
here is positive. Denote 3-1 I 9 (s) - s+ (T-a)"-((-a)) In order to find an upper bound on 3 which holds for all s, we look for the minimum of g(s). Differentiaaing, we get:
c(T-s)
-C -CT - 8)" - C - C(T - s) -a (T - ss)
dg (s) ds
1
(T- -C(-s)
= 1 - C a (T' - 8) -T
((T - 5) (1=
s)
aC
(IT 8) C(1 a))
(T - 8) - C(1 ()
(T' s) - a)
2 aC
C (T - C(--a)
((T 5) C(1 (1-a))
C11-a)
s)s) - - (1
=1 -)-
(T -)" C
Hence gs) 2 0 for small enough such that s) 2 2C(1 a)), and ofd g((s) 0 for larger values, up the maximum value under the current assumption of T Ca/a Hence, the minimum of g(s) in T C1/a] will be one of the boundary points:
C/Cl/a
T - C//a + C
g TT -1/0 =T T - ///a +
C-C(1-a)
= T + Cl/a (a 11) 2T
CT
9 T CC
T -22 a) T C و (T-- 9 (0) 2 T 1 T-a -a-((l-a)) = T'
C
This can only be negative when T < (C(2- (2) a)) covered in this Lemma, since we assumed C < I-a (and the bound is quite useless if it is larger 2
f. iee, -
2-a which is case
Th
than I anyway). Thus, is guaranteed that the lowest upper bound for 3-1 1 is for s = 0, and we get:
CT
8-1 <
To C(1 - a)
To
2 3 min
CT
Under this choice of 3, the upper bound of Eq. is monotonically decreasing with s as long as (T-s)a I 1.
C > 1. In this case, our upper bound We now address the case of 8 large enough such that (T-s)=
from Eq. 11 becomes: ((Ul.wo) [wr] I -لf (s+
1 Bs, which is also monotonically decreasing with 8. From continuity of the bound s = C1/a (it does not matter that this might not be integer), get that the bound is monotonically decreasing with for all T -(1-() and thus beats the bound for random ordering, achieved at
(T- ())
> when 3 2 3min
CT
s = 0.
53

---

G.3 Hybrid ordering experiments
Figure 6 was acquired using the same data as Figure 3a and using the dimension and rank cank-dependent B3 since the universal bound of 14/k-/4 requires more than 50 iterations to be effective. The hybrid method results with intermediate performance between random and greedy. The figures demonstrate that the hybrid approach combines trends we have seen earlier (App. B) for random and greedy MD, in terms of the effect of dimension, rank, task count and task correlation the performance.
upper bound of 2 (d - r)/ from Evron al. [35
d=20, r/d=0.1
d=20, r/d=0.5
d=20, r/d=0.9
10-5
10-2
Loss
10-12
10
10-12.
10-12
10
10-16
10-2
10
30
40
10
20
30
40
50
10
20
30
40
d=60,
r/d=
d=60,
0/5=0.5
d=60,
r/d=0.9
10.5.
10-5
Loss
10
10
10
10-19.
10-42
10
10-25
10-2
30
d=100, r/d
100, r/d r/d=0.5
d=100, r/d 0.9
10
10-5
10-3
Loss
10m3
10-12
10-12
10-19.
Random
10-11
Hybrid MD
10-25
10-2
Greedy
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
Seen tasks
Seen tasks
Seen tasks
Figure 24: Hybrid performance for varying dimensions d and ranks r of the data matrices, for isotropic data. T 50. In high-rank and/or low-dimensional settings, the rank ann-dependent upper bound employed by the hybrid strategy in this case is lower, prompting earlier transition from the greedy to the random phase. Interestingly, the performance of the random phase within the hybrid method is slightly inferior that of fully random ordering ordering-possibly possiibly because the initial greedy steps deplete the set of "extreme" tasks that would otherwise drive greater progress.
T=50
T=100
T=500
Loss
10
Random
Hybrid MD
10-r
Greedy MD
0
10
20
30
40
50
10
20
30
40
50
10
20
30
40
50
Seen tasks
Seen tasks
Seen tasks
Figure 25: Hybrid performance for varying task count T, for isotropic data. d = 100, 10. We see similar trends. Note that the previously observed slight drop in performance the random iterates following the greedy phase is less pronounced with higher task counts, possibly since more extreme tasks remain available for selection.
Anisotropic data. Similar trends were observed under anisotropic data, and we therefore omit the corresponding figures for brevity.
54

---

H Appendix to Section 4.1 Code snippet for regression experiments
The regression experiments intentionally simple, and for completeness and reproducibility provide short code snippet. Running it generates basic linear regression experiment on isotropic data, comparing random and greedy orderings (Eq. (4) Def. 3.1 and 3.2)
Minnimal Block Kaczmarz experiment with runnable demo import numpy as np import matplotlib. pyplot as plt from numpy. numpy.linalg import pinv from typing import List, Tuple, Optional
s simp le plot
5
Core utilities
def generate_datalle int, d: int, T: int, seed: Optional [int] None) -> Tuple Lmp. ndarray, up ndarray, up adprray List Lisple) List [np. ndarray], List [up ndarray]]:
Returns:
X: (T+r, matria; (Ttr,) labels; w. true: (d,) teacher. blocks: list of (I_t, b_t) with I_t in (-(rx, b_t in g- pinv_ blocks: list of paeudoinverses I_t+
14
md_proj: list of I_t+ I_t (used by ND-based selection).
***
if seed is not None:
18
np. random. (sed()
b_blocks = [np. random. randn d) for in range (T)] max _ad_ max (np. limalg. norm(B, 2) for x_blocks) X_ blookks [B max rad for X_blocks]
22
23
v_true np random. randn (d) /= np. limalg norm (w_true)
27
X np- vstack (X_bocck__))k)
b - X @ w_true
X_blocks [X[i<r: (i+1) :] for in range(T)]
b_blocks [b [blirr: (i+1)*r] for in range(T)]
32
(pinv(Xt) (Xt) for Xt in X_blocks]
md_proj [pinv_blocks [t] @ X_blocks[t] for t in range (T)]
blocks list (2st(((X__blloe blocks, b_blocks))
return X, b, R_true, blocks, pinv hinv_blocks, md_proj
Listing 2: Data generation.
55

---

def _pick_ uni int, used: Optional [List alloo_repetition: bool) >> Optional [int]:
if allow_ repetiiin::::::
3
return int random. randint (0, T))
pool list (range (T)) set (used or [])
return int (np random. choice (pool)) if pool else None
def pick_grredd. (bllokks: List(tuple], w: up. adarray used:
(blocks: Optional [ist[[it]]] allow_repetition bool) -> Optional [int]; best, best_val = None, inp.inf
for i, (Xt, bt) in enumerate (blocks):
if (not allox_repetition) continue
used and used:
12
val np. a.plinalg.... norm @ bt) **
if val best_val:
best, best_val i, val return best
16
def spick_greedy (me_pp__dmd__poo List [intaaa.ddarra up ndarray, w_true:
+ np. ndarray, used: Optional [List [int]], allox_repetition: bool)
Optional [int]:
best, best_val - None, ippinnf
for i, P in cnumerate(md_prr0)
if (not allou_repetition) and used and used:
continue
val np. ap.linalg.normee nP @ (v w_true)) ** 2
if val >= best_val:
best, best_val val
return best
Listing 3: Ordering strategies.
56

---

w) single block least squares step def block_kaczmarz
blocks: List [istle)
3
pinv_blocks: List List(np.Nug (tp. nddrrayl, md_proj: List [np. ndarrayl, v_true: np. ndarray,
4
5
T: int,
d: int,
max_iters: int,
selection: str "uniform", $ one of ("unéform", "greedy_mr", "greedy_md") relow_repetition: bool = False,
) >> Tuple[np Idarrdd List[floar [float], List [float]]]
"**Runs Block Kaczmarz and returns (w, out, losses, dist, teacher) per
- iteration. ~*~
13
W = up. zeros (d)
out_losses: List [floa]] Q
dist: [istaf] 0
used: List[int]]
17
for in range (max_iters))
if selection = "uniform":
wtppickkuiiforrttte used, allov_repetition)
elif selection "greedy_mr"
22
ww.pickggreedy_eee (blocks, H, used, allow_repetition)
elif selection -- "greedy_md" _md":
pickk_ hattaerreedd_dddddddeaaeeeeae md (md_prooj, и, w_true, used, allov_ropetition)
elae:
26
raise ValueError ("selection must be one of 4 {'uniform', ggeedyy_mm ggreddy_md'>"
if None: available block under no-replacement out_losses append (np. nan)
30
dist. (np. linalg. norm(w v_true) 2) continue
bt blocks [t.]
pinv_blocks [t] (bt
35
if not allow allow_reeetitee repetition: used. (t)
39
metrics
loss = 0.0
for Xs, bs in blocks: Xs @ bs
loss np ap..inaag..nnv out out_losses.u append
44
(1oss (loss / T)
dist append (np. linalg norm w_true) ** 2)
return R, out out_losses, dist
Listing 4: Experiment loop.
57

---

One reproducible esperiment
simple le figure
3
Problem size / schedule
d 100
r max (n. * d))
rows per block (r/d 0.1)
T = 50
# number of blocks
max_iters
single pass without replacement reproducsble
seed
# Data and precomputations
true, blocks, pinv_blocks. md_proj generate_data(r, d, т, seed-seed)
13
Compare three orderings (no replacement for poples-toappple single pass) strategies = [
14
("Random",
("selection"; "uniform", "allov_repetition" False)),
("Greedy MR", {"selection": "greedy_mr", "allov_repetition": False)), ("Greedy MD", ("selection": "greedy_md", "allou_repetition": False)),
18
results- 0
for name, opts strategies:
out out_losses, dist kaczmar)
23
blocks-blocke, www.bllock--pin_blooo.
md_prrojmm__pro v_true=R_true, T-T, d=d,
max car_iters-mar_iter
**opts
)
32
results [name] (up. aap..aaarray(out.ossss)))) np. (earray(dist))
Print final metrics print("Final loss and distance-to-teacherr:
36
for name strategies:
key = name [0]
I, D results[key]
pick the last
value
last_idx np print(f" (key:10s) loss=(L[last_ [dxx] :.4e) dist=(D(last_idx) : :.4e)")
[o] [-1]
Simple comparison figure fit.ffigur(ffigsizeeC (6, 4))
xs np arange max_iters 1)
for name, (L, _) in reaults. items ()
plt.plose axt. L[:max_iters]] label=name) www.xallllleerrttee loss")
(seen tasks)
50
plt. Aat.grid(True, alpha=0.3)
plt. legend)
plt. plt.tight. tight_layouut)
show()
Listing Simple ordering comparison experiment.
58

---

I Lower bound technical appendix: Delta positivity proof
This section supplements App. vd 2 25,000, V ,
E. which we recommend reviewing in advance. Here, we prove that vk E {l,...,d- 1}.
4 - Ww Wk+1ll (Wa-1 wx) Wi-1 || well (Wk -K+11) Wi-1 0.
In some places our proofs, we will need closed-form approximation of the first coordinates Jk - (W:)1 which we obtain recursively. Such an approximation was suggested in Hucht 48]]
k -
+
In
In
This will be formalized and proven in App. In addition this gives us lower bound Th 2 0.45, Ak E [d] when > 25,000 (Corollary J.3
I.1 Proof outline
The proof is straightforward: we decompose Ar, to smaller parts, and attempt to lower bound each of these parts. We then combine all of these lower bounds to achieve an overall lower bound on A and find a sufficient condition on for which this lower bound is positive. This condition, revealed in Eq. [3), is already satisfied when d 2 25,000, concluding the proof. We begin by bounding some intermediate quantities that appear later in the derivation, and starting in App. I.3.6 we decompose and lower bound Ar,
I.2 Auxiliary: Algebraic inequalities
Claim L11 Vd E N and S n S holds that 1 c 2 2-n/d E
n² 2n
(n(2)
2d
Particularly, this shows E
In(2)
(22 2d
ln(2)
d
Proof. To show the upper bound, we define a = n/d E (0, 1] and f (a) 2- a (2), and notice that ff is decreasing in (0, 1] since
f' (a) = (2- In x 1 0, Va E (0, 1]
Then, this means f (a) = 1- a/d n الااام lim f (a) = 0 as required.
Conversely, we get the lower bound by showing that the function g (a = (i) =1 - 2-n/d
[nl(()
n² In2 is increasing in (0, 1),
2
9 (a) 1- 1-1 1 an (2) a In2 (2) lim g 1 -0-0000-00 0=
a
g' (a) In (2) (2 +aln (2) -) x ~ +a -5
2 - a-
lim (() + 1- 2-0 0) +1=1>0.
Claim I.2. For Vd. n, E N and [d]. we have cnkmm= 2-n
Proof. Notice that c² = 2 2-d/d is decreasing with 2. Plugging in z nk m I nd, we get o² 2 and = n-
59

---

Claim 1.3. Ak E [1, d] it holds that - -) - - 1) = ((k c) (k- - 2)) E [0, 1].
Proof. It is clear that (1 c) (k 1) _ (1 (1-2 2-1)) (k - 1) 2 0. Then, we can simply show that from Claim L.
(k - 1) s (1 c) - 1) In (2)
d (d 1) < In (2) <1
20
Claim 1.4. vk [1.d] it holds that hc (k 1) 0.
Proof. From Claim 1.1 we have 1 - c c h2
1n2
Plugging that in we get:
d
kc (k- 1) 1 In 2
h
k
++==
In
1n2 0.
d
Claim 1.5. Ak E [d] holds that 3g E
0.3.20-5 20-3
Proof.
3k ((k: - 1)c (k: 22) 2 = -11-11-
2k-5
0.3c2k c2h-5
(1-(1-0) c) (l: 1)
E
d
d
d
c(0000
Claim I.6. Tkk is decreasing and Vk [d], 3
Proof. Decreasing follows immediately from positivity of 3g (see Claim and since 2 we get Ak E [d] 2x < 1.
1.5 and the construction.
Claim 1.7, vk [2, holds that By S cd
2k-5
2.2-5
Proof. Since e 1, we have 3a z
d
d
cd
Claim L8. Va > 0,b E R \ (0) such that a + 2 0, holds that Va + va + 2/0"
Proof. 0< b2 + 4a (a + b) < 4a² + 4ab + (2a + b)²
Va+b < va
2
Claim 1.9. vd 2 1: 21/4 1 +
ln2 d
Proof. Using Taylor's expansion: 2/d =e In2
1n2
In2
In 2
=1
+
> 1 +
d
i!
1=2
Claim L.10. I& ãnl S e and Ik 2 0, 11 - 226
< 2I + E
Proof. Defining
3z Ts. we have,
2 :2 = 2/1 (ax + +r)
12 7 12| S 12 + + = 22 (#x - rn)l + (Ex- xx))
< 2xze + 2
60

---

I.3
Proof body
I.3.1 Analyzing Tk-1 2h, (IK-1 xk)
1k-1
Proposition L11. For any 2 2. it holds that,
3k. k
20
8k
8k
2
2k-1
26 fan-1 (3k)
Øk-1
1--
+
k-
-k-1
x
+
(x
4,3x)
5/2
8k
18
B3
83
113c 15
[when 2 25,000 C
+
Tk-1
1k-1
3
2k-1
xx
d
Proof. By construction, we have
Fk 1
2 k-
4,3g
Fk- Jkk
2
Define fa (2) = (= V 4r) for E [0.45, (see Claim I.6
Corollary
J.3
and x² > x >
Expand with Taylor:
fe (0) fo (0)
1 -4
1 (x)
= 1 (0)
2/2² 4x V222 4x
1 (x) 2 (s² -4x) -3/2
(0)
2 23
1 (z) 3 4 1(2 -4r)
4r) 56/2
12 12 4x) 5/2
(3) (0)
12
25
and notice that generally 42 > x > 0 we have p!²²) (x) > 0.
Then, by Lagrange's 's form of the remainder, the error of the quadratic approximation (around x = 0) given by
(0) f())
f()) (0)
( (0)
x.2
(x)
0! x0 +
11 x² +
R2
(x)
Ra (x),
2!
where
f(3) (xo)
12
2
Azo)
5/2
2x
2x
R2 (x)
(x - 0)3
3
E
3!
6
25
(=2 - 4x) 5/2
since zo E 10,z).
We get that
Bk
82
2
Bk
B2
2,98
IK - Db faz (Bx) E
+
xk-1
Fk-1
Fk-1
Fk-1
(x% - -.xx 5/22
-3/2)
Finally, since Be S 26-
and Fk-1 [0.45, we have
2k-8 3
2
c
d
6k-
(x2 (x2_
4.8))
3/2
(0.452 4 026
3/2
d3 (0.452 4 5/2
/ 2 (0.2d - 4 23/d) 5/2
2 6k 15
11 1k 15
d > 10,000 4-2 2//4 0.000441d
<
/ (0.2d 0.00041d) 5/2
d3
61

---

Proposition I.12. For any k 2 2 (and d 2 25,000), it holds that,
1
Bx
(1+
10
8R
k
-k-1
d
kk-1
2
Proof. We employ the bounds we found for 2k-1 TAb
(Ti
Ik-1
+ Tk-1)
(5k-1 - Tik
Ik
-
3k-1
3k
2
8x
32
2
1
1
2
1
I
0k-1 (a%
4,8k)
6/2¹
x
2
8
3
2
Bk
C
#k-1
1--1
I (x 4.k))
5/22
Notice that from the bounds on Bk, -k-1, have:
23
2,3 22
13
Fk (x%-1
43x))
5/2
xk- (rf
-33))
5/2
2t-1 (0.452 4c28-3 6/2
2
2,32
Øk-1 (0.452
4 4
5/2
d 0.452 (1
4
5/2
0.452 2 1/dd
2
83
10
(d z 10,000]
d 0.45% (1
5/2
k
d
0.13
1/1000 10000
Since d 2 10,000, obtain
20
10 93
Overall, get
xx- (0h_1
-8n))*
6/3
x
5k
1
Bk
1+
10
3
Bx
2
d
2
Tk-1
4-1
k
62

---

Proposition I.13. For k 2 2 (and d 2 25,000), it holds that,
2
Fk-1
4,k
5%
613c 15
(Ix-1 - =x)²==
E
+
d3
Proof. We exploit the Taylor expansion of the following function (for 2² >> x > 0),
fxx)= v22 4r
2
2z
12z
1 (x) (x)
1, ( (x)
(
(x)
V22 4x
(22
4x)
3/2
(=2
4x) 5/2
Then, by Lagrange's s form of the remainder, the error of the quadratic approximation (around x = 0) given by
f() [0)
0! 2 + 1 (0)
(2)
(0)
22 + R2 (z)
2!
x²
= -0+0. +
x + R2
(x) =
+ R2 (σ)
2x
2
where
R2 (x) = ((3 (1r0)
(x - -0)
12z
5/22 x
2z
3
E
2r
2z x33
3!
6 (z²
4x0)
(x2 4r
5/2
x4
(2² 4xr) 5/2
since E 10,
Then, setting 2k-1
[0.45, 1), now conclude that,
Tk-1
488
(IK-1 xxa)²=
A (8k)
2
32
2,3
82
2
x7
1 k-
(x
4.8k) 5/2
We simplify the lower bound as (Ix-1 - kk)
2
2
1
27
Finally, for the upper bound, since 3x 5 2h
and f4-1 10.45, 1] we have
d
B2
200
20
15
(Ik-1- - 12x) <
+
k
x
(x%
4B1))
3/2
2
d3
1 1020-
5/2
d
B
2 2k-
82
6k- 15
<
+
S
+
2
d3 (0.452 - 4 11)
1//2
5/2
kk-1
2
d1/2 (0.2d - 4 21/d) 5/2
82
2k
32
56-15
12-00000
= 2000000
x -
/ (0.2d 0.00041d)5/2
x
d3
63

---

1.3.2 Expanding the inner product (Wk-1 Wk) Wi-1
Proposition I.14, Let E [d] and t < k - d (and d 2 25,000). Then,
(Wk-1- - - W
Tt-
3x + 24 1
32
+
1 1-2 2 c+ (1-c),
d
k-1
Ft-1 8k
21-1
t- 2
+ (1 c)
113c 15
2k-1
d3
Proof. We use the expanded form of the inner product, that is,
k-3 3 (1 c) cl-3
0 < (Wa-1- wx) W = (Ix-1 2kk x4-1 + (t-2)
Vd vd
1-2 2 ktt (1 c)
(Ik-1
Tk) 84-1
B
113.08 16
Since we already showed zk-1 - Ik E
+
we now have,
#1-1
26
d3
(Wk-1 - www) Wi-1
T1-1
21-1
82
+
t 2
kt-
6 (1-
Tk-1
2 k-
d
and,
3x
61-1 15
l 1-2 ktt (1 -
(Wk-1- - wc) W S xt-1
+
1--1
F k-1
d3
d
[x S 5
Tt-1
By
+
11-1
Pk
2-2 2 k+--6
(1 (1- c) + 11
3
1k
kk-
1
I.3.3 Bounding h (k) A
2=222000 (1 c)² + 2
V
Proposition 1.15, For any 2 2 (when d 2 25,000), h (1:) E
N-3 6-3
+
5.42
Vd
vd
1972
Proof. The lower bound is easy obtain:
k - 2k 6 (1-c)² + _22k-0> >>
1
1 V
k-
h (k)
2k
-
d
d
Vd
To get the upper bound, we employ the inequality (1 - 2
2 1
1/d 2-1/d
In(2) and get,
B2
k
22-6
h (k)
2k 6 (1 - c)² +
x2
d
d
82
2k
32
In² (2)
2k-6
(0.45)²
+ (1 - c)² +
d
V
(0.45)²
d²
+
d
In2 (2)
2
7
(0.45)²
dc
d
22
5.42
d> 10000
1
c 20.9998
d
2k 6
1
5.42
c²
k-3
5.42
2
2k 6
d
vd
2ck
3/2
k
5.42
2-1
d
d3/2
64

---

L3344 Bounding A(k+1) h(R)
Proposition 1.16. For any k 2 2 (when d 2 500),
(Ic + 1) h (k) E c
2k-5
2.44
x d : c+
2A 3,2
Proof. We start by expanding the expression in a way that will be useful for both the upper and the lower bounds,
R
-2 (1 - c)² + _02k-4
h (k + 1) h (k)
d
88 222 (1 c)² + 2c2h-
#i-1
t 22 (1 - c)² + 1 2²22-4
2 1 (1 cc)²
d
d
+ 88
2- 2k (1 c)² z 222-0
22- (1 c)²² + 222k
--1
#2-1
g 11
62
J _22h 4 cc)
c2
x 2h
2-2 2k 0 (1 c)) + 262
22 6 (1 c)² + 2
#2-1
For the upper bound. We show that,
h (k 11
h (k)
82
1 22 -4 (1 - cc)²
2
+ 8g
2
2k 6 (1 c) + 26-
h- 22k-6 (1 c)² + 222K-6
7-1
d
d
2²
IVB
1 (1 c)²
2 + 3
+
d
k-
22 6 (1 - -c)² +
202
+ d
22- (1 c)² 202
d In(2) 2
1 x²
IVG
1
2
-1-1
+
c² d
k-2
2k 6 (1 - c)² + 1 2
+ k-2 22 22 (1 c)² + 1 222k-6
#2-1
d
x/-1
d
ln²(2)
xx
+ In 2 (2)
de
c2 +
2
7 2 6
1 1h 2
2
26 ld
cx 2
In2 (2)
x x 2x
cx k-1 - c222
In (2) (2)
2
k-1
k
02
+
2k dd
22k 662
x 26 4d
x 20
2
x
ln² (2)
2 + (1 c2)
+
c2
xdc2k-4d
x
c2 dd
62k-6
where (1) is since BK+1 < Br, < 1; (2) is since BR < a. 1- 1
bn2 (3) is since dn S IK-1
and (4) is since xk-1 < 1. To upper bound 2 - xx we use the recursive formula of Ik. showing
65

---

that
-h-
2xr --1-1 1 1V
4.a + x
43x
-/-11
1//
2k-1
4
2
x k--1
4
0
2
K 1
x
2
[ 1- 2 v
2
S
1
F k-1
(1
4
x 6-1
0g
2
43,. + 23k
3.8
2
2
2
Back to our expression,
h (k 1))
1
33k
In (2) c2h- BpP
S 1
c2 + (1-)
h (k)
xx 22 4d
26
6d
1
3
In (2)
Bx S cd
$
0² + (1 - c2)
I x7o22-4d
2222k-
6d
In (4) d
c2 + In (4)
In2
1 d s
$
+ 2422k-58 dd2
xfc2k- 4d2
c2k 622
In (4)
3
I12 (2)
4.39 + 0.49.1
[<< 1/|s S
c +
+
+
S $
2
422
c2
x2c22-6012 622
4.88
4.88
2.44
02 + [at S 1
9
1+
c+
x
2k-
122
22
x
x7222 2k 3
where in the last inequality we used the fact that V2 0, v1+ S 1 + (since (1+ 2)²²
1 1+2 + 2 1+ =++:==(v++)}}
For the lower bound. We show that,
(k 1)
h (k)
08 11
c282
2 -4 (l-c)
c²
1
8
2-2
2k (1 c)² + 2x26
28
+ d 22 (1 - (1-c)² + 1 22
2-
d
o7
d
8
>
2
1--1
82
k-2
2 22 (1 c)² + 2
8 1
d
12
x
1+
8
k-2
2 22 -6 (1 cc) + 2
d
1 32
c
1 1
k d
2
22 6 (1 c)- + 6
where (1) is since 3 I I-- Since (Bk) is positive and decreasing, S6+1 - 32 < 0. and so we can simplify the expression using the fact that v11 1-1-2, 2, Vz E (0, 1):
h (k + 1) h (k)
32
32
| - 8241
k+1
2 v
2k
6
x
26 6
d
k-1
66

---

- _e20-3
Focusing on
and since 1 - (1-c)
11 -c) c) (k- - 1) = ((k: - 1) c (k= - 2)).
(k--1)e-(--2))
6
(k- 81
skl
3
1+1
Joth R+1
d
1 2
5
1 c225
d
d
2k-5
(1 - (1 - c) (k= - 1))² - (1 - (1 - c) 2)) (c)))
d
2k-5
(1-c*) - 21 (1 1 (1 ot) +h? (1 -c)² (1 (1-c4)+ +
d
20
+2(1 + (1- -) (-2k +1)
20
2k-5
(11 + x²2 (1 c)² (1 (1-c) ct) + +2 -) c) (1 (1-
d
Using the previously derived bounds of C In(2) 12)
In(2) 2d d
we can get.
8
2
k2 In2 (2)
(1 o + In (2)
In (2)
K+1
(1 c²)
_ 2R 5
d
[ 2 500 2 1000 In (2)]
2k-5
(1- th²
In (2)
c²) + In (2) 0.001
d
d
d
2h
(1-c*) +In2 (2) (1 c4 + In (4) + 0.001
[k S d
d
25-
In (4) + 0.001
(1++12 (2)) (1 - cc) +
d
d
Notice that we can use the previously derived bound of 1 c² S (2)
thus obtaining
|8 1 121
22
(11+ In2 (2))
4ln (2) In (4) + 0.001
2k-5
S 5.5
1 2k 5
d2
Finally, we get,
h 11)
18
B2
2k 2k-5 5
2 c
>
1 (k)
2k
5
2
d2
67

---

L3355 Expanding the norm
Proposition 1.17. For any k 2 2, |W-- wxll
h (k), h (k) +
56
where h (k) -
05-3,072
R + 22-6 (1 c)² 26
Proof. By construction we have
(c- (1-c) c)
2
ck-3 2
| - Wxll V (ox-1 (0x-1- - xx)² -x)) + (k -2)
+
vd
vd
-V -ol0k-1 - xx)2 d
(xx-1
2
26 (1 -1cc) c)² + ze2k-6.
Before, we proved that (I x
82
+
113. d
Now, we show the resulting
bounds for || W wxll which employ that bound. The lower bound is immediate, since
k - 6 (1-c) -c) c)² + joek-
= V (IX-1 - -xx)
+
d
32 k- 2 2h 6 (1 c)² -22 A h (b))
d
k-1
The upper bound requires an additional algebraic inequality of Va, b > 0: Va + < vā + 2V0 and the inequality of (k) 2 va
k- i.e.
B2
2 2 c2h c2k-6 (1 c)² + - 2h 6 2
113c6k-15
W -w&l S
+
x ---1
d3
113cbk-15 15
61- 15
6k-11
V
h22 (k) +
S (k) +
S h (As)
d3
2h (k) d3
c 3,/3
68

---

1.3.6 Combining the expansions
Proposition L18. When d 2 25,000,
WE Wk+1ll || (w Wa)
Wi-1 - | -wsll wk+1) We-1
A1 (k) A2 (k) + As (k)
96c
11-
1
556.5
+ -6140
d?/2
2b
d9/2
xx
where A1 (k) 2t-1
(h(k+1)
z6-1
By
h(k) Bk+1) ). A2 (k:)
x2-1
h((k-1)
x2_1
1)
83
h(k)
pRt1) As (k) 2
1-2 c) +tt- (h (k: 1) ch (k:)).
Proof. Keeping in mind that we wish bound
W Wh+ill (Wk-1 W Wi-1 | wwll (wi wx+1) Wi-1.
we start lower bounding the right expression. Using the bounds for (WR-1 Wx) W and Will we derived above, we get,
|
- -|WW--1- - Will (W*- - -Kk+1) Wi-1
2 - - wall
8t-1
Bk+1 +
Ft-1
S2 +
(1 - (1- c1
+
113
Ik
d
d3
(t (t- 2) 2 -c)
2 || wxll
F2-1 Bk+1
Ft-1 B
Ikk
61-16 d3
|| w
(k) +
56-50 15
c 3d5/2
Tt-1 Bk+1
3ik
Tt-1
32
k+1
+
t-2
d
ch kt c)
ka(k)
113 15
Wk-1 W
d3
bb(
The right function is casily bounded as,
113.6k-15
b (k) = |W-1 Wxll
d3
5k
1k-c
(k(k) +
35522
d3
11-
6384.5o
1.
12k-30
h (k)
d3
d
ck
1k 15
222k-6
5.42
1384
+
d3
Vd
d3/2
/11/2,k-3
113, 6k 15 15
612.46c
6k-1
1384
d7/2
d9/2
/11/2,1--3
7k-18
612.46
6k-
12769c12k-30
[c-3 al 0.5
d7/2
d9/2
d11/2
69

---

The left function is further decomposed as,
a (k:) = -h(() (k)
Jit-
Bx+1
+
Ft-1
3
82
k+1
+
t --
d
gtte 6 (1 - c)
(k)
56.5c58-12
[t-11 3k+1 +
It
p k++1 + t-2
chtt-- (1 -
d5/2
Ik
d
(k)
Then,
56.5c
T1-1 3k+1 +
It-1
t- ute e)
a2 (k)
pk+t +
d5/2
Tk
K
d
Tt-1
11.
1 1-2 2
d
5k-12 12
d6/2
Z
1
34+1
+
2k
3
%k+1 +
22
hte-5 (1 (1-c)
22k-3
56.5c 12
2k-3
Ak-6
h+- c)
d
d6/2
7&d
56. k1- 12
2k-
AR-6
In
(2)
d5/2
Lyd
5k-52 12
2k-3
+ In (2) kte-
6k-
[a S 1
d5/2
xzd
5k-5
+ In (2) 2- 33
d5/2. 2zd
z
6k- 15
3h
[e 1|
+ In (2)
d7/2 IT
F d
6k 15
56.5c -8 98-88
d7/2 Ik
d9/2 x
70

---

Overall we got,
ww -W-- Wxx) W l will (w* Wa+1)) T
-wk)
Wi-1,
2 |w Wk+1ll (Wk-1 - -wk) W + 01 (k) + 02 (k) + (k)
WE Wk+1
(Wk-1 - Wx) T
Wt-1 + 01 (R:)
16
113r72-18
612.46c
12769c12R-30
d7/2 Ikk
d9/2, 1k
d7/2
d9/2
dL1/2
l/ Wk+1ll
(W+-1
Wk)
T
W 1 + 01 (k)
66-5 15
56.5c 0k -18
30
12769c
d0/2. k
d7/2
d9/2
d/1/2
(1) Wk Wk+1 (W
Wk)
W
96c
56.5 18
113c
614c6k-30
+ a1 (k)) di/2. 2k
89/2.10 xx
d?/2
d9/2
|| Wk+1 1| (Wk-1 -wk) T Wc-1
56
+1 (k)
71-1)
18
61-c
di/2
Ik
d2/2
#
where (1) is since d 2 10,000. Focusing on the left terms, we get the overall expression, which we need to show is positive. We again use previousty-derived inequalities, to show,
Wk Wk+1ll (W Wx) W + a1 (k)
=I Wk+Ill (W&-1 - w1))
Wi-1
- (k)
Tt-1
Bk+1 + It-1
82 +
2-2 2 1-1-5 (1 -c)
1-2k-tt
Tk
3
d
2 h (I: + 1)
Tt-1
Bx + 1- $ +
t-2 2 ktt-6 (1 - c)
Tk-1 1
d
h (k)
Tz-1 1
Bk+1 +
It-1
Pk+1
t- 2 1-1 (1 -c)))
I'k
xx
(k + 1)
h (k)
(kk + 1)
h (k)
It-1
8k
3k+1
+ +x--1
3
ok B
Fk-1
J
Fk
(k)
2 Az(a)
( 2
(1 c) c (h (k -h
d
4 (k)
which we will bound separately below.
71

---

I.3.7 The second term, A2 (ke), is insignificant O
(7723)
Proposition I.19. When d 2 25,000,
h (k +
1)
h (k)
14.88 (- 1 12 3f.11/12
A2 (k) It-1
2
F--1
5k
Proof. We start from,
A2 (k) rt-1
(k: + 1)
xx 33
h (k)
I'k
3
Pk+1]
=
- h (1)) Bk+1
3
h hh + [b(k+1) 1)
h (1)
xk-1 Ph+1 -1
B3
Ea(k)
Dissecting the terms in a (k:),
((k-1)o- (K- 21)
Bg
1-c
1
d
+
Bk+1
(kc-
(k- - 11]c2h-3
(ke - (k-
c
2
>0, from L4
1
c
We already showed that _k E (1-
3
(1 +
10
d
1
1/ )
and we simplify it further:
#k-1
27
1/
Tk Ik-1
Bk
- 1+ 10
(1+
8x
- (1
10
3x
1
1
2 kk-
K-
1
x-
d
x d
(1+ 19)
1210000 2
[ 2
0.45] 2
+
1- 4.95
(0.45)²
(0.45)²
1 d
Now, using the algebraic incquality Vz E (0, (1 - 2)² = - 32 + +32² -23 > 1 - 32, we get,
x 1 - 14.85
Moreover, recall that we already showed that 1(k+1)
2 c
2k50
1i oF Now, focusing on (k).
A(R]
h (k +
(k) =
k
h
(k)
kk-
B2
kK+1
-h-
2V
(1 - 14.85,3)
1
25-
(1 14.85,3k) 1
c
2h d
2k 5
2
(1 14.853x) 1
d2
5.5c 5.5c2k 2k-5
81.675
14.85,3
1k
x b
d2
x2 22
5.5c 29-9
- 14.85
22 &
226-5
2k-5
2k
14.85
2.
BK <
2
2
d
d
1 o d
d
(0.45)² d²
14.85 2k-5
27.17
14.
27-17
d2
d
d2
14.86
p 2 10,000]
IV
d
72

---

And finally,
1
14.86c
A2 (k)
(k) 1 - (k) 2
h (k)
-1-1
2/
d
va
+
29/2
5.42
14.86c 2k-9
2k
14.86
1 5.42
14.86c
M(kss
k-3
2
d²
d
K
d5/2
d
T d7/2
d
14.86c 3--2
80.55c2k-12
l<< [c<1]>
x//d7/2
1//9//
1210000.
14.86c2h-12
0.0081
23k 12
(14.86
0.0081
3k--12
c =0.5
d/d
2//0/2
x2d7/2
14.88x 1c 12
A2 (k) 2
xfd//2
thus concluding this part.
I.3.8 The third term, As (k)), is insignificant O (31r2))
Proposition I.20. When d 2 25,000,
t - 2 (1 c) c (k - ch (1)) d
/c -
5.42 d//2
AAg (b)] =
x/
d3/2
Proof. Notice that,
1 - 2 (1 c) c) c (h (k: + +1) ch ch (A))
|Ag (k))
-
(1 c) c 1 (k + +1) ch (k)] S (1 c)
c 6
// + 11
ch (k)]
d
h (k)
h (k: 1)
k-3
5.42)
11 (k +
In (2)
S In (2) +
h (k)
d3/2
d5/2
(k)
where we used the facts that 1 <
2n2 d
and h (k) < vd
5.12 29/3
Using
A(k-1)
h(R)
[c-
" d C
2 d
2.44
we finally get,
k-3
5.42
(k: + 1)
A (k)l < In (2) h+e-6
d3/2
d5/2
h (k)
5.42
5.50 2k-5
2.44
In (2) 6+
d3/2
d
max
1 d2
c/.22k
11c2kk-3p 3dd2
[a < [k-1] S In (2) 6t--- 6
5.42
2k-02k-B 5
2.44
d2/2
/
max
222- 5
<<< 11 5 In (2) 6
[e<1]]
d7/2
d
5.42
max
2.
2k
2.44
62k
In (2) k+
5.42
5.5
mk- > n 3 k2 c c<
cd7/2
d9/2
max
9.76
<2 1-1100000 > 0.9999
In (2)
k k
0.9999d7/2
1
+
d
5.42
max
0.9999
5.5
9.76
6.77 6-1-6
5.42
z1
d7/2
d9/2
73

---

1.3.9 Back to the first term, AA (k))
Proposition 1.21. When d 2 25,000,
h (k + 1)
(k(k) Bk+1
0.0429
173.07c 3k
A1 (k) Dt-1
8R
2 xc-1
x8d5/2
x/
I'k
Proof. We have
1 (k: + 1)
h (k)
1t-1 11 (1)) Bk+1
Fk h 1 + 1)
Bx
A1 (k)) = It-1
3x-
8k+1 =
Ik-1
It
31e
Ik-1
h (k))
BK+1
(0(-3//2)
Aa(k)
We are going to the previously-derived lower bounds of _
2 1
3x (1
12) o and
zk-1
x
h(k-1)
,d 5.5
To lower bound 3e11
f 2 + (T-R(1-))cc we need a slightly stronger
h(k))
bound than before. Specifically, notice that for any (0, 1), T- 2 2. Then, since 1
[2)
In (2)
2n(
k (1 c) E 1 (2) _े In (2), 2 In (2)] C (0, 1). and
d
2d
1-c
1 k c)
1 c Σ (1 c)
(1 (1- 1 (1-1-c) c2)
2 (1 - 1s (1 - c)) 2²
c²
We now get,
Bk
1 1-c c 2 c
Bs+1
2
6² 2
We are now ready to lower bound (k) as,
Ikk
h (k + 1)
3k
a (k))
1
-
h (k)
B
+ 10
32
5k5
2 c c
1
c
-1 1
x
d
Fk-1
x 1 o2
c2
Bk
10
82
5.50 2k 6
2 (--6) c
+
1
1.
I k-1
d
I k-1
2 1 d2
Using Claim
1.9
2-c
-
1 = 2. 2./1/d 12 2
1 +
1n(2)
1 =
In(4)
d' we get:
(1 1+
10
86
(1
5.5c 2k
In (4)
a (k)) 2
1
1+
1
d
I/-1
x d2
d
In (4)
3k
5.502k
(1+ 10 32
In (4) 3x
d
2 1 d?
x d
k-
Old 1)
@(d-2)
BB
5.5 In (4) 26 6
(1
10)
d' In (4) 82
5 1
x2
d3
xt x dd
O(d-3)
5.5 (1 + 10) 2
G 32
5.5ln (4) 2k-6
3k
22
k d2
1 d3
Ik-1
2
Fk-1
Old 4]
74

---

Lower bounding negligible positive terms by 0, we get,
(k) 2 In (4)
3x
(1+ a Bk
In (4) 3k x d
x--
I 1
1/
Old-t)
@(d-3)
5.5ln (4) 28-6
(1 10
d In (4) $
8h 1 d3
2 = d
( 8)
We will now simplify the least significant terms above further. We start from an upper bound to the e (d-2) term (since its sign is negative in the expression above),
(1+
1
In
(4)
Bx
1.001
In [4) Bx.
+
2 d
1 d
I - -- k-1
k-1
22
1
5.5c 2k-
1.001 4K-10
In (4) 2k
Ik-1 0.45
S
d
cd'
2
d
" d20.453
1 d2
26-6
$
(5.5 + 4.95c. 2k-1 + 1.1... c)
d2
26
11. 11.84c20 2k
[ 2 2, c5
(5.5
4.95
#
d2
x² d2
Similarly, for the θ 3d term, again employ the upper bound 3r 2h
S
1 od and obtain,
5.5 In (4) 26-6
(1+ 10 In (4) B
5.5 (4) 24-6
1.001 In (
2 d
2
2k-8 8
9.02c 2k-2
(5.5ln (4)
1n (4)
(4,5l 1.001 In (4)) S
_ d3
2 d3
And so, we get the following lower bound,
In (4)
BR
11.84c
2
a (k))
d
x/-1
x
1
xt_ d3
In (4)
2k-6
9.02c
[ S xK-1
11.84 +
d
7
x
x
Back to the overall term we are trying to lower bound,
h (k:
+ 1)
(k)
IK (k + 1) Bx
Ai (k)
3x
BR+1
(k) BK+1
T1-1
Fk-1
I
F2k
Fk-1 h (kc
Bk+1
Aa(k)
1 h (k) 3
In (4)
3k
22
9.02c
11.84
d
T..2
x
1 h (1)) 9k+1
In (4)
3x
2k-6
9.02c-2
h (k)
3k+1
11.84 +
d
of.
zid
(1) k-3
3k+1
In (4)
8x
1
N-B
Vd
8372
5.42
2h 2k-6
11.84
9.02c
Vd
x
g d
x2
(2)
1
In (4)
3k-9 9
9.02 22/ 20/00000
BK+1
11.84 +
Vd
d7/2
0.45²d
2R-22--6
9.02
11.84 +
2/
0.452d
75

---

where (1) is since h (k) Furthermore,
cct-a va va
c/=
+
5.42 2372
BB41 S 2: (2) is since 2 10,000 and zą 2 0.45.
1
Ai
(k)
34
1 k-3
In (4)
8x
11.84c
44.55c
64.18c2k-6
241.4662k-6
BE+1
Tk vd
d
2
2//
x//0/2
2/
x/d11/2
1 k-3
In (4)
3x
11.84
44.5562k-9
64.18c2k-9
241.46c2k-9
BN+1
Kk Vd
d
xidi/2
xg/0/2
x//0/2
x/d11/2
(9) h-3
In (4)
8k
11.84
109-28-9
Sk+1
Tk Vd
x2d7/2
x/d0/2
where (3) since d 2 10,000. Overall, we get,
21- C-3
In (4) d
3k
11.84x, -c 3h
109r, 1
20-9
A1 (b) 2
3k+1
Ik
Vd
x xkd7/2
x d//2
It remains to get a lower bound for Bk+1
(-d
In(4)
d
2/
First, we show
In (4)
8k
In (4)
(1- (1
c)
(k
1))
2h-
b (1k)
d
Kk
x
In (4)
2k-5 5
1
k1
(1
c)
4
d
x d
c2c3
d
In (4)
2k-
1
1 1-6
h
-
d
aRd
x c
where we used an algebraic property that - 1, Vz E [0, 1]. Continuing,
In
(4)
2k-5 5
In
(2)
In (2)
k
(kk)
2
R
4
d
2d
In (4)
26-5
In (2)
k
In2
(2)
1: 1
d
c
d
d
In (4)
22
In (2)
k 1
In² (2)
k-
Jc < 2
d
zRd
In (4)
226-5
In (2)
k -
Ind (2)
8 (0.45) dd2 .1
d
zid
4
In (4)
22-5
In
(2)
k -
0.3
In (4)
(2)
k-1
2k-5
0.3
+
d aid
4x
d
d
d
4
cdd
Below, we are going to use the closed-form approximation
of JA. for which we have established 22 < 2x + è (Claim 1.10p. Also,
[2 Exl < 170.4 c (Lemma J.2). and also note that !
recall that, Zt = V ln4
m4
Ind
2k
m
We now use these
76

---

relations to further refine the lower bound on b (k);
0.3 In (4)
In (2) {
2c
4x In (4) + In (2) (}11)
2c2
b (k))
dd2
d
4x
4 In (4) + In (2)
((=ي) 2626-5
4h (4)
2 222
4x
4x
483 in (4) + In (2)
1 2626-
(4)
d
(2 + 2?
4 d
202 4 (4) - 1 2h (1 - 2 In (4))) + In (2) {-2)
2²
In (16)
4
rnd
1.545 + In (2) ( (bg)) + 2h (1- - In (4)) - 2k25-5
6²
In (16) e
4x d
27 d
xRd
1.545 + In (2) ( ((
2k In (4) 2/2
26-5 (1 (3))
2
In (16)
4x
2 d
b d
r&d
1.545 + In (2) k-1
2h In (4) k
5 (2) 2h-5
2
In (16) e
4r
d7
xx
and
Focusing on the left nominator,
(k=1)
( d
) 20 In (4) k = =1545 + In (2) (2
(
d (1: (A-1)) 1) - 8c h:)
1.545 In (2)
d
d)
1..45 + In (2) (1-8822)
k 1
1.545 In (2) (1822 -1) k
" + d
d
= 1.545- - In (2) ((s 8. 4 h -
k
+ 41)
1
d
d
To upper bound g (xx) = Sx 4 (inside x E [0. 1)), we show that
x (1 - x In (4)) g (x) = 8 4- 8x In (4) 4- = 8 8.
solved by
1 In) which falls inside x E [0, 1]. meaning it is a global optimum.
The second derivative is
g" (x) = (8 18-4-=--0 8ln (4) 4 4-xx)² = -2-22== In (2) - 8 In (4) 44)4444- # (1 - x In (4)
1 22-22-m) in(3) In (2) 16 In (2) <0,
9" In (4)
ln
meaning that the x = In(4 is the global maximum. Also note:
4 प
= 4 = 4
4
So overall, we get,
1.545 + In (2)
h: 1-1)
2c 2h In (4)
k 2 1.545 - In (2)
(
(8.4 -
2/2
k
++ d
1
d
d
2 1.545 - In (2)
((..4- पेे -1)
1
+ 1)
= 1.545
In (2)
In (2)
88 (8-1) E
In 4
2ln (2)
0.7
0.7
2 1.545 0.972
2 0.573
d
d
Finally,
0.3
2
In
(16)
5l
(2) 2k
1.545 + In (2)
In
(4)
(k) +
+
d
x d
r&d
x d2
4x
0.7 0.573
0.14325
0.175
d
4x d
x7d
77

---

Going back 8k+1
In(4)
3x+1b (k), we have
d
=
0.14325
0.3
è²
e
eln (16)
5 (2)
2k-5
0.175
Bk+1 b (k: 2 Ba+1
+
+
+
and
d2
2&d
x
00.14225
0.3
e²
eln
(16)
5ln (2)
0.175
[c 1, k 2 B
aLd
afd
red
co
x
0.14325
1
(0.3z
e
eln (16)
5 (2)
0.175
= BK+1
agd
Tk
d
IRd
d
c d2
and
0.14325
1
0.3
eln (16)
5
(2)
0.175
e²
[0.45 < Ih 1 <1] 2 B
+
aRd
d
c.
0.45d
0.45d
0.45d
0.14325
1
0.3
2.78c
7.71
0.39
2.3c
2 Bk+1
e
d
cd2
d²
d
Since c = 2-
1/d 2 0.9999, AA
2
10,000, and plugging in
170.4,
d
In (4)
3%
3R+1
d
0..14225
0.3
2.78
170.4
7.71
0.39
2.3
170.4
2 8k+1
+
xRd
Fk
d2
d²
0.9999.2
d²
d3
(0.14325
482.2
66783.17
2 8kt1
xgd
Ikk
d²
d3
0..14255
1
488.88
88
))
Bx+1
0.14325 488.88
B
xRd
Tk
d²
Zzd
Ik
d
where (1) since d 2 10,000. The inside of the parenthesis is positive AA can bound the expression by lower bounding 27
3413, So
0. 14325
In
3k+1
0..4325
488.88
0.
00.14255
488.88
Bx+1
2
axd
d
d²
and
00.449
146.7
2 2k-3
x&d3
And then,
1 k-
In (4)
11.84
109 9
A (z) It-1
31+1
Zk Vd
1/12
x2.0/22
1 6-3
00.0499
146.7
11.84c
2k
2 8t-1
21-33
Vd
x2.22
F.
x
x2.9/2
c.04
146.7c
31.84c
20
T1-1
22/15/2
af/d7/2
x2/77/2
0.0429c23--
146.7.3k-9
31.84
309
C<< 1 xt-1
r2/5/2
zi.d'/2
c 2
11)
0.0429
146.7c3k-9
11.84.3k-9
10
Σ1-1
x2/2/2
0.45x22d'72
0.5
0.45.x2.092
0..042963--
17
484.45
2 It-1
r//5/2
2/.0112
0.0429
c 3k-9
(d 2 10,000] 2 xz-1
d5/2
2//d7/2
where (1) since o 2 0.45, c 2 d = 0.5.
78

---

1.4 Conclusion
We are reminded that we want show positivity of A
Wi
w (Wk-1 - Wi)) W(-1
|W-- Will (W* w Wr-1- Applying Proposition
L.18
we show Ak 2 t:
4 - |Ws - W || (Wi-1- wx)² Wi-1 ||
wxll (Wx
Wk+1) Wr-1
2 A1 (k) A2 (k) + A3 (k)
1
66c6k-15
18-18
56.5c
+ 6k-c
d2/2
Tk
19/2
(1)
A1 (R:)
+
A2 (R)) + As (l:)
1
96c 6k-15 15
113c
7k
76 7k
+
dT/2
13/2
3k
(2)
A1 (R))
+ Ag
(k)
+ As (k))
1
96c 1kckk-1
+ 7k-18
Th-18
/56.5
+ 614
1.00007 2)
d7/2
1//2
(3)
A1 (k)
+
Ag
(k)
+ Ag (k)
1
16c6k-15
+ 11-
Th-
56.5
1238.36
d7/2
0.45
d
0.453
2 A1 (k) + A2 (k) + As (k)
(213.34c 0k-15
+ 113c
7h 18)
d//2
d9/2
(4)
2 A1 (l)) As (1) + As (k)
(213.34c
6h-15 15 113.19c
d//
where (1) is since < 1, k > 2; (2) is since 2/100000 < 1.00007, c < <cd 2: (3) is since
Tk-1 2 0.45; and (4) is since d 2 10,000. Plugging in the results Propositions [.19] 1.20 and 1.21
we derive
A
|| Wi+1 /| (WK-1- W || Wall (wx wk+1)
Wr-1
0.0429
173.07c3k-9
14.88r, 14.881-1c26611
5.42
2 Tt-1
x/d5/2
xidd/2
xtd/22
d7/2
d9/2
(k)
A2(k)
Ag(k)
(213.34
15 113.19
d7/2
0.0429r;-100
3k-66
173.070;-1(2k--
14
6.77ck+1-6 3k-12
(
5.42
=
d2/5/2
2//
x2d712
di/2
+
63/2)
6k- 113.19c
d//2
3.0429a3k-6
173.07x;-
99-9
14.88k, 1
3k-12
6.77c
1
5.42
+
2//5/2
x2/'/2
1./d1/2
1t
dl/2
29/2
6k- 15
+
113.19
7k-18
d7/2
3.
2k-
34-8
6.776
1
5.42
2//5/22
xfd7/2
x/d7/2
2
d7/2
d//2
6k-1
7h-
1//2
(3)
0.0429
173.07
34.88
6.78
2/2
x//7
22/71/2
xf
(213.34
1 7k-188
18)
d7/2
79

---

0.0429cth
14.88c
#112
6.78c
22/d5/2
2/.07/2
x//11/2
2////2
0k-13
+
113.19c
2/
0.0429
173.07
2 6/2
14.88c3t-12 12
6.78
213.31c 6k-15
7 7k 7k-18 18
+
Fk
(..0429 6
173.070 3k-9
2 //2
32-12
6.78
+ 2t
2
0.45
0.45²
3. 3k-0
(173.07c
24 d5/2
d
+33.07c
36-12
12
+
+
11
3
1
0.0429
(173.07c-3
x 15/2
d
+33.07c
+ 33.49c
28+
213.34c
19
3k-6
0.0429
(173.07c d
33.07c- + 33.49c
213.344
113.19c
//2
W3
3k-6 6
1 (173.07c d
0.0429
33.07c + 33.49 44 213.34c + 113.19c
d/2
3k-6
0.0429
(173.07 -99.09--.9999- 0.9999
2//5/2
d
+33.07 0.9999 6 + 33.49 - 4 + 213.34 0.9999 -3 + 113.19 0.9999 ()999991))
where (1) is since Ø;-1 > I&: (2) since 2;-1 S 1; (3) is since 2 10,000; (4) since 23. S 1;
(5) is since æ4 2 0.45; (6) since e < 1, 2 2; (7) is since c 2k = 4h/d < 4; and (8) since d 2 10,000 = 2 0.9999.
Finally, we conclude that,
3h 3k-6
666.82
DC.
0.0429
(13)
2 d5/2
d
Hence, sufficient condition for [W].
Wt
We
We 11)
w. to be positive and monotonicity
We.
Ww We+1
to hold, is that d 2 666.82
0.0429 = 15,544. Since this is smaller than 25,000, this concludes our proof
of positivity of At,
80

---

Lower bound technical appendix: Properties of the recursive construction
This section complements App. E.1 by confirming that the recursive construction introduced there is well-defined; readers are encouraged to review it first for context.
Specifically, we prove that the recurrence defining the sequence (æx) is well-posed, in the sense that the square root always taken over a nonnegative quantity: Lemma J.1 (Existence the recursive sequence). Given the sequence (1)) recursively defined by
31 1, Ih Zu. 1 - 1h-1--4h 40x
Vk {2. ..... ., d3 where 2 2-1/d and Bg. & ([k-1)e- (k)
we have Ad 2 30, Ak E (2.... df that
x 48k 2 20.
In addition, we prove the following lemma: Lemma J.2 (Approximation by closed-fomm reference). Given the sequence (z), recursively
3h V -8 Ak E (2....,d) d} where c - 1/d and Sx. -
defined by 21 = 1, Ik (k-1))--k-2))ee-- and the sequence is
2
44-
( In4 $), have Vd 2 30,
vk E [d]:
170.4
22
Exl
d
Before proving this lemma, we note the following will immediately hold:
Corollary J.3 (Lower bound on x&). Vil 2 25,000, vk [d]: a 0.45.
Proof. Zд is decreasing (Claim 1.5
so Vk E [d]:
170.4
170.4
Zb Zd
Iz
+
4-1
In4 -
d
In4
[d 2 25,000] 2 0.45.
This bound is extensively used in the proof of App.
J.1 Proof outline
First, we show the above holds numerically for 30 < d < 100,000, as can be seen in Figure 26 We then prove analytically for > 100,000, by constructing ODE for which the sequence (x), serves as an Euler trajectory. We then bound the distance between the solution to this ODE and a known function ā (7). Combining this bound with Euler's method global truncation error bound, we obtain a bound for the distance between (x), & and (T) We then use this bound to show the existence of the sequence (x)), for all is E (2.....d).
Computational resources The numerical validation took 6 hours to run on a home PC with i5-9400F CPU and 16GB RAM.
10a
4.25
Rel-
Distance
10
4.00
max X
3.75
Xel
10
KEldI
3.50
170.4/d
102
10a
10a
10a
10a
10a
10a
10a
d
(a) laa Øxl < 170.4 derived upper bound.
This is a loose, analytically
(b) Actual upper bound is <
4.5
d
Figure 26: Numerical proof of Lemma J.2 for d<1000,00. Using the recursive definition of æk. we calculated the sequence for each value of d, vk E [d]. and compared with ã..
81

---

J.1.1 Euler's method construction and bottom line
Here, we leverage the global truncation error of Euler's 's method to establish the bound. The auxiliary propositions supporting this result are proved in the following section. Define
f (T, = d V02 4,3 4.3 ( +))
2 (T) (dd-1))2 (dT 2)) 2 2(5-2dr)/d
d
Then, using step size of h d in Euler's method we have the iterates
Ik+1 Ik + h (Tk,
7++1 = Th + h,
and thus
Th+1 Ix + 4 43 ((+11) 3k
2 +
2 43x+1
2
2
which are exactly the iterates we want to solve for. These are the Euler's iterates for the differential equation
(T) = (T), (0) =1
(14)
While it's hard find an exact solution to this equation, proved that for d 100,000:
38.9822
Ix (T) - (T) d
Proposition 1.19 where we define the function suggested in Hucht 48
3 (7)
4-
In 4 7
In
such that Gt # (7) Next, we bound the iterates using the global truncation error of Euler's method, obtaining
F k:
131.3685
Combining this with the previous result, Proposition
J.26 yields
131.3685
38.9822
170.4
[ -ul <
d
d
Finally, we use this bound to show the iterates exists vk E [d]
82

---

J.2 Full proof
J.2.1 Auxiliary propositions
We begin with preliminary claims and move on to the propositions used in the previous section.
Claim J.4. (d) -d (1 (-1//) is decreasing Ad 2 1.
Proof. (d) 2-1a) ((-1) to2 1n2 1n2.2-1/4 21-111/ + 2 1/d
(1- ln2) 2 2-1d < 0.
Claim J.S. Ad 2 1: d (2 1) 1n
Proof. Using Taylor's expansion:
22/d cd =1+ In2 +
8
In2)
d (2/// -1) In +
2
8
1 (ln
In 2.
i! di
Claim J.6. -d ad11211/44 2 - 2 (alternatively: 2-1/d > 1 1n2).
Proof. From Claim J.4 we know that dd (1 - -2-1/d) is decreasing with d, have,
2-h -1
2-h - 20
-d (1 21-2-111
lim d=
d (1- (1-2-1/d)
lim h-
lim h-+0+
h
We recognize this as the definition of the derivative of 2- for x = 0+, so we have:
lim -d (1 (1- (1-1///d) d+000
dr (x 0+) In2 2 2" 1n d (2-
Claim J.7. (T) > 0, decreasing and convex for < In2
Proof. Reminder that (T) ((dr- 16d--1121144 1/4 -dr (dr 21) and d > 1.
Denote 3 (r) f (T). where f (7) (dr 1) 11d /d (dr 2) and g (T) 2dd
We have VT, g > 0.
Note that from Claim J.6 1n < 2-11/1 1/d < 1, so:
1n2
= dr - 2- 1/d 11d dr +2 1
dr - d7 dr +2 -12
d
so / (7) > for + < - Thus 3 (T) > 0 for - < m
Now we note that (T) d (2-1/d 1) < 0, vd 2 1, VT and g'( -22 2 2 24
0, Vd, VT
So:
(7) + <0,
as long as g (T) 0 and (r) 0- which get for T
1
83

---

Now note l" (r) and g" (r) 41n 2. 2d > s0:
(T) (r) 3"
ã ())
as long as / (r) 2 which we get for 1
Claim J.8. (r) defined by the ODE in Eq. 14 satisfies the ODE (0) 1, (r) = <dVu>-a(T)
g())
2
with (r) 4,8 (r + 4). We also have:
23/4
PA 2
max 9 (8) - g 4
E
[0011
Proof. Substituting I' (T) d 433 (T + 4).
18
-
in x (T) d n² g(r) x
we get g(t)
2
We get from Claim J.7 that decreasing, so: For [0, and d 2 3, r + / S In
max g (6) (0) = 43 2 = (1--) 1) 2 1/4 (1 2)) 2 20-- 2)/d ac[0,1]
23/d
d
Remark J.9. The solution the ODE (T) (T) = -f) x x0) is
x (() = v -2
1-2 //" (s)
Claim J.10. VO Saspssi: 1-V1-a S a5
P
Proof. The right side inequality is trivial: (1 (1= = a a > 1 1 aVI-
For the left side: denote f (a) = VI a. f is concave: (a) = =- 2v110' f" (a) So we have 40 < < - 1:
2 a 4(1aa)
$
V1-a= (() (n 1 a) (0) + +af af(m)
r
= a
Remark J.11. The solution the ODE Eq. (14 is only defined when the quantity under the square root remains nonnegative, i.e.,
(² 2 48 T 2
Given that (0) = 1 and that 4,3 (2) = 23/4
for all d 2 6, i.e., a. (0) > 4, (2) strictly, from
continuity we have that =<()) 2 / 43 (T+ )) 0 for all E [0, <]. for some ( E (0, 1]. Going forward we focus on [0 when stating facts about x (7), and eventually show that Ç 1 in Corollary 1.23
84

---

Proposition J.12. Assuming VT E [0.4] 0 v
2
I 1 and x > 0, the solution of x (0) = 1,
x' (T) = dv (F--(())++
holds
2
vI 1 S
1 d
2 - 9 (s) ds
x (T) E
| d
(s) ds.
1
for μ _ max 9 (x)
sE|0.5] x (s)² 2
Proof. Let 0 S p S 1 such that V/ E [0,5] 0 V
g(T) x=
S S 1. From Claim J.10
we have:
1 1 - v1 ugl (T)
g [T)
(T)
1
1
x22
x2
2x
(1- 1 v (T(
(T)
1 9 (T)
20 S x
x
x²
x²
2x
vI
(T)
9 (T)
S x2 - (T) S x
1
x
2x
V
Mgg (T)
I v2² 9 (7) - -x (T)
x
2x
VI
(T)
12 g (T) σ 5
dg (T)
< d
2/
2
4x
(VI- 1) dg (T)
dg (T)
<
2p10 (T)
4x (T)
(V1 u 1) dg (T)
dg (T)
S x (T) x' (T)
2p
4
where the last transition is valid since x > 0. From Remark J.9 we know that the solution to the
ODE x (T) (r) = (x)) (0) = 1 is x (T) = 1 2 2 f (s) ds. Put differently this means
x (r) / 1+2 (s) x' (s) ds (when x (0) 1). We aim to plug this into the inequalities,
now achieve the required form:
1 (VT 1 -1 dg
ds S [ x (s) (s) < [" dg (s)
ds
2/
4
1 2 d (1 vI - 14) (s) ds $1 l' x (8) (8) ds 1 1 - 2 [ d
J 0 (s)
1 1 vI 11 11
S' (s) ds $1+2 [ x ( (s) ds < 1
d /''
g g ds.
ds.
P
2
Denoting A 2 d fo ((s) ds 2 0, note that for the LHS,
- VT P A - (N- (M- A+ A 2 (μ A+ A(1 1)) = 0.
Hence is legal to take a square root:
I 1
S' (s) < 1 1+2 /// x (5) (s) S V 1- 2
d l' (s)
Finally, plugging in x (T) / + 2 Jo x (s) x (s) ds. we get:
-I
# [ g() (z)) = / 1-2 2
1 d S gs) ds.
85

---

Proposition J.13. For d 2 100,000 and r E [0, 0 - d So (s) ds - 1.5821.
Proof. For T [0, and d 2 3, T d In
We get from Claim J.7 that 3 is positíve and thus 0. For the right side inequality, we have:
d g (5) ds 4d Ju (s+ + 2) ds
d L 9 (8) 4d !
3
8 + d
ds
[820| v 4d
+ ds
4d f
((ds 1 - 1)2-1/12 1/d
(ds + 1 - 2)) 2 - 2do 23/d
ds
d
2 2x dd1- (1-2-1/0) / 82 20
22/////
(1-27
2 (1 11-2-114 21-2-1/a)
2-25 (sIn
23/d
In 0
In
d (22/d (plld-1) [
(In 4 + 1)
4. 22/d
22/d 4ln4
41n² 4
From Claim
J.5 we know that dl (21/d_ - 1) 2 In 2, So:
d (s) ds s 4d f 3
( s+ ds S 4. 22/d
3
In 4
2 2//d
In
4 4
4 4n
3 4
[d 2 100,000] < 4 22/100000
21/100000
ln2
< 1.5821.
4 4
4ln
Claim J.14.
1-v1-x
S z for E (0,
2
Proof. Note that
1 v1
+ v1 1
x
1+ 1+ --x
x
so we define a (x)
A
1+v1-7
This function is monotonically increasing, continuous and convex for x E [0. 1]:
d' d((x)
2
(1+ VI 2-
-1 2 22 (1+VI-2) +2 21 v1 2/1= 2
d' (x)
4(1 - x) (1 + v1-x)
VI-Z (1+ 1 -
2 + + (1 + v1 -
2 0,
4(1-x) (1-x) (1 + 1-xx)
and thus from convexity we have for x E (0, 1]:
/I (x) < 2) a (0) (1- x)
1
1
za
+
r
2
+ 2 1 T 1
xx.
2
86

---

gis) Proposition J.15. For d 2 100,000, μ - max,e x(+)² _ 19.
Proof. From Remark J.11 we note that a (7) positive, and since 3 (T + 2) > 0, we know x (7) is
decreasing in [0, <] (Claim J.7j. and thus the minimum of x (r)² is (S)², and (C)² - x (0) = 1.
Applying the upper bound of g (s) from Claim J.8. get
4 2//4
9 (s)
I maxx
# A max
sEJ0,
x (s) min (s)) (C)
From Proposition J.12 we know that V1- Vi-a'-vI-
- I- (() ds S x xC).
Squaring both (positive) sides, substituting and denoting A = =d dō 9 (8) ds, get
1 -I- A < x (C)²
Note that A 2 0 (from Proposition J.13
and that f (4) A 1-vI- increasing, since using
12
Claim J.10 we have f (u) 2 2-2-2/1-E
2- 20122)))/)) 21-
0. Combining these and μ S x(C)²
21-11-
we get that,
42d
[())²
VI
AS
A S (()²
20/4 d
(C)²
4 12// d
4 20/2 5
23/d
A AV
S 4
x (C)²
2
(C)
Av
4 20/4
S (C)
(x()) 1) A. 4
23/d
1
23dd d
For simplicity denote =(() r
Recall that = 2 1, and are looking for upper
bound for it, so we can have a lower bound for x (C)². We have:
A (1 -
A)2 = = (z 1)2 2Ar (a 1) + A2
- APrr S x²2 - - + +2Ar
05 02 (A2 24
- 2r)-rr 2A+T.
2r)
A) + v (2r A A))² 4r 4r 4r(A 2r A (2 -))
Finding the roots, 21,2
2r
Since we are looking for an upper bound, we care about the smaller root:
2 2r A A) 4r 4r (2 A) + A2 A)
A
4
2r
2r + A A A)
A2
A2 (2 A)2
A(2 A)
4r
= =1
1
1
2r
2r
(2 - AA)
87

---

4-4 25/d
For 2 100,000,
4r
4.4- 100000 (2 1.5821)2
I 10-3 < 1, (we used Proposition J.13)
(2-4)²
(2-A)2
can apply Claim J.14
A (2 A)
4r
4r
+1))
A
4.Ar
2 2 1
=1+
2 A)
(2 - A)
2 A
(2 AA)
-5..11100
d2 100
$ 1 +
2 A
A
4
4.1 10 5
(2 A)
A
1.5821
1.5821
AA$15582
1
+ 4.4441
4.1 10 5
S 4.7894.
0.4179
0.41793
23/d
19.1576
23/10
19.158
Then, for d 2 10;; x (C)
S 4.7894
= p S 4.7894
S
d
d
Proposition J.16. For d 2 100,000, we have Vr E [0,c] (T) - 11- fo (8) da 5 33.1
Proof. Denote A d So 9 (8) ds. We know that
(1 VT
1
1
AA
x
V
1
2
1
1
(1- -I A
(T)
V
A
<
1
A
V
2
2
1
(I-VI-A)
1 1 A
1+
V1
1 A+ +
(1-v (I-vI-R)
2
VTv A
(1-vI-p)
1.4 A+ + V
1
A
1--I--
From Proposition J.13 we have for d 100,000 that < 1.5821, then
1.5821
V1
14
1666
3.4611.
We further know from Claim J.14 that 1-vI-#
デ for E (0, 1].
Combining these and applying Proposition 1.15
we get:
3.4611 19.158
33.1539
x (7) V 2
A $
3.4661
2
2d
Claim J.17. Vo E [0, 1]: 2 < +
Proof. 2n is convex, so we get in [0, 1]:
2 < (1 x1) 20
x2 = x
22 =1++ ++..
88

---

Proposition J.18. For 2 100,000, We have ((T) - Vi- 2 So (s) ds S
5.8283
d
Proof. We are reminded of the following:
((r) = V 1 1n4
+ 4-
In4 [7)
(r) ((dr - 1) 11222 2-1d
(dt - -2)) 2(5-2dr)/d
d
(()) = 43 (++ (1)
(d72- 1/d (dr 1)) (33-2dr)/d
d =
d
Define ( _ J0 (s) ds, B (T) = 1 --
lnd
ln
We have (() B (0) 0, and (T) B (T) is non negative and increasing for T E [0, 1]:
- (T) d
d
dr 2 (7) - 4- (2 12-1ln4)
(d72- 1/d (dr - 1)) 2(3-2dr)/d - (2 - rl14)
2
d
= -" (2(23/0 11) -1) + 7 [In4 2- 2. 2./ (0 -
-2- 2 2-1/d)
If we assume 4 > 2- 23/d (1 (1- - 2 1/dd, then the derivative is in fact positive and we are done. If we assume the opposite we have:
(T - (r)) -4 (2 (23/d 11 (2. (3/23/d 23/dd 2112-1/0 lm4)
dr
{ 1] 2 7 (2 (2(23/ -1) - (2/.2// (1 1--2-1/0
- -nn
-4 (3/2 (1- d (1 (1-2-1/4 1-12 - ln4)
J6
> - 2 23/d (1 (1-1n) 2n) - 2 In4)
2 -- (2 ln2) - 2 In4) 4- (2 - In44 0.
This means that
0
B (() A(L)
In Proposition J.13 we saw that:
J g (s) ds 23/2
2//d
3 In
4 4
4ln 2
3 In 4
A (1) 22 22/d
21/d
ln
4ln 4
4lm 2
1+ (+ 2)
3
(1 + 1)
[ In 4
J.17
d 2 2, 14= 2m2 <2
ln2
8ln
161n _
=2 1+ 2
6 6
3- 3n1n4]
= -1+ d
2
[3 In 2 +
d
16 l
16ln2
8ln 2
89

---

Subtracting B (1) we get:
3 + 21n + à
-1)
A -
5
1+ d
8ln
In4
4
1n4
2
3 + 2l d
3 2ln2
8ln2
8ln2
6
2
3 2 2
d In 2
d
8lm2
2.6641
[d 2 100,000
v
d
leading to
2.6641 d
0 -
Now note that,
d o
1- B1)
5 (T)
(s) -I- -11--(()---AGG)
VI-A())
V1 - 11-B((++v1-(77
A(r) (T)
VI- A(T (T)
Since 0 S (T) B (r), we have & (T) V
2 So g (x) ds. Lower bounding the denominator:
d
1
AI- VI B
V1
(T)
+ 44-
-T)
In 4
In
1
+
4-11
In 1
> 0.4571,
1n4
and so,
2.6641
5.8283
0 5 (s) ds <
0.4571d
Proposition J.19. For d 2 100,000, we have VT E [0, | (T) x (T) <
38 98.9822
Proof. From Proposition J. J.18 and Proposition J.16
d
d I' g - ds)
(7) - xr (r)
(7)
% ( ds +
2
1 d f g (8) ds
d
L g ds x(7)
< (T)
+
2
2
5.8283
33.1539
38.9822
Corollary J.20. For d > 100,000, we have VT E [0, <), (7) 0.4567.
Proof. Note that (7) In4 + - 1 - 7) is decreasing for 7 E 10,
- (2 T In 50.
H' (T)
2 m + mm
90

---

Note that it is lowest at 7 1. Combined with |z (r) - 2 (T)
38 9822
we get:
38.9822
38.9822
x 2
2 0.4571
1
4
In4
d
38.9822
(d 2 100,000] 2 0.4571
2 0.4567.
100,000
Claim J.21, For 2 b2 va va- Vb.
Proof.
Va- va-b= (10a-V(Va-VV) vō) (va+ 2 v(va- vb)- =vā vb.
Proposition J.22 (Existence of the solution to the ODE). For d 100,000, we have a²()) 2 4,3 (T + 2), Vr [0, 1].
Proof. Note the following for T Ç:
x 2²(()) 2 0.45672 > 0.2 > 4 2
48 (+ )) (s+
d
for d 2 100,000, from Claim J.8 and Corollary
1.20
From continuity and the strict inequality, there
exists such that Vr E [c,5 0]. x² (T) 2 43
(T 4). Observing the definition of the ODE
Eq. [14]] have the following for all E 15.5 5]:
x2 43 (T + 2)) x
s' (7)
2 / (T+
2)
2
-488 T+ d 2 dl
V2d
V
= x (C) 22d - (T 2 0.4567 - 22 (T - ()
We can show that 2 0.3 by showing the solution must exist at T = Ç + vd
0.3.
Vd'
(5+) 2 0.4567 V2dō 2 2
2 d
43
c+ 8 4)
/2
5 b= 0.3
8 < 2d 0.4567 - 2 d
Vd
Hence, have that _² (T) 2 4,3 (7 + )) for 7 E [o.5+
0.3
and thus we can apply all previous Vdl
claims replacing Ç with (+ + va* and specifically,
0.3 Vd
2 d
0.3 vd
4)
x² (c
N 0.4567 0.2 >
43
c+
Which allows repeating all the previous steps without alteration. After repeating
vd 0.3
times, we get
that x² (r) 2 43 (r + 2) for E [0. 1], concluding the proof.
Corollary J.23. All previous propositions, and specifically Proposition J.19 and Corollary J.20 apply VT E [0, 1] (indicating Ç -= 1).
91

---

Proposition J.24, For d 2 100,000, L - max, m
d (T, (T) I 4.7955.
Proof. L. the Lipschitz constant of f, is given by
d dæ
L _ 2,rE(0,1]
(T,
We have:
/ / (T, dx
d dx
d x²
43 (T
+ 2) x
x
1
2
2
1²
43 2)
Assume that x 2 Emins T E [0, 1]. from 2 3, T +
S 1
From Claim J.7
we get B (T + 2)
2
0. This means that dz (T, 2 0. So
d
d
L = max 2.7E(0.1] dæ
f (T,
For any fixed z, the maximum B ( 2) will maximize L. From Claim J.7
we know that B is
decreasing with т, so to maximize I,, r
To maximize z
note that this
x0--4((3)
function is decreasing with respect to
x 43 (2)
d
d
x x²
d
x2 22-40- (00000(()))) (++1)
dx
2
43 (2)
2
x2 2 (1)
d
x² 48 (2) x²
48 (3)
50,
2
(x2 43 (4)
3
2
(12 43 (4)
hence the optimal x is Tmin We get that
d
Fmin
2
43)
Amin
Now,
1
((1
1)
1/d (1
2)) 2 2(3-2)/d
2)/d
23/d
4,3
4
à
d
d
and applying Corollary 1.20
we get:
0.4567
RIP
0.45672
4 23/d
NIP
0.4567
0.4567
[d 2 100,000]
IA
0.45672
23/ 10000000
0.455672
4.0001
1
1
10 1788
17
2
19.1783
19.1783
10. 1EST
18. 1783
d
19. 1783
d
16 1783
1781
1
2
2
1+1
19. 19.1783 1783
18 1283 V1-
19.1783
< 4.7955.
19.1783
100000
92

---

Proposition J.25, From 100,000, M a m
d (r)
d² - 10.5027
Proof. M is defined upper bound the second derivative (absolute value) of a (7) in the
relevant interval:
d²
d dr (,,
M
max rE/0.1|
d72
x (7)
max rE(0,1]
We have:
x2 43
T
+++ 2)
0
x22 43
(T
+ ② x
dr f
(T,x
d
+ x (T)
2
dr
2
0
x²
48
(T + 4)
0
x2 43 (T + 4)
f (T))
2
Ox
For the first term:
2
43 (T + 2) - x
d
-4
θT 3 T+
2
2
2 x2 43 (T+
2)
d
0
(++)) 1
x2 48 (r
d)
From Claim J.7 know /3 is positive and decreasing,
is maximized
In
49 (7+1)
addition
& 3 [T 4) < O, and thus the entire expression is non negative. We know 3 is convex,
0F
so the absolute value of the negative a. (r + 2)) is also maximized 0. All in all, the entire expression is maximized at r = 0, and is bounded by:
d
S
θT (++ d ==0
02 (2)
d
(d (2(2-// - 1) 2-20(1/d)
x2 (3
d
-2hn2 3-2011/0
(dd1//)- 1/4 10/10/0--)-- 14 2))
23/d
21n + d (1 (1-2- 21101
x2 43 (t)
23/d
<
(2 2 + lm2)
2 4 29/4
23/100008
(3
2
29/100000
100000
2.08
2 4.1
10-5 5
2.08
I200
< 4.555.
0.45677
4.1 10-5
Moving the second term, have from Proposition J.24
2
43
(T 2) x
5 dz
L = 4.7955.
2
93

---

Now we need to bound (T, = d V22 43 (T + à) - x
which is always negative. From Claim J.7 we know 3 is positive and decreasing, so its maximum, which minimizes this and thus maximizes its absolute value, is received at 0. We also know that f (0,z) increases with (see the beginning of the proof for Proposition J.24). so its absolute value decreases with a. Utilizing these facts get:
43
(T
4)
x² 43 (2)
2
2
0.45672
-422
22//4 d
0.4567
d 2 100,000
0.4567
d
2
0.4567
4
23/100000
0.4567
d
2
19.1782
0.4567
2
1
d
19.1782
0.4567
19.1782
19.1782
0.4567
19.1782
J14
2
19.1782
2
2
2d
0.4567
19.1782
dd 2 100,000] >
19.1782
2.1901
2 100000
To summarize, we have 2.1901 < (T, x) < 0, and thus
d (T, E [0,55555] + 2. 1901 0] [0, 4.7955] C [- 10.5027, 4.555]
and in absolute value,
M S 10.5027.
Proposition J.26. For d 100,000, E .,...., d} for which the sequence (z), exists, ie.. 2 4/3 (1) 2 0 for all S S
170.4
2x ikl 2
where 3t.
V1
1n + +4
In
Proof. As noted in App. J.1.1 the sequence (x) are Euler's iterates for the ODE Eq. 14). Using the global truncation error of Euler's 's method 9 chapter 6.2] we get:
hM
T. 0)) -1)
M
(e" - 1),
Jk
7
2L
exp
2Ld
where
d
L = max
dx ʃ (T,æ)
(where + is treated as a constant),
(0,
M max 0.10
dr2 (T)
dr (T, [
For d 2 100,000 we have 10.5027.
< 4.7955 from Proposition J.24 and Proposition J.25 gives M S
94

---

So in total
k
-
10.5027
(c
1) -
131.3685
4. 4.755
d
Combining this with Proposition 1.19
we get
k
K
Fnl =
I
7
2k
T
7
+ x
7
k
k
2k
x
7
131.3685
38.9822
170.4
d
d
d
Corollary J.27. For d 2 100,000, k E {2.... 43 (2) for all 2 S k: 2 2 0.45.
d} for which the sequence (r) exists, i.e. 2ÿ-1
Proof. Ty. is decreasing (Claim 1.5 vk: E
[d]:
170.4
170.4
Ih 22
+ 4-1
1
d
In
In4
d
d 2 100,000] 2 0.45.
Proposition J.28 (Existence of the sequence). For 2 100,000, the sequence (x) exists for all E [d]. i.e., =2-1 43, 2 0, for all 2 i 1 d.
The proof is similar to that of Proposition J.22 but simpler. We first note that
= 1
4 d
48
2 (
d
4,2
which means 22 exists. Now assuming for some , Ik 2 0.45, and we have
d). 3& exists, then from Corollary J.27
2
k ++1
2.45 0.2
4 43
4.
which means that 2441 exists, and by induction the proof is done.
95

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction clearly state the setting (detailed in Section 2 contributions, and assumptions made (namely, continual linear regression setting under a joint realizability assumption). All results presented in the paper outlined 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 contribu- tions made in the paper and important assumptions and limitations. A No 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 as long as it is clear that these goals are attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The exact setting and the main assumption are mentioned in the introduction and fully discussed in Section In Section we discuss, and settle, other findings from the literature; and also extend future directions to address our work's limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not diseussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificationn 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 only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken low lighting. Or a 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
96

---

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]
Justification: Assumption 2.1 is clearly stated in Section All theorems mention their assump- tions and refer to their corresponding proofs in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' 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 a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or 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 experimental results of the paper the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Regression experiments, done with synthetic random data, can easily be regenerated using the full details given in the appendices corresponding to each experiment (App. B F2
and and their code provided in App. H A link to the code for the classification experiments
is provided in App-[C C The algorithms simple and always formally stated (Schemes and
We detail the construction of the adversarial task collections (Section 5.1 in App. E
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make possible for others 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 to replicate the results, access to hosted model (c.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily architecture clearly and fully.
model architecture, the paper should describe the
(c) the contribution is new model (e.g., large language model), then there should either be way access this model for reproducing the results way reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, which case authors are welcome to describe the particular way they provide for reproducibility. In the case of
97

---

closed-soue source models, it may be that access to the model is limited in some way (e.g.. 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
Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Regression experiments, done with synthetic random data, can easily be regenerated using the full details given in the appendices corresponding to each experiment (App. B R2
Justification:
and G.3). and the code available in App. H. A link the code for the classification experiments provided in App.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines
uuiidee/Cooeeubbbbssssmooooo..., for more details.
While we encourage the release code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https wwwpc//guue/////ee htt////ooebbiiiniiniiiii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details of hyperparameters and experiments with varying hyperparameters are detailed under Figure 3a and in the relevant appendices (App. F.2. App. App./G.3.. The data synthetic and we measure only the training performance (as explained in the paper).
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 a level of detail that necessary to appreciate the results and make sense them.
The full details can be provided either with the code, appendix, or as supplemental material.
98

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All figures of classification experiments include 95% confidence intervals, see App. for details. The figures of regression experiments shown in the main body of the paper aim to show qualitative trends on random data, rather than quantitative results on real-world benchmarks. Thus, we defer confidence intervals to the full experiments in the respective appendices, see App. B for details.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the enror 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 library function, bootstrap, etc.)
The assumptions made should given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show tables or figures symmetric eтrоr bars that would yield results that are out of range (e.g. negative eπrоr rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8, Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: Experiments and numerical validations (for Section 5.1 required very little CPU resources that detailed in the corresponding appendices (App.
and G.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each individual experi- mental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn' 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 http://p/p//errrp.ccppppp/l....t hccpppblcc/ccc.ccuuueel.l...
Answer: [Yes]
Justification: The research involves theoretical research, synthetic data experiments, and CIFAR experiments. fully conforms with the NeurIPS Code of Ethies.
Guidelines:
99

---

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 preserve anonymity (e.g., if there is special consideration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper involves theoretical research of continual learning, and has no societal impact.
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 societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment 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, there is a direct path to any negative applications, the authors should point out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No models or data were released. The provided research code compares different task orderings in continual learning, and has no risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 restrictions to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
100

---

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: [Yes].
Justification: All creators of datasets and models used were properly cited. Specifically, we use LIFAR-100 and cite Krizhevsky al. [55] accordingly in Section 4.1 and employ pretrained models from Chen cited appropriately in App.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if 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, papersvithcode com datasetasetttt has curated licenses for some datasets. Their licensing guide help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Released code is documented appropriately.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codemmodel part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
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 research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage the country of the data collector.
101

---

for 15. Institutional review board (IRB) approvals 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 an equivalent approval/teview based on the requirements of your country or 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 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.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used only for editing purposes and code corrections.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer our LLM policy luttpp://benriisscc///ofttreeeee what should or should not be described.
102


Reviews:
[{"review_id": "kj34gsZxrF", "reviewer": "Reviewer_nmNC", "summary": "This paper explores task ordering in continual learning, offering theoretical insights into how task sequences with dissimilar adjacent tasks can enhance performance. The authors specifically examine a greedy strategy designed to maximize the difference between tasks in continual linear regression, discussing both its benefits and potential drawbacks. They also propose a hybrid approach that combines greedy and random task orderings to address the identified limitations.", "questions": "Please refer to the Strengths And Weaknesses.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. This paper is well-motivated. Studying task ordering is crucial for understanding the intrinsic nature of continual learning. \n\n2. This paper is clearly written and easy to follow. The geometric intuitions and the theoretical analysis of greedy task ordering in continual linear regression provides insight.\n\nWeaknesses:\n\n1. I am currently confused about the significance of this paper's contribution. As discussed by the authors in the related work section, the importance of task ordering in continual learning has already been demonstrated both empirically and theoretically in previous studies. In particular, the work by Li et al.[47] seems to have addressed this problem under more complex settings, providing theoretical analysis from the perspective of a global task graph and conducting experiments on more realistic image classification tasks. In contrast, this paper focuses on understanding greedy task ordering in the context of continual linear regression. Could the authors further explain the necessity of this research and how it differs from prior work?\n\n2. While I appreciate the theoretical insights presented in this paper, their practical relevance is limited due to the highly idealized experimental setup, which focuses solely on linear regression tasks with data generated from Gaussian distributions. It would significantly enhance the paper's impact to explore how the proposed greedy or hybrid strategies perform in more realistic, real-world scenarios.\n\n3. I am curious about the relationship between greedy task ordering and globally optimal task ordering. As the authors mentioned in the paper, finding a globally optimal task ordering is equivalent to solving a Maximum-Weight Hamiltonian Path problem, which is known to be computationally expensive. However, in practical settings, the number of tasks T is often relatively small, making it feasible to compute the globally optimal ordering or, at the very least, find a solution that outperforms the greedy approach. In such scenarios, how does the performance of greedy task ordering compare to that of a globally optimal (or near-optimal) ordering? Additionally, can the failure cases of greedy task ordering be interpreted or explained through the lens of global optimality?", "was_revised": true, "final_justification": "The authors’ response addresses several of my concerns. I agree that the paper’s chief value lies in its theoretical insights into task ordering, which deepen our understanding of continual learning. That said, a stronger demonstration of realistic relevance would enhance the impact of this work.", "rebuttal": "We thank the reviewer for their positive review. We are pleased that they found our work clear and well motivated, studying an important problem in the field of continual learning.\n\nWe would like to address the reviewer’s concerns:\n1. **Significance of contribution in light of prior work.**   \nThe reviewer asked that we elaborate on the differences from prior work, and particularly to the most closely related work of Li and Hiratani [47]—indeed an important work in the field, which we cite and discuss in many places in our paper (e.g., lines 37-39, 259-260).  \nHowever, we believe that our *theoretical* setup is more revealing than theirs; and that the contributions in our work are independently important and significant to the field, and actually improve the understanding of their findings as well.\n    - A few inherent similarities and differences between their analytical setup and ours:\n        - **Same model:** Both papers study **linear** models, where each task is learned to convergence.\n        - **Our “data model” is more revealing:**  \n    Our paper assumes **joint realizability**, i.e., $\\exists \\mathbf{w}\\_{\\star} $ such that $\\mathbf{y}\\_m=\\mathbf{X}\\_m \\mathbf{w}\\_\\star, \\forall m$, but allows **any arbitrary** feature matrices.  \nOn the other hand, their analysis employs Gaussian feature matrices with a low dimensional latent representation and simplistic cross-task pairwise similarity assumptions, captured by the covariance matrices $\\mathbf{C}\\^{\\mathrm{in}}, \\mathbf{C}\\^{\\mathrm{out}}$.   \nThis is crucial when analyzing the effects of task similarity on forgetting, since higher order and rank-dependent effects on similarity can’t rise under their simplistic model.  \nFor instance, analyzing arbitrary feature matrices was essential for us to uncover complex phenomena such as the adversarial construction of Theorem 5.1.  \n    - **Different tested aspects and novel findings:**   \nWe discuss novel phenomena, not previously explored in the context of continual learning (CL), and specifically, not in Li and Hiratani [47]:  \n        - We test the effects of repetition in similarity-guided orderings—while Li and Hiratani [47] focus solely on single-pass orderings (see their Limitations section). Consequently, we formally prove a clear separation in worst-case behavior depending on the presence or absence of repetition.\n        - Our geometric interpretation (e.g., in Figure 7) allows a more intuitive discussion of their task typicality.\n        - We formalized greedy orderings in the context of CL, linking to other areas of research such as Kaczmarz and projection methods.\n        - We derive convergence rates for the forgetting under greedy orderings. Importantly, after hard work on the matter, we achieved **a stronger (dimensionality-independent) bound of $\\mathcal{O}(1/\\sqrt[3]{k})$** for the loss of greedy ordering with repetition, instead of the $\\mathcal{O}(1/\\log (k))$ bound which was previously presented in Proposition 5.2.\n        - Our elegant linear regression setup is sufficient to reveal a surprising failure mode of greedy orderings (Theorem 5.1), ‘warning’ future practitioners that dissimilarity-guided orderings do *not* invariably perform better.\n        - Drawing inspiration from other fields, we introduce a practical hybrid approach to overcome the potential failure modes we uncovered.  \n\n    To address the reviewer’s concern, we will elaborate in the revised manuscript on how our work extends and complements the findings of Li and Hiratani [47].\n\n2. **Practical relevance of the experimental setup.**  \nThe goal of our paper (discussed in lines 31-41) is to deepen the *theoretical* understanding of the practical benefits of similarity-guided orderings that were *already* demonstrated in prior empirical work [e.g., 10, 34, 43, 47, 48, 54, 55, 61, 68, 69]. We propose more rigorous, analytical tools and perspectives that provide theoretical justification to such orderings, while thoroughly discussing several aspects of them (e.g., rates of convergence, failure modes, effects of repetitions).    \nHence, the goal of our experiments is *not* to demonstrate the empirical superiority of similarity-guided orderings, but rather to support our analysis, facilitate discussions, and *develop intuition into our analytical findings*—which are the main contributions of our work.  \nFor instance, the simplified experimental setting provides insight on the effects of dimensionality and rank on the performance of each algorithm, not available via other settings (Appendix B).\n\n\n3. **Greedy vs optimal task ordering.**  \nWe thank the reviewer for this interesting question which sparked discussions among the authors.\nThe reviewer is right that, when the similarity metric between tasks is *prespecified* and fixed, finding the sequence that maximizes the total pairwise dissimilarity reduces to finding a **maximum‑weight Hamiltonian path**, which can be solved for a small number of tasks or approximated.   \nHowever, (i) we do *not* assume a prespecified metric, and (b) even the optimal path w.r.t. such a metric is not guaranteed to minimize the loss or the distance to the joint solution $\\mathbf{w}\\_{\\star}$!  \nIn contrast, our Maximum Distance rule (Definition 3.1) greedily maximizes the decrement in the distance to the joint solution (Eq. 3). One would imagine this “decrement” can be a valuable metric for a Hamiltonian path solver—however, it is *impossible* to even use it to define a static metric since it is an *online* quantity depending on the current iterate/node (and indirectly, on the entire path to it). Consequently, it is no longer a Hamiltonian path problem but rather a sequential decision problem whose brute‑force solution requires *simulating the entire training* for all $T!$ orderings.  \nIt is only in the nearly‑determined case $r=d-1$ of Section 4.2 that the problem maps to finding a Hamiltonian path on a static graph—and then we show that our greedy selection indeed approximates the optimal path (Lemma 4.1).  \nCharacterizing the globally optimal ordering and deriving its convergence rate remain promising open questions. We will mention this in the revised manuscript.\n\nWe hope the important discussion above has helped make the reviewer more confident in their positive assessment. We would be happy to further address any remaining questions."}, {"review_id": "PzOmSfHYgM", "reviewer": "Reviewer_rjvw", "summary": "The paper considers the theoretical performance of continual linear regression when the order of several jointly realizable tasks changes.\nThe paper proves the optimality of greedy ordering according to the maximum distance (MD) in the limited setting when the rank of data in each task is $d-1$.\nThe paper also shows an adversarial counterexample on general data in which the greedy ordering leads to catastrophic forgetting.\nThe paper further discusses learning with repetition and the hybrid task ordering.", "questions": "Q1: How can you compute MD when the task is not rank-1? We do not have access to the $w_*$.\n\nQ2: In Scheme 2, similarly, how can you compute Line 3 a 4 without knowing $w_*$?", "limitations": "N/A on societal impact", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "While I believe the work is sound, the result is novel, and the writing is clear, my worry is that it seems to me for now that the result is a little disconnected from continual learning. I am also not aware of how the insights on task ordering can benefit the area of continuous learning and Kazcmarz methods. Please feel free to educate me on this; if there is substantial evidence that the result can provide some insights into practice, I will be happy to raise the score.\n\nThe authors mentioned in the footnote on page 3 that they only consider a noiseless optimization-based setting in analyzing the effect of ordering. Furthermore, they are considering the continual linear regression algorithm without any other regularization, replay, etc. for improving the CL performance. On practical relevance, this algorithm is known to suffer from forgetting and not used for performance in practice; on theoretical significance to CL, [Evron, 2022] already discussed this algorithm and some effect of task ordering, and the additional message of this paper seems incremental. Also, I am not exactly sure for the theoretical significance of such ordering in the Kazcmarz methods field, plus that direction is not claimed as the main contribution of the paper.", "was_revised": true, "final_justification": "Thank you for your detailed explanation. I think these arguments make sense, and they kind of address my concern. Generally speaking, I would be happy to see and to encourage CL theory works. I am raising the score from 3 to 4.\n\nThat said, it will be quite some work to integrate these arguments into the paper. Regardless of the final result, please ensure to carefully incorporate them into the intro and discussion part of your paper.", "rebuttal": "We thank the reviewer for their review. We are pleased that they found our paper novel, clearly written, and theoretically sound.  \n\n### The reviewer’s feedback entails a lot of ideas, carefully addressed below:\n\n1. **Benefit to the continual learning and Kaczmarz fields.**    \nWe are happy that the reviewer is open to reconsider their score, especially on the significance of the paper. Let us mention some specific benefits of our work.   \n\n    - **In continual learning (CL):**  \n    Our main goal (discussed in lines 31-41) was to deepen the theoretical understanding of the empirical success of similarity-guided orderings [e.g., see 10, 34, 43, 47, 48, 54, 55, 61, 68, 69].\n    Our analytical framework not only offers a theoretical **foundation** for recent empirical findings, but also yields **insights** that can guide future practice. For example:  \n \n       - **Foundation:** A rigorous analysis showing provable advantages of (dis)similarity-guided task orderings, justifying recent empirical findings in CL [e.g., 10, 47], in a more permissive analytical framework compared to recent prior efforts [47, 48]. Moreover, throughout our paper and specifically in Section 6, we thoroughly discuss and compare related work from several different fields of research (Kaczmarz, SGD, sample mining, etc.), thus establishing bridges that can benefit both theory and practice.    \n\n        - **Theoretical progress:** New upper bounds for the loss include Lemma 4.2 and Proposition 5.2—which will be improved in the revised version to a meaningful dimensionality-independent $\\mathcal{O}(1/\\\\sqrt[3]{k})$ bound for the loss of greedy orderings with repetitions.    \n\n        - **Practical insight:** We uncover a surprising *failure* mode of single-pass greedy orderings (Theorem 5.1).     \n\n        - **Practical insight:** We compare greedy and random orderings from multiple perspectives, highlighting differences in their empirical behavior. Contrary to conventional wisdom on random orderings, we demonstrate that in *greedy* orderings, task repetition often leads to faster convergence, both theoretically and empirically.    \n\n        - **Practical insight:** Leveraging the empirical benefits of greedy orderings while avoiding their possible pitfalls, we suggest a hybrid method (Section 5.3)—novel to the CL community—that provably converges.     \n\n\n    - **In the Kaczmarz literature**, there is much ongoing work on how to practically accelerate convergence using better sampling schemes (of rows or blocks; equivalent to tasks in the CL context). Evidently, greedy methods are of high interest in the Kaczmarz community [e.g., 57, 58, 52, 56, 79, 82, 84, 7, 8, 74, 83; cited in our lines 168-175].   \n    Our work promotes the understanding of such methods by:     \n    (a) analyzing the **loss behavior** rather than the convergence to the intersection (as more common in the Kaczmarz field);       \n    (b) focusing on **single-pass** orderings rather than orderings with repetitions (which are more common in current Kaczmarz literature, despite sometimes behaving worse [58]);      \n    (c) showing non-trivial **failure modes** of these methods.    \n\n2. **Practicality of the studied scheme: CL without replay, regularization, etc.**      \nAs the reviewer mentioned, we study a plain CL scheme, without actively trying to prevent forgetting with replay, regularization, and so on.       \nHowever, we do not think it limits the significance of our work, for several reasons:    \n    - **The greediness itself can mitigate forgetting, even in plain schemes!**      \nA nice take-home message from our work is that even without active methods like replay or regularization—greedy orderings make the model forget less and converge faster (in some cases with proven convergence rates). This illuminates the effects of the task ordering specifically, rather than those of other algorithmic factors.      \n    - **Inherent analytical limitations.**    \nExisting analytical tools are more mature for plain CL schemes than for regularization- and replay-based methods, which have received comparatively less theoretical attention.      \nThis makes it possible to conduct a more elegant and fundamental analysis of task ordering effects, without the need to account for additional factors such as buffer size or regularization strength.    \n\n3. **A note on the setting being “noiseless”.** We point out that we only require the *training* data to be realizable by a linear model. This naturally happens given sufficient overparameterization, e.g., in neural networks that, famously, can perfectly fit data, even with random labels [*1, *2]. Importantly, this makes our analysis relevant to linearized approximations of such networks (e.g., using the Neural Tangent Kernel; see lines 82-86 in our paper).   \n\n4. **Difference from Evron et al. (2022).**     \nWe respectfully disagree that our work is “incremental” in comparison to Evron et al. [15].   \nIn fact, other than the initial setup (jointly realizable continual linear regression), the intersection is small. Of course, we build upon some of their analytical tools (giving them full credit where we do so), but the focus, findings, and insights of the two papers are very different.  \nIn particular: (a) they never mention reordering tasks to mitigate forgetting; (b) they discuss effects of task similarity given two tasks *only*; (c) they propose no task selection rule like our similarity-guided greedy rules; (d) they do not investigate ordering optimality; \n(e) their convergence results (somewhat restrictively) require task repetition, while we study the benefits of more practical greedy orderings that require no repetition; and so on.\n\n\n### Regarding the reviewer’s **questions**:   \n1. **Can the greedy MD rule be calculated without prior knowledge of the offline solution $\\mathbf{w}_{\\star}$?**     \nYes, both greedy rules analyzed do *not* require any prior knowledge of the offline solution.   \nThe greedy MD rule’s objective (Definition 3.1) can be rewritten as \n$ \\Vert ( \\mathbf{I} - \\mathbf{P}_m ) ( \\mathbf{w}\\_{t-1} - \\mathbf{w}\\_{\\star} ) \\Vert^{2} = \\Vert \\mathbf{X}_m^{+} ( \\mathbf{X}_m \\mathbf{w}\\_{t-1} - \\mathbf{y}_m ) \\Vert^{2} $,\nbetter illustrating that no knowledge of $\\mathbf{w}\\_{\\star}$ is required. Thus, it *is* possible to compute the MD rule exactly, making it not purely theoretical. \nOne might claim that explicitly computing $\\mathbf{X}^{+}\\_{m}$ is also prohibitive (but not impossible!); however, it can be estimated quite easily with small subsets of the training data from different tasks—again, without knowledge of the offline solution $\\mathbf{w}\\_{\\star}$ (see also lines 150-155).   \nWe thank the reviewer for pointing out this misunderstanding which we will resolve with a clearer explanation in the revised version.    \n\n\n\n2. **Similarly, how is the hybrid method evaluated without prior knowledge?**     \nHopefully, the above clarifies how the Maximum Distance rule is computed in practice and that it requires no knowledge of the solution $\\mathbf{w}\\_{\\star}$. The same applies to lines 3-4 in the hybrid Scheme 2.\n\n\nWe hope we have addressed the reviewer’s questions and concerns, and we would be happy to engage further should any additional questions arise.\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."}, {"review_id": "i4qr9deNHn", "reviewer": "Reviewer_E1hb", "summary": "The paper tackles the continual linear regression problem. The main algorithm analyzed is a Kaczmarz-type method that chooses the next task with a greedy rule. The main theorems are as follows. Lemma 4.1 shows that the squared distance of the greedy method to ground-truth is smaller than or equal to the (unsquared) distance of an \"optimal\" method. Lemma 4.2 proves an upper bound $O(1/T)$ on the losses of the algorithm where $T$ is the number of tasks. These two results assume the data matrix has rank $d-1$, where $d$ is the data dimension. Theorem 5.1 shows that in high dimensions ($d\\geq 30$) the loss of the greedy rule is lower bounded by a nonzero constant (for example, 1/16). Proposition 5.2 instead provides an upper bound of the loss that is of order $O(1/log k)$, where $k$ is the number of iterations", "questions": "- At line 988 of Theorem 5.1, I saw $u_t$ is defined based on $w_t$ and $X_t$ is constructed using $u_t$. But the learner only produces $w_t$ after seeing $X_t$. Does it mean that the adversarial construct assume knowledge about all iterates? If so, the values of Theorem 5.1 would be greatly reduced.\n\n- While I am not very familiar with literature, I imagine there would be some convergence bound on greedy Kaczmarz or greedy Gauss Seidel method. I furthermore imagine that these convergence rates are linear, depending on eigenvalues of data. How would the bounds in the paper compare with those results? A very detailed comparison is needed to understand the contribution of the paper.\n\n- Line 241: Once these projections diminish, we switch to the random ordering, which—unlike the greedy approach—cannot be adversarially “tricked” into failure ... why the random ordering won't fail? I think the randomized rule would also admit some lower bound, as shown in earlier work.\n- The main title \"Task Similarity Matters\" is a little bit confusing to me. It seems that task similarity doesn't matter for randomized rules. Could the authors better explain the rationale behind the title? On the other hand, in fact, in my opinion, the connection to \"task similarity\" is very weak. I believe the notation of task similarity is not related to algorithms. The greedy rule instead is an algorithm that chooses a task based on the current iterate vector, not on task similarity. Could the authors better justify why task similarity is a suitable angle towards appreciating the paper?", "limitations": "Personally, I think the main limitation is that the paper works with simplified settings and a hard-to-implement algorithm. Even though the analysis of greedy rules is more difficult and the paper seems to make solid theoretical contributions, this does not justify the study of an algorithm that can not be used in practice.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- the paper reads smooth and is very clear, with figures and visualization properly placed to explain the ideas and results.\n- the paper contains a solid array of technical results on continual regression with a greedy rule.\n\n\nWeaknesses:\n\nA major weakness in my humble opinion is on the significance and relevance of the study. To begin with, continual linear regression is an idealized problem, and the paper furthermore analyzes a hard-to-implement greedy rule that need to know the ground-truth vector (Definition 3.1). My first question therefore is: how would the authors justify the practical value and impact of the studied problem and the analyzed algorithm?\n\nA potential justification might be that the theorems proved could provide practical guidance for continual learning. However, this point is not very clear to the reviewer. Could the authors explain: what practical insights do we obtain from the theorems?\n\n- Proposition 5.2 doesn't provide a good bound. In analysis people only ignore the log term. The bound $O(1/log k)$ of Proposition 5.2 is like a bound $O(1)$. The authors are encouraged to illustrate the difficulty of obtaining a better bound that is dimension independent.", "was_revised": true, "final_justification": "The rebuttals addressed several of my concerns, and promised to include a stronger bound in the revision. \n\nI have read the comments from other reviewers and also the author's reponses.\n\nMy original concern was that the paper didn't analyze a practically implementable algorithm. This was partially addressed in the rebuttal. \n\nBased on these, I increased my score from 3 to 4, and increased the score on \"Significance\" from 1 to 2. I believe the paper represents a solid contribution to the theory of greedy rules. Personally, I love to see and encourage more theoretical works like this, as continual learning theory is scarce compared to empirical works. Moreover, the paper provides new results from the Kaczmarz or  Gauss-Seidel viewpoint.\n\nThat being said, I am not recommending acceptance with a higher score, as its practical significance is still not very clear to me. For example, computing the maximum distance rule is much more expensive compared to randomized rules. In fact, this is a shared concern among reviewers.\n\n\nFinally, regarding the concerns of Reviewer Lb47:\n- *... may not fully capture the complexities of recent advances in continual learning.*\n- *...  may not fully reflect the characteristics and challenges of real-world datasets.*\n\nI respectfully disagree with that, as it is a general criticism without specifics. To be rigorous, I am not sure what \"the complexities of recent advances in continual learning\" are, and what \"the characteristics and challenges of real-world datasets\" are. Do the reviewer have a precise definition on these?", "rebuttal": "We thank the reviewer for their review. We are pleased that they found the paper clear and deriving meaningful results.\n\nBelow, we answer the knowledgeable questions by the reviewer, using them to clarify several important aspects of our work, particularly regarding its practicality and significance. We hope these clarifications enable the reviewer to reassess our paper.\n\n\nIn short, here is how we resolve/alleviate the ‘weaknesses’ raised by the reviewer:  \n* The **practicality** of the greedy selection rule → we rephrase a formula, clarifying that no knowledge of the ground-truth solution is necessary.    \n* The **simplicity** of our linear regression setup → we explain that this setup suffices to derive meaningful (and even surprising) results that illuminate recent empirical findings.    \n* The **strength** of the $\\mathcal{O}(1/\\log k )$ bound in the greedy with-repetition case → we improve it to $\\mathcal{O}\\left(1/\\sqrt[3]{k}\\right)$.   \n\n---\n\n### Now, we go into detail on the raised ‘weaknesses’:\n1. **Significance and relevance:**  \n    - **Is the greedy rule “hard-to-implement”? (no)**  \nWe clarify that both of the greedy rules we analyze do *not* require any prior knowledge of the offline (‘ground-truth’) solution.\nThe reviewer seemed especially worried about the Maximum Distance rule (Definition 3.1); however, its objective can be rewritten as  $ \\left\\Vert ( \\mathbf{I} - \\mathbf{P}_m ) ( \\mathbf{w}\\_{t-1} - \\mathbf{w}\\_{\\star} ) \\right\\Vert^{2} = \\left\\Vert \\mathbf{X}_m^{+} ( \\mathbf{X}_m \\mathbf{w}\\_{t-1} - \\mathbf{y}_m ) \\right\\Vert^{2} $,\nbetter illustrating that no knowledge of $\\mathbf{w}\\_{\\star}$ is required. Thus, it *is* possible to compute the MD rule exactly, making it not purely theoretical. \nOne might claim that explicitly computing $\\mathbf{X}^{+}\\_{m}$ is also prohibitive (but not impossible!); however, it can be estimated quite easily with small subsets of the training data from different tasks—again, without knowledge of the offline solution $\\mathbf{w}\\_{\\star}$ (see also lines 150-155).\nWe thank the reviewer for pointing out this misunderstanding which we will resolve with a clearer explanation in the revised version.\n    - **What practical insights could be obtained from the analysis on the ‘idealized’ continual linear regression setting?**  \nThe main goal of our paper (discussed in lines 31-41) was to deepen the theoretical understanding of practical benefits of similarity-guided orderings—which were already demonstrated in prior empirical work [e.g., 10, 34, 43, 47, 48, 54, 55, 61, 68, 69].  \nOur elegant linear regression framework not only offers a theoretical **foundation** for recent empirical findings in the field, but also yields **insights** that can guide future practice. For example:\n\n\n        - **Foundation:** A rigorous analysis showing provable advantages of (dis)similarity-guided task orderings, justifying recent empirical findings in CL [e.g., 10, 47], in a more permissive analytical framework compared to recent prior efforts [47, 48].\n\n\n        - **Practical insight:** We uncover a surprising *failure* mode of single-pass greedy orderings (Theorem 5.1). \n\n        - **Practical insight:** We compare greedy and random orderings from multiple perspectives, highlighting differences in their empirical convergence behavior. Contrary to conventional wisdom on random orderings, we demonstrate that in *greedy* orderings, task repetition often leads to faster convergence, both theoretically and empirically.\n\n        - **Practical insight:** Leveraging the empirical benefits of greedy orderings while avoiding their possible pitfalls, we suggest a hybrid method—novel to the CL community—that provably converges.\n\n      We will better emphasize these contributions in the revised version.\n\n\n2. **The $\\mathcal{O}(1/\\log k)$ upper bound for greedy orderings with repetition is weak.**  \nThank you for this insight. After working hard on improving this, we derived **a stronger (dimensionality-independent) bound of $\\mathcal{O}\\left(1/\\sqrt[3]{k}\\right)$**. This emphasizes the effect of task repetition in these greedy orderings and strengthens our theoretical contributions. \nWe will include this in the revised manuscript.\n  \n\n\n### Addressing the raised **questions**:\n1. **Does the adversarial construction assume prior knowledge of the chosen iterates?**  \nThe *learner* does *not* assume knowledge about future iterates, but simply greedily maximizes over unseen (prespecified) tasks at each iteration (as in Definition 3.1, 3.2).\nTo show *how* a task collection that leads to failure can be *constructed*, we “reverse engineer” it as follows:  \nWe define vectors $(\\mathbf{w}_t)$ by specifying their coordinates, then define tasks $\\left(\\mathbf{X}_t, \\mathbf{y}_t\\right)$ in terms of the $(\\mathbf{w}_t)$. With these tasks and an explicitly-defined initialization vector, we show that the greedy task selection naturally yields $(\\mathbf{w}_t)$ as the iterates.  \nConsequently, Theorem 5.1 retains its validity and significance.\n\n2. **Comparison to convergence bounds from Kaczmarz method literature.**  \nContinual learning seeks to minimize the average task loss (Definition 2.3), whereas the greedy Kaczmarz literature minimizes the distance to the joint solution (Definition 2.5). Proposition 2.6 bridges the two: any bound on the distance immediately upper‑bounds the average loss.  \nExisting linear convergence rates for greedy Kaczmarz—e.g., Nutini et al. [57] and other works cited in lines 168‑175—fall short in two ways: (i) they rely on repeated rows/blocks and therefore do not apply in the single-pass regime central to continual learning; (ii) when repetitions are allowed, their rates depend on data eigenvalues, so they can be much slower than our (improved) data‑independent $\\mathcal{O}\\left(1/\\sqrt[3]{k}\\right)$ guarantee—especially for nearly collinear tasks, as illustrated in Evron et al. [24, Thm 8 & Lem 9].  \nTo make this contrast concrete, we will add a small‑angle experiment to the supplementary material. In addition, we will extend the discussion in lines 168-175 accordingly.\n\n\n3. **Doesn’t random ordering also fail?**  \nWhen we mentioned that *“the greedy approach can be tricked into failure”* (Section 5.1), we meant a complete, “catastrophic” failure that yields $\\Omega(1)$ forgetting after learning (even infinitely) many tasks.  \nThe reviewer is right in suggesting that random orderings also exhibit worst-case behaviors in certain cases, but these are much more mild, admitting an $\\mathcal{O}\\left(1/\\sqrt[4]{k}\\right)$ bound, as shown in prior work [26]—which we do not consider as “failure” modes.  \nFollowing the reviewer’s question, we will make this clearer in the next version.\n\n\n4. **How is task similarity connected to greedily choosing the next task based on the current iterate?**  \nThis is indeed a subtle issue to which we have given considerable thought, and we have explicitly discussed it in the paper.\nAs we explain in lines 133-136, the distance between iterates (affecting both greedy rules) relates to the principal angles between the solution subspaces of tasks. \nIn turn, these angles measure task similarity, as we illustrate intuitively in Figure 1 and further exemplify in Section 4.2 (see lines 195-196). \nFurthermore, we discuss heuristic similarity measures (lines 156-160), and the usage of greedy rules as an idealized theoretical “proxy” for optimal and similarity-guided task orderings (lines 164-166).  \nFinally, the reviewer’s intuition that “task similarity doesn’t matter for randomized rule” is largely correct (or at least, it matters less). Such random orderings are mostly invariant to many of the more “complex” interactions between tasks, which our paper aims to better understand. \nThe fact that the greedy (dis)similarity-guided orderings *beat* random ones in our experiments and in many other empirical works (including those that rely on heuristic notions of similarity), implies that, indeed, “task similarity matters”.\n\n\n5. As a side note, in their summary, the reviewer mentioned that our adversarial lower bound applies from a dimension $d \\geq 30$, calling this a “high” dimension.\nConsequently, we improved our result, and in the next version we will include another adversarial construction in *3 dimensions only* that shows that high dimensionality isn’t necessary for demonstrating “catastrophic” (non-diminishing) forgetting.\n\n\nWe again thank the reviewer for their feedback. We hope we clarified the significance of our work, and we would be happy to engage further with the reviewer to address any additional questions."}, {"review_id": "QToj8pqgxq", "reviewer": "Reviewer_Lb47", "summary": "The paper investigates the impact of task ordering strategies in continual learning for linear regression. It focuses on greedy task orderings that maximize dissimilarity between consecutive tasks. Using tools from the Kaczmarz method literature, the authors formalize these orderings and develop geometric and algebraic intuitions around them. The paper also provides theoretical bounds on the loss for greedy orderings in a simplified setting and constructs an adversarial task sequence to demonstrate potential failure modes.", "questions": "See weaknesses.", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The paper provides a rigorous theoretical analysis of greedy task orderings in continual linear regression. It formalizes the concept of similarity-guided orderings using tools from the Kaczmarz method literature, offering new insights into the dynamics of task ordering in continual learning. \n\n2. The paper introduces a hybrid task ordering strategy that combines greedy and random orderings is innovative. This approach leverages the strengths of both strategies. The hybrid strategy inherits the bounds of random orderings, making it a robust alternative.\n\n3. The paper draws meaningful connections between continual learning, Kaczmarz methods, and other related areas such as projection methods and importance sampling. \n\nWeakness\n\n1. The study focuses solely on the linear regression setting, which is relatively simple and may not fully capture the complexities of recent advances in continual learning. \n\n2. The empirical results are based on synthetic data and are very small-sized, which may not fully reflect the characteristics and challenges of real-world datasets. Conducting experiments on real-world data would provide a more comprehensive evaluation of the proposed methods and their practical utility.\n\n3. Though the author mentioned this in the checklist, it is better to provide the sample code for better judgment of the implementation complexity.", "was_revised": true, "final_justification": "I have read the response and found the applicability of the theory to a more realistic setting is doubtful. But it makes some contribution theoretically, so I raise my score from 2 to 3.", "rebuttal": "We thank the reviewer for their feedback. We are encouraged that they appreciated the contribution of our work to the understanding of the effect of task ordering, as well as the novelty of the suggested hybrid method and the discussion of meaningful connections to other fields.  \n\nBefore answering in detail, we note that the reviewer mostly pointed out as weaknesses the simplicity of our analytical setting (which is already discussed in the paper; e.g., lines 73-74) and the lack of experiments on “real-world” data. However, we analyzed a setting that is **widely used** in theoretical CL studies [e.g., 5, 21, 24, 26, 28, 29, 36, 48, 60; cited in our lines 72-74, 82-86] in order to better explain and characterize phenomena that were **already** observed empirically in more complicated models and datasets (as cited in our line 33).\nMoreover, even this simple setting allowed uncovering novel failure modes not previously observed—that would have been almost impossible to uncover in more complex models—and identifying a separation between greedy and random orderings in the effects of task repetition.\n\nThus, we respectfully find the attached rating extremely harsh, not accurately reflecting the place of our paper and contributions in the **theoretical** continual learning literature.  \n\n--- \n\nBelow, we would like to comment on the concerns raised by the reviewer in more detail:  \n1. **Simplicity of the continual linear regression setting.**  \nWe agree with the reviewer that our (and frankly, any other) simple setting “may not fully capture the complexities of recent advances in CL”.  \nHowever, theoretical progress is made gradually and always starts from the simplest analyzable models (as done in the papers we cited above). Our simple model already exhibits phenomena related to similarity-guided task orderings—including ones observed empirically in recent papers [e.g., 10, 54, 63, 50, 67, *1 below]—thus providing a good opportunity to better understand such phenomena analytically. See our paper’s lines 31-41 for a more detailed discussion.  \nIs the reviewer aware of other theoretical papers that rigorously analyze these task ordering aspects in more complicated models?  \n2. **Experiments use synthetic data.**   \nThe goal of our experiments was **not** to show the benefits of similarity-based orderings, as these were *already* demonstrated in various settings (mentioned in lines 32-33), including vision tasks with neural networks [10, 48, 54, 63], NLP tasks with word2vec embeddings [50], tabular data with linear and logistic regression [67], and in incremental fine-tuning of LLMs [*1 below].  \nInstead, the goal of our experiments was to exemplify specific aspects of greedy orderings in ways that support our analysis, facilitate discussions, and develop intuition into our analytical findings which are the *main contributions* of our work. For example, we used our simple experiments to clearly discuss repetition in greedy orderings (Section 5.2, Appendix E.1) and the effects of the rank and dimensionality (Appendix B).\nOf course, more experiments can always be interesting, but we believe this could be done in future work.  \n\n3. **Providing a sample of the code.** We accept the reviewer’s suggestion and in the updated manuscript we will improve the reproducibility by sharing a full code sample of the straightforward implementation of our experiments.  \n\n---  \n**Additional references:**  \n[*1] Andrew Bai, Chih-Kuan Yeh, Cho-Jui Hsieh, and Ankur Taly. 2025. An Efficient Rehearsal Scheme for Catastrophic Forgetting Mitigation during Multi-stage Fine-tuning. In Findings of the Association for Computational Linguistics: NAACL 2025."}]

Author rebuttal:

Meta-review: This paper considers continual learning for (jointly) realizable linear regression, focusing on the greedy task ordering that maximizes dissimilarity between consecutive tasks. The paper makes some advances in our understanding of how promoting task dissimilarity between adjacent tasks can help convergence, what the failure modes of such a greedy ordering are, and how allowing repetition can cure the failure mode. Most reviewers appreciated that the theoretical contributions are solid, and I believe the authors did a good job of articulating what kind of practical insights can be gained from this theory. Even after the submission, the authors made efforts to improve the $O(1/\log k)$ bound to a stronger dimensionality-independent bound of $O(1/k^{1/3})$, and also found another set of failure examples that work with only 3 dimensions.

The biggest weakness of this paper, as commonly pointed out by the reviewers, is that it studies a simple setting and a vanilla algorithm that may appear detached from practical continual learning. While I find this criticism reasonable, I also believe that the theory presented in the paper provides useful insights and makes a solid contribution to the continual learning theory community. Hence, I recommend acceptance.

For the camera-ready version:
* I strongly recommend adding some experiments that more closely resemble real-world conditions, involving real-world data and/or simple neural networks. Such experiments would be a valuable addition to the paper, supporting the theoretical analysis.
* Please carefully incorporate the discussion with the reviewers (why study vanilla CL, practical insights, comparison with Evron+[24], etc.) into the paper. As Reviewer rjvw pointed out, this will require substantial work, but I trust the authors to make a thorough revision.
Decision: Accept (poster)