Nearly Optimal Bounds for Cyclic Forgetting
Authors: William Joseph Swartworth
Deanna Needell
Rachel Ward
Mark Kong
Halyun Jeong
Venue: NeurIPS 2023 poster (2023)
Keywords: catastrophic forgetting
linear systems
TL;DR: We improve on previous bounds for forgetting by precisely bounding the numerical range of a product of projections.

Abstract: We provide theoretical bounds on the forgetting quantity in the continual learning setting for linear tasks, where each round of learning corresponds to projecting onto a linear subspace. For a cyclic task ordering on $T$ tasks repeated $m$ times each, we prove the best known upper bound of $O(T^2/m)$ on the forgetting. Notably, our bound holds uniformly over all choices of tasks and is independent of the ambient dimension. Our main technical contribution is a characterization of the union of all numerical ranges of products of $T$ (real or complex) projections as a sinusoidal spiral, which may be of independent interest.

Nearly Optimal Bounds for Cyclic Forgetting
Halyun Jeong
Mark Kong University of California Los Angeles markkong @ ucla.edu
University of California Los Angeles hajeong @ math.ucla.ed.
Deanna Needell
William Swartworth
University of California Los Angeles deanna @ @wwth.ucla.ed
Carnegie Mellon University wswartwo @ Pendrew.cmu.ed
Rachel Ward
University of Texas at Austin rward mathhuteeassccuu
Abstract
We provide theoretical bounds on the forgetting quantity in the continual learning setting for linear tasks, where each round of learning corresponds to projecting onto a linear subspace. For cyclic task ordering on T tasks repeated m times each, we prove the best known upper bound of O m)) on the forgetting. Notably, our bound holds uniformly over all choices of tasks and is independent of the ambient dimension. Our main technical contribution a characterization of the union of all numerical ranges of products of 7 (real complex) projections sinusoidal spiral, which may be of independent interest.
Introduction
While machine learning often focuses on learning from a static dataset, one is often interested in acquiring data on the fly and adapting the present context. This is known throughout the literature as "continual learning" or "lifelong learning" [Wan+23 CLI8 Par+19
TM95).
One challenge of continual learning is "catastrophic forgetting" Had+20 may learn useful information context A but then lose much of this knowledge when adapting to context B. If context A is not representative of future contexts, then this is correct adjustment for distribution shift. However, if contexts similar to A arise repeatedly, this may be undesirable..
VT19
Kem+18): model
Building on prior work, we aim to better understand the catastrophic forgetting phenomenon when faced with series linear regression problems that are revisited in cyclic order.
In machine learning, many data sets display cyclic or periodic patterns. These patterns often arise from factors such as the "day of the week effect" [QR22] observed financial or search engine data (Yn++22). Additionally, the methods of cyclic alternating projections by Von Neumann (Von49) and Halperin [Hal62) are well-studied methods for solving linear systems [Kar37]. Equivalently, one can think of this as studying residual bounds for cyclic block Kaczmarz-type algorithms. Our work can be thought of as studying the worst-case forgetting of these popular methods. (Evr+22) mentions this perspective, but leaves open the problem of obtaining tight convergence bounds. In particular, dimension dependence on the ambient data the bounds of [Evr+22] could be problematic since high-ding high-dimensional data is so ubiquitous in machine learning. In contrast, our new bound for the worst-case forgetting does not scale at all with the dimension of the ambient data.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Problem Setup
The learning algorithm we consider fits linear map to a of data points of the form (Z.y) with F R2, y E TR.
Our data is split into "tasks", which are lists of elements from our dataset (with repeats allowed). These tasks are fed to our learning algorithm one a time. Our algorithm updates its prediction after being given each task.
We assemble the inputs of the /th task into a matrix X E gradd, where each row is an input vector ET, and their corresponding outputs into a column vector T E R" We aim to to find a column vector V E IR such that X₃ = ye for all
The learning algorithm initialize dgg E Rd anywhere, and for E Zz1 we set wi to be the projection of w onto the solution space P. for the fth regression problem. That is,
consider applies block Kaczmarz update at each step. Explicitly,
Wh++1 = Wi + (7 - X(+1
where + denotes the Moore-Penrose pseudoinverse.
Geometrically, the set of vectors V [ such that the map R + R: / H a agrees with all the data in task is an affine subspace Pt. This algorithm obtains wx+1 by projecting wi onto Pr+1- The set of vectors in Rd satisfying all tasks is P == Nr P.. The algorithm never leaves the maximal affine hyperplane through Wh perpendicular to P. so if the we converge to a solution then it converges to the solution closest to Wo..
is well-known that running gradient descent to interpolation with quadratic loss on task starting from Wy produces W1++1-
Typically, projecting onto the solution space for task t moves u off the solution space for task t t- 1. We wish to understand the amount of information "forgotten" over the course of training. Following [Er++22], we define the forgetting for a sequence of tasks and initialization S at iteration
1 Fn(n) = n
N -711
That is, (n( is the average loss of w. on all previous tasks (including task n)), where each task is weighted equally regardless of how many data points it has. As mentioned in the introduction, large forgetting is not always undesirable, but "forgetting" in humans is not always undesirable either, so the name "forgetting" not imply an inappropriately negative connotation.
In this work, we focus on cyclic task orderings. That is, we have T tasks (X1.8)).... "...... (Xy, yr) we visit cyclically, i..., X₁ = Xx mod T+1 and y Vi mod T+1 for all t. Then the sequence of iterates converges to a cycle of length T in the sense that, for any 1 E Zzo. We, WT+T, Wt+27, converges, either linearly after finite number of iterations; We justify this in the supplementary material.
In particular, if there is at least one simultaneous solution to tasks, then the limit must be a solution; We justify generalization of this in the supplmentary material, so we get linear convergence to solution which implies linear convergence of forgetting.
However, this does not guarantee that, for any collection of T tasks in m cycles, the forgetting can be bounded above by O(c "m) for some constant c, even after normalizing the tasks in the way we describe later: The choice of tasks that give the largest forgetting for one value of m may not be the tasks that give the largest forgetting for another value of m. Here we ask whether we can obtain worst-case bound on (m(TT) that only depends on the number of tasks T and the number of cycles m.
We focus on bounding the forgetting after a whole number of cycles; The forgetting in the middle of cycle is weighted average of the losses each task, and therefore can be treated in the same way as getting a bound without normalizing the tasks. For quick bound, the weights are close to 1, so we may rescale the tasks to get all coefficients be 1 or less without increasing our bound much. The forgetting for T tasks after m cycles is
mf
T
X - 17.12
[X - -2
(1)
m
T

---

each of the T tasks is visited equally often.
This can be made arbitrarily large by scaling the data points, so we describe normalizations in the next section. Given these normalizations, [Evr+22] showed that such a worst-case bound is possible, but the bounds they provided are not tight. Here, we improve on the forgetting bounds from [Evr+22] and, as a byproduct, show the union of the numerical ranges of all products of T orthogonal (real or complex) projections forms sinusoidal spiral.
1.1.1 Normalizations
Following [Evr+22], we restrict to the setting where P nonempty (i.e., the union of all tasks is consistent with single linear function) and let W. P. So every data point (ž, y) satisfies z" WT_ = y. and the planes P; we project onto all pass through u...
Unlike [vr+22] we translate the setup so w. = 0. This modifies each data point (ž, y) by setting y but preserving d.. This translates the P. to pass through 0, so they are subspaces, and P, the kernel of X,, and the loss of task t at E is now || [X,,ū|], turning forgetting into.
Fn(n)= = Σ X
X X₁
(w))
where the product is the categorical product. Thus, for fixed collection of tasks X1, X2,..., Xn. abusing notation to let Pe denote the projection onto the plane Pt, the largest forgetting over all
X
x,
P.) i 1
initializations Wh
Rescaling We rescales iterates, and hence the forgetting, by the same amount. So we normalize ||o 1. Similarly, rescaling all tasks X, by the same scalar scales each term in the forgetting by that factor, so we normalize so that max, Xx 1.
As |||||| decreases in i, this implies the loss of th at task t is | | < 1, and hence the forgetting most 1.
In the cyclic setting, for fixed T and m. these normalizations make the domain of optimization (the space of -uples of tasks with max, Xxe| < 1 and initializations wh sd-1) compact, so forgetting attains a maximum, which is what we bound in this paper.
In the supplementary, describe tighter normalization that gives the same forgetting bounds.
1.2 Observations
In this section, we describe some observations that help us get our bound.
As noted in the previous section, using our normalization, there is trivial bound on the forgetting of 1.
The data matrices X, only affect the iterates W, via their rowspan (i.e., the span of the data points in the task), so we may replace X; by any other data matrix with the same rowspan, or equivalently the same kernel, without affecting the iterates subject to normalization constraint. As ||X S it a contraction, so the norm of the image of any ú is at most its distance to the kernel, and this is realized when X; is projection away from its kernel. Therefore, the worst-case bound is not affected by restricting X; to be orthogonal projections with kernel P.-
With this restriction, for any wi, |||] is the distance from / to P.. Therefore, the forgetting can be interpreted as the average distance to each P. over all previous tasks (weighted equally).
1.3 Prior Work
Bounds on forgetting. Fvr+22 considered forgetting bounds both for random task orderings and cyclic task orderings. However their bound for eyclic task orderings is not tight. After cycles of T

---

tasks, they show an upper bound of min
{
T2
on the forgetting, leaving gap with their 2m7
I'd
VmT
lower bound of S2( T
mt
key step of their proof is bounding || | /7 where A is a product of T projections and u is unit vector. Their dimension-independeee bound gives a T /mT dependence on the forgetting after m eycles. Their other bound improves the m dependence, but only uses that A is contraction. This forces linear dependence on the dimension d, this is possible if the supremum is taken over all contractions. Indeed, for any m a multiple of d, one can have
||A"" - ||A bo| N M(d/m)
by choosing A be an operator that maps
Ex + (1
)
m
and taking ã = ēτ where E denotes the ith standard unit vector.
RRZ23 bound || A 1m+ for A a product of projections. However they are primarily interested in the asymptotics with respect to m. They supply two proofs which rely on either the bound in [BS16] or in [Cro08), and hence do not avoid the exponential dependence in T.
[in++3] study forgetting from a different perspective. They assume Gaussian i.i.d. tasks ( caaledd features in their paper) at each iteration and explicitly compute the expected forgetting and general- ization error. We analyze the worst-case forgetting without any assumptions on the distribution of tasks, so work is quite different from [in+23]
As mentioned in [Er++2]], the iterate W, can be equivalently obtained by running the (block) Kaczmarz method INT14] with the cyclic row selection rule for solving consistent system Xpw, Vt [T]. However, most id=MKJof the convergence analyses of Kaczmarz-type methods EIIO, NT14 SV09) bound the distance from the least-norm solution, whereas in our setting we interested the residual errors. Moreover such analyses depend on the condition number of the system, so are unlikely to adapt to our setting, since our bounds hold for all choices of tasks (i.e. blocks), with no condition number dependence.
Bounds on the numerical range. Lemma 5.1 in Cro08 gives a bound on the numerical range of any linear transformation A expressible as a product of projections. This, combined with other When combined with the results
results in that same work, yields a bound on ||A A x of [Evr+22], the result is a bound of the form O(f(T)/m on the forgetting. However, the function f(T)) turns out to be exponential when applying the results of [Cro08] directly. This is due to Lemma 5.1 of [Cro08] being loose. There they show that the numerical range of A is contained in region of C wwth a boundary point one where the tangent lines 1 have exponential slope. this paper, we give the smallest region that is guaranteed to contain the numerical range of A given only T.
BS16 also gives bound the numerical range of a product of projections. Specifically they show that the numerical range is contained in a Stoltz domain with the angle at depending on a quantity called the Friedrich's 's number of the (subspaces associated the) projections. They then combine their bound with that of [Cro08] to obtain somewhat tighter control over the numerical range. However the Friedrich's 's number for I' subspaces can be made arbitrarily close for our purposes their bound will not yield better results than the bounds in [Co088.
1.4 Results
We give nearly optimal bound on the forgetting for cyclic task orderings, removing the dimension dependence of [Evr+22 and avoiding the exponential dependence on T that would arise from applying results in [Cro07].
Theorem 1.
sup Fs(mT) SO T
where S runges over all (task, initialization) pairs where the tasks are given by matrices X1, X2,...... Xx with max; |Xell < 1 and Wo E Rd with [ 1.

---

To prove this. [Evr+22] show that, if A denotes the linear map given by one cycle, letting (m) == ||AT || m wil.
T --1 2
T-1 Am 1 A)II-
sup (s(mT) S
Am
2
We provide a geometric interpretation their proof in the supplementary material. [CP17] that there exists a constant Q - 1+ v2 such that
showed
[|p(A)]I S Q sup [p(=)] =EW(A)
for all polynomials p. Our approach is to determine UA ((A) where A ranges over all products of & complex orthogonal projections. As this includes the class of products of & real orthogonal projections, combining these inequalities gives our bound.
We will show in Section that the problem of bounding the numerical range of the product of k - 1 complex orthogonal projections is equivalent understanding the range of the product
P(uo..... 1 (vo. 0 (01, (22 (ūx-2, 2, Th -
bu)
where the 0, range over complex vectors in Cd of norm 1. We give a complete description of the range of P the filled sinusoidal spiral
re" cos(T//k)r cos(
π k
This shape has simple geometric description. Let PA be the convex hull of the kth roots of unity. Then the sinusoidal spiral above is the image of Pa under the map + 2
The main challenge in computing P's range r is in computing its boundary since topological argument (given in the supplementary material) shows that F; is simply connected. To compute the boundary, first observe that it suffices consider input vectors in C2. To see this, P maps sequence of vectors to the cyclic product of pairwise inner products, so any of the input vectors is coplanar with its neighbors, then projecting it onto the plane spanned by its neighbors and scaling it to have unit norm increases the magnitude of the corresponding factors. So it suffices to consider the case when all vectors are coplanar, which is equivalent considering input vectors in C2, In this case, P is smooth map from the (real) manifold (5²) C C" to the (real) manifold C, so any input that gets sent to boundary point T has singular Jacobian. That is, the directional derivative in all directions tangent to the domain must be parallel. It turns out that these algebraic conditions can be manipulated characterize all critical points and critical values of P. and the computation made simpler by using quaternions.
As side effect of our proof, we also fully describe the tuples ūn ....... - that map to boundary points of the image of P and show that they naturally correspond (up to multiplying each in by complex unit Φx) certain quaternionic roots of unity.
Using this result we obtain the following bound on the increments between consecutive powers of A when A is a product of projections. We believe this result may be independently useful.
Lemma 2. For any linear map A: C
C expressible product of k complex projections,
[[ A) < (C on k
m
where an absolute constant which can be taken be 0.4.
This lemma, with the inequality of [Er++22), immediately implies Theorem
In particular, for fixed T, we obtain an asymptotically optimal bound in terms of iteration count m, independent of dimension. In contrast, the dimension-inndeeedden bound given in [Evr+22) was sub-optimal by factor of /m.
Finally, So our results be interpreted giving bound for this setting well.
5

---

variable name
element of
a. b,
U, t
C2
q
H
100
050
025
0.00
-0.25
-0.50
-0.75
-1.00
0.
Figure 1: The boundaries of m for m = 22, 23
27. ,?.,,....
1.5 Notation for proof
We use C and to denote the complex numbers and the quaternions. While the previous sections considered real vector spaces, proof works by obtaining bound over all complex projections. So for sections 2 and 3, all vector spaces will be over C. In these sections, we use the following guidelines for variable names:
Our complex inner products are always conjugate linear in the first argument, so (ū, w) 6" where v" denotes the conjugate transpose of J. The argument of a complex number is taken to be in (-T, x]. The numerical range of a matrix A E Cdxd is defined by
((A)= = AzIE C4, || = 1}.
Bounding the range of P
In this section, we fully describe the range of P given by 2 and obtain full description of the inputs that map to boundary points. We will use the following notation throughout the next argument. Definition 3. For (a, b) E C2 we define b), == (,, -)).
The following identity is straightforward consequence the definition.
Proposition 4. For U, w E C2, (ū, a-) - w).
Our first theorem shows that the range of P is a filled sinusoidal spiral. This result is mathematical interest its own, and will also be applied to eyclic forgetting bounds in the next section.
We begin with a lemma characterizing the critical points of P treated as smooth map R22 - R... We defer the proof to the supplementary material.
Lemma 5. For any critical value c E C of P, there exists a sequence of vectors (ao: bo) = (1,
(ak-1, such that P((am) ) = c. Furthermore, there exist a, 3 E C
such that
1. ((am, bm)) (0m41, bm+1)) for all m
2. ((am: bm) (Am+1, bm+1)) m-1 for all
(where indices are treated mod k). Furthermore, any sequence (m)m)))) attaining ((((a,; by (=1))) e can obtained by taking sequence satisfying the above conditions and multiplying each vector by complex unit.

---

Given this characterization of P's critical points, our next result computes the boundary points of P's image, from which we obtain the entire image of as consequence.
Theorem 6. Let Pluu...., Uk-1) = (06. b)) (01, (2)) ... (ūk-2: Uk-1) (Uk-1, Bo) and let I& be the range of P as each Us ranges over unit vectors in C² Then
T&
re
cos
π K
r
1/k 2 cos
0 - π
r
2
0, 0.00
[0. 2m
k
which is a filled sinusoidal spiral.
Proof. We show this result for vectors in C² In the supplementary material, we show that increasing the dimension does not affect the range, so considering vectors in C² is sufficient. The result is trivial for k < 2, so we will assume k 2 3.
The domain of P is compact, a is also compact. P is also smooth (as function RR - ?R?), so its boundary consists of critical values. We will give complete description of the critical values and critical points and show that the outermost critical values form sinusoidal spiral, which is enough to show that I' is contained in the claimed region. We defer showing that I' contains the entire filled spiral the supplementary material.
Fix critical value e P and let dg,b, be as in Lemma 5 above. As (ams bm) and (ams bm) are orthogonal, they form a basis for C2, so letting ao bu we get recurrence relation
(01, = a(1, 0)+
(a2, a(a1, b1) Bu(a1, b1)=
(az, bz) aa2 b2) 3w2 (a2, b2)
(ax-1, al b + Bw (ax- b2-2) (1, (0o, bn) alax - + Alr (ak-1, / by bz-1)
Representing each vector (a, b) E C as a quaternion via (a, b) + a bjj it follows from direct
computation that (a, b)- + j(a + bj) and, for ø E C. Φ(a, b) + sla+ + bj) = (a + bj)ø. In
particular, multiplication the left by complex number is unambiguous.
Our recurrence relation can be expressed as
a1 + bıj (a + B1) 0j)
02 + b2j = (a (a)) + bbj)
03 + baj = (a + uwr i] + b2j)
ak-1 + by = (a+ B (a) by 25)
1 0j = (a + 3w" (ax ) + by bz-
In other words, the vectors must be the partial products
(ams bm) = (a + mn {a (ax + m- (a + Bwoj)
for m 0, . (which is the empty product of m 0), where a, B satisfy the equation
(a + 3w" (a + 3wt ... (a + B)
We now show that any sequence of vectors (ao. bo)..... (ax-1, hk-1) in solution to the above system of equations can be obtained by slightly modifying solution in the with a different value of k).
(possibly
Let Ça be (not necessarily primitive) complex kth root of unity. Consider the sequence
(oo,bo); bo), (a15a, b1))), (2252 bo(R), (ak-15h k-1 by b 11-1).
c-1)
7

---

This also satisfies the two conditions in Lemma 5 so we can run the same logic above. The corresponding change the resulting system is this multiplies a, B by Se and by Gk. so by multiplying each vector by these complex units we may freely modify w by Ç for any kth root of unity Çk. or equivalently any power of e
If & is odd, this is enough to show that any nonzero critical value can be ob- tained by w
and furthermore that any critical point be expressed as (ao, bo), (arCe, bi (x), (a2Ck, b25))... ( - - 1 for some kth root of unity Çk- If l is even, let C2e be a 21th root of unity. Consider the sequence
(au, bu), (an bi C2k), (2252kr b2l2e).... (ak- 1-11 b
(ao bn ) (a) S26 by S2k ck+t),, )...), (ux-1 22--1 by- S2k
22-1))
This satisfies the conditions in Lemma for 2k in place of k. The corresponding values of a, 3 the resulting system are the same in the original multiplied by (2x, and the resulting value of w is the same as the original multiplied by 22.. As 22, can be chosen to be w- we can reduce to the case
= (a2x(a + 2k- (o)2a-1)) ()) (a + BW 2k-22 (2))--)))--- (S2x + Bw0j))
where w = 1. or equivalently
== (S2x + Bj))
Remark 7. These reductions can also be interpreted using quaternions, which we demonstrate the supplementary material.
For any integer m, the muth roots of unity in HH are precisely those numbers whose real parts are the same as those of the real parts the mth roots of unity in C. So (a + 3y) -1 if and only a lies on one of the vertical diagonals of the m-gon whose vertices are the mtth roots of unity (where the vertical diagonals are those with constant real part, including sides of the n--gon)
Therefore, the values of a in the phase-shifted sequences are vertical diagonals in the regular k-gon i is odd and every other vertical diagonal in the regular 2k-gon if is even, where the vertices are the corresponding roots of unity. Inverting the phase shift gives that, regardless of whether l is even or odd, the values of a the solutions to
1 = (a -w () +
(a B)oj)
form the diagonals (including the sides) of the k-gon whose vertices are the leth roots of unity.
As the inner product of consecutive vectors at such a sequence is a, the value of P at such sequence is a²_ Therefore the critical values of are then kth powers of these diagonals. Furthermore, when is odd the critical points are sequences of the form (am, bm) = dm (a + 3j)" where a + 3j is quaternionic kth root of unity and Φm are units in C; When & is even, the critical points are sequences of the form (ams bm) = Φm (a + 3j) where a + ßj are quaternionic 2kth roots of unity and dm units in C,
By the maximum principle for holomorphic maps, the outer boundary of I' is obtained by taking the kth powers of the sides (where each side maps to the same curve). Using polar coordinates, the resulting curve is the sinusoidal spiral cos( } -1/k cos( f-
The same proof shows that all other critical points other than those that P sends to 0 arise from the other diagonals of the polygons and their corresponding critical values are their kthh powers, which are also sinusoidal spirals. computation shows that sequence of vectors that P sends is critical point if and only if at least two of the inner products are O.
3 Application to cyclic forgetting bounds
As an immediate application of Theorem 6 we can control the numerical range of product of orthogonal projections.
Corollary 8. Let A Pt P........ Pi be a product of orthogonal complex projections Cd - Cd. Then W (A) C T
8

