The Joint Effect of Task Similarity and Overparameterization on Catastrophic Forgetting — An Analytical Model
Authors: Daniel Goldfarb
Itay Evron
Nir Weinberger
Daniel Soudry
PAul HAnd
Venue: ICLR 2024 poster (2024)
Keywords: deep learning
continual learning
overparameterization
task similarity
catastrophic forgetting
theory
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: Analyze the joint effect of task similarity and overparameterization on catastrophic forgetting by deriving an exact analytical expression for forgetting in a two-task random orthogonal transformation problem.

Abstract: In continual learning, catastrophic forgetting is affected by multiple aspects of the tasks. Previous works have analyzed separately how forgetting is affected by either task similarity or overparameterization. In contrast, our paper examines how task similarity and overparameterization jointly affect forgetting in an analyzable model. Specifically, we focus on two-task continual linear regression, where the second task is a random orthogonal transformation of an arbitrary first task (an abstraction of random permutation tasks). We derive an exact analytical expression for the expected forgetting — and uncover a nuanced pattern. In highly overparameterized models, intermediate task similarity causes the most forgetting. However, near the interpolation threshold, forgetting decreases monotonically with the expected task similarity. We validate our findings with linear regression on synthetic data, and with neural networks on established permutation task benchmarks.

Published as a conference paper at ICLR 2024
THE JOINT EFFECT OF TASK SIMILARITY AND OVER- PARAMETERIZATION ON CATASTROPHIC FORGETTING AN ANALYTICAL MODEL
Daniel Goldfarb" Itay Evron'2, Nir Weinberger 2, Daniel Soudry ?, Paul Hand
Northeastern University Department of Electrical and Computer Engineering, Technion
ABSTRACT
In continual learning, catastrophic forgetting is affected by multiple aspects of the tasks. Previous works have analyzed separately how forgetting is affected by ei- ther task similarity or overparameterization. In contrast, our paper examines how task similarity and overparamettrriztton jointly affect forgetting in an analyzable model. Specifically, we focus on two-task continual linear regression, where the second task a random orthogonal transformation of an arbitrary first task (an ab- straction of random permutation tasks). We derive an exact analytical expression for the expected forgetting - and uncover a nuanced pattern. highly overpa- rameterized models, intermediate task similarity causes the most forgetting. How- ever, near the interpolation threshold, forgetting decreases monotonically with the expected task similarity. We validate findings with linear regression syn- thetic data, and with neural networks on established permutation task benchmarks.
INTRODUCTION
Modern neural networks achieve state-of-the-art performance in wide range of applications, but when trained on multiple tasks in sequence, they typically suffer from a drop in perfor- mance on carlier tasks, known the catastrophic forgetring problem (Goodfellow Continual learning research is mostly dedicated to designing neural architectures and optimization methods that better suit learning sequentially (e.g., Zenke et al. (2017); De Lange et al.] (202T))
al.] 2013).
Despite these efforts, it is still unclear in which regimes forgetting is most pronounced, even for elementary models.
A number of works have explored the relationship between task similarity and catastrophic forget- ting [Bennani et al. 2020 Ramasesh et al. 2021: Doan et al. 202T; Lee et al. 2021; Evron et al. 2022 Lin al. 2023). While carlier works struggled to have consensus
whether similar or different tasks are most prone to forgetting, recent works suggested that continual learning is the easiest when tasks have either high similarity or low similarity, and that it is most difficult for tasks that have an intermediate level of similarity (Evron et al., 2022 Lin et al. (023). The main exper- imental evidence of this claim so far focused on the similarity of learned feature representations of a neural network (Ramasesh et al.) 202T). Theoretically, Lin et al. (2023) quantified task similarity using Euclidean distances between underlying "teacher" models. However, this notion of similarity cannot capture the task similarity in standard benchmarks (e.g., permuted MNIST), where typically the input features are changing between tasks (and not the teacher). Others (Doan et al. 2021 Evron et al. 2022 interpreted task similarity as the principal angles between data matrices.
In practice, neural networks are typically extremely overparameterizee. Several works have stud- ied, empirically and analytically, the beneficial effect of overparameterization in continual learning. particularly on the commonly used permutation and rotation benchmarks (Goldfarb & Hand 2023] Mirzadeh et al. 2022). In this paper, we propose a more refined analysis, which able to show the combined effect of overparameterization and task similarity for a general data model. We show that task similarity alone cannot explain the difficulty of continual learning problem, rather it depends also on the model's overparameterization level.
"Equal contribution. Correspondence <goldfarh.ddnorrhesseee
<itay @eroy@@eerr.........

---

Published as a conference paper at ICLR 2024
Our main result is exact analytical expression for the worst-case forgetting under two-task linear regression model trained using the simplest (S)GD scheme. Data for each task is related by a random orthogonal transformation Transformed Subspace (DOTS) controls the task similarity - the higher the DOTS, the lower the similarity between tasks. This similarity notion provides natural knob that controls how similar tasks are after a random transformation. This notion also closely characterizes popular permutation benchmarks, for which it was first suggested by the seminal work of Kirkpatrrc al. (0177)
randomly chosen subspace, and the Dimensionality of the
Figure M informally illustrates the essence of our result. When the model is suitably overparame- terized, the relationship between task similarity and expected forgetting is non non-monotonic, where the most forgetting occurs for intermediately similar tasks. However, if the model is critically pa- rameterized, then the behavior monotonic and the continual learning problem is most difficult for the highest dissimilarity level. This behavior illustrates how hard it is to estimate the difficulty of continual learning in different regimes.
Expected forgetting
Expected forgetting
19-2
10
10-
13"1
022
04
0.
0.0
0.2 0.4
Dim. of Transformed Subspace (Task dissimilarity)
Dim. of Transformed Subspace (Task dissimilarity)
(a) A highly overparameterized regime.
(b) Near the interpolation threshold.
Figure Informal illustration of our theoretical result. Formal details are shared in Section 2
The contributions of this paper are:
We present linear regression data model motivated by empirically-studied permutation tasks that exhibits joint effect of task similarity and overparameterriztion on catastrophic forgetting.
We derive exact non-asymptotic expression for the worst-case expected forgetting under model. We reveal a non-monotonic behavior task similarity when the model is suitably overpa- rameterized, and monotonic behavior when it is critically overparameterized. We demonstrate that contrary to common belief, overparameterization alone cannot always prevent forgetting.
We replicate this theoretically-obeevee interaction of task similarity and overparameterization using fully connected neural network in a permuted image setting.
ANALYSIS
We study linear regression model trained continually sequence of two tasks under varying overparameteriiztion and task-similarity levels.
2.1 DATA MODEL AND ASSUMPTIONS
Formally, consider two regression tasks given by two p-dimensional data matrices X2 E Rexp and single label vector y E R". The first data matrix X₁ can be arbitrary. For case notation, we often denote & X1.
The second task's data matrix X₂ is given by rotating the first task's p-mmeensional data in a random m-diimensional subspace for some m E [p). Specifically, we set X₂ = X,O = XO, where O RPXP is random orthogonal operator defined as,
= Q
O
and Qm O (m), Q, 0 (p) are orthogonal operators, sampled "uniformly". i.e., using the Haar measure of the orthogonal group. Our definition of the operator results in a more mathematically. tractable orthogonal transformation version of popular permutation task datasets (like the ones use in Section 3. where the labels stay fixed while features permute. This definition also reduces (when p) to the random rotations studied in Goldfarb & Hand (2023).
2

---

Published as a conference paper at ICLR 2024
To facilitate our analysis, assume that the first task is realizable by linear model (implying that the second one realizable as well). A similar assumption has been made a previous theoretical we do, arbitrary data matrices (rather than assuming
paper (Evron et al., 2022) that analyzed, random isotropic data). This assumption is especially reasonable in overparameterized regimes, such in wide neural networks under the NTK regime.
Assumption (Realizabilitt). There exists a solution w E R' such that X1w" = -Xw" =
Note that this assumption implies that the second task is also realizable (since X2(O) w*) XOO w Xw" = y). When p 2 2 rrank(X), it readily seen that the tasks are also jointly-realizable w.h.p.
2.2 THE ANALYZED LEARNING SCHEME AND ITS LEARNING DYNAMICS
We analyze the most natural continual learning scheme. That is, given two tasks (X1,y), (X2, we learn them sequentially with gradient algorithm, without explicttly trying to prevent forgetting.
(X2,y) y),
Scheme Continual learning two tasks
Initialize Wo = Op
Start from Wo and obtain Wi by minimizing L (i()) - X1 yl with (S)GD (to convergence) Start from W1 and obtain Wa by minimizing L2(w) _ X2w y| with (S)GD (to convergence) Output W2
The learning scheme above is known to mathematically converge to the following iterates,
W1 = arg min |w
woll s.t. y=X,w, X = X
(2)
WER
arg min |w will2 s.t. y y=x
x + (Ip - X2 X2) W1
wERP
where X is the pseudoinverse of (we use X X3 for analysis only; we do not compute them).
We now define our main quantity of interest.
Definition 2 (Forgetting). The forgetting after learning the two tasks (parameterized by X, w=, O), defined as the degradation the loss of the first task. More formally,
ww" & (w(2) L1 (w1) = X1W2 - y11 ||| - yll XXw2 - 2
Our forgetting definition is natural and relates to definitions in previous papers (e.g.. Doan et al. 2021)) l... Notice that under our Assumption [ the forgetting is the training loss the first task (exactly as in Evron et al. (2022)). Alternatively, one can study the degradation in the generalization loss instead, but this often requires additional data distribiitiiiion assumptions (e.g.. random isotropic data as in Goldfarb & Hand 2023); Lin et al. (2023), )) while analysis is valid for any arbitrary data matrix. Our analysis thus gives a better insight into the problem's 's expected worst-case error.
To analyze the forgetting, we utilize our data model from Section 2.1 to show that,
F(O; w*) = Xww - y/| x (x (I, X; w - y1
X==X0]
X(XO) X(X))XXXXXXXXX (x00) yyl
X= wi - -w==xt==X y Xw
= - (I- X Xw
(4)
[pscudoinverse propertics]
(XX (0 x XII Xw
Ml]]]
xo < X
where |X||| 0 max X). We used two pseudoinverse properties (any matrix X and orthogonal ma- Our upper bound is sharp, i.e. saturates when all nonzero singular values of X are identical. This allows for exact worst-case forgetting analysis.
trix O hold XX X and O
In the realizable case, minimizing the squared loss of linear model using (stochastic) gradient descent, is known to converge to the projection of the initialization onto the solution space (see Sec. 2.1 in Gunasekar et al.) (2018). This happens regardless of the hatch size (as long the learning rate is small enough). Finally, the projections are given mathematically using the pseudoinverses (e.g., see Sec. 1.3 Needell & Tropp (214)).
3

---

Published as a conference paper at ICLR 2024
2.3 KEY RESULT: INTERPLAY BETWEEN DISK-SIMILARITY AND OVERARRAETTERIZATON
We now present our main theorem and illustrate it in Figure 2on random synthetic data.
Theorem 3. Let p 2 4, E (p.....p).. m 2 2. Define Xp.d _ {X < n Z rank(X) }.
Define the Dimensionality of Transformed Subspace a - m2 as our proxy for task dissimilarity and
é 1-4 as our proxy for overparametertzation. Then, for any solution w R' (Assumption
the (normalized) worst-case expected forgetting per Def. (obtained by Scheme (
Eo (O; X, w-)
=0 2 (a
6a + 11a + 3 + 22a - 300 + 12)
max x
X X
X Xw*
8 (5a 18a² + 20a 6000-6) -6) + +0 (t).
where X Xw* projects w onto the column space X. Notice that X | X Xw" 112 is neces-
sary scaling factor, since the forgetting (Xw2-yl |X - X naturally scales with | and X Xw" 1|2. The exact expression (without the notation) appears Eq. 88) in Appendix
The full proof is given in Appendix C
Below we outline an informal sketch of the proof.
Proof sketch. In our proof, show that the expected forgetting is controlled by two important terms, namely, Eo (e. - EI -) e.)) and IFo o Σ E O)) for * J. where C, the 1th standard unit vector. Each of these expectations is essentially polynomial of the
entries of our random Qp. Qm from Eq. [ To compute these expectations (in Lemmas 6 and 8
we employ exact formulas for the integrals monomials over the orthogonal groups in p and 771 dimensions Gorin 2002). A more detailed proof outline given in Appendix C
Highly overparameterized: 1,p p 100 (B 0.99)
Interpolation threshold:
d 10, 100 (B- 0.9)
d' 100, 100 (8 0)
10a
Forgetting
10-1
10
Analytical bound
1
Empirical mean
1.0 0.0
0.8 1.0
0.6
0.8
Dim. of Transformed Subspace (a)
Figure 2: Empirically illustrating the worst-case forgetting under different overparameterization lev- els. Points indicate the forgetting under 1000 sampled random transformations applied on a (single) random data matrix X. Their mean is shown in the thin orange line, with the standard deviation represented by gray band. The thick blue line depicts the analytical expression of Theorem Here, we restrict the nonzero singular values of X to be identical, saturating the inequality in Eq. (4) Indeed, the analytical bound matches the empirical mean, thus exemplifying the tightness of our analysis. For completeness, in Appendix C.3
we repeat this experiment with 10 and p 1000.
2.3.1 INTERESTING EXTREMAL CASES
To help interpret our result, we exemplify it in several interesting regimes, taking either the task similarity proxy a or the overparameteriizatin proxy B to their extremes.
Highly overparameterized regime (3
+ 1). Plugging in f = into Theorem
we get
FoF O X. w*) a² -1-00 a) m
2
max XEX
1
(5)
Xw*
This behavior is illustrated in Figure I(a) and in the top part of Figure The mon-ooootonic nature of this behavior and its peak at a 0.5 corresponding to intermediate similarity, seem to agree with Figure 3(a) in Evron et al. 2022 (especially when repetitions are made, i.e., their k= curve).
4

---