---

Proof. We first observe a general fact. Let P: Cd + Cd be an orthogonal projection and let 2 E C
Let q
Then [S
Pg
P 74 2) qq
Now let z be an arbitrary unit vector and let
T P.P; 1.... PI
PP:P-- 11
Iterating the fact stated above,
[ (qiT)) === Pi.
for all E [k]. Hence
- 2 (gh 14-- (q: = = (z, Tx> (gk T1- (12.9) (),
(hk-1
so W (A) C T
In the supplementary material, we use our characterization of P p- (ar k+11 to characterize the pairs (A, 2) such that A ör k+1-
We now bound || (T - A)ll uniformly over all linear maps A C + C that can be expressed
product of k complex projections by applying the above bound the numerical range into the
result of CP17 that there exists constant Q
v such that
[Ip(A)] S Q sup [p(=)]
=A)(A)
for all polynomials p. We defer the calculation the supplementary material. Lemma 9.
4
sup 1T 2)1
+ 0s.m (1)
=ETx
m
en
can be improved in terms of & will be given in more precise version of this bound in which the supplementary material.
m
This, combined with Crouzeix's inequality, gives Lemma which restate below precisely, and hence Theorem[]
Lemma 2
For any linear map A: C - C expressible product of i complex projections,
A (I - A)l S m ( ex² Ox. (1) Q
where Q the constant of Crouzeix's inequality as presented above.
4 Real projections
In the application to forgetting, all relevant projections are real projections. Therefore one may ask whether our bound can be improved by restricting to products of k real projections.
As we show in the supplementary material, the union of the numerical ranges is the same even if we restrict to real orthogonal projections R + R& and it is possible to get the maximal asymptotic decay rate on 1 mm+1 but any real complex sequence orthogonal projections attaining point on Ør in its numerical range can be orthogonally decomposed into invariant (under all projections) subspaces U @ V where ||A'-aT]| || * xill decays quickly U. In particular, any indecomposable such sequence must have quickly decaying forgetting.
Future Work
It is not clear that this yields completely optimal bound for forgetting. Is it possible improve O /m) to O(T/m) matching the lower bound of (Evr+22]?
Finally one might wonder how rare the worst-case bound is. For example if one visits the T tasks cyclically, but in a random order possible beat the OTT2/m bound, perhaps with some weak dependence on the ambient dimension?

---

6 Acknowledgment
The authors would like to thank Itay Evron for interesting discussions about [vr++22
References
[Kar37]
Stefan Karczmarz. "Angenaherte auflosung von systemen linearer glei-chungen". In: Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat. (1937), pp. 355-357.
[Von49]
John Von Neumann. "On rings of operators. Reduction theory". In; Annals of Mathemat- ics (1949), PP. 401-485.
[Hal62]
Israel Halperin. "The product of projection operators". In: Acta Sci. Math. 23,1 (1962), pp. 96-99.
[EI(80]
Tommy Elfving. "Block-iterative methods for consistent and inconsistent linear equa- tions". In: Numerische Mathematik 35 (1980), pp. 1-12.
[TM95]
Sebastian Thrun and Tom M Mitchell. "Lifelong robot learning". In: Robotics and autonomous systems 15.1-2 (1995), pp. 25-46.
[Cro07]
Michel Crouzeix. "Numerical range and functional calculus in Hilbert space". In: Journal of Functional Analysis 244.2 (2007). pp. 668-690.
[Cro08]
Michel Crouzeix. "A functional calculus based on the numerical range: applications". In: Linear and Multilinear Algebra 56.1-2 (2008), pp. 81-103.
[SV09]
Thomas Strohmer and Roman Vershynin. "A randomized Kaczmarz algorithm with exponential convergence". In: Journal of Fourier Analysis and Applications 15.2 (2009), p. 262.
[NT14]
Deanna Needell and Joel A Tropp. "Paved with good intentions: analysis of a randomized block Kaczmarz method". In: Linear Algebra and its Applications 441 (2014), pp. 199- 221.
[BS16]
Catalin Badea and David Seifert. "Ritt operators and convergence in the method of alternating projections". In: Journal of Approximation Theory 205 (2016), pp. 133-148. Michel Crouzeix and César Palencia. "The numerical range a (1+2)-spectral set". In: SIAM Journal Matrix Analysis and Applications 38.2 (2017), pp. 655.
[CP17]
[CL18]
Zhiyuan Chen and Bing Liu. "Lifelong machine learning". In: Synthesis Lectures on Artificial Intelligence and Machine Learning 12.3 (2018), pp. 1-207.
[Kem+18]
Ronald Kemker al. "Measuring catastrophic forgetting in neural networks". In: Pro- ceedings of the AAAI conference on artificial intelligence. Vol. 32. 1. 2018. German Parisi et al. "Continual lifelong learning with neural networks: A review". In: Neural networks 113 (2019), pp. 54-71.
[Par+19]
[VT19]
Gido M Van de Ven and Andreas S Tolias. "Three scenarios for continual learning". In: arXiv preprint arXiv:1904.077: 07734 (2019).
(Had+20)
Raia Hadsell al. "Embracing change: Continual learning in deep neural networks". In: Trends in cognitive sciences 24.12 12 (2020), pp. 1028-1040.
[Evr+22]
Itay Evron et al. "How catastrophic can catastrophic forgetting be in linear regression?" In: Conference on Learning Theory. PMLR. 2022, pp. 4028 4079.
[QR22] Chao Qin and Daniel Russo. "Adaptivity and confounding in multi-armed bandit experi- ments". In: arXiv preprint wrXiv:2202.0903: (2022).
[Yan+22] Yingxiang Yang et al. "Fourier Learning with Cyclical Data", In: International Confer-
ence on Machine Learning. PML.. 2022, pp. 25280-25301.
[Lin+233] Sen Lin et al. "Theory on Forgetting and Generalization of Continual Learning". In: arXiv preprint arXiv:2302 05836 (2023).
[RZ23] Simeon Reich and Rafal Zalas. "Polynomial estimates for the method of cyclic projec-
tions in Hilbert spaces". In: Numerical Algorithms (2023), pp. 1-26.
[Wan+23] Liyuan Wang et al. "A comprehensive survey of continual learning: Theory, method and application". In: arxiv preprint w:Xiv:2302.00488 (2023).
10


Reviews:
[{"review_id": "AxnMdqbNnQ", "reviewer": "Reviewer_U3GB", "summary": "Consider an overparametrized system solving a periodic sequence of tasks in linear (least squares) regression in the following way: starting from a weight vector $w_t$ for task $t$, perform gradient descent  to solve task $t+1$, which, due to overparametrization, will eventually return an exact solution $w_{t+1}$ for task $t+1$. Here $w_0 = 0$ and each task is specified by a set of input vectors $X$ and output labels $y$.\n\nThe procedure amounts to projecting $w_t$ onto the solution (hyper-)space of task $t+1$ and implies a loss of information about task $t$ and all previous tasks. This raises the question just how much is forgotten after n tasks have been visited, which can be quantified as the error of $w_n$ averaged over all previous datasets. While this \"forgetting\" depends on the data, it is still possible to give a worst case bound for the worst possible periodic task sequence with period $T$.\n\nPrevious work gives a bound of $T^2/\\sqrt{nT}$ and a dimension dependent bound, as well as a lower bound of order $T^2/n$, the paper at hand gives order $T^3/n$, which has optimal dependence on n, though not on T.\n\nThis result is obtained by a reduction of the problem to a bound on the numerical range of a polynomial in $T$ projection operators, which is obtained by an intricate analysis, which (because of time constraints) I didn't completely verify, although I didn't find any flaws.", "questions": "The various bounds are sometimes expressed in terms of the number of iterations and sometimes in terms of the number of cycles. This may cause some confusion. Would it be possible to unify this?\n\nThe $m$ in l 43 and in (1) seems to be a typo.", "limitations": "The authors have adequately addressed the limitations of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper approaches an interesting problem with an equally interesting mathematical technique. The given bound is a relevant improvement and to me seems an important contribution to the subject of continual learning.\n\nThe problem is clearly stated, the minor limitations of the main result are nicely exposed already in the title by the word \"nearly\".", "weaknesses": "The paper is technically very heavy in the proofs of Lemma 4 and Theorem 5. If possible the authors might sketch the basic ideas of the proof of Theorem 5 in a short paragraph. \n\nThe statement of Lemma 4 is somewhat opaque and its relevance to the problem is not immediately clear. It doesn't help that $\\Gamma_k$ shows up in the proof of Lemma 4 (l154), while its definition comes on the next page in the statement of Theorem 5. \n\nThe paper leans strongly on the reference [Evr+22], without which it is very difficult to understand. At least Theorem 11 in [Evr+22] could be reproduced.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Technical Proofs: As Reviewer eHkq suggested, we will move part of the proofs to the appendix and include a high level proof in the main body. We summarize the proof of Theorem 5 as follows: To compute the range of $P$, we show that the outer boundary of $P$ is the claimed sinusoidal spiral and show that the range is simply connected, which implies that the range is the filled sinusoidal spiral. Once we get the outer boundary, the simple connectedness follows from a topological argument given in the supplementary material. To compute the outer boundary, as $P$ takes a sequence of vectors to the cyclic product of pairwise inner products, if any of the input vectors is not coplanar with its neighbors, then by projecting it onto the plane spanned by its neighbors and extending it to be unit norm, we can increase the magnitude of the corresponding factors without changing any directions (shown algebraically in the supplementary material), so it suffices to consider the case when all vectors are coplanar, so it suffices to consider $\\mathbb{C}^2$. In this case, $P$ is a (real-)smooth map the (real) manifold $(S^1)^n\\subset\\mathbb{C}^n$ to the (real) manifold $\\mathbb{C}$, so any input that gets sent to a boundary point of $P$ has singular Jacobian. That is, the directional derivative in all directions tangent to the domain must be parallel. It turns out that these algebraic conditions can be algebraically manipulated to characterize all critical points and critical values of $P$, and the computation is made simpler by using quaternions.\n    \nReference to $\\Gamma_k$: We will remove the reference to $\\Gamma_k$ in the proof of Lemma 4 in the main paper by changing the statement to exclude 0 (where the statement is false, but this doesn't affect the rest of the paper).\n    \nReliance on Reference:  We will add a re-statement of Theorem 11 from [Evr+22] and some exposition around this result.  In addition, in light of our response to Reviewer eHkq titled ``Precedent for Problem'', we plan to also add more exposition and motivation, alleviating the heavy leaning on the [Evr+22] reference."}, {"review_id": "9qxpMy69Dt", "reviewer": "Reviewer_eHkq", "summary": "This paper describes bounds for cyclic forgetting when an overparametrized linear model is fit successively to a series of tasks. The exact same setting has been studied fairly recently before in the , and the main contribution here is to improve dimension dependence of the bounds.", "questions": "- Please make a pass for key typos. The abstract says T^3 instead of T^2; lines 52-53 shouldn't have T in the denominator anywhere; and many more. \n- Is there scope to extend these results to parametrize dependencies between tasks?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The theory of Theorem 5 is clean and beautiful, and certainly of mathematical interest in its lack of dependence on ambient dimension. The core idea is creative and the writing is good.\n\nLines 56-62 of the text are valuable for intuition as to why the suboptimal dimension dependence arises, and how to fix it. This is a very interesting insight which could potentially be exploited for more data-instance-dependent bounds in the future.", "weaknesses": "Catastrophic forgetting arises especially when there are certain types of dependencies/correlations between the tasks. This entire manuscript is about studying that situation theoretically, but it completely neglects to provide. The manuscript relies on the publication [Evr+22] to set precedent for the problems studied. However, that paper was pathbreaking in setting up the problem and establishing that cyclic task orderings don't suffer catastrophic forgetting, and included much more interpretation and exposition linking the theory result to the motivation for studying the problem. The current manuscript does not give any of this. Instead, the main result obviates all dependencies on the tasks other than their number, so it does not lend much further insight into the problem.\n\nThe proofs are far too long and technical for the main body of the paper - they should be moved to the appendices. The entire discussion leading up to Theorem 5 is full of mathematical beauty arising from symmetry - but none of this is in the service of the task of learning from different tasks, only using the generic fact that the tasks are projections. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Precedent for Problem: There are indeed motivations for our work discussed in referenced paper [Evr+22], that we list here, and will elaborate on in our introduction. \n\nMany data sets in machine learning are cyclic or periodic in nature, for example, due to the \"day of the week effect\" in  financial data or search engine data. In a manufacturing facility using robots, a machine or robot is typically instructed to repeat a series of tasks for producing certain products. Learning this type of task on arrival can be formulated as cyclic continual learning, which is our main subject of study in terms of catastrophic forgetting.\n\nAdditionally the methods of cyclic alternating projections (by Von Neumann and Halperin) and cyclic Kaczmarz methods are well-studied methods for solving linear systems. Our work can be thought of as studying the worst-case forgetting of these popular methods.  Equivalently one can think of this as studying residual bounds for (cyclic) Kaczmarz-type algorithms. While very natural, this is somewhat of a new take on analyzing the convergence of these methods.   [Evr+22] mentions this connection, but leaves open the problem of obtaining tight convergence bounds.  We think this problem is sufficiently natural to justify study.\n\nFinally since high-dimensional data is so ubiquitous in machine learning, we believe that the dimension dependence was a major weakness in the bounds of [Evr+22].  Indeed our bound captures a qualitative phenomenon: the worst-case forgetting need not scale at all with the dimension of the ambient data.  \n\nThe equations in lines 98 and 99 bound the forgetting of any single sequence of $T$ tasks after $m$ cycles by $(1+\\sqrt2)\\frac{T-1}{2}\\sup_z\\lvert (1-z)z^m\\rvert$ where $z$ ranges over the numerical range of the product of the projections in that sequence. Our paper bounds this over the class of all sequences of $T$ tasks by characterizing the union of their corresponding numerical ranges, but we do not yet have any simple subclass of sequences of tasks over which the supremum of this value over that class has a better bound. We have later characterized all tasks that attain the maximum possible value in each dimension and shown that none of them can optimize the forgetting.\n\nProofs Location: As a characterization of the union of the numerical ranges of the products of $k$ complex (and, after submission, also real) projections (for any fixed dimension) is mathematically interesting in its own right, we feel that some of the proof should perhaps be left in the main body. However, we agree that it would make sense to move more technical portions to the appendix, leaving more room for discussion.\n\nTypos: We will indeed make a thorough pass for typos. Note that lines 52-53 do not contain a typo, see ``Minor comments\" in the Reviewer SAj1 response. We agree that this could be more clear however.\n\nTask Dependencies: Dependencies between tasks is an interesting setting, and we do believe that this is interesting future work. Since this is a relevant question for a reader, we will add a remark discussing the challenges."}, {"review_id": "aQtZIbUlnU", "reviewer": "Reviewer_SAj1", "summary": "\nThe paper studies the setting of continual learning for linear tasks, and in particular the phenomena of catastrophic forgetting. \nThey prove the best known upper bound on forgetting for the setting of cyclic tasks.", "questions": "See above. ", "limitations": "none. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper demonstrates an upper bound on Forgetting that is independent of the dimension.\nThis is a strong improvement for settings with very large dimension spaces. \n", "weaknesses": "\nI think the main weakness is the significance of contribution, compared to previous work. \nThis result build on recent work by [Evron et al.22] and demonstrates improvement in a certain setting (cyclic).\nThe paper would be strengthened if either the results would be extended to other setting, and incorporated experimental evaluations - both of which similarly to [Evron et al.22].\n\nAdditional comments:\n\n1. Not clear why the paper use the term “near-optimal” : \n- The known lower bound from [Evron et al.22] at T^2/m. The bound given in this work has a worse dependence on T compared to [Evron et al.22]. The improvement comes for large dimensions, which is indeed important but not necessarily near-optimal ? \n\n2. Forgetting vs. Regret:    by Evron et al., in the cyclic setting both quantities of Forgetting and Regret will go to 0 as m increases. Since regret is a well studied quantity, it is interesting to compare these and examine how will the convergance rate behave ? a connection between them may allow to build on the vast literature on regret. \n  \n\nMinor comments: \n- Notation: I assume you mean $X_i \\in \\mathbb{C}^{r_i \\times d}$. Maybe say r_i refers to samples each with d dimensions. \n- Line 92 : “We give nearly a nearly optimal bound”\n- Citations do not indicate the names of all authors, incorrect format\n- Lines 52-53 - why write T^2/*mT instead of T/m ? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Significance: We would be happy to add a remark about other settings and compare our approach to that of [Evron et al.22]. The challenge with experimental results is that our bounds are worst-case bounds. Empirically, nearly-worst-case examples seem to be quite infrequent.\nHowever we could include a simple experiment showing empirical performance on the examples given in [Evron et al.22] that were used to obtain (theoretical) lower bounds on forgetting.\n\nNear-optimal bounds: Please see the response to reviewer kHo7 above titled \"Gap in $T$.\" In addition, we would be happy to modify the title to replace \"Nearly Optimal\" with \"Dimension Independent\" or \"Improved ... for high dimensions\", since we also agree that the improvement comes for high dimensions, which is quite important.\n\nForgetting vs. Regret: We think that regret is also interesting to study. A worst-case bound on the regret is indeed possible, however is fairly simple and does not require our results. To give a quick sketch: In our setting one can bound the regret (see Evron et. al. for a definition) by the average of the squared increments $\\|w_{k+1} - w_k\\|^2.$  By iterating the Pythagorean theorem one sees that $1 = \\|w_0\\| = \\|w_k - w_*\\|^2 + \\|w_k - w_{k-1}\\|^2 + \\ldots + \\|w_1 - w_0\\|^2$ which gives a (tight) bound of $1/k$ on the regret.  If one defines regret with the non-squared loss, then it turns out that one can give a tight bound of $1/\\sqrt{k}$ using a slightly more complicated (but still elementary) argument. (Both bounds are attainable in the cyclic setting, and both bounds also hold without the cyclic assumption.)\n\nTaking average regret over the last cycle is more relevant to our results. In this case, with $m$ cycles of $T$ tasks each, the average regret becomes $\\frac{\\|w_{mT}\\|^2-\\|w_{m(T-1)}\\|^2}{T}=\\frac{\\Delta_{m-1}(w^*)}{T}$. Combining this with the equation in line 98 of our paper bounds the worst-case forgetting by $\\frac{T(T-1)}{2}$ times the worst-case average regret over the last cycle.\n    \nMinor comments: We will correct the formatting and notation as suggested.  Our original reason for writing $\\frac{T^2}{mT}$ was to make it look more similar to the other bounds in that sentence ($\\frac{T^2}{\\sqrt{mT}}$ and $\\frac{T^2d}{mT}$), and thus easier to compare; An earlier version of our paper stated our main bound as $\\frac{T^3}{mT}$. Furthermore, $mT$ is the total number of iterations, which may help interpret the bound. However, we ended up stating our main result using $\\frac{T^2}{m}$ because, as an independent theorem, the first advantage does not apply."}, {"review_id": "jjr2J10Kvb", "reviewer": "Reviewer_kHo7", "summary": "Authors provide theoretical bounds on the forgetting quantity in the continual learning setting for linear tasks, where each round of learning corresponds to projecting onto a linear subspace.\nFor a cyclic task ordering on $T$ tasks and an arbitrary iteration $m$, they prove the upper bound of $O(T^3/m) $ on the forgetting. For the proof they use a bound on the numerical range of a product of T projections.", "questions": "What is the differnce between the $T^3/m$ bound in the abstract and the $T^2/m$ bound presented in the paper?", "limitations": "As they mention in the conclusion there are some gaps for real projections and  for forgetting, all relevant projections are real projections.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-near optimal bounds are proven for the worst case for cyclic task ordering(also improving the bounds for less general settings if I understood the related work section correctly): their upper bound $O(T^2/m)$ compared to a $\\Omega(T/m)$ lower bound and the previous known upper bounds $O(T^2/\\sqrt{mT})$.\n\n-also provides a bound on the numerical range of a product of $T$ projections", "weaknesses": "(Common) notations could be defined earlier or there could be a reference to the noation section when first notaions are used in the introduction.\n\nThere is still a gap of T if I understood everything correctly.\n\nAs I am unfamiliar with some pieces of related work and Math/other details were not carefully checked so it is hard to rate the novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Notation: We will clarify the notation in the introduction as suggested.\n    \nGap of $T$: To clarify: The upper bound given in our paper has worse $T$-dependence than the lower bound given in [Evr+22], but it has the same $T$-dependence as their upper bound for any fixed dimension. Our bound of $O(\\frac{T^2}{m})$ may appear to have worse $T$-dependence than their dimension-independent bound of $\\frac{T^2}{\\sqrt{mT}}$ if $m\\ll T$, but in this setting both our bounds are worse than the trivial bound of 1.\n   \n \nReal projections: We have since resolved the real case in the following sense: [Evr+22] bounds the forgetting after $m$ cycles of $k$ tasks in terms of $\\sup_A\\lVert A^m(I-A)\\rVert$ where $A$ ranges over all products of $k$ (real) orthogonal projections. Our paper bounds $\\sup_A\\lVert A^m(I-A)\\rVert$ in terms of $\\sup_{z\\in W(A)}\\lvert z^m(1-z)\\rvert$ where $A$ ranges over all products of $k$ orthogonal projections and $W(A)$ denotes the numerical range of $A$. Our original paper computed the supremum over all products of complex orthogonal projections, leaving open whether adding the condition that the projections are real improves the bound.  We have since shown that real projections can attain the same supremum, \n\nAbstract typo: The $T^3/m$ in the abstract is a typo and should say $T^2/m$."}]

Author rebuttal:
We thank the reviewers for their feedback. The following are our responses to the questions and concerns raised by reviewers. 

We will move the proofs of the main lemmas and theorems (through Theorem 4) to an appendix.  This will leave room for additional discussion of the connection to previous forgetting bounds, as well as a less technical exposition of our techniques.

Please see the individual responses for more details.

Meta-review: This paper makes a significant advance on a problem that has attracted substantial interest, using sophisticated techniques.
Decision: Accept (poster)