Published as a conference paper at ICLR 2024
At the interpolation threshold (d
B 3= = 0). In this extreme, the theorem asserts,
Eo w")
2a
2m P
P.d
X A
This behavior is illustrated in Figure [(b) and in the rightmost plot of Figure 2
Notably, get a monotonic decrease in forgetting as tasks become more similar. This seems to contradict the conclusions of Evvon al. (2022), according which intermediate task similarity should be the worst. We settle this alleged disagreement in our discussion in Section
Minimal task similarity (m = - a m =), Plugging a = into Theorem we get
Eo FO w*)
|X X =2 28 82
max XEXP
This minimal task similarity regime matches the (noiseless) model of Goldfarb & Hand (2023).
where (generalization) risk bound with scaling of / proven under particular data model.
2.3.2 THE ENTIRE INTERPLAY BETWEEN TASK SIMILARITY AND OVERPARAMETERIIATION
The figure below illustrates our main result (Theorem 3 While high task similarity consistently reduces forgetting, this effect becomes more evident with sufficient overparameterization. Notice- ably, non-monotonic effects of task similarity (our DOTS), only occur when the model turns highly overparameterized. Importantly, we observe once more that even with extremely high overparam- eterization levels (5 = contingent task similarity, captured by our DOTS measure. For instance, Eq. (5) shows that when p 0.5, the worst-case forgetting becomes (0.5)* 0.0625 when 3 3=1-- +1.
+ 1), forgetting does not vanish entirely. Instead, this outcome is
Highly overparameterized regime
0.99
0.98
High task similarity
Dim. of Transformed Subspace (a)
10
10-
0.2
0.4
0.6
10
1.0
10a
Worst-case expected forgetting
0.8
0.8
@verparametenzaai (B)
10
0.6
0.6
100
0.4
0.4
10-3
0.2
0.2
10
0.0
0.0
Levelsets depicting main result from Theorem The entire space (combinations of a, 3) appears on the lowhr-right subplot. We zoom into more interesting regimes, i.e high task similarity and high overparameteriization, on the lower-left and upper-right subplots (respectively).
Figure 3:
5

---

Published as a conference paper at ICLR 2024
2.4 EMPIRICAL FORGETTING UNDER AN AVERAGE-CASE DATA MODEL
We aim to simulate the (linear) model from Section 2 and show that the average-case behavior matches the joint effect that task similarity and overparameterization have on the worst-case for- getting analyzed in Theorem 3 We choose the data model of Goldtarb & Hand (2023) for its clear analogies to learning with neural networks. Under this model, samples of effective di- mensionality d are sampled independently. The latent dimensionality p of the samples controls the overparameterizztion level. These parameters are precisely defined in Section 2.1 therein. We also utilize the same hyperparameters and noise levels as defined in their numerical simulations Sec- tion 2.3. We compute the statistical risk and training error (MSE) of W1, W2. and the null estimator on task as a function E [0, 1] for p E [500, 1000, 3000] averaged over 100 runs.
Risk on Task
Training Error on Task 1
10
10a
10
10
Error
10-1
10-1
10-2
10
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
DOTS (a)
DOTS (a)
W1. p=500
W2. p=500
Null estimator
W1. p=1000
W2. p=1000
W1. p=3000
W2. p=3000
Figure 4: Results of the numerical simulation. Risk and training eπror on task are plotted as function of a for various levels of p. The solid (blue) curves denote performance on task 1 of an estimator that is trained on task and then on task 2. The dashed dark lines denote performance on task of an estimator trained on task only. The dotted black line denotes the performance of the null estimator. Training error curves for wi are omitted as these values are 0 for >> d.
The results of the experiment shown in Figure 4 The dotted black line denotes performance of the null estimator (the parameter vector 0p) providing level for which any non-trivial estimator should beat. The dashed horizontal lines denote the risk of the single task estimator on task 1, providing hypothetical best-case bound for W2. The forgetting of the model is then defined by the difference between the performance of W, (grey curves) and the performance of w (blue curves). The grey curves are omitted for the training error plot as the single-task training error is 0 for > d. Thus, forgetting in training error is controlled solely by the performance of W2-
Comparing Figure 2 (for the worst-case forgetting) and Figure here (for the average-case data model) reveals that the interplay between task similarity and overparameterization in both cases agrees with our analytical result in Theorem 3 Here, for large (3000), we observe n-shaped curve for the forgetting W2, where the highest amount of forgetting occurs in the intermediate similarity regime. The model under small p (500) has the greatest forgetting when tasks are most = reduces to the model of Goldfarb Hand (2023),
dissimilar. Forgetting risk at the extreme whose main result explains why overparameterization is beneficial in this setting. Additionally. not surprising that higher levels of overparameterization benefit the single task risk setting of wi, as this reduces the model of Hastie et al. (0022) where the double descent behavior observed.

---

Published as a conference paper at ICLR 2024
3 NEURAL NETWORK EXPERIMENTS
In this section, we examine whether our analytical results apply to a continual learning benchmark using neural networks. The permuted MNIST (LeCun 1998) benchmark is popular continual learning problem that has been used to measure the performance of many state-of-the-arr continual learning algorithms (Kirkpatrick et al., 2017; Zenke al.) 2017, Li et al.) 2019). One performs number of uniformly chosen permutations on the 28 x 28 images of the MNIST dataset. This results in equally difficult tasks (for an MLP): each task is different pixel-shuffled version of MNIST. One then trains in sequence on these tasks and measures catastrophic forgetting. We consider a variant of the permuted MNIST benchmark, first suggested by Kirkpatrick et al. (2017), where instead of permuting the entire image, we only permute square grid of pixels in the center of the image. Define the width/length of the permuted square to be the "permutation size" (PS). When PS O, each task is identical and thus extremely similar. When PS = 28, each task is fully permuted and thus extremely different. Any value PS E (0, 28) can be deemed to have some level of intermediate similarity. Figure [ shows examples of high, intermediate, and low similarities in this setup. We are interested in the relationship between PS and catastrophic forgetting. Based on prior work (Ramasesh et al.] 2021 Evron et al. 2022), , it seems should expect the most forgetting to occur in the regime of intermediate similarity in a two-task scenario.
PS 14
task 1
task
task 3
task 4
7
PS 0
PS = 28
task 1
task
task
task 2
7
7
7
Figure 5: Three versions of permuted MNIST for PS = 0 (high similarity), PS = 14 (intermediate similarity), PS 28 (low similarity).
We use vanilla SGD to train a 2-yrrrr MLP of width 400 on sequences of up 4 tasks of MNIST and EMNIST (a more difficult 26-class version of MNIST for handwritten English letters; see (Cohen et al. (2077). After each task is trained, we report the test error on all seen tasks. We compare forgetting across varying permutation sizes. See Appendix complete implementational details. The results are shown in F The leftmost plots best illustrate the relationship between PS and forgetting. The remaining plots are intended to ensure that each new task is being sufficiently fit. We observe O-shape behavior where the most forgetting occurs around PS [16, 24], agreeing with our hypothesis that forgetting is most severe for intermediately similar tasks.
Now consider the experiment in Figure butt using a 2-Layer MLP with a lower overparameterization level. For each dataset, we find an overparameterization level that is significantly lower than before but still saturates to the training data and has comparable single-task test error as the highly overpa- rameterized version. For MNIST we choose width 20 and for EMNIST we choose width 40. The results of this experiment are shown in Figure 7 We can observe that the n-shape behavior is now less pronounced and it appears that the continual learning problem has relatively equal difficulty for intermediately similar tasks as for extremely dissimilar tasks. This general behavior agrees with previous results the relationship of overparameterization and forgetting in Section 2 both in the theoretical results and numerical simulations. See Appendix [ for evidence of the connection between the notion of similarity in permuted MNIST and the NTK feature regime.
7

---

Published as a conference paper at ICLR 2024
MNIST
Task Error
Task 2 Error
Task 3 Error
Task 4 Error
Model1
Model
0.0
10
Permutation size
Permutation size
Permutation size
Permutation size
EMNIST
Task Error
Task 2 Error
Task Error
Task Error
Test error
0.6
Model
Model
0.2
10 Permutation size
Permutation size
Permutation size
Permutation size
Figure 6: Results of the permutation experiment for varying levels of permutation size. The archi- tecture is a 2-layer MLP of width 400. Model I corresponds to the net that is trained on task 1, Model corresponds to the net that trained on task then task and on. Plotted curves have been averaged over 10 runs and error bars denote standard deviation of test error over the runs.
MNIST
Task Error
Task 2 Error
Task 3 Error
Task 4 Error
Model 3
Model 4
0.0
Permutation size
Permutation size
Permutation size
Permutation size
EMNIST
Task 1 Error
Task 2 Error
Task 3 Error
Task Error
Testt error
Model
0.6
Model
0.2
Permutation size
Permutation size
Permutation size
Permutation size
Figure 7: Replication of the experiment in Figure 6 using less overparameterizee 2-layer MLP models (width 20 for MNIST and width 40 for EMNIST).
4 DISCUSSION
While several related works study continual learning theoretically (Kim al. 2022 Heckel 2022
only some of them study the relationship between task similarity and catastrophic forgetting. |en- nani et al. (2020) prove generalization bounds which suggest that forgetting more severe when tasks are dissimilar. Lee al. (2021) analyze student-teacher setup, showing that intermediate tasks forget the most. Li et al. (2023) show regimes for which dissimilar tasks may be difficult and where performance tally, Ramasesh et al. (2021) provide evidence that intermediate task similarity is most difficult by studying learned feature representations during training number of modern neural networks.
intermediately similar tasks can benefit from regularization. Experimen-
8

---

Published as a conference paper at ICLR 2024
Geometric interpretation and Comparison to Evron et al. (2022). Previous studies utilize prin- cipal angles between the solution subspaces of the two data matrices (X1, X2) to quantify task similarity (Doan al.) 2021 Evron et al. 2022). Evron et al. (2022) show analytically that interme- diate task similarity (an angle of 45") is most difficult in two-task linear regression. Their analysis applies to any two arbitrary tasks, and thus seemingly contradicts the behavior observed, e-g., in our Figure [(b]] where maximal dissimilarity is most difficult. The key to settling this apparent disagreement the randomness of our transformations (Eq. (I). Their analysis focuses on any two deterministic tasks, while our second task is given by a random transformation of the first, as done in many popular continual learning benchmarks (e.g., permutation and rotation tasks).
To gain a geometric intuition, consider two tasks of rank d = 1 (x1. X2) Consider also a max- imal task dissimilarity (DOTS of a = m = 1). Then, X2 = Ox1 is a completely random ro- tation of X1 in p dimensions. It is known that T 1. X2 ~ v/ (Remark 3.2.5 in Ver- Near the interpolation threshold, e.g., when p = 2 (recall that d = 1), we get = (E((x, ~ 45", corresponding to the intermediate task dissimilarity in Evron et al. (202)), where forgetting is maximal. Conversely, given high overparameterization
shynin (018)). X
levels (p + oo), we get B| x:
+ 0 = [E((), x2) - 90", corresponding to the maximal task dissimilarity in Evron al. (2022). where forgetting is minimal.
X
Xx
~ vp
Comparison to Lin et al. (2023). Lin al. (2023) prove generalization bounds on forgetting which suggest that forgetting may not change monotonically with task similarity. However, their data model is not suitable for high overparamettriiation. For example, in the limit of high over- parameterization, their model is performing as well as a null predictor. In contrast, we focus on the training error, and do not assume specific data model for the first task, which allows us to generalize even in the highly overparameterizer regime.
A starting point for analysis. Our work focuses on linear models and data permutation tasks. Exploring linear models using (stochastic) gradient descent is the most natural starting point for theoretical analysis, as an initial step towards understanding more complex systems. Moreover, recent work shows connections between extremely overparameterized neural networks and linear models via the neural tangent kernel (NTK) (Jacot et al. (2018); but also see see Wenger et al. (2023). We choose to study data permutation tasks for their well-defined mathematical relationship and generation of equally difficult tasks (for a fully connected model). However there is criticism that permutation tasks are relatively easy to solve in practice and only provide a best-case for real-world problems (Farquhar& & Gal 2018 Pfülb & Gepperth 2019.. Despite these critiques, we believe that the data permutation setting is the most amenable for initial theoretical results.
4.1 LIMITATIONS AND FUTURE WORK
Our analysis in Section has centered around a continual linear regression model. An immediate next step is to explore the extension of our analysis and empirical findings to more intricate non- linear models (e.g., MLPs, CNNs, and transformers) or to other notions of task similarity. Another avenue of investigation involves extending the analysis to continual classification models, possibly using the weak regularization approach suggested by Evron et al. (2023).
Our analysis has also primarily examined settings with T 2 tasks. Extending these analytical results to T' 2 3 tasks poses an immediate challenge. The complexity of our analysis, which already required intricate techniques and proofs, suggests that tackling the extension may be considerably difficult. Moreover, the convergence analysis presented in a previous paper (Evron et al.. 2022) for learning T 2 3 tasks cyclically has proven to be notably more challenging than that for T tasks (and was further improved in follow-up paper (Kong et al. 2023)).
Finally, since our models are linear, our proxy for overparameterization, i.e., 13 = p. directly con- trols the overlap between the task subspaces (see also the geometric interpretation above). Clearly, this proxy is different than the width of deep networks. On the other hand, there are still relations between these two proxies through the theory of the NTK regime (Jacot et al.) 2018). A further examination of these relations, both theoretically and empirically (perhaps in the spirit of our Ap- pendix B and Wenger et al. (003)). ), could benefit the continual learning literature.
For simplicity, we discuss the principal angles between x1, X2 instead of between their nullspaces (Le., the solution spaces). In two-task scenarios, these are essentially equivalent (see Claim 19 in Evron et al. (002

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We would like thank the anonymous reviewers for their insightful feedback. DG is partially supported by NSF DMS-
PH acknowledges support from NSF DMS-2053448, DMS-2022205, and DMS- DOMS-184083 1848087. The research of NW was partially supported by the Israel Science Foundation (ISF), grant no. 1782/22. The research of DS was Funded by the European Union (ERC, A-B-C-Deep, 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair AI.
REFERENCES
Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama. Generalisation guarantees for con- tinual learning with orthogonal gradient descent. arXiv preprini arXiv:2006. 2020.
Tómas A Brody, Jorge Flores, J Bruce French, PA Mello, A Pandey, and Samuel SM Wong. Random-matrix physics: spectrum and strength fluctuations. Reviews of Modern Physics, 53 (3):385, 1981.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 20/7 international joint conference on neural networks (IJCNN, pp- 2921-2926. IEEE, 2017.
Matthias De Lange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE transactions on pattern analysis and machine intelligence, 44(7):3366-3385, 2021.
Thang Doan, Mchdi Abbana Bennani, Bogdan Mazoure, Guillaume Rabusseau, and Pierre Alquier. A theoretical analysis of catastrophic forgetting through the ntk overlap matrix. In International Conference on Artificial Intelligence and Statistics, pp. 1072-1080. PMLR, 2021.
Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, and Daniel Soudry. How catastrophic can catastrophic forgetting be linear regression? In Conference on Learning Theory, pp. 4028- 4079. PMLR, 2022.
Itay Evron, Edward Moroshko, Gon Buzaglo, Maroun Khriesh, Badea Marjieh, Nathan Srebro, and Daniel Soudry. Continual learning in linear classification on separable data. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 1440-9486 PMLR, 23-29 Jul 2023.
Sebastian Farquhar and Yarin Gal. Towards Robust Evaluations of Continual Learning. Lifelong Learning: A Reinforcement Learning Approach Workshop ICML, May 2018.
Daniel Goldfarb and Paul Hand. Analysis of catastrophic forgetting for random orthogonal trans- formation tasks in the overparameterized regime. International Conference on Artificial Intel- ligence and Statistics, pp. 2975-2993 PMLR, 2023.
Ian Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empiri- cal investigation of catastrophic forgetting in gradient-based neural networks. arXiv preprint 1rXiv:1312.6211, 2013.
Thomas Gorin. Integrals of monomials over the orthogonal group. Journal of Mathematical Physics, 4346):3342-3351,
2002. 2002.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pp. 1832- 1841. PMLR, 2018.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of statisties, 50(2):949, 2022.
10

---

Published as a conference paper at ICLR 2024
Reinhard Heckel. Provable continual learning via sketched jacobian approximations. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 10448-10470 PML.R 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Norman Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan. Continuous univariate distri- butions, volume 2, volume 289. John wiley & sons, 1995.
Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, Zixuan Ke, and Bing Liu. theoretical study on solving continual learning. Advances in Neural Information Processing Systems, 35:5065-5079, 2022.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska Barwinska, al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13)33521-3526 2017.
Mark Kong, William Swartworth, Halyun Jeong, Deanna Needell, and Rachel Ward. Nearly optimal bounds for cyclic forgetting. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmistf/, 1998.
Sebastian Lee, Sebastian Goldt, and Andrew Saxe. Continual learning in the teacher-student setup: Impact of task similarity. In International Conference on Machine Learning, pp. 6109-6119, PMLR, 2021.
Haoran Li, Jingfeng Wu, and Vladimir Braverman. Fixed design analysis of regularization-basee continual learning. arXiv preprint arXiv:2303. 10263, 2023.
Xilai Li, Yingbo Zhou, Tianfu Wu, Richard Socher, and Caiming Xiong. Learn to grow: continual structure learning framework for overcoming catastrophic forgetting. In International Conference on Machine Learning, pp. 3925-3934. PMLR, 2019.
Sen Lin, Peizhong Ju, Yingbin Liang, and Ness 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, pp. 11078-21100, PMLR, 23-29 Jul 2023.
Seyed Iman Mirzadeh, Arslan Chaudhry, Dong Yin, Huiyi Hu, Razvan Pascanu, Dilan Gorur, and Mehrdad Farajtabar. Wide neural networks forget less catastrophically. In International Confer- ence on Machine Learning, pp. 15699-15717. PMLR, 2022.
Deanna Needell and Joel A Tropp. Paved with good intentions: analysis of randomized block kaczmarz method. Linear Algebra and its Applications, 441:199-221, 2014.
Benedikt Pfülb and Alexander Gepperth. A comprehensive, application-oriented study of catas- trophic forgetting in dnns. arXiv preprint
(at:::995500000 2019.
Vinay Venkatesh Ramasesh, Ethan Dyer, and Maithra Raghu. Anatomy of catastrophic forgetting: Hidden representations and task semantics. In International Conference on Learning Represen- tations, 2021.
Nazakat Ullah. Invariance hypothesis and higher correlations of hamiltonian matrix elements. Nu- clear Physics, 58:65-71, 1964.
Roman Vershynin. dighediimesiooal probability: An introduction with applications in data science, volume 47, Cambridge University Press, 2018.
Jonathan Wenger, Felix Dangel, and Agustinus Kristiadi. On the disconnect between theory and practice of overparametrized neural networks. arXiv preprint arXiv:23100.00..7, 2023.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In International conference machine learning, pp. 3987-3995. PMLR, 2017.

---

Published as a conference paper at ICLR 2024
Table 1: Hyperparameters for the neural network experiments
Hyperparameter Value
learning rate
0.01
batch size
64
epochs task
100
momentum
0
dropout
A NEURAL NETWORK IMPLEMENTATION DETAILS FOR SECTION 3
Table reports the hyperparameters used in the neural network experiments. All architectures used ReLU activation functions for the hidden layers and softmax for the output layers. Weights were initialized as Uni 7 Vi) where is the input dimension of the given layer. The experiment in Figure 6 used intermediate width 400 and the experiment in Figure S used intermediate width 20 for MNIST and 40 for EMNIST.
B NTK FEATURE SIMILARITY EXPERIMENTS
[a. Let a, b E RP be two sets of NTK features and define correlation as |
Then the average cor-
[(). relation between datasets A, B E ROxp is Ei= ||. /n. Figure 8 plots the average correlation between original MNIST and permuted MNIST as a function of permutation size. We that the average correlation monotonic in permutation size extremely high for low permutation size and extremely low for high permutation size. This provides evidence of the connection between the centered permuted MNIST problem and task similarity in the NTK regime.
Average correlation
15
20
25
Permutation size
Figure Results of the permuted MNIST NTK feature similarity experiment.
12

---

Published as a conference paper at ICLR 2024
C SUPPLEMENTARY MATERIALS FOR OUR ANALYTIC RESULTS (SECTION 2)
Throughout the appendix, we denote the singular-value decomposition of a given X E R"xp by X UEVV for Σ E R=xp, The number of nonzero entries on the diagonal of Σ is d rank (X).
Recall Theorem 3
RxXp n 2 rank(X) = d Let 2 4, E pL.....p..m m 2 Define Xp.d _ {X
Define the Dimensionality of Transformed Subspace or A m. as our proxy for task dissimilarity
and B A - as our proxy for overparameterization. Then, for any solution w E RP (Assump-
tion D. the (normalized) worst-case expected forgetting per Def. (obtained by Scheme ! is
Eo Eo X. w')
a 2 + (03(0 (a + 1la - -6a² - 8) + B2 (-5a² + +222² 30a + 12) +
max X
X X
8 (5a - 18a + 20a - 6) + p
where X "Xw" projects w* onto the column space of X. Notice that || Xw* is neces-
sary scaling factor, since the forgetting [|W2-- y| Xw: Xw2-Xw*ll naturally scales with |
and |X Xw 112. The exact expression (without the O notation) appears in Eq. (8) in Appendix C
Proof outline. bounded as,
We start our proof (below) by showing that the expected forgetting is sharply upper
d Σ Eo (c 1' ΣV /V
BoF(O:X. w
|
Eo
+ (d
Eo (c o (I- 0I-
Σ (V (VTw)) w
=|
where e1, B2 the first standard unit vectors in RP, This directly implies that,
Eo F(O w+) Eo (c (00000)
- Bo (c000'='(1-0)c))
| X
solved in Lemma K
salved in Lemmal S
Each of these two expectations is essentially polynomial of the entries of our random orthogonal
Qm
Q, E RPxP, Qm E mm which form the random operator O Qp
O as
Ip-m
explained in Eq. (I).
We compute these two expectations (in Lemmas 6 and g by employing exact formulas for the integrals of monomials over the orthogonal groups in p and dimensions (Gorin 2002). Our
derivations often get complicated, and so we split them into three appendices:
1. Appendix C
(below): Derivations of more complicated expressions involving the operator O.
2. Appendix D Derivations and properties of monomials of general random orthogonal matrices, mostly using results from Gorin (2002).
3. Appendix B
Derivations of auxiliary expressions (mostly involving Qm: Qp) that are used as building blocks in multiple derivations.
13

---

Published as a conference paper at ICLR 2024
Proof for Theorem
3
Starting from Eq. (4) show that for any given X, w it holds that
X Eo
w*)
X Eo xx xo
X XO
x X
where, importantly, the inequality saturates when all the nonzero singular values of X are identical. Plugging in the SVD, ie., of UEVT we get
1 Bo BO w V' (I (I- X
w*l
=oo (I 0) VΣ EV
where the last equality stems from spectral norm properties (recall that V is an orthogonal matrix).
Following our definition of O Op Qm
O (Eq. (1) and since Qp is sampled uniformly
I--m
from the orthogonal group Op)), we notice that O and V VV are identically distributed. Hence, we can rewrite the above expectation as
x (:Eoo((OXX.w)) E
E0 Σ E (1-
w
E
e -1
Pythagorean theorem]
Σ E
2 |e:11
Remark 4 (Ease of notation). For simplicity, in the equation above and from now on, omit the explicit subscript notation whenever it is clear from the context of our derivations what the expectation pertains For instance, instead of writing Eo (F(O:X,w*)) w.)] we can simply write E X.F(OXX,w*).
As another example, we often analyze (for i + j) expressions of the following spirit,
Qm
2
Eo (eT)e,)²= _B, ~((m))
e,j
@T
Q2 e,
I-
Q
E - ( (plulv Qm)m((m)
u1
I m
where the last step follows from the angle-preserving property of orthogonal operators (Qp). For the sake of simplicity, we take the liberty to also write the expectations above as,
E (e (e; -E Qpp
Qm
QUT 05
= -ELLy (uT
(1T(0))
Q
Ip-m
I Ip-m
Finally, when the dimensions clear from the context, interchangeably write matrices in the
Om
Qm
Qm
two following forms:
and
Ip-m
Ip-m
0
14

---

Published as a conference paper at ICLR 2024
Back to the proof.
Focusing just one term from the above Eq. 7 we have,
E ( O O1)
=E ((''''=E(10) - Σ g.o
2
e ()00)))=(-
E
d
k=1
Σ
00
jØk=1
=0, by Lomma
Σ oB e (
E
ee
0 ((-))))
0),,
jE|DR(}
2f O + (e00 2
Σ of
jE|D
We are free to use c1, 02 instead of e; ey (for i.j [d] due the exchangeability different rows of Qp. For instance, notice that
E O
=E ee.00
Qp
Q I--m
Q exee Qo (I- Qm
I,-m 1) 0 ej
That is, the expression is function of Q 2p and are entirely exchangeable (see Prop.
p
e.....,
Q2 ea which are first d rows the random
15

---

Published as a conference paper at ICLR 2024
Going back to Eq.
X =o S
Σ oj
jENN/()
(e 0 -)) -0
Σ
jE(d)(
- E Σ
0
ME
= =E(e00'>>\(-000- Σ 2 -1
of
0 Σ
(d-1) 1) Σ on
= 11060033110000000-00000000300300
1) 1
Σ
Interestingly, this worst-case scenario, the direction of w that lies the column span of X, i.e.
X"Xw" EVEVVI w does not play role, but only its scale VV ΣV
|Vv
|| Dim us FO; w*)
(since is only nonzero in its first d entries). Normalizing by this scale, get,
=0(e)0'=-2(-0)aa= (d-
X X 1w+1|
solved in Lommalg
solved in Lemma
where we remind the reader that the inequality saturates when all the nonzero singular values of X identical.
16

---

Published as a conference paper at ICLR 2024
By plugging in the two lemmata and after some tedious algebraic steps, get the final bound of,
Fo
max x.
|
m²'p((2ppp) 2m 21
m(p² 228p +17p" 324p
(p-3) |1
d. m' (1pp-pp-3 Tp- |1 -022-- -302p-240)
(p 0=-310~280011gggg-------------11
m 1100-3p' 3p" 118p'' hgg.hh/.....................a..0
(8)
(r- 6-231|p2||0010000------000000010
2d.. m ||tp://|hhh..nng..g11.1001011110
2m
+
129p -100--08---110g---0------0---1-0
2d.
(p 10--011220001111------1-0111111-
83 m' m 1-Bp-ppp-6-- 6)+m
(p-3) 2)p 11-31pp~211--1110---11111111111- (|0
d. m (6p +90p" +96p" + 600 + 32p" -22
(p-3)6 3)(p 2) (p+ 1p 2)
The above the exact expression for the worst-case forgetting. To reach the O notation, we assume that p >> 1, and so we are left with the most significant elements of each product. That is, we show that,
m² (>>p((p)) (x²) 2m 2m2mmmmpppp p(="'((=mm)))) +m (1pp")) +m (+m()")+2p(2) +2p(p") +d p(-=>(">)+++)) + (m (-11p") )2(2)0) -
2d m p(5p) 2m (sp") +m² (15p') ml (-3pp +p(pp))p((p))))
d3 m² (bp)) 18pp" +m 2000) +m (60 (200"
m 2m p+m +mpp 22p²
+ dl 6m 16m 11m pp² +2222mm +2mp 24p²
2d 5m 16m p 15m=pp 3mp' pp" + d -5m* 18m 20m pp +6mp +2p²
p²
m 2m pttm pp mpp 22p d - 6m 116mmp p-1mppp-lmms 11m=pp p 24p
D
prt
d
16m 5m
15m2 pp 3mpp (g)
3
+18m 220m 2 +6mpp +2p
pt
p+
+m++)) (m
6m 4 16m p nd
11m2 2 +2mpp
2
d
5m
16m p+
(3m++ 1n
d
5m 18mm
8 p- 20m2 p22 +6mm+
p
2
m
+
m P
2
+
m
1
2
+
6
m p
+16
m
-
11
(m))
+2
=2(m) mm) (=))+
P
p
p
3
2
d
5
16
+
15
1
+
1
d
5
m
18
m
20
m
6
m
+ 2
P
2 a² + (1 3) (-6a* 16a
11a2 + 2a) +
211 8)² (5a* 1 16a² + 15a² 30) + (1 -3)3 (-5a² + 18a -00a² + 6a) 0
= =a 2 3 (5a3 18a² + 20a 6) + 82 (-5a² 3 + 22a² 300 12) +
3 (a² 2a² + 1la - 8)) + +0 (1)
17

---

Published as a conference paper at ICLR 2024
Lemma 5. Let [d] and let j, [d] such that k. It holds that
E (c. O (1- [ =.
Proof. The expectation can be decomposed as,
E ( E' -1
- = =
(e 0 [0e)]]
-
+
(e
=E((c]O0o,) (c ex)] - [Ec 0,) (o E+
-E[(c, E E E0e, (c)) [ O E E0e,) (c. E E0c²)]
where the last step holds because j, E [d] and therefore E Σej = ooj E Σeg = ek.
Following the definition of O (Eq. (I), the first expectation becomes
E (e, OTe;) OeT ex)] I Qm e, e,
Qp
Qm
O e Qp
Qm
O2
In m
Since j * k. we must have either & {i or l & {i.j} (or both). Denote the relevant rows of Qp by q: - Q c; q & Q Cj. qk Q27 e₁ and notice that they are independent of Qm (or A). Without loss of generality, j & ki. The above expectation becomes Q [q] Aq: qu Aq:], where q appears only once (an odd number). By Cor. 11 the expectation vanishes.
Quite similarly, the second expectation becomes
E ee,, (e. Σ E0Eee))]
B O Σ
e, e, e Oe:]
[=1
Σ
E [q Aq: q. Aq. qf Aqu]
Notice that both i, appear even number of times in (each of) the above expectation(s). Since * k. at least one out of j, k appears an odd number of times (either one, three, or five) each of the above expectations. Again, by Cor. II this expectation vanishes. Clearly, the same holds for the third expectation.
The fourth expectation is,
d = Σ Oe e, ee,) OT ee,, eee))
f,t=1
g Aq. oo Aq; A. q. Aqu Σ
Notice that i, E, appear an even number of times in (each of) the above expectation(s). Since # k. least one out j. appears an odd number of times (either one, three, five, or seven) in each of the above expectations. Again, by Cor. II this expectation vanishes.
18

---

Published as a conference paper at ICLR 2024
C.I. DERIVING E (1
Lemma 6. Let p 2 4,m (2....;D). described in Eq. 4 Then, vi E [d], it holds that
p. d E (p], and let O be random transformation sampled as
B 0 e),;)
m m=( 2m +m 4p 20p² 24) 2|
10p
(p 1)p- 10
d(pt 2m 6m pp 2m 2m 1) 5)-1ppp-111mm111
10-1pp/o++1]0+t221111111----- 3p+ ((p
d' - m² +m halp
Proof. We decompose the expectation as,
E (ee(000'0(--)ee)
O = [E 2E ((e Oe:) (ee: +
E0e)
and derive each of its three terms separately in the following subsections. By adding these three terms and by simple algebra, get the required result,
m² 2mpppppp- m +2p+2 (d-m) -m m² 2mppmmmm+mmmmmmmm (p- (ppppp)()++)))))
3mp+p" +5pp +8p-8)
p(++2)
3(m 10 22mp0-mmmmmmmmmm22mmm-m---------
((p+2)p++)(p+t)
T0p 34p -10p))
(p- (p-1
(d (1-1)(((122130011110===-
(p- (p-l))((tt)((tt))()p))
-m -
2m |r -22-0))) "(p" mm(p" m
2m
1p +20p (
11pp2
(p- (1=111(0++106+++00000000
d 4tt
Remark 7 (Explaining proof techniques). In this subsection, explain the proof steps more thor- oughly than in other places, since most of the techniques repeat themselves throughout the appen- dices.
19

---

Published as a conference paper at ICLR 2024
C.I.1 TERM 1: E (e, Oe:)²
Recalling Remark on our simplified notations, we show that,
E (e. Oei) 2 = E e._ Qpp
I pmm m
Op e;
Bu
T
Qm
I p-m
u
E
auu uuu
m
Ip
I p-m
Opening the product above, by Cor.
12 we are only left with the following terms:
0
Q
Qm
E
uu
u
+
u
uu
Ip-m
= E (u) Ubb
27
+
J Q.. Ua u Qm Ua
where, like we frequently do throughout the appendix, we decomposed into u
R
with ua E Rm and ug E Ro-m. This decomposition is often useful, since for two thogonal unit vectors u, v, it holds that = u Va + +u Vo = i v. = un Vb and
1= || ||, + || = || 1| 1 |ull
-
Another "trick" that we use often, is reparameterize Qm Ua (for Qm O(m)) as | for 5m-1, Then, the expectation above becomes,
=
E [mb
+
EE
Uu
11
Im
=
E
|
+
E ||ua||"
= Σ
[u?
U. 3
m
i=m-1
1 j=++1
1=1 j=1
= (p m) E
+ (p - m)) (p
m
[u] 16 + (mE [u]] + m (m 1E [ufu²]
(p m) E [
+ (p (p
1) (p-
E
[w]]] + (m 1) [u
where in the last step we used the fact that different entries of are identically distributed (see also Prop. 9.. Using simple algebraic steps and employing the notations presented in Appendix D for monomials of entries of random orthogonal matrices, we have
(p- m + 1) EE [u]]] + (m² 2mm + 2m + p²
1) E ur
= (p m + 1) ( $/ ) + (m² 2mp + 2m + p² -
2
Finally, we plug in the expectations (computed in Appendix and get
3 3p-m++1
p + m² 2mp 2m + p² p m² 2mp (p + 2)
p² + 2p +
p
20

---

Published as a conference paper at ICLR 2024
C.1.2
TERM 2: E [ee] (e. 0 T E+Eee]]]
It holds that,
E
[(c]
Oc,)
(c. O' E0ce)] E [(c] 0e1) 100E=1 E0ee)))
d
ej e
extr Oel Σ
E ej e o e Oei
E (o) Oei 2 ee Oe = E [e] 0e,) )d
+ (d 1) (o) Oel) )2 ej Oei
R=1
sulved Prop
solved Prop
(p- m) (m² - 2mp - 3m 1² + 6p 14)
(d 1) (p m)) mm= + 2mmp + 3m 6) (p - pp 2) (p + 44)
p(p + 2) (p + 4)
(p m) ((p 1) (m² -2mp- 3m + p2 + 6p + 14) + (d 1) ( (-m² + 2mp + 3m 6))
(p (p- 1- + 2) 4p)
(p (0-m)(e (d(-m² + 2mp + 3m 6) + m 2mp² 3mp + p² + +5p² + 8p 8)
())
C.1.3 TERM 3: E Oe 2
holds that,
E(c, 0 E E00.) E 000s 3= E
c T Oc
=E Σ
c Oct)
c
d
(ef Oei)* (e] 0ei) = Σ Oee)
E (e Oe )² (e. Oe:)
+
k
k=t
(e Oel)
+ (d 1) e Oe
Prop 1n
2 solved Prop.
1d (e Oe,) (e 0e.))
+ (d ((d
1) (d Oei) (e) Oe
V solved in Prop 18
k, A-gh solved in Prop.
19
We note in passing that since d p. then when p + d 2 the rightmost term is necessarily
zero. Therefore, we can use Prop. 19 freely vp 2 2, even though it requires that 2 3.
(e, O " E0ee)= 3(m (44+4))mm (m (p m) (p-mm----- m 2 2mp--mmmmmmm-:::mmmmm 4m+pp
10p+-3)
3(d- 3(d-1)(m 2m (2p+3)
22-3))
(p- (0-1
2 (d 1)
p(p+2)(p+))p+t)
(p- (0-1)ppg++1)0++/2004+440000+
(p- ( |:
(d-1)(m) (p
(d- -m 44
( (=
21

---

Published as a conference paper at ICLR 2024
C.2 DERIVING E (e, -1
Lemma 8. Let p 2 4.m E (d E [p], and let O be random transformation sampled as described in Eq. 1 Then, Vi,j E [d] such that i f j. it holds that
O (-4p² 6p 12p 8 10p 20p +m 44p 100pp 134p2-120p 120p 144)
(p 3/P 20-00002200000000---0012211-1--1
m +84p* 1ag
168p 168p-288)
d. 3m (-4+4p+33p 4m (p+2) 0==30002010-10000++101+0121111-1
d. --tp::----10.-------------1---1-
(p (1-3)---
d² 1ggg
(p 0-230~1-|1p-1pp11111----+11111)
d= 1p (p (--100-2100-110---1000-00----1--
Proof. We decompose the expectation as,
E (c. [(=00'''(--))c)
= (e Oe,) 21 [(e] Oe,) (e. >0e,) + Oe, xx0e)))00))
and derive each of its three terms separately in the following subsections. The final result in the lemma is obtained by summing these three terms.
C.2.1
TERM 1: E (e. 0e,)²
holds that,
E (e, Oe,,,e, 2 =E T ([ Qm
+ Om 1) v== =E (u, Qm + uz vo)²
= E (n Qm Val
+ 2E (u. Qm Va Ub vo)
+ E (u, vo)²
solved Eq. 22
by
solved in Eq. 23
mp + m 2
m (p m
mp m 2 + m (p m
(p (p-1) 1)p 2)
(p 1) +
(p 1) (p 2)
2mp + m - m 2
(p (p-1)p(p+2)
22

---

Published as a conference paper at ICLR 2024
C.2.2
TERM 2: (e)
Oe,) Oc E0e,)
It holds that,
2E [e)]os) (e]0T==E0e;) 22
2 Oel e 0
e 0e2
C₂ Oct0 o0 c.ek
0c0]
E C2
OcteN
Octor Oc2
k= l
km
E Eie O 0 0e2]
+E (e) Oe,) e
ee Oe2 + (d - 2) 2) Beeeeeeee Dele Oeler 0e2
solved in Prop. 20
sulved Prop
solved Prop. 21
= 2p - -m)
-m= (x- 2p=1
2m (p- (--1)p(++)((++4+)
(d-2) (2m² -mmp 2m 2m-p+88 (p (--2(lp ()p((++)((
22m² + 2m + (3m- + 1)
(d 2) (2m² 3mp 2m p 8) (p - 2) (p - 1) p (p + 2) (p + 4)
2 - mm)
1 ()-1))(p+2)) (p + 4)
(p m) (d (2m² 3mp - 2m - p 8) + + 2m2 + 3mp + 2m + 8))
(p-2) 1) p (p 2) (p + 4)
23

---

Published as a conference paper at ICLR 2024
C.2.3 TERM 3: E (e. holds that,
d
2
E (e. O E =0e,)² 2= E [ej -TT E E0e))* =
T 0
e Oeg
E [e 0 e 2 O0z) (e) o eree Spee/0og O02)
Σ
E (e Oe 6p Oez) (o, Oe e 0e2)
k,t=1
k,t=1
Σ E (eg Oel
e T 0e₂)
E (e Oel
o Oez) (eg Oel o, 0e2)
k
k=t
We now show that,
E (ox Oel 0% Oez)²
2 (e] Oe: o Oez)
2² (d (d-21 2 (eg Oel eg Oez)
k= solved in Prup 1
123, solved in Prop.
19
2(1m+4) (2mp))))2m++-4o 4p 2at 6)+10))
(p-0)p(p--21(
(d (1-2)((mpp))) Dao (mmm -)2p()))))
(p- (p- 22hh--_--aia1a1111-------------- (
(p-
-2(m---11)(m
Am 2 +m
(p 1)m 2
Moreover, we have that,
E (c% Oe, of Oez) (e, Oel e 0e2)
k=t==1
= 2 (e) o Oez) (ez o 0e
+ 4 (d - 2) (e] Oeje Tee) (eg Oel Oe +
1=1,6= km 2,6 2, solved
132/201133//22 solved Prop DAl
(d 2) (d 3) E Deje 002) (e) e O02)
2 solved Prop. 25
By summing all of the above and by some tedious algebraic steps, we finally get that,
E Ee, (e.TotT )0e,)²
(| -Bp""-pp")
(p- 00-31p1-2110--0000-1p1--01111111
+8p 2wpp"=""*p'21'00==200"""""" ogg.::0--..-.aapag.......-----10
(p- - ----0------
3m || d
(p- (=23001-2000011110--111110011101
- 2m 11--
82 mm(-5p-6)++m 20
(1-3)(P (1
d² +10pp 2 +96p +154p+60) -20
3) 2)(p 1)p(7+ 10p=))/)+)))
24

---

Published as a conference paper at ICLR 2024
C.3 EXTENDING FIGURE 2 d= 1, 10 0.9)
MORE RANDOM SYNTHETIC DATA EXPERIMENTS
d= 10 10 (8 = 0)
Forgetting
100
10-1
Analytical bound
10"2
Empirical mean
0.0
0.2
0.4
0.6
0.8
100.0
0.2
044 066 0.8 1.0
Dim. of Transformed Subspace (a)
(a) Experiments for 10.
d 1, p 100 0.99)
d 10, p 100 BB 0.9)
d 100, p 100 0.0)
100
Forgetting
10-1
10
Analyt cal bound Empirical mean
10-3
0.4
Dim. Transformed Subspace (a)
(b) Experiments for p = 100.
1.
1000
0.9
10, 0 1000 88 0.99)
100. 1000 (B 0.9)
10-1
Forgetting
10-2
10"3
10
Analytical bound
10-5
Empirical mean
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
C.8
0.0
0.2
0.4
0.6
1.0
Dim. of Transfommed Subspace (a)
(c) Experiments for 1000.
Empirically illustrating the worst-case forgetting under different overparameterizztion levels. Points indicate the forgetting under many sampled random transformations applied on a (sin- gle) random data matrix X. Their mean is shown in the thin orange line, with the standard deviation represented by gray band. The thick blue line depicts the analytical expression of Theorem 3 The analytical bound matches the empirical mean, thus exemplifying the tightness of our analysis.
Figure 9:
25

---

Published as a conference paper at ICLR 2024
D MONOMIALS OF ENTRIES OF RANDOM ORTHOGONAL MATRICES
Throughout the supplementary materials, we often wish to compute the expectation an arbi- trary monomial of the entries of random orthogonal matrix Q ((p) sampled uniformly from the orthogonal group, e.g., Eql9i, 22.2) Following Gorin (2002), we define a "power matrix"
M E Z (for some R S p) that maps into monomial I 4i constructed from the entries of the first R columns of the random Q E Rexp. We denote the expected value of this monomial by
EQ
& (M). for example,
Eqlqi,
We employ the notation 0 to complement M have p rows. For instance, in the example above, 0' a vector with p-2 zero entries.
The following are helpful properties of the integral (expectation) over the orthogonal group. as mentioned in Gorin (2002).
Property 9 (Invariance of the integral over the orthogonal group). Let Q O(p) and M Z R
1. Invariance w.r.t. transpose. Since Q and Q are identically distributed, holds that (M) (M)) For example,
o1 clave
12 22 23, 13.2)
Eolii 29. < /
2. Invariance w.r.f. row and column permutations. Since different rows/colunns of Q are identi- cally distributed, the integral over the orthogonal group O(p) is invariant under permutations of columns rows of the power matrix M (see also Ullah 1964)) ). For example,
0
6
12, EQohi 1
0
The following is known property of odd moments in integrals (expectations) over the orthogonal group (see Brody et al. (198I); Gorin (2002)).
Property 10. If the sum over any row or columi of the power matrix M is odd, the integral vanishes,
0
i.., (M) = O. For example,
1 0 0.
(In contrast, generally, holds that 1 0/ + 0).
Corollary 11. Let qi be the 8th column (or row) of Q Let A
(N) R2xP be N matrices
independent on Q and let 11....,221 i2N E (p) be 2N indices. Then, if there exists an index E [p) that appears an odd number of times in i1, i2N the following expectation vanishes:
E[q; (61) qiwt1 A.,A (12) qix+2
qiy (6x)
giaxl 0.
For example, the above dictates that,
Qq...Q.. Qm.
c
Qp
Qm I Ty-m 0 eT Op
Om
Q 0 02
03 Qp
Qm
Q 02 0,
Ip-m
since qı appears 3 times (also because q3 appears once).
Proof. The expectation be rewritten as,
Elq, A (1) Giv.: ... Lix A (6x) [
Σ Σ
E I
(00 aeeve jake Thesxee
(e)
jt....N=1 kw=
kN=1
Let t E [p] be an index that appears an odd number of times in i....., S2N. The th column (or row) appears the same number of times in each of the (summand) expectations. Thus, the of the tt column (or row) corresponding to q, in the power matrix M corresponding to that expectation will be an odd number. Thus, by Prop. 10 the expectation vanishes.
26

---

Published as a conference paper at ICLR 2024
Corollary 12. Let Vi....... V2N E R' and c R be random variables independent of Qm O(m).
Then, if is an odd number, the following expectation vanishes:
Elc V1
0p-m VN+1
V22
Qu. 0p-m
VN+2 ..
0y-m
V2Nl = O.
For example, the above dictates that the following expectation vanishes,
EQ,..... Qm 1 Qp
Qm
.ej erQrp
Qm
Og e1
.e 0
Qm
Q2 e2 00
Op-m
Op-m
Pp-m
since here N 3.
In contrast, the above does not imply that the following expectation vanishes.
Qm
Eq, Qm
ei Op
Op-m
O el
e1 Qp
Om
1p-m
Qu Q
Qm
0p-m
Q e2
here, this considered
since here N-
Proof. The expectations become,
E
C
Vi
Qm
0,
VN+e
=
E
c
i.j=l
(ve);
(Qm)s,(VN+e))
N
lis (ve))(
c
ii==
E II These (ve)e((
E
h=..N==1
We notice that each of the (summand) expectations the entries of Qm appear exactly N times. However, since N is odd, at least one row or column of the power matrix corresponding to the monomial in the expectation must have an odd sum. Then, by Prop. IO all these expectations vanish.
27

---

Published as a conference paper at ICLR 2024
The main result need from Gorin 2002) is their Eq. (23), providing recursive formula to compute (M) for any power matrix M. We bring this formula here for the sake of completeness.
Lemma (Recursive formula for computing expectations of monomials over the orthogo-
nal group). Define the Pochhammer symbol (2)n
T(*+n) T(2)
Denote
Il
Denote (7l K) I (ne Ki......: K).n-1).
Then, the one-vector integral is given by (m) ( m/2 IP (2)
Moreover, the R-vector integral (corresponding to a matrix M 20 1t
given
-1
(M)
1+1
m R
(-1)
R22
(1 k, EmmR-RI RK) (1),2 (M(R-1+K))
where the first sum runs over all 7 with all even entries (less or equal to the corresponding entries of the last column Ti n.) The second sum runs over all K E 2020 ZP.R-1 for which all sums of columns
even, i.e., kj - Ed= kijj is even Vj [R - 11. Finally, ( stands for the first R
columns of M, and m = ELe ii Mi.n and R = > im1 Kg.
In the pages to come, we present many calculations of expectations different monomials that throughout the supplementary materials. We include these calculations since the recursive formula of Lemma 13 is somewhat complicated to apply. and we wish our derivations to be repro- ducible and easily followed.
D.1 MONOMIALS ONE ORTHOGONAL. VECTOR
Biui| ( (g) -1 (2) (8
(2 p+2
3
p(++2)
Elul = ($) (9) -1 (4) p(p+2)(++4)
E[ufuj]
(2) -1 (4), (4) ( (2t2)
p(p+2)
Eluiušl
5 (2), (2) p(p+2)(x+4)
Elu
= (2), (1) plpt21(p4))
28

---

Published as a conference paper at ICLR 2024
D.2 MONOMIALS OF Two ORTHOGONAL VECTOR
D.2.1
ONE INDEX (ROW)
< () ( (-1) (1) ( (
(())
(p-1)
(()) (4))
- ( (t)s + (2) -1 (b))
[x-1)
105
30
(0-1)(p+1)
((0+2)
p(p+2)(++1) p(x+2)
3
3(p-1)(p+1)
(p-1)(p+1]
(x+ -lp-2)(pt4)p+t)
< ( p(++2)
4 = (e5²) (--)) (2), (-1))
(-1)*
fp-ī -
- (()) (1) (g) 3 (1))
(NED 3
15
3(p
(p-1)
p(
p(+t2)l++)
22 p(++2)(p+4)
( 3) ( - (4), (2),
p
29

---

Published as a conference paper at ICLR 2024
D.2.2
Two INDICES (ROWS)
( ( ((())(())(3)-
3 1
2
0
(0)
(1)) (b)))
tp 1)(+1)
(3%
-
To- 1)++1
27
(2. p42
p44
( p+2)
p#3 2 2
(r- 1)(+11)
16
ip 1](+11
plp+2)p++))p++
p(+
4 plp plp+2 2(
15
()-+)(++1)
p(p+2)(++()(ppt)
(p- (0-1))(0++10++((0-0110666
1
(+1)
(-1)² (1) 4 (-1)² (t) 1 (b)) (
0
(3 (11 / (
+3
Tp- I)(+I)
3
( - 2 (g)) (2)2 (t) + (4) (2)2)
to- 1)(+)])
3
6
3
((-+)(++1)
+6042100+(0040
2(++2)x++4)
p(++2)
3
3(p+3)(pt5)
(--1)(++1)
p(p+2)(p+(((++)
9(p+3)(p+5)
p-
= ( (-1)) (4), (+) (-1)) (t), ( )
- (0)) (t)2 (9) (t)) (t).
3
3(p+3)
11-1)
p(++2)
plp+2(p+4)
(1-1)((+))pp-
-
((11)) (4),
(-)) (t),
(-1)
)1)
( ( (()) (5) (5), - -()) -1 (2), (2).
=
= ا
15
15
15(p+5)
p(++2)(0+4
2)=
1/4
3
+) (-1)) (1)) ( + (3) (0) (-1)² (1), (t), (4))
(8() (t), (t)
a1
(G)
-1 (t) (4),
tp 1)++T)
2n1
(2 (8)
(B)
(o-1)(+1)
45
(B 2+ 200)
9 (g.
2t2 241
[--)(++1)
04
32
(ppt
[p-1][+t]]
Pl
p(p+2|p+47
30

---

Published as a conference paper at ICLR 2024
3/4 ) (*²1)) ((11) (()) (t) + (0) (-1)) (6) (2) ( )
(-1))())
2
(z)) (1) (z),'((1) (1)2
= (m-1)(++1]
( = ( [)++ ا
-)(+)3
= (0-1)(+11) (10+2)(0=1)0+0)
p(++2)(0+1)
1/4 ) (2) - ((5) ())((()) (P-11p1++2
- (-)))))))))))))))))))))))))))))) (-(9), -1 (1)) ()))
15
200
(
(-1)²(b) ( (+)
(-1)² (2) ())
(3 (1) -0-(())) (1) ())+
(--1)(++1)
(3()) -1 (4) (4) (5) 3
(1) - -9)) 11)+
+ (()2 -1 (1)))
= (-1)((+11
45
-3-15 15
3
(p- [-1+]
p()++))p+ 4)(+6))
Mp++)
P(P-2)
3(p 3(p+1Xpp+3)
3(p+3)
(o-
20-1)pp--210++
1 2 ) ) - (-1)' (2), ( (1), (t)) ب -
(t) (2)
= - (()) ())(()) - (4) (t)) (t))
1
3(p+1)
= p-1 (p(+22)p+0) ( (0-1))(0++2(0++000--)
1)) ) = - (=)))) =0
3 ) --م
2
(-1)) (b))
(b)) (()-
1 p
p(ptt)
( 2)
x+1
) = - (- - (-) (b))) .
1 ) - ( ((1)) ((-1))()))))) ( (1), (2)( (2)
= ( (
-0)) (t), (t))
13
p+1
= (p-1))(pt2)(z+++ (p-1)p(tt2((7t4)
3 =
( 1 2
)
3
0 0
(p 1 1p(p+ 1p
31

---

Published as a conference paper at ICLR 2024
D.2.3
THREE INDICES (ROWS)
= (
2
(-1) (2)2
+
0 0
(-1) ()) / 1
()
( )
(-1) (2)
3 - / 1012
G- [X++T]
+
(3 (b) 11 (4) (b) - (b) (1)) (t) + +5) -1 2()))
[X|+]
= (x- ()-1)(+ 1) (()+)))++)))++ -(0+3)6044) + 3
6
p(pt2))
kpp+))
= --- (0-1)pp++1/- (pppp+)(++2(+> (ppppp++
2000 ) ( (11) ( 1
())+
))
= - (6)) (2), (1)- - ()))
3(p+5)
1p-1)pp++110++
7 1 = ( -1 (-11)(2)) ( (1)+(-1) (2)
44 (11)) -1 -
3 124
= 6 1)++1)
()(+) (3)) -1 (2), (2) (B))
-1 (2))) 6 1)(p+
0 ) ( (-1) (t), 1/8 +>(()))) (2) -
= - (B)) (2) (G)
-1 (1)) = ا (
f (p-1)p(+t)(p-t))
1000
= ( (11)) ( + (-1)) (2)
-
= - (5)) (1) -0)) (5) (t))
p+3
)) - p-1 ((B), (4), (1)
- (- (-1) (t),
3
(p- 10p
+ (-1) (4) 2)
( (
(-1)²(1)) 2
3 (B) -1 (1), (1)
2
(0) -1 (t) (t),
w-1)e+1
x- p(z + 2)++2)(++4)
3
-3pt33
32

---

Published as a conference paper at ICLR 2024
4 0
1
(5) (#) (4)
1
(p- 1ppppp + 2) ()( +
= (()))²² - (11)) (4))
(#)
+ (-1) (2) ( 1 +- (2) )
(-1) (2)
1p-1XptT
3
+
3 (() (1)
(1)
2
(4) 3
(4)
3 (5) -1 (4) (4) (5)) (4)
9- ()+ 3(p (pp
(p+3)2
1)p(pt 2))
1/ppt (x) 4)(++6)
1
(-)) (1)
(3) (2)
(p-1)p(p+)
33

---

Published as a conference paper at ICLR 2024
D.2.4 FOUR INDICES (ROWS)
plaisn alanao
(
11
(-
1)2 (g)
+ (-1)* (1)
0
3
(4) (3))
(1)
p
(-t1 (4)
P-T (2) (#))
440
( (221))
(-1)² (2)
+ --1) (2)
+ (-1)) (2)
[1-1](+1]]
(()
(1)
(g)
(1) 3 + (5) (1)
(p-1)(++1)
(k++))(--)(6 2(++2)(p+4) + plp+2)
(p- [][+1]
(p+3)(pp55)
(p- 20-1p(ptt//p2200--000
(H))
1)(+1) (G) (1)
3
(0- 13p(+ 1) f)6
(2t2)
(-1)² (-1))(())
1
(5) (1) (B) (1)
p-1
R (p-1)p(p-21 21 ())++)
p(p+2)
34

---

Published as a conference paper at ICLR 2024
D.3 MONOMIALS OF THREE ORTHOGONAL VECTOR
D.3.1 ONE INDEX (ROW)
( 8) = 2(--))
< g = -ー (11)) (1 (())
-P Fー (t
( (पOteïAн1))
16-9
3p-2)
3
(p- 4)
D.3.2 TWO INDICES (ROWS)
3+3
p-- ()p( ()
aloo 449
(p-3)
(p- 2))(
alou
alec+ Jaad
3(p+3)(p+5)
(p- 1000
(1
p-2
1p-1) 2))+4)+))) + (p-1)p1
1+
(0-1)p(o+2(p--)))
1
1
7
1) (p-
()++
0
/
-3
(x+3)²
1)
olon
) -ー
+
(
+
(-1)
1 2
100
p-2
3(p 1]pp6) -(p
3p++5
35

---

Published as a conference paper at ICLR 2024
D.3.3
THREE INDICES (ROWS)
aloon
alONa
))
alooN
1
2
p+1
2(2+-3)
1)(p+2)
(0-1)ppp+2(pp-0
1リ~2Xpp
cloc+
3(p+3)
3(p-5)
21=1 ()+1)))++)))))
3(pt3)pp55)
p-2
(p-1)p(++)) (++4)
3(p 1o0t))1--91000
2-
4(p'+8y++138
23(p 1)p(2t
4)(++6)
+ (-1)²
alecw
p.d 2
3(p+3)pp+))
p+3
p-2 (p- 1) (p- (0 (p=))
pp-
2)( 11100001pp0+100--0+01101100
(p+3)(p+5)
13p(F (pp+)((++))+++++++
p-2
p+33
3(p=5)
(p+3)2
p-2
(p-1)((t2)pPt (p=1)p(p==
(p 1)p(p
2² +3p
2X -=00
alNow
(0=1))(p+3(@++ 10
(p+3)²
(p ())+))))
3(pt (1p+(1)-1 ())33)
00² +3
(p- 2)(2 11p(++1)(ppp) (p 4)(++6)
(p- 2){F pp x 1)1 6p+
-(++2)
(0- (p+p+))(+++)
(p-1)p((+2)(0-+)
1
3(pt3) 3 1
(p- 111ppppp22//11100001111 1
Hiat 1) 1) 3(p 3(p+3)((++))))) -))
- 1)(p-1))p(ppp 1)p(p 11 )
- -3 +7p+41111 )
(p-
36

---

Published as a conference paper at ICLR 2024
1
1) ---
z-
3/ 12433
2)6 - 1
2-d
(p-
1)plpt
1
+5p 2 
2-4
(p-
(p 6
(p- 2)( 11 1100+21000000
2
(p-1 1 2) 1o
4)
(p-
1)p(p+
p-
1)p 2)(2 -1-
1)(P 21
---
3)
3
200
1
1
) - -2
0
( ---211-- )
1
2
22
37

---

Published as a conference paper at ICLR 2024
D.3.4 FOUR INDICES (ROWS)
1
p+3
p-5
(p+
(p+3)(p+5)
p- 3
-0-
1ppp-
(p-
(p+ 1)(p+ 3X (pt (1
(p
(9 2 2)
480 13p-2
(0-1))ppp+1 11-1)))==160++)(-+++ 2()+))(+++)))))) +
(p+11 (p++))(p++)(p3)))
8
p-
(77+7p+14)
[p-
21(p 1pp(+113
(2
4)(+6)
(5+5)
(p-1)p(p+1)(p++ (2= (
p+3
2-d
(p-1)p(p-1)
(p= +5p+2)
22 1
4)( 
2]( ip-
1
2
3
---
2
[p-
3+3  
0
2-1
1P-
0
1
2 1o-di
11/57 2/1
-l11
38

---

Published as a conference paper at ICLR 2024
D.4 MONOMIALS OF FOUR ORTHOGONAL VECTOR
1 ) p-3 (-1)
(-1))
p-3 (
1
p-3 p(p++2)(++)) p(p+2)(+t
2-3
(p-3)p(p+2) p
DUSSEN
clen
clow
(p-
aleoio
aloN
cloR
olvo
o/vo
( 1pppppppptpppp(ppp 1 4)(++6)
(p+3)(pp5)
aleas
alec
aleeok
+13p 2)
27 2)pppppppppp-0000--10011 ()0-
CLSOON
alocno
alowco
alocoo
Elecic
cloooN
alocio Elaecs
)) 1-
claccio aloono aloico
clocow
clooNo
3 Srd
3
+spp+sp2 +13p133-22)
1--2][6-1133 1
(p-2)(p-1)pae 1)p(p+ 2) 4)
(p-2)(e+3(pp) +6pp++11))
(p-3)(p 2)(2 1i 10 (0=
slow aloN
( 1)pp)+2)ppt+)pp
2/20
(1+3)
1bppp+1 () 4)(++))
R1IION
- (p' 1 +5p+2)
alou
clecs
3j000
(p- 23(p 1) 11-2 (p+44)(++
clo-
(p²+7p+11)
(p 21(p 1)p(rt 2)
(p- 2) 2(++2)
39

---

Published as a conference paper at ICLR 2024
HLOOE
ajowet
al
aloNco
aloRe
cl
2
1 11
80
+ 18p-2
10-2)lp-10
2
2
// -09 -3p-0
-a - a1/4 10ll-111000
2
2 2(02 2 Sp-+2 - 2(p -
0
1
2p(
(p- 31 2)(1 11p( 
3 (p- 1)-()))p44 160 110.001111111111
8
2
(i0-=:/---)(--11---- )
E E-d
-
2
p p'+7p+14
-
( () 2)(
0
E-d
( 2
1-d
-8- (0-1)p(++11 11 (p-1)))1) (-- 1)
101o=-t)p(=+|((++2))11= (p++ () 66
[0-3][p-2)6 - 1)p(p+1)(pppre 1 {)
0
40

---

Published as a conference paper at ICLR 2024
E AUXILIARY EXPECTATION DERIVATIONS
In this section, we attach many auxiliary derivations of simple and complicated polynomials that we need in our main propositions and lemmas.
Proposition 14. For 2 2, m E {2..... .p} and random transformation O sampled as described in Eq. 47. it holds that,
(p - m) (m² - 2mp 3m + + 6p + 14) IE [ee 31
p + (p++))
Proof. We notice that the expectation can be written as
E [cc Oc:) E (u Qm
u
Employing the algebraic identity that (a + 6)2 = a + 3a²b + 3ab² 53 and Cor. 12 (canceling terms with odd number of Qm appearances), with (a + b) x 3 3at² 13. We thus get,
be readily that in our are left
E (el Oel 3E
Qm [lu)
0
u
+E
(u
[ 1--m ] ]u)"
1p-m
3E
Qm
2
+ E
Σ
i=m+1
iim++1
3
Σ
E
Qm
[u)
up
Σ
E [uuuufui]
i=m++
i=
j=m+1 k=m+1
m)
3E
Jug u Qm u. In Qmu +
Σ
Σ
E [ugufuR]]
j=m k=m+1
The inner left term becomes
3 E
3
E
up |uull
un E Ep
Fr
Up U1
E u
1=1 1=
3 mE
[u m (m - 1)
=3 (
(m 1)
)
m
(
while the inner right term becomes
+ (p (p-m--1
2 p-
12
k=m+1
k=m+1
j=p
m+1Sisp-1
E [ug] + +p--m 1- 7 16 up + (p-m-11
2E
+ (p--
2) 2 U
k=p
m+1Sk5p-
k=pvk=p->
5+15 2
=
(p-m-1) m
(
3 + (p- m 2)
Combining these two inner terms, we get,
E {eTTe:))" 31
= (pp- - m) (())+3(p m) ( ) (m² 2mp + 6m + p² 3p - 1)
41

---

Published as a conference paper at ICLR 2024
(p m)
m² 2mp + 6m p² 3p
= (p- - m)
+
(p + 2) (p 4
p + 2) (p + 4)
p + 2) (p + 4)
(p m) (m² - 2mp - 3mm + + + 6p + 14)
+ (p+
Proposition 15. For p 2 2, m E 1.,... .P} and random transformation O sampled as described
Eq. 77. holds that,
(-m² + 2mp + 3m 6) (p m) - (p-1)p + 2) (p + 4)
2 Oei) )²
02 0e
Proof. By decomposing the expectation into the two additive terms below, we get that
E
[e) Oei)
B2 0e = (u Qm
I--m
v
Q
(u [mm v + To (o 1--m v)² (u
Qm 0. 11 + 11
[ Ip-m u)
(u, Qm Va up vo)² (ua Qm un + up uuuu
[n Qm Ve (na Qm va + up vo) (n Qm u + ug ub]
below
E ug vo (na Qm + u vo) (n Qm us + ub ub)
below
m) (m (p+ + 2) m² mp + 2)
(p m) (-m² + 2mpp 3m 6)
(p- () 44)
(p (p-1) 1) + 2) (p + 4)
Using Cor.
12 in the first step below, show that the first term is.
E un Qm Va (ua Qm Va + un vo)
[u Qm Ua + un uz)]
= E [u, Qm Va Vbua Qm Un
+ E
Un Qm V. Un Qm Va
up
Ua E
u Va U Vo
+
| || ||
m
m
E
Ub
E
12
|ubll
m
salved Eq.
17
solved Eq. 19
(p m) (m (p + 2) 4)
(p- (p-m)m(m++2
mip m (mm(p+3)-2
10=1ppp++((pp+ (p- ()-p)p)(())+ppp+>)
(p 1)p 2) (p 4)
From Eq. we know that the second term is
E Ju Vo Un Qm V. + un Vo)
(n, Qm Ur + un un)]
E u1 vn)
1 E
| 1| (u, vo)
mp-m)m m++1 (p- (p- m Jam (m-+22)
1)((+2]
(p- (0-1)p(++)(pp+]))
solved Eq.
solved Eq.
(p m) (-m? + mp + 2)
(p (p + 2) (p + 4)
42

---

Published as a conference paper at ICLR 2024
Proposition 16. For p 2 2, E (2....,p) .P} and random transformation O sampled as described in Eq. 47). it holds that,
E (e] Oei)"= 3 3m 4) (m + 6) + (p m) (p- m + 2) (m² 2mp 4m + x² + 10p + 36)
p
+ +
( 4) (v + 6)
Proof. We start by showing,
E Oe:) = E (uT QQm
u) = E (n Qm Uo + un ub)
Employing an algebraic identity and Cor. 12 to cancel terms with an odd number of Qm appearances, it can be readily seen that in our case we are left with (a + b)* a + 1r + ba? Aat b². We thus get,
E (u Q. )a) + 61E (u Qm u.) ) (u un)² + E (ny ub)
B u -u-s-- (|lual) r T uu)) - 61 [nn ub) Be-sm- (1|lg] r ["aa)) 27 + E (u, us)
E ||u.l| =B|lu.l] Eewsm- (r un) 6E || || u Br [rr un
+ EE ||
We employ the isotropy of and show that,
6 E
=E
| En-sm
(|ua||r*
e1)
+
||m
[ua 1! u uu
13 ||ubl
m
6
= E
[r]]
E
Uul
+
E
||ua|l"
+ E ||ub
m
(+) ) m
E C|lua|l
E
||ua|
1))
|| ||
+ E ||ua||
E
[ual
+
6
E
uu
||
2E
|ual
1|
||u./|| 11"
+ E | 1")
+ E ||ub/|
m (m + 2)
m
3
12
E2
+
11
+ E ||bbll
m (m + 2)
m
m
m
6m + 15
6
12
E
|
+ m
E
E
|ua
11
||ull
E
m (m + 2)
m
where we use the subscript in < ),,,
to indicate that, unlike in most places, the corresponding
m
random vector is in s rather than SP-1
Next, we derive these expected norms in Prop
26 and obtain
6m + 15 m (m + 2) (m+ (m + 6)
6 m (m +2)
12 m (m + +2) (m + 4) p(p+2) 2) m p + 2) (p + 4)
+
m (m + 2) 2 ()+6)
m (
m m6)
2)
(6m+ + 4)
p(D+2)(p+4(p+6) + (mm+ + 2)
12 (m + 2) (m + 4)
p(p+2) 2)
p + 2) (p + 4)
(p (p-m) (p- m00-m+440 m +6) 6)
2)
(6m + 15) (m + 4) (m+ 6m + 2) (p + 4) (p 6) 12 + 2) (m + 4) (p 6)
p + 2) (p (p+
(p- mp- p + 2p)+))))))))
m 66)
3 3mm + 4) (m 6) (p- (p - m 2) (m² - 2mp-2mpmmm - 4m + + + 10p + 36)
( (p + 4) (p++) 6)
43

---

Published as a conference paper at ICLR 2024
Proposition 17. For p 2 2, ,2....,.! .P} and random transformation O sampled described in Eq. (7). it holds that,
IE 0e2) 3(m² 2m 200 +m (4p +4p +
(p- ()p(++ 1)p + 2)(++4(p++)
Proof. We begin by showing that,
E Oez) E (eT Q2
Qu
Qp 02
EuLv
u
Qm
p- v)
pm
= EuLv (n Qm Va + un vo)
E (n Qm Va Un vo)
where the last step simply employs our simplifying notations (Remark 4
Employing an algebraic identity and Cor. 12 to cancel terms with odd number of Qm appearances. can be readily seen that our case we are left with (a + b)* a + - + 2a + 64. We thus get,
E [ Quva))))a
6E [n. Qm va)²
+ E (u, (oTTvb) (u, vo)
solved Eq.
solved
selved Eq.
3(
5) (1
(
(p- (p--
(p- (o-11pop--10021))---1111111
6m 3 6m 6mm
(p- 1p-1)p(p+ 1
After some tedious algebra, we get, as required.
E (e] Oe2)* 2 3(m² f1n'-2m 2m 2m 3)++33++mm (4p² 44 1) 22m + 188)+)++((7" +-(p2=2pp) -2p-3))
(p- 1)((p+ 1) (pp 21p
44

---

Published as a conference paper at ICLR 2024
Proposition 18. For p 2 2,m, E (2....,P? p)} and random transformation O sampled described in Eq. 47.. it holds that,
[ej Oel 62 Oei)² E (e) Oe2 e 0ei)
(m + 4) (2mp- + 4p + m - m² -6) 6) - (p - m) (p m + +) (m - 2p - 5) + 10)
(p 1) p (p 2) (p + 4) (p+ 6)
Proof. First, due to the exchangeability (Prop.
9). we have,
E (e] Oel e Oei) 2 =E E (e) Oeze 0e>) 2 =1 (e) o eze, 0Tei)² e2
=E (e) Oe e, 0eie)
Then, we show that,
I e
Oe2 e2 Oei) = E (n' (( o] + [ [--m] auuu T (1 o] + [ I-- 1) ()-m)) v)
E (u Qm Un u, un) 2 (u Qm + up vo)²
E'' (u. Q. Qm., ) 2u, Qm u. u, + (lubl")) (u. Qm + up vo)
We now partition the above into three terms that we solve separately. The first term is.
E _ um)
((1) QaV)²
2 + 2ug Qm u. vo + (n, vo)))
E u Qm un)
[ Qm)
+2 (u, Qm u. Qm vo + (u, Qm uo) (u, vo)))
solved Eq.
14
=0, by Prop 12
solved in Eq. 16
(m + 4) (m (p + 3))
(m + 2) (m 4) m)
+
(p- 1) 1)
(p ( (
(m 4p
(p - 2)ppp=))((++))p+++++
The second term is,
E (2 Qm u. u us) (n1 Qm + 2 Qm
Vay _
+ (u, (u]vv)') v))
Prop
4E T Qu ua u Qm Vau, vi]
4EuLv
Eq_ Qm Qm u, u Qm va] |///| 2 ub uTvy) vo
4ERLv
Epasu [[[[ua]] u (||ual) T va)] || 2 u1 vo
4EuLv
| |u.11² u Er-gm- [rr'] I Va un vol
Eulv ||ua|
|moll I va un vol
4 =
||uol ??? (1- |uu
(-u vo) u, vo
m
E | (u,, vo) vo))
4
||aal (u, vo)² 27
solved Eq.
solved in Eq.
17
m (m + 2) (m + 4) (p m)
(p-m) (p-m) (m +
(p 1) 2) 4) m 100-1] ()
4 (m (p+
(p (p=1))(0+2)(0+4
(p (p=1)
The third term is.
||ual| Qm.)) 2u Vayg vs + (u, vo)
45

---

Published as a conference paper at ICLR 2024
= ||لb||* (u Qm va)
+ 2 ||/m||
u Qm uo vol
+E ||ubl|* vo))
=0, by Prop 12
||ull ( Qm va)
+ E
||us||
(n) va) ?
solved in Eq.
2S
solved in Fqq. (T)
(plugeing m + p m))
(mpp) - m m=pp-pp---p p- 5m 2 + 1mmpp-mmm222
(0- 2mm +6p++)
(p- 2
(0- (p+
(p m) (m² 3 3m²p 11m² 3 + 2mmpp 13mp + 20m 2p 3p--1 4)
(p 1) (p 2) (p + (p
Finally, summing the three terms (and after some tedious algebra), we get the required
(m (2mp)))mmp -m (p-m)(p m -p-5)+10) 10)
E (c2 Oe2 0g Oe,)*
(1-1)p(=-21(p-11/10
46

---

Published as a conference paper at ICLR 2024
Proposition 19. For p 2 3,
12, ...p.....P) and random transformation O sampled as de-
scribed in Eq. 7 it holds that,
B ( Oea e Oei)² Amp(- hwtp::/:::....///////////o-oooo0
(p 1)p(pt 11
Proof. We show that,
E Oe Oe3 Oei) = E((u (u )=
([am o] I z u (1 o. + 1 [[-mm))) v)²
= E [ Qm Zn + u, zb.) (u Qm Va + u, vo)²
E Qmoo) 2 + 2u Q Za up 2b + (n, zo) )²) (n Qm Vo + u v))
where the expectation is computed over the orthogonal matrix Qm O(m) and three random (isotropic) orthogonal unit vectors u L v z S
Again, starting from the first additive term,
E [ Qmza)² ((u. (mn)Qmaa) + 2u Qm Vou vo + (n, (u]vv)') v
[n Qmaa) 2 (u.Qmma Qm va) 22+ + (u, Qmza) 2 u Qm Qm vo (u Qmza)²
vo)
E
solved in Eq. 34
=0, by Cor
solved in Eq.
35
mmp+33l((mm+2))++m=++-- 16p-22 (p-m) +pp+) (p- 1p-1011p-1110002200000000000
( 11 6p-4)
(p (0=2)(mm))3))( 11pp0
16p (00
The second term is,
_ Qn up 26 (nu) (mu.Qm vm) +2 2u 222TQ.. Qm v. vo + (n, vo))
EE
2 Qu ug zu (u? Qm v.)² )²1 +4E [u] Q. u, nu Q. u, vo] +
E
-0, by Cor 12
E
n T Qm
Zn up 2o Ub vo)
=0, by Cor
u, Qm up 2 Qm Va vol
4 Eniviz ||ua|| V.v up uy vo
4Enivia
|| Er-sm Iv rr zza) un zou1, vo]
solved in Eg. 30
4 m) (mm + 2) (2 3m 2m (p + 2) 6m + 4)
(p (p-2) 2) (p 1) (p + ( And the third additive term is.
(u, 20.²² ((1. Qm vo)² 2u Qm vo vo + (u,7 vo) [²)]
E
E (u, 20)² (u. (T
+2E (uj 2n)
u Qm Vo un vo + E (u, 20)
vo)
=I [[u 2m ( v.)= due to the invariance (Prup already solved in Fq.
0, by Cor
solved Fq.
(p- (o-m)(m+2)(mm)) +5p+2) +5p+2)-6p-1)
(m
pp- 2)(p 1)p(p (p+ - (==1)p/==+|))+++((((++++++++++
m) (m + 2) (m (p² + 5p + 6p 6p 2) (- mm + 2p + 4))
(-m²
(p 2) (p 1)p + (p + (p+
By adding these three terms and after some tedious algebra, we get the required proposition.
47

---

Published as a conference paper at ICLR 2024
Proposition 20. For p 2 2, E .2....,p? .P} and random transformation O sampled described in Eq. (7). it holds that,
Dele Oele Oele [e2] (p - m) (-m² + mp + - 2) (p 1) (p (p+
E e
Proof. First, we notice that
Em [va Qm Unu U Qm vo] = BuLv Vaa Br- (1/uall r) (1|ual) || x) ug un vo
= =Eulv
||ua|| va Ep [rr |u Vol
1
EuLv
| Va un vo
1 E uull (u vo)
m
m
Then, focus our quantity of interest here,
E (c, Octe Octo (0c))
= =Euiv.Q. v
mn-
1p-m uu
qm
= E [(v. Qm Ua + Vo an, Qm us + u, un)
(u Qm Vo + +u vo)]
Splitting the first multiplicative term, we get,
E
V Qm Ua (n Qm + u ub (u Qm + un vo]]
Cor.
2
E [v T Qm Un Ug Qm Un u vol
+ E [vo Qm un up unu Qm va]
E Q Un u Qm u, ug vol
+ E | ll vo Qm u Q Va
solved in Eq 27
+ (p-m) m) m
[aooe]]
En ||mm|| (ug v.)²
()
and
vo us (u, Qm Ua + u, un) (u Qm V. + up vo)l
Coo.
12
E v u Qm u, u Qm va] + vv un u un vo]
E 1 u Qm u, u Qm v.] + E || (u. vo)
linvariance of Qm w.r.t transpose (Prop.
E [v] Qm ua Qm u, u vo] + E
(1 |maa|| | (n,, vo) "
[above]
En LV
|| 2 (u, vo) 2 1 (u, vo) 2 *]
|n 11 (u, vo)
m
Combining the above, get
E (c] Octe Octo Ocz)
(p-m)(p-m-t) (p-1))(pt2((x44)
E (u,, vo)=
(1
2 m
E
| 11
(u vo)
solved in Eq. 23
solved in Eq. 17
(p-m)(p-mat m+ + (p-m)) mmm (p-1)pipt))p++) (p-1)p(p+2)
m+2 (p (p-m)m((+2)) (p=))p(p+2)pp+4)
(p m) (-m² + mp 171 +p
(p - 1)p
48

---

Published as a conference paper at ICLR 2024
Proposition 21. For p 2 3, 32......,, p) and random transformation O sampled as de-
scribed in Eq. 7 it holds that,
(p m) (2m² 3mp 2m pp + 8)
E 2 Oc Oere Ocgl
(p 2) (p 2
Proof. We start by decomposing the expectation into the following,
E
T Oeleg
Oeleg 0e2]
E T Qm
I. u uuzz a..z
Qm 1, m u.zz z
Qm
ba |
E Qu Ua
(z.QQmu
Qm uh + 2n ub) (2. Qm Va + z vo)] +
[v us (z Qm Up + 2z ub) (z Qm Va + zb vo]]
Focusing the first additive term and by employing Cor. 12 (in the first step below), we get,
E v. Qm Ua (z Qm Uh + 2 ub) (z Q. Va + zn vo)]
E [vo Qm Ua zn Qm Ur 2n! vo]
+ E [va Q. un Zn us Za Qm
E
|un 12 Va Brwsm- [rr
Za 2b T
Vb
+ E
Zi Ub
Vilkill
f.j
k1E=1
-E | ?|
vozua 2 vb
+E
Ug
Uggiyuj
1==++1
vo
1
E |
2 (v] 20) 2
+ (p- m)
E Up [kc]
k=t=1
solved Rq.
By Prop 10 most summands are zero]
1 m (p m) (mp+ + 2m
m
m (p - 2) (p 1) 2) (p (p+44) 4) + (p m)
E U, E [
i==1
(p-m)(mpt2mm1) (p- 2)(r 1)(
m
mE U1 Up 21
+ m (m - 1) E) 21
(=)
(p- m) (mp + 2m - 4)
(
1 2
(m 1) / 9
+ (p m)
1
(p-
(p 1) p (p + 2) (p + 4)
(p m)
mp+ 2m 4 (p-2) 1p-22 11P-211111 + (p-1)pp+t))Pa
2(m 1)
fp-2)( (- 1))ppp)))ppt(ppp1))
mm +2
(p m)
(p-2)
(p- ()=1)((++2 (x++
(p - m) (-mp- -mmp--+44
(p - 2) (p - 1) p (p + 2) (p + 4)
In addition, the second term is,
E [vi. us iZ. Qm 2 Ub) (Z Qm + 2n vo)]
E vvo up 2 Qm Un 2 Qm + E Vi us 2 us 2 vo.
E ||z.e 1 Vn u Eprsm 1 |rr
ua + E VoJ fz u0 vol
1 m
E | vi ub U
vo 1b2
us 2n Vb
2 V.
49

---

Published as a conference paper at ICLR 2024
E
[zall' 1 (vb ub)
27 -E [vg Ubzy u Val
solved in Eq. 41
m (p m.) (mp 2m - 4)
Σ
Σ
E [1
(p (p 2) (p+g) 4)
1m kmm++ I 8m
(p - m) (mp + 2m 4)
E [[iecueehuuz4
(p- 2) (p 1) 2) (p 4)
i=m+ k==+1
(p m) (mp 2m 4)
P
(p m) m Σ
(p - 2) (p 1)
+ (2) (4)
(p- mm)
mm
+ m
u 11 Up 21 Epl
+ (p- m - 1) 11p-11ppp11 11p01 Up- 1110011-11p0000-112133
k=
m m+1skSp-1
1
(p- - m)
(1-2 + m
mp
[
+ (p
m 1)
(p- m)
mm- 4
2(p 1- 1)ppp=-)ppp+)))2p001
(g-2)
(p-1)p(p+2)(=+1)
-2 (p- m)
(-m² + mp m -2)
(p 2) (p- 1) +
Overall, we get that
(p-m))- mpp-)+11) 11-2)(p-1)p(p-21 + -2(p- m) +mmpmmmmm
E [ Dele e 0e
1p-2)
(p m) (2m² 3mpp 2nn 2 p
(p 2) (p ()
50

---

Published as a conference paper at ICLR 2024
Proposition 22. For p 2 2, E .2....,p) and random transformation O sampled described in Eq. 47). it holds that,
E [ej Oe1 e Oc2) (02 Oc1 02 0e2)
-m (p+3))m (3p² +8p +m² (33p" 6p 13p+3) +m(p" +1p+6) -p² -188² 180p 44pp-24
(p-
1 1) 2)p++)((++))
Proof. We start by decomposing the quantity as follows,
E (e) Oel ej Oe2) (e) Oel e Oez)
= [u Qm u + up ub) (n, Qm Vo + vo) (va Qm + vo v. (v. Om + voo voovoo]
E. [u_ Qm (n Qm + un vo) (v. Qm + vo ub) (va Qm + vo vo) +
E [ug up (u Qm Va up vo) (vo Q. un vouu) ub) (va Qm Va vy vo)l
We show that the first term is,
E [ Qm Un [n Qm up vo) Qv.Quu, Qm +V, u,) (v.Qnv Qm + vo)]
I Qu u Qm Va (v. Qm Un + vo ub) (v. Qm Va + viJ vol]
E I Qn U. un (Vo Qm u. + vi ub) (v. Qm + vo vo)]
Cor
E u Qm Un u Qm VaV. Qm uav. Qm +E I Qm Um ug voVY u.v. Qm
E [ uau, Qm V 4 vol E [u, Qm u. vov. Qm V. vo
equivalent
ju Qm u Qm Qm ua Vn + 2E [u! Qm u Qm V. V. uvv
E Qm v Qm (u v
E [ Umu Qm Qm uav. Qm + Lull PE (r urr vo) v ub vo
+E u, Qm ua Qm (u.vv) vo)²]
2E
E
[n Qu Un u Vav Q.. v. Q Va
E ||u 1l u Va vī 1| +
solved Prop.
solved in Eq.
29
E
un Qm Qm ub)
solved Fq.
(m2 +14 6p +4++24)
2 mm 2(pppt-))
(p-l)p(r+ 1p-1)ppp=1111+33)+44410
3(p-m) (00mmm((mm+mm-app) +mp+2p+4)
(p- 10-
(2p+3)+m (4p² + 2m +0) 10p0+2pp+*00p0p
(p- 1>(p+ (2) (p+ 4)(++))
Moreover, show that the second term is,
[ug ug ( Qm v. + ug vo)
(v Qm + V ub) (v. Qm + vo v:]] E uu uhu VONT 4bVE va
Cor
+E un in T Qm Vav Qm u. Vo +
uu u Qm VaV u
Qm Val + E [u, uou Vov. Qm u v Qm
+ [ug u Qm Qm ue V vz]. ug ub (v. ua) 2 vg vo
E
[ug uau vb u QT. v Qm va] + F [u, u.u, Vb V Qm v Qm va]
equal due the invariance Q... transpose (Prop.
E
Uu ub (v. Un) vo + E Ub n Qm Qm Vb. +
solved Eq.
solved
51

---

Published as a conference paper at ICLR 2024
2E J u.u Vo u. Qm Va Qm Vo
solved Eq. 33
+5p+3)+ppllpp -1= +
2mp |a (p-
(P- 11-1ppp0-1ip+2(0++0000000
9m 12
Overall, conclude that
E (e) Oel e Oez) e
+
(p- 11-10-01-
+
(p- 1= 20
-m mm++a+)4m (39" 8p +m+ 30" 13p +m - +4p+6) 66) +pp +p""-"" -1²=187" -8p 24
(p-1)p(p+ 1)
52

---

Published as a conference paper at ICLR 2024
Proposition 23, For p 2 2, .2....,p! ,p} and random transformation O sampled described in Eq. 47). it holds that,
(2m+)) (2p+33)+mmmm - +34 - +4p+24)
E I Qm Q Vava Qm Qm
(p- (pp)))p+)p)ppp+p+000000
Proof.
E
u Qm Ug u
Vaya Qu Qm
m
m
m
Σ
Σ
E 1o Bay Ist
6-=1
m
m
u Bnn +
Σ
E (ww. (E (ea (er
symmetry wort n,,5
E u, Elgeggeeeanna
f, jdrtt=
E 0a (E (eg + (1a
Σ
E (
E 9nd +
j.r.t=1
(A) below
E 1lwiiia (E 9h.. + E (1.)
2= j.E,r,t=1
(B) below
-m -m (p+ 6p-2--1111) 6p 26p 60) 16p2 8p-48 48
5p
mm p- 2-
(m==310-=llppp-11102220-00-- 6mp-21pmmmmmmmmmm 2mn-
(m² (2p + 3) + ( 1 30) - 6p² 4p + 24)
(p 1)
(p
53

---

Published as a conference paper at ICLR 2024
Deriving (A).
m (A) j.Rir,t=1
m
[ E (mo
E [ E (n. +
j.,,t,11
n= solved below
(m - 1)
E ( on
n solved below
m [10
m(m 1
mm p- 9m p 2
16p-24
m (p+3) + m² 5p
m (6p² 1
26p 60) + 16p² 8p 48
m (m 2) (p 1) (p + 2) (p + 4) (p 6)
When n = The only nonzero options are ( 9 and < 2 ) We have.
0
Σ
E
= =
o X
0
E
m
m
171
Σ
E uu
Σ j/r=1
E 6
E
[ufugueozueof]
0
jæt=1
j=
==b
j=tt/=
<
0
0
E
EE (L + 2E [uju,eeffu,aa)
j=t=1
= 4
(E
(m 1) E (2 [ufof]]
8
E [uiuçoju0j] +2 Σ
E [uiugueriusuu
j=(=1
j=(=1
< 9
( + ) + (m 1) ()
(
3
2 Σ i+f=1
m
E
0 0
(m- 1) E [ut2007] + +(m 1) E [u
+ (m 1) (m - 2) E [1:1B0P03]
m
j=1,222
122.8=1
jff22
0 )m
( a
+ (m -1) (mm-1)
(
2 ) ))+ +
0
2
0
2 (m 1)
c 2
+ (m - 1) (m 2)
+
o
m
/
0
2 (m - 1)
21E [ 12
+ (m 2) E [ [ufuzuauruar]] 21
V=1.222/22..111
j#f22
54

---

Published as a conference paper at ICLR 2024
= - 9),, ( {t),
+ (m - 1) ( {1/)
) ,,,++
+
+ + 2) )
<
)
( 3 1
(m - 1)
+ (m 2)
+
T 7
0
p
3
( // >,, + (m - 1)
<
)
+
m (m + 2)
(m 1)
+ 4 (
) + (m -2)
2
)
2
m (m - 2)
0 8
σ p
9(p (00-111
mlm--2)
(0-11)66-110--22000000---0000000
(m-1)
-1++ (m-2)(((==)))()
m2m+2)
m² (p² + +00---10--000000--00000-0100101-
m (m + (p- 2000011000000003000000000
55

---

Published as a conference paper at ICLR 2024
When n 2 2: The only nonzero options are (
(
( 2 (3)
) We have,
0 0
0
E
[uf Hy
E (lm.,91,
j,tr
m
<<
3
E (
E
[uiu (uiuzueuyvev) + + [uAugeZus)
m
+
j=t=r=!
m
E (ruguu0zuruB
jpr=
j=(fr=t
172
m
Σ
E [ufuuuf03]
Σ
[ +
/=1
Σ
+
+2)+
E [uiuf
+ E uuuuur
(m
2) E Ju
+2
523
E 1 E Tutun
(m)
mm11mm2
2,
(m
2)
E [
E
[
E
+ E [E/NNN3
(1 1m(m+22)
j 3-1223
123,8=1
2-2223
123.82
(m 3) E [u/130300]
j7123
2E [M u2 ug
2 (m 2) E inluger
+ (m 2) I [1/n2ug02us]
22
j-2
(m - 2) (m 3) E Bu
oLoON
(
mmm++2
2
(m 2)
[17e
+22)
- (1
+ (m
3)
+
(m-
3 111
2
+ 2 2m 2)
2 (m - 2)
2m+
0
1
(m- - 2) (m 3)
56

---

Published as a conference paper at ICLR 2024
2
0 0
+ (m 2)
)) +
m(
0
+
(m- ()m
4
clNo0
Neaaed
(m 2)
2
2
+ (m 3)
1
3
+ 4m 2)
+ (m 2) (m - 3)
/
+) (m (
m(m+2)
16 (1
(m- [mm=)(++2
(m- (m--)m((++2) (pp+)) (p
( (m 33) 5)
21 + (m - 2) (p- (=-1ppp+++ (8pp-)
=m p- 3m 2 - mm -- 27m 1mmp 1p
(m 1 mm #2 1)p 1)p 2)p
57

---

Published as a conference paper at ICLR 2024
Deriving (B).
m
m
B
E El (E 9ke. + E (ke.9k999)))
k=2 j.f,
(m - 1)
E U1 (IE (1, + IE (g,, (220
(m 1) 2 3
E u1222fer222s1
j=r=t=t
(m 1)
E
U1 M1
0
1
j/t=1
m
j=rfi=t
(m 1)2
1
E 0o0000
ifr=1
m
)m))
(m 1)
E Un ueer
+
j+t=1
j=lfe=r
(m - 1)
2 3) m
E [212228010203] +
(<2 0
[u )
j
(m 1) 3
+ (
E u (u
0
jptel
(m - 1)
2
E [1 J2
(m+1)-1
E [1u
mm
(m- pm(m+2)
(m - 1)
(m++))
(m-1)mm lmm(m+2)
(m
2 2 1)
E
[un m
E u
(m (m+)
+ (m - 2)
Σ
ixr=1
2 2 1)
Σ
E (2 m
E (u
#+E=
(m 2)
Σ
E [1
j#r=1
2 (m 1)
2E
1 u2 u2
22
+ (m
2) EE in Tn
mm
1=1.2
58

---

Published as a conference paper at ICLR 2024
E [un )
m
(m- 2)
2 L 1
+ (m 2) E (ufueusufezs
m2)+22
1.j=2
JS2r23Vr52.23
(m 2) (m - 3) E (4
jfr23
mm
2(m-1))
2
1 0// + (m - 2)
+
0
[m
2
2 2
+ 4 (m -2) 2)
2
+ (m - 2) (m - 3)
1
+
m(m++2
1 0
0
2E [ulu2010)
+2 (m - 2) E [u [ulu201220 + (m - B [ui u2 +
m(n+2)
2.
JE(1.2).e23
6E(1,2)1533
(m- 2) (m -33 3) E U1 u2
64123
nn (m
2(m 1)
2
0 ) (m 2)
3
2
))
m(m++2
(m-2)
2 2 2 2
0 1
+ 4 (m - -2)
0
2
///
1/16
+ (m - 2) (m 3)
+
2 (
3
1
)
+ 2 (m 2)
1//1
1
+
m2
1 0
//
1 3
2 2m - 2)
2
+ (m 2) (m - 3)
2000
mn (m)
4(m=1) 1)
/ 3 3
1 0/
1 1
)+
+
2( 1mm 2)
(m 2)
+ 4(m-2)²)
(mm+2)
(m-2)
2
2
+ (m - 2) (m -3
+
m[m++2]
0 π
3 3
3 1
11/1
2
+ + (m - 2)
+ (m 2) (m 3)
m2
(0)p-)))))(++++)(m----))) --( p-3)
(m-2)
15) +3 2) (p-
m[m+2] (p- 1)p(++1)) +1(++)
m[m++]
(p- 11ppp=t110=+ 33m
22
-m²p 13m2p 24m² 2mp2 6mp 24m 4p2
m mmmm + 2) (p 1) (p + (p (p 4) (p + 6)
59

---

Published as a conference paper at ICLR 2024
Proposition 24. For p 2 3, 32.3....,. ......pPp and random transformation O sampled as de-
scribed in Eq. 7 it holds that,
E (e, Oel ej 0e2) (e) Oel eg 0e2)
2m p p+44mmmm 4m
7m p2 18m 8m 25m +4mm (p 2) (102)))++000220000=00=0000000001
20m 3mpp 11mpp 44mp" 64mppmpmmmmmpppppm 201pp' +08
2)
Proof. Like in previous proofs, decompose the expression into,
E [eTTee Oei e/ Oez) (ez Oe og Ocz)
= E [[u Qm un + ug un) (ug Qm V. + up vo) (2 Qm us + +2,,uu (z.Qm
Qm Va + + vo)
E Iu Qm Ue (Nr Qm Va + ug vo) (2) Qm ua + 2 ub) (z.Qm
Qm Va + 2 [o]]]+++
E [ug us (n, Qm Va u, vo) (z Qm U2 + zT, ub) (zo Qm Va + 2 vo)]
(10)
Focusing on the first term, and employing Cor. 12 we see that,
E [ug Qm Un (n V. + un vo) 22 Qm UI 2 ub) (z. Qm Vo + 2 vo)]
E [ Qm Ua u Qm Vaz.0 T. Qm 2 Qm vo] E [uo Qm u Qm Va u62n vo]
u, Qm u. u. Vozi uaz Qm The polynomial in the first summand can be derived tediously, very much like in the proof of the former Prop. 23 and shown to hold
E Ju Qm ua u, voz. Qm Z vol
E un Qm un u. Qm V. Qm u T -m² + - +32
(p- 2]
The sum of the three rightmost summands is, E I u Qm Vazg u vol E [u] Qm u. vozg Qm U, vol
+ E Ju Qm Voz 1zzz Qm
(B un Lzz vo] + E [uuygyu vocuueguez, vol) +
k,j.k.E=1
m
Σ
E (uu,ggaeueeee voz, unl)
Σ
E aay (E [u Tzz vol + E Luuuu verueez vol)
[agguuel (E muutzzeenu voz, unl)
k
E
9
[E
Luuyuuyzzz uz vo] E [uurzuuu Vozz + E Tuuezrzzn vozi u!)
=1/m
1
|1
2 u1
Va
1627 vb BB[llaall u u, vozg vo] + +B(u, vau u0 Von, mb
1
2E u
vo
2 uu Vi
E u V. Zn ub VoRl. us!
m
obtained from Eg. by plugging mi + p-m
salved in Eq (4))
since u. Vo = u Vo and u. 2n 2. us
2 m [m 2( 2-
(p (p-m){ - -
2 1100=
(p m (m m 3p²
10-2)0--pp(0
60

---

Published as a conference paper at ICLR 2024
Overall, the first term of Eq. (10)
equals.
E [ Qm Ua (u, Qm Vo + up vo) (z Q. Ua + 20 ub) (z Qm Va + zb voll
6(m² +m +2m+8)++((mm)) - 205m== +8m- (mm-))=mm2
(n- (0-2)(p-11p)) 1)p(p 2))+)))))))))
The second term holds,
E [ug (ng Om Vo + ub vo) (2.g Q. Ua + %/ us) (2 Qm Va + 2 [z)]
E ub H Vozg u, vol [ug u Qm V. Zg Qn 4o Vol +
E Iug u Qm Voz unz Qm val + I u. voz. Qm 2 Qm Vol
equal (swap v. z and mup Q Q
E I i Vozg u.z, vol E [ u Vb u Qn Veza Qm +
2E [ug ugu Vo 2 Qm U1 2 Qm
E [ug M Vo2. u. Va
+ E [ug 1z Va I1 Qm Va Qm
salved Eq.
solved Eq.
E [n u. Vb 2 u Vo]
solved in Eq. 466
(p-m) 1 m(p 1mmppmm-200 (2mp 3p+2))
(p- 6--21p--ppp0011111:2110------111
(p-m) m² +5m pm -6mp- Ht 4166p41)1 +16p+16)
(p- (p--
(e-m)oem+21l) 2m ft 21
(p 2) ()p(pt 10+
Finally, the overall expression holds,
E (ej Oei e, Oez) (e} Oe: e₂ 0ea)
6(m 4m 2 42m +4mm 2)n² 2( 8m 2)p +mm (mm-2)(5m)) 45mm++3m--mm 4-3--14mm) 16)0
(p-
2m p+ 7m 18m
(p- 11pp: 1
20m - 3mp' - 11mp 11mp - 24mmm +32p +68p+-48
+
(p 2 1ppp
61

---

Published as a conference paper at ICLR 2024
Proposition 25. For p 2 4. m 32.3......p! and random transformation O sampled as de-
scribed in Eq. 7 it holds that,
E (cg Oc cg 0c1) (e) Oc1 02 Oc;)
55 Donnpp6nr pm 6m + 18m2 p² +33m p 12m 20m 2 16m= - p- 12m +6mp" +10mp" +96mp" (p 230pp21ppp 1ppppp11ppp2200 2)
154mp 2p 30p 32 144p-144
31 2)(p- 1ppl- 1) 2)++)))++))))--0
Proof. We begin by decomposing the expression into four terms,
E (eg Oep eg Oei) (ez Oеp e Oei)
= E [u Qmza za + un 2s)) (n Qm + un vo) (xg Qm?a + x, 2b) (x Qm + xx vo)]
E I Qm Zo u, Qm Vo (x Qm Za + x zo) (x Qm Vo + x; vo)] +
un 26 u, vo (x. Qmza Zu + x 2b) (x_ Qm Va + X vo)] +
E I Qm Za u, vo [x]_ Qm Za + x 20) (x, Qm Va + x,, vo)]
E [ug 26 ug Qm Vo (x, Qm Zn + x kn) (xa Qm V. x vo)]
Below we compute each these terms separately. The result in the proposition is given by summing these 4 terms.
Term 1. Employing once again, the term decomposes as
E uu Qm u Qm Vo (x. Qm + X Zb) (x, Qm + X vo)] [u Qm Za u Qmvax Z Qm Va] + E L Qm Za u Qm Va X5 zoxx vo]
solved in Eq. [4
The polynomial in the left inner term (the first summand) can be derived tediously, very much like in the proof of Prop. 23 and shown to hold
E
[ Qm / Qm VeX, Qm Za Vnva]
-m² (2p² +11p² +o- +0-30) 30) +m " (p'+x" +20² +00p+ +p 11p -000))))))
(m+2)(p (11131p1p 3]1 2) 1
Overall, the first term is. E [ Qm 2n 1 Qm x Qm Zn + x, 2,) (x, Qm Va + v.)]
m -m0 30 +m (p* +p" +2p" +60p +2m 40* + +14p-60) (000
-(200)))
(m 2m)p 3)(p 2)p (p 1)( 2 4)pp
()-m)((a 2m 3 p+ p+my + 1mp
6p
(p- 3)1p 2]( 1)p(pt 1) 2
2m 48m 3 23m 16m² 2 12m 2mp 40mp - 4 24mmpp0mppmmmmmmmmm--m--- 18p² 1089- 144 (p-3) 2)- 1)(0)))))))) 1)(+))))))))))))
Term 2. Notice that u, V, 2, x are exchangeabee in the sense that we can swap them freely (see
Prop. 99. Therefore,
E u0 Zo
Ub (x= Qm + x, 22) (x Qm + x vi)]
Cor P2
un Zb u, Vo x Q. Za X Qm Ve
Xy Zb X Vo)]
un 2 T VaX, Q 2 x Qm Va
+ E [1 th Vox, 2,,,, vi]
[wap
E [ Qm Z 1 Qm V X,, X
+ E [u, VEXi u vb 23]
swapped x. u: solved Eq.
swapped v, us salved lig,
(p m) 22m 2m 8m 8m3p mp3 4mp2 15mp 18mm 6p 6p 12)
(p - 3) (p- 2) 2p- ( +6+
m (p m) (5m² + 6m 5mp +p
(p ()3 (p 2) (v 1)
(p m) 5mm p 7m 3 p² 14m p 2mp 5
18m 6p 2pp-pp-000
6p 12
(p- 3) 2
62

---

Published as a conference paper at ICLR 2024
Terms 3 and 4. invariance; Prop.
First, notice that subterms 3 and 4 are equivalent (we swap 2, due the 9). that is
E Uu Qmzo us Vo (x. Qm Eu + x zh)) (x Qm Vo + x, vo)
E u, Zb un T Qm Va (x² Qm Za X zb) (x Qm Va x, Vo)) [p-m]] m)( - 2m p² 3m p+ ump" mp +9mmpp 18m+p" -5p² 12)
[bllo]]
(p 3]m-
and focus just of them.
By employing Cor. 12 we see that
E un Qm up vo (x. Qm Za + x 20) (x Qm Va
+ x3 vo)v
E I Qm u, vo [x, Qm X + x Zbb x Qm Va)
(p- ()-m)((f (5m² p+mmpm+mmmmmm 5mpp 6mptp' +p 22p 2mm
8Y P pt +15mp 6pp 6p- 12))
(p-3)p-
(p-m)(-a0 22m 2mmpp pp 3m 6m 6 1mm 42
(p-3)(0 110000--00011000000000000011-000
where we used the following two derivations, i.e.
[
Qm Za
Us Vb
x Es
x Qm vol
E [[u, Vb xb 20)
u, Qmzo x Qm Va
m
m
m
-E
[ng Vb x1 20)
1=
E [u, Vo X3 2b) -.
k.j.k.bm1
m
E (u, Vb X 2b) Eq lgs]
k.
Prep
10
EQ..
(u, vo x, 20) u.0y012z]
:-=1
=1/1
[ Vo
X 2b up Xb. Vo Zó
m
solved Eq.
(p m) (5m + 6mn 5mpp 6mm + pd + + 2p)
(p (p 2) (p 1)p 1) 2) (p 4) (p)
and
u, Qm u, vox Qmzo x vol
E [|aa|]] |1a 1 (u
rr xx) (x,)
ub vox, vo
1 | u1 x. ub vox, Vb
m
salved in Eq 48)
(p m) (-2m² 8m1ppppppp + mp + 4mp 15mp 18m
6p 6p 12)
(p - 10-2lol-ppoott))+2((---000-
63

---

Published as a conference paper at ICLR 2024
Proposition 26. Let Sa-1 and let ua consists of its first coordinates. The expected n power of the squared norm is,
m + 2r
Bu
|
II -=
p+ 2r
Specifically, holds that
||ua|1== m
E Su-Sp-
m m +
Bu-Ss-1 ||ua|1
p p+2
+ 2
m + 4
Bu- | E
P
p+2
p+4
2
+ 4
E En
Uu
p p+2
p+4
4
p+6
Bu-so-1
||ub|1*
p m
P
m1
+
p
m +
m +
P
P
4
+ 6
Proof. Notice that the squared norm be parameterized
|1 1 u U1 X+Y
where X x Y ~ Xp-m Consequently, it is distributed as |u 1
B
p-m
Moreover,
given n E N+, the n raw moment given by (Chapter 25 in Johnson 1995)
2 +
n-1
m + 2r p+2 2r
Eu
2
+r
r=0
-=0
Jual uP = E Σ u
Σ U
=
Σ 1=1
E
[uZuz
E [uf0p]] +2 (m 1) E [ut futufuu
+ (m- - 1) (ufug
+ (m-
E
1= ((
1=/22
(412
( }) + 2m -1 ( 1 2
+ (m - 1) () (m (m (m
(11)
15 + (m
(p (p-1)p(++))(++4)))pp
m (6
m
(0-1)p(4+t)00+0100000
64

---

Published as a conference paper at ICLR 2024
m
E
E
Σ u
E [u
=E
+E
+2
E
+2 (m 2)
(uiv2u3
====1
(===
2=
Vi=l.j2
i=1j23VV==1.22
2mm 2) 13
(m 2) (m 3) E [u703uuu3]
+ (m 2) E [uf
1=2j23V-=2.22
if123
= = 1 2 ) + ( / )
+
2
) + 2)
0
+ (m (m (
+
0
(12)
(m - 2) (m 3)
+ (m 2)
π
-( JUB / ) ( 2
1
0
+
3
3 (m 2)
+ (m 2)
(m - 2) (m - 3)
(p- (0=1pp0+22)0+++00100
2m (3+ m² (p+5) + +
( +)
We notice that the following derivation is symmetric in i,j. Thus, we assume j 2 and multiply everything by 2.
m
E
|
I|
=E
Σ
11U2U109 U1
E
[u u2
=2
1 (uu2t111 [2]
+2 T (n
+4 (m 2) E
U2
V
1,j=2
1=1/23
(m 2) (m 3) E Un uuuuenuuuu
U2]
+ (m 2) E (ulueafure)
1932
E=
(13)
= 2 1
1 } + (m 2)
1
+ (m - 2) (m 3)
+
0 0
(m - 2)
0
7
-30 - 18 + (m - 2) (- 3) -3)
11-1)
(p (p
- 6m (m +4)
6 1)p (p (p
65

---

Published as a conference paper at ICLR 2024
E. AUXILIARY DERIVATIONS WITH TWO VECTORS
Below we attached many auxiliary derivations of simple polynomials that we need in our main propositions and lemmas.
Euiv.Q. Qm (ng Qm ua)² (n, Un m
||ull| (>m=r reuss) )² (E m
= =Bulv B
m7
M
m
Eulv E ||ual| ruurr,
j=1
m
E Euiv
||ual| u.u.therl [rasyatTe]]]]
Prop 10
Fulvy
[u uF [ri]]]
Σ
Bull
|lua|| uf E [r3 +
#=
i=jzk=t
2
Eudv
| u.s [r3r3]]
m
(14)
(
E
u6/07 +
E
u
11
2 Σ
E
|
k=
{デj=1
(+)
E
|uall
+
m
m (m
1)
+ 2E
|| u
un (22
3
E un
of
E 1u
uff
+2 E
U/ 222
m + 2
m + 2
salved in Eq. [1]
solved in Eq. 12
salved in Eq. 13
((
(m+ + 2) (m ()
(m + 2) + 3))
(m + 4) (m (p + 3) + 2 3))
1p-1) 10-1) + ()
66

---

Published as a conference paper at ICLR 2024
Bulv ||ua|| (ug vo)
=E [|laall (-u va)
E
| 1 m22zz4z
B
U -1 upuff
+
E
uall
171
= m
|uul||
u9
+m (m - 1) E
|u ||
U1 1221 022
(15)
solved Eq. 11
solved in Eig. 13
m² ())
24 6)
(m - 1) (m + 4) (m 6)
m
1--1)p(7 + 2) (0 4) (r + 6)
(m (m+
(0-1)p6++))0+440-6
Eulv.Qn [u, [u, Qm (u,,v)) vo)'] EULv Be-os- (|lual) T uo)² (u, vo)
= Eull
uua ||ua|| uu rr ua (ng (u]vs)² BuLv ||mm|| vu.vv)) =
(16)
in Eq
(m + +4) m)
2) 4p
67

---

Published as a conference paper at ICLR 2024
27
p
||ua|| (ug vo)² E
U
Uz
ml
ui
iml
jmm+1
j m-++ k=m+11
= m (p m)
E Uppuutpu
Amm+1
m (p- m)
IE
[uiu "
(p m 1)E [ufur 12 1 1211pp
(17)
k=p
m+1sksp-1
((
m (p m)
+ (p - m 1)
m (p m)
p+1
(p-m-1)
(p- (p=
(p m2) m (m + 2)
(p 1) (1 + 2) (v 4)
Consequently,
(p (p-m)m(pm+2 4)
E
|ull? (u, vu, va)
(18)
(p
E [na | |[vall 2 ||us|"
ΣΣ
E [u = (p- Σ Σ (u
k=m+1
=m (p m)
E "
j=1
m (p - m)
E [ufuu 2
+ (m
1) [u
(19)
j=1
j22
((
1/2
<
1011
)
m (p m)
+ (m -)
0
p p+++ (m - 11) (p
=m (p m)
(p - (0-1))(p+2) (p+4)
m (p m)
(m (p 3) -2
dp 1) (p
4)
68

---

Published as a conference paper at ICLR 2024
m
2
122
27
E
| " 1/ [1]
E ||0,||
[va 11
BLLv
Σ
u
Σ
?
m
m
E
u +
Σ
ufu
Σ
172
m
B
E
[
E [u
A=
i lipte
same, due to the identical distributions (see Prop. .
E 1
+
Eulv [u/ +
E
1=1 &ighl
175 RighlE
L [1fof]]
+ 2m
E [utuRez
+ (m 1)
Σ
E [2fuzozo8]
lefh
E [ffof]
+ (m- 1) 18 uu (uf
+2m 2 u 1mm-1) (m- E [uf u22303)
m
k=1
1-2
kPE22
+ m (m -1)
2E (ufuzui +4 (m [ [1R336305] (m- 2m - 3) E [ufuZuzrd) 2
0=1. k52.223V
= m ( ( + (m - 1) c
)
2mm - 1) ( g g ) + (m - 1m - 2)
(
1
1
)
+ 2m
+
m (m 1)
(
2
2
) + 4 (m 2)
2
+ (m 2) (m 3)
9m p(p+2)(++()p++)) + 3mm(m=11((p+((pp33 + +2m 1|0-:-10~|-|1--------0---------0 14mm
(p- (p-11p0=-10+2/00000000
m (m 1)
(m 2) (m 3) (pp33)
-:t.h:/.h.................-----e 1)(m 2)(p+3)p+5))
(0m--1)(((2))) -
m (m + 2) 100
(20)
69

---

Published as a conference paper at ICLR 2024
E ||ual| ||val? = Σ
E [u
E [u
-mE.E E [ufeP]]
+m (m - 1) [
f,j=1
J=1
j=1
j22
=m ( ( ()) + m (m - 1) ( 2
m
m (m - 1) (p (21)
+
1
p (p + 2)
(p- pp
m (mp+m-2 2)
(p-1)p(p+ 2)
Bulv,Qm (u, Qm vo)² BaLv.r (//uall r vo)²
Bulv ||ual| 2 E - (v IT [vo)
(22)
1
Eu | [vvll
mp + m - 2
m
(p- 1)p (p
solved Eq.
E [u] JuTvo. vo)² Bulv (-u, (=u] EuLv (u]vo) vo)² Σ
E [uy
i
m
E [ui = m (B [ufwu]] + (m - 1) [1 (11220122))
m
j=1
(23)
( (1))) (m)
+ -1 (m - 1)
m
m ppp (pp+2) 2)
(p 1)p (p
m m)
m (p m)
(p-1))(p+2)
(p (p 2
70

---

Published as a conference paper at ICLR 2024
E Bu (n va)=
-Eulv (-ug vo)² =E E (u, va) (u, vo)²
E
4
:=1
kmm++1
E ww = m(p
m
E (uuunuuu
1,j=1 R 1==+11
i=1
-m(p-n)
E W iuiei + +p- 1) whee up upp 1plp +
i=1,k=p
im 1khpp1
(m 1 1) B (ieueieeue1
+pp m 1)(m 1) E) 1401 (24)
122,kpp
122m++
1 2 ) (p- + (m (m-1))
m(p-m)
+ m (0-1)(m-11))
[ 3
m (p- m)
///
+ (p 2)
(p m 1) (m 1)
0
17
(p² 4p 15) + (p - 2) (-p 3) + m 1) (m
= m (p - m)
(p ( + ()) 1==
3m3 6m22 + 3m 2 2 - 6mpp 12m + 6mpp + 12mp
(p - 1)) (
EuLv (u.QQm Qm Va)² 1 va)
En v.r-smm (1|uall TT vva EuLv ||uu I1 E (x va)"
reparameterize F + ATr
Eu Lv [ua Er-gm- (1/val TT [ea)) $7
where Av.. =
En
[ || || Ee-sm- = ) E || [vvl] (25)
3 mw0p:3/||kkoo00000---------11100
m(m+2]
3 (0+-))--))--22000-)))0--)------) 3))
71

---

Published as a conference paper at ICLR 2024
E [ Qm vo) (2)((n)))) (u]v:) =B (n, Qm va) vu.
En va) EInso- (||ua||=* r
va) [va))
= 1
Bulv (nn va) | || ||vall [2]
= Fulv (-ug (o)²||ual? |val
m
1 E || 12 |[vall (ug vo)
Bu
= m
m 1,j=1 k,8=++1
E [uiefunosueno = (p m)
E iuiee
j=1 k,E=++1
k=m+1
= (p - m)
E ui vi u
1p-m 1) ui 1 1ppp-0pp1144
(26)
j=1,b=p
j=1. 1SA5p-1
(m - 1)E
"1'2uppp
+
(p-m
(p
(m - 1) Lu
up- 1uppp
j22.==p
j22. -SkSp-1
2 (p m) ((
3 2
(p 1)
1
2
2
5
(m 1)
(
1 π
0
(p-na m 1) (m 1)
0
(p - m) 0244p++5+ 15+
p+-3)++3 3) (m 1)(9 1) p-33)
(p- (p=1)pp1+
(m + 2) (mp + 2p 3m) (p m)
(w- 1) + (p (v (p
E ||ua||
v. Qm un u Qm
u va]
=E ||ubll 1| Σ
Σ
R
m
m
2g uu 1u f
E Elaygkel
i-=
Prop
10
E
E [92)
i-=1
1
mil
||ubal
+ m (m 1)TE EE
||ubl12
un
1e 12
(27)
m
i=j
E
2
(m 1)
Σ
un
112221122
k=m
k==++
(p
m)
(m 1) (p - mm) E [
"i [2
(p m)
(m (m 1) m))
(p - m) (m
(p m) (p m + 22
69- ()-1)p(++))
(p 1) p (p + 2) (p ++44
72

---

Published as a conference paper at ICLR 2024
E
(ug Qm va) va) = FuLv |lubll*
Vo
Bqm.
(Qm Un us Qm) Va
Buiv
||ua|| v T Er
||ue|1 rr
Va
Fu
||mal|
||bbll
1
T
Va
P
E
| ||
||ual
1| l|val?]
-
E
u
2
m
m
1=++1
j=m+1 1
p
m
E
Up
2
2
m
1m
R=1
f=1
p
m
E
U
2
uk
= (p - m)
E
3 2
Σ
ot
j=m+1
A=
+
1
m Σ 1
(p- m)
E
2
+ (p
1)B B
u u
j=p
S+1SSpp11
(p- m)
E of
+ (m - 1) [ +
(28)
25p5m
(p- m
1) (E [ 1 + (m 1) u
E=1
25e5m
(p- m) E [ufuge]]
(m 1) [ufuee]] +
(p- m 1) (E 1 Fu2uz0?
+ (m - 1) (122223003)
(3 ) + (m 1)
1
8
(p- 10-m -m)
+
1000
(p-m m - 1)
+ (m - 1)
(p - m) (( (00++))++((-1((444
+ (p- m - 1)
(
(p - m)) (mp² - m2 m²p 5m 7mp + 12m 2p- 4)
(p- 1) pp (p 2) (p 4) (p + 6)
73

---

Published as a conference paper at ICLR 2024
E |uul 2 u Va vi, ub l[vell
E Ju Ugyy ug of
k=m++1 C=m++1
m
m (p- m))
[u] Ug 2 r
j=1
k=m+11
m (p- m)
E uu Walk o/p + (m - 1)
Σ
E [uu U2 ugve of)
k=m++1
A=m+1
m (p- m)
EF uuirruupe (p 10 +
(m (m-1) ( [uiu222uppp) + (p- m 1) [ [1100024,-110-111
(
1/4
3
(p- m)
/
(p m 1)
0
2
(m 11
[ 3
(p
m
0
= m (p- m²)
3 0
+ (p- - 2)
1
1
+ (m 1) (p m 1 1)
?
1181 1
)
0
0
= m (p m)
-(p+3)
+
3ip 21(++33
(m- DM
74

---

Published as a conference paper at ICLR 2024
E
a Qm V.
Qn Vo (vo iannQv
(v)uu)²)
=E
(vb ub)
B
(vo us) uuueekee
E [gg
R.j.R.E
By Prop.
10. most summands are zero]
E (vD ub)
E [
E
Ukuk
2
k=m+1
m
m (p m)
m
E (l
m
11== k,t=
111==+1
(p m)
E (ww.uuaeeeeeppp
1=+++1
p Σ
(p- m)
Σ
E [u Bufuuueeruupu (m 1)
/=m+1
8=m+1
(30)
(p m)
E [uf uf of
+ + 11p-m
+
(m- E((1u2220111 + (p-m- 1) u2 Ugy 1 Up)]
2
(p m)
+ (p - m 1)
0
1
(m - 1)
+ (p m 1)
0
(p- m)
(p 2)
(m 1) (p m 1)
(p- m)
+5
(m-
(1-1ppo-1110-
3 3p m)
(-m² +
(p- 1)) 1) ()+++)
un us (v. ua) vo vol
E
|| (v] ua) ) || 112
E
|ull (2)
(v. un
|| 2
E
[|vs]] 1| (v. un
E
1n | (v. un)
27 )²]
E
||vs 1| (v. u
+ E
2
|| 1| u Vo vi ub
(31)
solved liq. TB
solved in Eqg 2y
(p-m)nn(p-+22) mm (
(p- (p)ppt(+))) (p- po-
(p (m+3) 2m p|ap://00000000000---66000000""0
75

---

Published as a conference paper at ICLR 2024
E [ug u.u. Im VaV Qm
E In u.V, 204447554444.044
R.E=1
E Un u vo uuuyerus IE [usguu,l]
R.
Prop
10
E
||ubll
volll
1-==1
1
m.
[nb
1 |ooll u9
m (m -1) 1)B
| llvoll un 02
m
i=j
p
Σ
E [uju] udujl
+ (m 1) Σ
Σ
E saiaznirr u/ull
i=m++
f==++1
1=m+1 j=m+1
= (p - (m)
Σ
E [ufof N5 + (m - 1)
E M11ui0122 x6/
(32)
jmm++
j mm++1
= (p - m)
uf n6
21
(p m 1) E uu
u 1
j=p
m+15isp-1
(m 1)
E
U 122202111 U2 u2
+ - m - 1) E
j=p
m+1sisp-1
= -pp-m) - m)
(p
m 1)
+
(m-1) 1)
//
+ (p m 1)
(p mm)
(p m) (m² p 3m² 2mp² 10mp - 6m +2² 7p² 10p)
(p - 1) (p +
EE [u] u. Vv u Vav Qm = E [|vall up uu vs Eras (v)
1 E Vaall un th voug va
- E [Ivall |لmall (u.va)) 2
m
m
E (1-1|voll? ||mal| voT) )?]
E || (n, va) 2 + m
[|uall || 2 (u va) 27
(33)
salved in Fq.. [8]
solved in Fq.
(p-m)pp-mme
(p-m) (p+ (3)
7p01))
p-- 1))ppp-2((ptt) 2]
m) + 3) m=
(p-1)
76

---

Published as a conference paper at ICLR 2024
E.2 AUXILIARY DERIVATIONS WITH THREE VECTORS
Bulviz. Qma)) (u Qm vo)
-Eulvix
Ep-ss-
[I|ual| r 20) (1/ua|r') (|uaarrTva)
Eulvis x
|uall Er (rrrsssaamnaaaaaaaaaaaaa
1==1k(
= =Eulviz
|
+J=1 k,ē=1
[by Prop.
most terms become zero]
=
(
E
i=f=k=
E
U1
24 Uk
2 2
22
Uu
242
i
(34)
1
E
11
2?
m (m + 2)
i=1
Un
11 2/ 2/00%
+ 2 Σ
IE
||ull| 222502133
m (m + 2)
ifj=1
3m
(m 1)
27
+
2700
+ 2E
||ma|
21 21221112
m (m + 2)
m
(m + 2)
3
E
[u $ 27
E un
27
+2 E
||u,||
2 22221012 2/2
m + 2
m71 +
solved in Fq.
solved in Fq.
37
solved in Eq.
3 (0
m+2 (1-11poott1o=-210t+0(1==+ (220))))802+00-0
m-1 m² (12
m+2
(p= [---,
2(m-1)
(p-2) pp b| 1000:000000000000000000-1--11-11
(m
m+2
m (p+ ( 2) 5m + 2) 16p 24
(m+2) 1)> 11000000~~0-00000000000000000001
()=))pp++1)00 2) (D + ()
77

---

Published as a conference paper at ICLR 2024
BmivizQ (uIQm Qmza) (n) vo) BuLvie B (||ua|/r² [=))' (u, vo)
=Enlve Enivix | 11 Erngm- (z. rr. [z)) (nb Vol 2 m
1
EuLviz | 1 (ug vo)
P
E [
m
m (p- m)
E (
m
]m k=m+1
(p m)
Σ
E Iuiziuuu,unee (m 1 1)
Σ
E [ui upen
k=m+1
k=m+1 1
j22
(p- m)
E
+ (p m 1) [u] u 1 uy Up
(35)
k=p
m m+1sk5p-1
(m 1))
IE u2
(p m 1) [1] u2 Up 1pp
k=p
m+1sk5p-1
(p- m)
1 2
2
(p
1)
3
0
2
S
(m - 1)
(p m 1)
0
(p- 21-
(m 1) +6p" +3p (p- () +5p+))) 10-2
(p- m)
0-210011110001111040001111111110
mp 1aw-::hwwhhh.-pp-22--2-22//----1
0-22000-11000-0000-2200000001100 +6p-4)
(p- m)
(p m) (m + 2) m 2 6p
2) (p 1) p (p (p (p
78

---

Published as a conference paper at ICLR 2024
E |1 11 2/
= -Σ> E [
1=1 j=1
=E 11
- -2
u2
+ (m - 1) E 2222 +
ı=j=1
V
i=22
(m - 1) (m - 2) E [u
id122
= (
2 } + (m 1) (
2
(m 1) (g
0
0
(36)
(m (m-1) (m 2)
3 *)+2))++440+0 + 2(m-1)(p+3)
(0-0000 3(m -0---)----000000-00---0---------
(p-
(1) (00p:-1000002221010000000---1---
(p
E [ual 1 2/
E [
-2
[u 2 62
+2 E U
+ - 2) 07
+2 - 2) [uguuep
(1,))
V==
1=2
equal
(m
E
+ (m - (m - 3) E [
1=23
4//2
2
1 108
+2
(37)
0
(m -
4
+ (m 3)
((p=))) +
4(m 1(m-2) (o'0'"+-pp (10
(p- 1-
m² + - + 100
+6)
--
79

---

Published as a conference paper at ICLR 2024
E ||ual| 212201122
E [ U2
=2E 2121220102
+2
14 21
(1,2)
i=lj=2
2 (m 2) E [u1u5=122U10]]
+2 (m 2) E [1315112201111++ +
i
V
equal
(m 2) E [2321220102]
+ (m 2) (m 3) E [1 U2
i4123
(38)
2
0
>
+ 2
2
1111
(m 2)
4
+ (m 3)
1000
0
0
1)pp)pppt)(()+)(+++)101 (p-1))(pp+ -2(p-3)
-1(m=2)(p" +3p+6) (3m hh
(p 2) O
(0lp2)(pp 1) - 21p 3) 2- 1-2001111100-00000000011111-111- |0
(p-
16p 8p² (m 2) (mp² 7mp 14m 4p 12p 24)
(p 2) (p 1)p (p 2)
80

---

Published as a conference paper at ICLR 2024
Bulviz
||ull v.J za up 2 Vb]
E uu uuUuzzunzzeeet
k,8=++1
m
P
=m (mmpp
Σ
Σ
j=l k=m+1
m (p-m)
E uu (1 + (m - 1)
E
(uf
k=
k=m +1
J22
m (p- m)
+ (p (p-m- m- E) [ufu121 up 2p- Up E [uj 21 2p2p
m+1sk5p-1
(39)
(m
E [1fere2u + (p-m-1) E 1 12p 1pPpp
k=p
m+1gksp-1
( o
m (p- m)
(p
1)
8
1
(m 1m 1)
(p m
0
m (p- - m)
(p 3)(p (00lpp2))+4pp) 4pppp 1
(m (m-1)
(x)+22)
m (p m)
(mm + 2) p² + (2 3m) p 2m (p + 6m + 4
2) (p 1) (p+ 4) (p+0)
81

---

Published as a conference paper at ICLR 2024
E (u] 20) ( (ny v E (-u [ 20) vb) 31 =E [(u 2a)
(ug vo) (u]vv))
E (ww
m))
E 21nrzuuu22223000
+, k. R,
k=
= m (p- m)
uu u u 1 1p-m- 1) u1 Up
2 Up +
j=1, k=p
ISASP-1
(m 1) IE [n (1122 +
25j5m, kmp
(m (p (p-mm m 1) 11122lpp 1up21 22 -p 11pp
scjsm,miisspp
m (p- m)
00) 0
+ (p m 1)
+ (m (m- 1)
+
0
(40)
equal due invariance (Prop,
(m- 1) (p -m 1)
0
0
0
2
(p- mh
+ (p 2)
+ (m - 1)(p (p- -
0
m (p m)
(p+3)²
- (p (p-2) 2) +3p+6)
p 1)p(p+ (ttp:=+1((+23(ppp-))p0p)
1022]p-1>pppt313 (p
(10 1)(p
p-11p(e-111p2((p--1110
(p - 3p+ 3p
(m (p m 11
m (p- m)
(p - 1) 1) (p
m (p m)
(-m² + mp 2p 44)
(p - (p (p)
E
Euiviz ||za|l (v.Tu,, un)) IE [|u.112 (v. 20)
(v.220)² )|
ui
2
Ugz5
g=m+1
E [uf0yzz0EzR1
Σ E [ufuyzjUAEn
1= 1
J.k=++1
m
(p
m)
E
+m (p - m.) (p m
1) E [ up 12p-
(41)
j=k
j
2
m
(p m)
(p m 1)
0
(p m)
(p+3)
(p 1p-m m 1)(++2)
(p-1)p(P+2)pp
1p pp 1pppp)))pp)
4)) m)
(mp 2m - 4)
ap 2) dp 1) p (p + 2) (p 44
82

---

Published as a conference paper at ICLR 2024
E ||ub| 2 T Zu ua Zu uu ubvvv) vo] = E usu, voza uaza Vo!
( = (p m) m
E U1 uu Σ
==1 R=m+1
(p- m)
EE [uruterz [daan)] + (m - 1) EE' [nj 0221 (uxu))))
k=++1
(p m) m [E
11pp11 + (p- m 1) EE 1u +
(p m) m (m
- (B
[1 U
+ (p m - 1 1u
(42)
(p- m) (<
1
1
1
(p- - m) mn (m - 1)
0
+ (p - m -
1
(p- m) m
1=-1))g=+116+++))+++*+0-9 + (m 1)
21p
(p-
2) 10000100100000++)++++0000-0
(p m) m (p m 2) (2mp (2mp 4m p² 3p 3p+
(p 2) (p - 1)p
2) (p (p +
m
P
E
Uu 2 v Za vn Xb X, Zb
Σ
E [[
fJ== k,t=++1
m
m (p- - m)
E [11u
/=1 k=m+1
m (p- m)
E 2Mfur (m E [u/
/=1,k=p
25jsm,
m (p-pm) (p-m-1)
E -1
10p
(43)
j=l.m+ 15
ssism,misshst
m (p- m)
1
+ (m 1)
0
0
1
m (p - mm
(p m 1)
+ (m 1) (p - 1
0
0
0
m (m(m)))
+2pp - 1)(++2)
(m-
(p² (p-3)
m(p-m)
2m pp mm8 p+ 18m -6p
(p- 3]( 2) 1fp
E [ Qm _ Qm Xa 26x, vs]
Epasmm 1 ||u, 2 (z Fr vva (x.. 2b xJ vo)]
E3
um, 2 2 V. xz 2s x5. vb
m
(44)
solved Eq. 43
(p m) (-2m²p² 8m 3m3p mp² + 4mp
15mp + 18m
6p2
6p 12)
(p 3) (p 2) (p 1) p + 2) (p
83

---

Published as a conference paper at ICLR 2024
E [ng uz Vo un Qm va Qm un]
E
[ub 18Z9
k,
Un 1575 Vb U4
IE [ge)
m
Prop
Lgg Uz Vb u,0y2,05]
E [
m
(45)
/m
E'
[ug Ub Z vou Va u zu]
||
(-zz Vo) (-u, vo) u Ze
m71
17
E
| 2
Vn Za n Za un Vo
solvod in Eq. 42
(p m) (p- + 2) (2mp + 4m 1²2 3p 2)
(p - 2) (p 1) (p + 1) (1 - 2) (p + 4) (p + 6)
E
|uss
2 un Vb 2 Qm u Qm Va
p
E
2 |uall ||2 un vou Er-sm- (r (rTr) Val
E
Zza 1
Σ
ut
un vou. Vo.
f==+1
p
(p-m)
up |zzlll
Σ
4,20
Σ
\=m+1
1=1
p
(p- m) E
U1 11 m
|2all
Σ
4
4=m+1
(p m)
E
U1 2 Up ||za|| [12]
+ (p- m - 1)
U1 u1 1 ||z ||2
(p m)
E
U1 S U
+ (p- m - 13
u1 u1 11
(46)
(p m)
E
[1 1 11
(m 1) E 21)
(p m))
(p
m
1)
(E
[n t1 12 12 + (m 1) (1
/
(p m)
+ (m - 1)
0
0
2
(p m) ap
m
+ (m 1)
(p m)
3(++3)
-3(m ()
(p 2) 1p 10
(p m)
(p-2)(-3(xt3)) 3)) + m 4mm -pgea 12m-7p + +9p-2
(p m)
(p- b0-2)1111pp===)))=22+++0-00
(p-m) m 2 4.mm pm2m² - mp 7mp 12m
(p 2](p 1ppp
84

---

Published as a conference paper at ICLR 2024
E.3 AUXILIARY DERIVATIONS WITH FOUR VECTORS
E [b Vo
X
2b
up X6
vo 2n] = [ua Va Xa Za
Ub
X6
Vb Zb
m
m
B 2 m (p m
kj=1 k.f=m+1
1mm++1
(p- m)
E 11101011111ppppp3 + (m 1) E U1 12 +
jm1,kmp
25jsm, kmp
m7 (p m)
(p m 11
j= Skhp-1
(m - 1) (p - m 1 [211122222 18 1 ppppp
m
= m (p- - m) ((
1111 0
1 0
+ (m - 1)
+
(47)
i 112
(p (p-m- m 1)
0
+ (m 1) (p m 1)
1
1
(p m)
1
(p 2)
0
0
0
(m-
1) (p- m 1)
0
= m (p m)
3(-3)
+
[p- (p-1))(p+1] (p-2)
m (p - m)
m (p m) -mm +
6m
(p 2) 100-0//011pp0-000000---000000000
85

---

Published as a conference paper at ICLR 2024
1 un Xx un Vexg Vbl
Zu
m
E [ur m (p- m)
I (ewaary
k.
+1
m (p (p-m) (p-m)
[1izi of up
+ (m - 1) E 2222 o up spapp
j=1,k=p
25jSm, k=p
m (p-m) (p-m-1) 1)
E B2izi 2 12pppp11pppp + (m E u222222 up 1 1 1xpp1p
j=1, s
25/sm, m
m (p- m) ((1)
0
1
1
(48)
(m 1)
+
0
2
0
0
(p m 1)
0
0
0
+ (m 1) (p m 1)
0
0
() 2) 10000-0000-00)--0--------1111---
m (p- - m)
(m - 1|
(p-3) (---8p02||g-1pgg---00++--0111111
m (p- m) (-2m²²p² - 8m2 1mm 18m 6p - 6p - 12)
86


Reviews:
[{"review_id": "vSLgwjYBTP", "reviewer": "Reviewer_vLwn", "summary": "The authors present an analytical upper bound for the expected amount of catastrophic forgetting during linear regression with gradient descent as a function of overparameterisation and overlap between tasks. In particular, they show that there exist two phenomenologically different learning regimes: In the overparameterised regime (i.e. $rank({\\bf X}) / rank({\\bf w})$ small) intermediate similarity between tasks leads to largest amount of forgetting (inverted U-shape) and monotonic behaviour is observed near the interpolation threshold ($rank({\\bf X}) / rank({\\bf w}) \\approx 1$). To this end, the authors make the following assumptions: (1) The target values for both tasks $({\\bf y})$ are identical, (2) both tasks are realisable (i.e. a zero-loss solution exists) (3) the second task is an orthogonal projection of the first task (c.f. permutation) and (4) the first task has successfully converged to the global, minimum-norm solution of task one before training on task two. By changing the subspace which the orthogonal operator transforms, the overlap between the tasks can be exactly controlled and its effect analytically studied.\n\n\n**--------------------------------------**\n\n**Unfortunately, I can not add official comments (anymore), thus I will add my comments to the author's comments here**\n\n**Reply 1**\nWeaknesses 1&2 and Questions 1,2,3: Thank you for the clarifications. As it is not obvious from section 2.1 why equation (3) is the closest point on the solution manifold when starting to train from the convergence point of task 1, I would like to suggest to include this derivation in the appendix.\n\nWeakness 3: Thank you for the clarification.\n\nWeakness 6: As there is no direct mapping from permuting MNIST to DOTS, I have mild concerns that the observed phenomena could be explained away by the fact that most information is in the center of the image and thus increasing the permuted area from the center to the outside may result in a non-linear transformation of the dimensional of the data-manifold. If the effect is non-linear, comparisons to phenomena observed when manipulating DOTS would be erroneous. However, I appreciate that the authors try to test their hypotheses on more complex data.\n\nWeakness 4: The minimum-norm solutions studied by the authors are part of the \"rich\" learning regime. The lazy regime does exist in (multi-layer) linear networks. For example, in the regression model, weight values that lay in the null-space of the training data of the first task could be unequal zero. For example, when initialising the weight matrix from large random values, GD would still converge to a gloabl optimum, however, the convergence points would be unequal to equation (2) and (3). Thus, I would argue that the presented analytical results only apply to the rich learning regime.\n\nFurther, in an over-parametrized linear two-layer network, the first layer can be initialised, large and arbitrarily (and in theory even kept fixed). GD would still converge to a global optimum, however, as a consequence, the learned representations in the hidden layer would be \"lazy\". Again, I don't think that the analytical result apply to this regime and thus simulations that compare these two regimes (i.e. training from (very) small initial weights and training from large initial weights) would be useful. \n\nSee also question: For Figures 6 & 7, how are the neural networks initialized? Do they operate in the rich or lazy regime?\n\n\n**Reply 2**\nI would like to thank the authors for addressing my questions.\n\nWeakness 5: Thank you for adding these additional simulations.\n\nQuestion: Can you give an intuitive explanation for why the expected forgetting is non-asymptotic for overparameterized regime and near interpolation threshold\n\nSorry, that question was not very well formulated. What I tried to ask is: Do you have an intuitive explanation for why in the overparametrized regime, the expected forgetting for increasing task dissimilarity if falling off, whereas near the interpolation threshold, it keeps increasing?\n\n**The following points remain unaddressed:**\n\n- **Weakness 7: Simulation details and / or code are not provided which makes interpretation of simulation results difficult and reproduction impossible.**\n- **Weakness 10: The introduction to continual learning / catastrophic forgetting is, in my opinion, not referenced well enough**\n\n\nAs a result of the changes made by the authors I have increased my rating to a 6.\n\n**--------------------------------------**", "questions": "- To what optimisation algorithm does the analytical result exactly apply?\n- Could you please hint me at the Theorem in Gunasekar et al. (2018) from which equation (3) is derived?\n- What assumptions are made on the size of batches and the size of the learning rate?\n- Why does Theorem 3 have the assumption of p >= 5?\n- Why can you assume that a randomly sampled data matrix X is identical to the worst case in Figure 2?\n- The smallest expected forgetting in the interpolation regime (except for values close to 0 DOTS) is larger than the largest expected forgetting in the overparametereised regime. Why is that the case and how is it relevant to the analysis?\n- Is there a benefit of using an informal illustration instead of slices from figure 3 in figure 1? The inverted U-shape seems to be slightly exaggerated as expected forgetting for large DOTS don’t fall off nearly as strongly as suggested by the illustration.\n- Can you give an intuitive explanation of why the expected forgetting are (non-)asymptotic for overparameterised regime and near the interpolation threshold?\n- Do the authors think that their results do generalise to learning more than two tasks? I think that would clearly contradict some of the assumptions and thus maybe should be listed as a limitation of the work?\n- Is it maybe possible to use a log-scaled axis in Figure 3 instead of using subplots to represent the results?\n- Is it possible that the x-axis of Figure 3, bottom right is labelled incorrectly? Values from 0 to 0.1 seem to be missing\n- For figures 6. and 7., how are neural networks initialised? Do they operate in the rich or lazy regime?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors tackle an important research question: What are the underlying mechanisms that govern catastrophic forgetting during the continuos acquisition of knowledge using gradient descent. Their analytical result fully describes phenomenologically distinct operating regimes during the continuous optimisation of a linear regression model using gradient descent. The authors validate their analytical result using simulation studies and test whether their results generalise to more complicated two-layer networks. Notation is consistent throughout the paper and explanations for variables, equations and derivations are provided. The paper and plots are generally well structured and accessible.", "weaknesses": "1. The model (i.e. single linear projection) and algorithm (gradient descent, full-batch gradient descent?!) are not stated in the introduction. Information about the regime to which the analytical result applies is scattered throughout the paper, which makes it difficult to contextualise the results.\n2. It would be really helpful if all assumptions of the analytical result would be stated explicitly and collected within one section of the paper. For example, the ${\\bf 0}$ initialisation and resulting convergence to the global, minimum-norm solution of the first task is hidden in Scheme 1 but crucial to understand the extent of the analytical result.\n3. I think the paper could benefit from making it more explicit that the analysis focuses on the dimensionality and overlap with respect to the manifold of the data distribution, which is often called overparametereised, but should not be confused with the overparameterisation deep networks (i.e. wide hidden layers).\n(4. Resulting from 3., the model can not be used to make predictions about the underparameterised regime, e.g. bottlenecked networks.)\n5. I think the paper should state explicitly that the analysis is limited to the rich learning regime. It does not provide any insights into the lazy learning regime. Comparisons and references from the paper’s “overparameterised regime” to e.g. the NTK regime are confusing and incorrect.\n6. Simulation results in Figure 2. are limited to $d = 2$. There are no simulation results to validate the analytical result for edge-cases like p = d and large(r) d etc.\n7. I am not entirely sure if the author’s version of permuted MNIST is suitable to study changes in task similarity that are comparable to DOTS, as vanilla MNIST data is on a very low dimensional data manifold and large parts of the information is centred on the middle of the picture. I think I would prefer a simulation study that uses artificial data as in Figure 4., with well controlled DOTS in two layer networks.\n8. Simulation details (initialisation scheme, learning rates etc.) and / or code are not provided.\n\nMinor:\n9. The notation in equations (2) and (3) is confusing. There are too many equal signs\n10. The introduction to continual learning / catastrophic forgetting is, in my opinion, not referenced well enough\n11. Using X_1 and X interchangeably is confusing and seems unnecessary", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xWgqHVH2Up", "reviewer": "Reviewer_yV41", "summary": "This paper aims to reveal the connection between the parametrization regime and forgetting. The authors start by analyzing the forgetting in a linear regression model and define their definition of their specific distribution shift for the second task. Moreover, the upper bound of the forgetting (derived as the loss of task 1 after learning task 2), is calculated and later used for different parameterization scenarios. The authors conclude that in an overparametrized regime, forgetting decreases as the task dissimilarity increases, however, in an underparametrized scenario, the trend is reversed (more forgetting for more dissimilar tasks). Finally, they evaluated the soundness of their derivations in a custom version of the permuted-NIST tasks.", "questions": "My question goes back to the previous comments:\n\n**Q1:** Is the overparametrization proxy enough to provide a similar analysis in the CNN case? i.e., can we just substitute the $p$ with the number of parameters in a CNN layer?\n\n**Q2:** Have the authors tried to evaluate their upper bound in more challenging scenarios?\n\n**Q3:** Have the authors tried to test their upper bounds when the definition of the task similarity is different? i.e., more subtle semantic distribution shifts in the data. e.g. CIFAR-100 Superclass.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "I think the presentation in the paper is concise and to the point. The mathematical derivations in the given context are sound and clear. Maybe it would be better to show some of the derivations in eq 4 in the appendix but overall it is fine. \n\nThe results within the linear regression and simple nist-type experiments look interesting and worth pursuing in future works.", "weaknesses": "**Limited scope:** The main issue that I see in the paper is the limited scope of the provided analysis. I am fine with simple experiments in a theoretical paper but the upper bound of forgetting is very specific to the linear regression task. \n\n**Overparametrization proxy:** The second issue is tightly related to the above, in theorem 3,  the proxy for overparametrization is defined as $1 - \\frac{d}{p}$, where $d$ is the rank of the input data and $p$ is the data dimensionality. It makes sense in linear regression since the number of parameters is the same as the data dimension, i.e., $p$. This is true to some extent in the MLP layers (at least they are correlated). However, none of the derivations hold in the case of the convolutional layers where there are shared parameters and $p$ cannot be a surrogate for the number of parameters. I encourage the authors to evaluate their upper bound in CNNs. \n\n**Task similarity definition:** Also, the definition of task similarity is very limited to the rotation of a subset of the data dimensions. All of the derivations are based on this initial assumption. I believe a good theoretical paper on this subject should expand this definition so that more real-world cases can be included in the analysis. My comment is the same for the permuted-NIST scenario. A simple permutation of a subset of pixels is not enough to back the main message in this more challenging scenario.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FXjfnXUu6f", "reviewer": "Reviewer_TGNt", "summary": "This paper provides a mathematical analysis of how task similarity and overparameterization jointly affect forgetting in continual learning. By proposing a pair of orthogonally transformed datasets, authors define their similarity measurement DOTS $\\alpha$ and the level of overparameterization $\\beta$. Theorem 3 provides the worst-case expected forgetting w.r.t $\\alpha$ and $\\beta$. Furthermore, synthetic and empirical experiments provide more support for the proposed analysis.", "questions": "1. Is the theory able to provide worst-case forgetting analysis with more general dataset assumption, or T>2 datasets?\n2. It is still unclear that how DOTS relates to other notions of similarity, e.g. the principle angles in Evron et al. (2022). Is that possible to plot a figure that shows the relation between DOTS and $\\theta$?\n3. In Evron et al.(2022), Figure 3 shows the worst-case forgetting on T=2 tasks, where p=d-1(rank(X1)=rank(X2)=d-1), which in this paper, should corresponds to $\\beta=1-\\frac{d-1}{d}\\approx 0$, which should fall into the very less overparameterization regime. However, there results still show the descent with a large angle. Can authors provide some explanation? (And this is also one of the reasons I hope to know how DOTS relates to $\\theta$)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Writing is clear and easy to follow.\n2. Their novel result provides a new perspective for forgetting analysis in continual learning.\n3. The theoretical result is solid and consistent with empirical results.", "weaknesses": "1. The dataset assumption is strong, which only focuses on 2 datasets, and can be converted by orthogonal transformation. \n2. It is unclear how DOTS can compare with the notion of similarity in related works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "whswrCxR5N", "reviewer": "Reviewer_ckB1", "summary": "The paper considers the continual learning problem in the case of two linear regression tasks. The first task is arbitrary, while the second is assumed to be a random orthogonal transformation of the first one.\n\nThe main result of the paper is a precise expression of the normalized, expected forgetting (Theorem 3). The expression is related to the level of task similarity and overparameterization.\n\nThe paper proceeds to specialize the main theorem to the highly overparameterized regime and at the interpolation threshold, visualizing the amount of forgetting on synthetic data or the MNIST dataset.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper has several strengths:\n- First, while the proof idea is straightforward (e.g., as shown in the proof sketch), it involves lengthy algebraic manipulations that the paper manages to excel in; this is commendable.\n- Related to the first strength, even though the proof can be lengthy, the main paper is clearly written and easy to understand.\n- The experiments numerically verify the correctness of the theorem and provide interesting insights into catastrophic forgetting. While some of the observations have been made in prior works, the paper suitably discussed that, and moreover provided different results in the highly overparameterized regime.", "weaknesses": "While I tend to vote for acceptance, I do have several questions or comments:\n\n- At first glance it seems a little bit weird to have the same $y$ for two different tasks. I think it might be motivated by the case of permuted MNIST where permutations do not change the label. It would be great if the authors could comment on that in their revision.\n- Certainly there is some gap between the theory and MNIST experiments. The authors are encouraged to discuss that gap. For example, the training loss in the theory vs test error in the experiments. The least-squares loss in the theory vs classification loss in the experiments (I suppose).\n- Is there any deeper connection between the bound in the highly overparameterized regime, $\\alpha^2(1-\\alpha)^2$, and the corresponding bound in Lemma 9 of Evron et al. (2022) for the case $k=2$?\n- While the main theorem is accomplished by algebraic calculations, I wonder whether there is a geometric proof that would achieve the same. For example, the two steps can be thought of as two projections (onto certain subspaces), and the forgetting can be bounded deterministically by some quantity related to the principal angles. With a random orthogonal transformation, the principal angles between the two subspaces would be in some sense random. Would it be easier if one analyzes the randomness of the principal angles, and could the algebraic proofs be replaced by geometric reasoning?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sDs474knH3", "reviewer": "Reviewer_6udf", "summary": "In order to explore the common impact of task similarity and overparameterization on forgotten, the paper obtains a conclusion through formula derivation. The conclusion shows a non-monotonic behavior in task similarity when the model is suitably overparameterized, and a monotonic behavior when it is critically overparameterized. In addition, the paper verified the conclusion through a large number of experiments.", "questions": "1.\tIs the conclusion proved to be universal? If in a non-linear complex neural network, is the model forgetting the same as the conclusion?\n2.\tWe can only mess up pixels as a standard of dissimilarity, which does not match the real scene. So it's hard to verify the conclusions on other data.\n3.\tIs overparameterization equivalent to the learning capacity of the model? Do the conclusions of the paper apply to other data and models?\n4.\tThe formulas derived in this paper are rather complicated. Can you please explain Pseudoinverse Properties and Operator Norm Properties in detail?\n5.\tThis paper only conducted experiments on the mnist dataset. Can the same conclusion be reached for other complex datasets?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper obtained a precise and effective conclusion through a large number of formula derivations and experiments. This conclusion can help us better understand the forgetting problems of the model.", "weaknesses": "The experimental setting of the paper is very limited, and the scope of application of the conclusions is questionable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2Dwbu9l2VN", "reviewer": "Reviewer_SXpA", "summary": "The paper studies catastrophic forgetting in an analytical way. \nSpecifically, they focus on two-task continual linear regression and uncover a pattern in overparameterized models \nwhere intermediate task similarity leads to the most forgetting.", "questions": "1. I have tried to read all proof, but it is difficult to follow and check all the long expressions. \nI think it will be better to make the proof clearer to understand.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The results under overparameterized models are interesting.", "weaknesses": "1. The writing needs improvement as it is difficult to grasp the central logical structure.\n2. Format in assumption 1 seems not correct since there is a long blank.\n3. The proof is difficult to follow, I can tell why the three terms in Lemma 6 can be replaced by the long formulas.\n4. I think the paper 'Analysis of catastrophic forgetting for random orthogonal transformation tasks in the overparameterized regime' discusses a similar task. It is difficult to tell what the difference and improvement compared to that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)