Theory on Mixture-of-Experts in Continual Learning

## Abstract

Abstract Continual learning (CL) has garnered significant attention because of its ability to adapt to new tasks that arrive over time. Catastrophic forgetting (of old tasks) has been identified as a major issue in CL, as the model adapts to new tasks.
The Mixture-of-Experts (MoE) model has recently been shown to effectively mitigate catastrophic forgetting in CL, by employing a gating network to sparsify and distribute diverse tasks among multiple experts.
However, there is a lack of theoretical analysis of MoE and its impact on the learning performance in CL.
This paper provides the first theoretical results to characterize the impact of MoE in CL via the lens of overparameterized linear regression tasks.
We establish the benefit of MoE over a single expert by proving that the MoE model can diversify its experts to specialize in different tasks, while its router learns to select the right expert for each task and balance the loads across all experts. Our study further suggests an intriguing fact that the MoE in CL needs to terminate the update of the gating network after sufficient training rounds to attain system convergence, which is not needed in the existing MoE studies that do not consider the continual task arrival.
Furthermore, we provide explicit expressions for the expected forgetting and overall generalization error to characterize the benefit of MoE in the learning performance in CL. Interestingly, adding more experts requires additional rounds before convergence, which may not enhance the learning performance. Finally, we conduct experiments on both synthetic and real datasets to extend these insights from linear models to deep neural networks (DNNs), which also shed light on the practical algorithm design for MoE in CL.

## 1 Introduction

Continual Learning (CL) has emerged as an important paradigm in machine learning [, ], in which an expert aims to learn a sequence of tasks one by one over time.
The expert is anticipated to leverage the knowledge gained from old tasks to facilitate learning new tasks, while simultaneously enhancing the performance of old tasks via the knowledge obtained from new ones.
Given the dynamic nature of CL, one major challenge herein is known as *catastrophic forgetting* [, ], where the expert can perform poorly on (i.e.,
easily forget) the previous tasks when learning new tasks if data distributions change largely across tasks. This becomes a more serious issue if a single expert continues to serve an increasing number of tasks.

Recently, the sparsely-gated Mixture-of-Experts (MoE) model has achieved astonishing successes in deep learning, especially in the development of large language models (LLMs) (e.g., [, , , ]). By adaptively routing different input data to one of the multiple experts through a gating network [, ],
different experts in the MoE model will be specialized to grasp different knowledge in the data. Thus inspired, there have emerged several attempts to leverage MoE in mitigating the forgetting issue in CL (e.g., [, , , , ]) by training each expert to handle a particular set of tasks. However, these studies have primarily focused on experimental investigations, whereas the theoretical understanding of MoE and its impact on the learning performance in CL is still lacking. In this paper, we aim to fill this gap by providing the first explicit theoretical results to comprehensively understand MoE in CL.

To this end, we study
the sparsely-gated MoE model with $M$ experts in CL through the lens of overparameterized linear regression tasks [, , ]. In our setting of CL, one learning task arrives in each round and its
dataset is generated with the ground truth randomly drawn from a shared pool encompassing $N$ unknown linear models.
Subsequently, the data is fed into a parameterized gating network, guided by which a softmax-based router will route the task to one of the $M$ experts for model training.
The trained MoE model then further updates the gating network by gradient descent (GD). After that, a new task arrives and the above process repeats until the end of CL.
It is worth noting that analyzing linear models is an important first step towards understanding the performance of deep neural networks (DNNs), as shown in many recent studies (e.g., [, , ]).

Our main contributions are summarized as follows.

We provide *the first theoretical analysis to understand the behavior of MoE in CL*, through the lens of overparameterized linear regression tasks. By updating the gating network with a carefully designed loss function, we show that after sufficient training rounds (on the order of $\mathcal{O}(M)$) in CL for expert exploration and router learning, the MoE model will diversify and move into a balanced system state: Each expert will specialize either in a specific task (if $M>N$) or in a cluster of similar tasks (if $M<N$), and the router will consistently select the right expert for each task. Another interesting finding is that, unlike existing studies in MoE (e.g., [, , ]), it is necessary to terminate the update of the gating network for MoE due to the dynamics of task arrival in CL. This will ensure that the learning system eventually converges to a stable state with balanced loads among all experts.

We provide *explicit expressions of the expected forgetting and generalization error to characterize the benefit of MoE on the performance of CL*.
1) Compared to the single expert case ($M=1$), where tasks are learned by a single diverged model, the MoE model with diversified experts significantly enhances the learning performance, especially with large changes in data distributions across tasks. 2) Regardless of whether there are more experts ($M>N$) or fewer experts ($M<N$), both forgetting and generalization error converge to a small constant. This occurs because the router consistently selects the right expert for each task after the MoE model converges, efficiently minimizing model errors in the long term.
3) In MoE, adding more experts requires additional rounds for exploration before convergence, which does not necessarily enhance the learning performance.

Finally, we conduct extensive experiments to verify our theoretical results. Specifically, our experimental results on synthetic data with linear models not only support our above-mentioned theoretical findings, but also show that load balancing reduces the average generalization error. This effectively improves the capacity of the MoE model compared to the unbalanced case. More importantly, the experiments on real datasets suggest that our theoretical findings can be further carried over beyond linear models to DNNs, which also provides insights on practical algorithm design for MoE in CL.

## 2 Related work

Continual learning. In the past decade, various empirical approaches have been proposed to tackle catastrophic forgetting in CL, which generally fall into three categories: 1) Regularization-based approaches (e.g., [, , , ]), which introduce explicit regularization terms on key model parameters trained by previous tasks to balance old and new tasks. 2) Parameter-isolation-based approaches (e.g., [, , , ]), which isolate parameters associated with different tasks to prevent interference between parameters. 3) Memory-based approaches (e.g., [, , , , , ]), which store data or gradient information from old tasks and replay them during training of new tasks.

On the other hand, theoretical studies on CL are very limited. Among them, [] and [] introduce NTK overlap matrix to measure the task similarity and propose variants of the orthogonal gradient descent approach to address catastrophic forgetting.
[] considers a teacher-student framework to examine the impact of task similarity on learning performance. [] proposes an ideal CL framework that can achieve no forgetting by assuming i.i.d. data distributions for all tasks. [] provides forgetting bounds in overparameterized linear models on different task orders. Further, [] provides explicit forms of forgetting and overall generalization error based on the testing error. These works collectively suggest that learning performance with a single expert tends to deteriorate when subsequent tasks exhibit significant diversification. In contrast, our work is the first to conduct theoretical analysis to understand the benefit of multiple experts on CL.

Mixture-of-Experts model. The MoE model has been extensively studied over the years for enhancing model capacity in deep learning (e.g., [, , , , ]). Recently, it has found widespread applications in emerging fields such as LLMs (e.g., [, , , ]). To improve training stability and simplify the MoE structure, [] proposes to sparsify the output of the gating network.
Subsequently, [] suggests routing each data sample to a single expert instead of multiple experts, which reduces computational costs while maintaining model quality.
[] theoretically analyzes the mechanism of MoE in deep learning under the setup of a mixture of classification problem. Note that this study focuses on a single-task setting, and hence does not analyze the dynamics involved in training a sequence of tasks in CL. In contrast, our work delves into MoE in CL, resulting in distinct training phases of the gating network compared to []. Furthermore, we provide explicit expressions for both forgetting and overall generalization error.

MoE in CL. Recently, the MoE model has been applied to reducing catastrophic forgetting in CL ([, , , , ]). For example, [] integrates the cooperation of multiple experts to make predictions based on a weighted sum of feature representations. [] proposes to diverse experts by routing data with minimal distribution overlap to each expert and then combine experts’ knowledge during task predictions to enhance learning stability. Additionally, [] applies MoE to expand the capacity of vision-language models, alleviating long-term forgetting in CL. However, these works solely focus on empirical methods, lacking theoretical analysis of how the MoE performs in CL.

## 3 Problem setting and MoE model design

Notations. For a vector $\bm{w}$, let $\|\bm{w}\|_{2}$ and $\|\bm{w}\|_{\infty}$ denote its $\ell$-$2$ and $\ell$-${\infty}$ norms, respectively. For some positive constant $c_{1}$ and $c_{2}$, we define $x=\Omega(y)$ if $x>c_{2}|y|$, $x=\Theta(y)$ if $c_{1}|y|<x<c_{2}|y|$, and $x=\mathcal{O}(y)$ if $x<c_{1}|y|$. We also denote by $x=o(y)$ if $x/y\rightarrow 0$.

### 3.1 CL in linear models

General setting. We consider the CL setting with $T$ training rounds. In each round $t\in[T]$, one out of $N$ tasks randomly arrives to be learned by the MoE model with $M$ experts. For each task, we consider fitting a linear model $f(\mathbf{X})=\mathbf{X}^{\top}\bm{w}$ [, ] with ground truth $\bm{w}\in\mathbb{R}^{d}$. Then, for the task arrival in the $t$-th training round, it corresponds to a linear regression problem, where the training dataset is denoted by $\mathcal{D}_{t}=(\mathbf{X}_{t},\mathbf{y}_{t})$. Here $\mathbf{X}_{t}\in\mathbb{R}^{d\times s_{t}}$ is the feature matrix with $s_{t}$ samples of $d$-dimensional vectors, and $\mathbf{y}_{t}\in\mathbb{R}^{s_{t}}$ is the output vector. In this study, we focus on the overparameterized regime, where $s_{t}<d$. Consequently, there exist numerous linear models that can perfectly fit the data.

Ground truth and dataset. Let $\mathcal{W}=\{\bm{w}_{1},\cdots,\bm{w}_{N}\}$ represent the collection of ground truth vectors of all $N$ tasks. For any two tasks $n,n^{\prime}\in[N]$, we assume $\|\bm{w}_{n}-\bm{w}_{n^{\prime}}\|_{\infty}=\mathcal{O}(\sigma_{0})$, where $\sigma_{0}>0$ denotes the variance. Moreover, we assume that task $n$ possesses a unique feature signal $\bm{v}_{n}\in\mathbb{R}^{d}$ with $\|\bm{v}_{n}\|_{\infty}=\mathcal{O}(1)$ (cf. []).

In each training round $t\in[T]$, let $n_{t}\in[N]$ denote the index of the current task arrival with ground truth $\bm{w}_{n_{t}}\in\mathcal{W}$. In the following, we formally define the generation of dataset per training round.

###### Definition 1 .

At the beginning of each training round $t\in[T]$, the dataset $\mathcal{D}_{t}=(\mathbf{X}_{t},\mathbf{y}_{t})$ of the new task arrival $n_{t}$ is generated by the following steps:

1) Uniformly draw a ground truth $\bm{w}_{n}$ from ground-truth pool $\mathcal{W}$ and let $\bm{w}_{n_{t}}=\bm{w}_{n}$.

2) Independently generate a random variable $\beta_{t}\in(0,C]$, where $C$ is a constant satisfying $C=\mathcal{O}(1)$.

3) Generate $\mathbf{X}_{t}$ as a collection of $s_{t}$ samples, where one sample is given by $\beta_{t}\bm{v}_{n_{t}}$ and the rest of the $s_{t}-1$ samples are drawn from normal distribution $\mathcal{N}(\bm{0},\sigma_{t}^{2}\bm{I}_{d})$, where $\sigma_{t}\geq 0$ is the noise level.

4) Generate the output to be $\mathbf{y}_{t}=\mathbf{X}_{t}^{\top}\bm{w}_{n_{t}}$.

In any training round $t\in[T]$, the actual ground truth $\bm{w}_{n_{t}}$ of task arrival $n_{t}$ is unknown. However, according to Definition 1, task $n_{t}$ can be classified into one of $N$ clusters based on its feature signal $\bm{v}_{n_{t}}$. Although the position of $\bm{v}_{n_{t}}$ in feature matrix $\mathbf{X}_{t}$ is not specified for each task $n_{t}$, we can address this binary classification sub-problem over $\mathbf{X}_{t}$ using a single gating network in MoE [, , ].
In this context, we aim to investigate whether the MoE model can enhance the learning performance in CL. For ease of exposition, we assume $s_{t}=s$ for all $t\in[T]$ in this paper. Then we will introduce the MoE model in the following subsections.

###### Definition 1 .

### 3.2 Structure of the MoE model

Figure: Figure 1: An illustration of the MoE model.
Refer to caption: x1.png

As shown in Figure 1, an MoE model comprises a collection of $M$ experts, a router, and a gating network which is typically set to be linear ([, , ]).
In the $t$-th round, upon the arrival of task $n_{t}$ and input of its data $\mathcal{D}_{t}=(\mathbf{X}_{t},\mathbf{y}_{t})$, the gating network computes its linear output $h_{m}(\mathbf{X}_{t},\bm{\theta}^{(m)}_{t})$ for each expert $m\in[M]$, where $\bm{\theta}^{(m)}_{t}\in\mathbb{R}^{d}$ is gating network parameter for expert $m$.
Define $\mathbf{h}(\mathbf{X}_{t},\mathbf{\Theta}_{t}):=[h_{1}(\mathbf{X}_{t},\bm{
\theta}_{t}^{(1)})\ \cdots\ h_{M}(\mathbf{X}_{t},\bm{\theta}_{t}^{(M)})]$ and $\mathbf{\Theta}_{t}:=[\bm{\theta}_{t}^{(1)}\ \cdots\ \bm{\theta}_{t}^{(M)}]$ as the outputs and the parameters of the gating network for all experts, respectively. Then we obtain
$\mathbf{h}(\mathbf{X}_{t},\mathbf{\Theta}_{t})=\sum_{i\in[s_{t}]}\mathbf{
\Theta}_{t}^{\top}\mathbf{X}_{t,i}$,
where $\mathbf{X}_{t,i}$ is the $i$-th sample of the feature matrix $\mathbf{X}_{t}$.

To sparsify the gating network and reduce the computation cost, we employ top-$1$ “switch routing", which maintains model quality while lowering routing computation, as demonstrated by [, , ]. Although this top-$1$ gating model is simple, it is fundamental gaining a theoretical understanding of the behavior of MoE in CL, and its theoretical analysis is already non-trivial.
Extending to the top-$k$ routing strategy (as introduced by []) is nontrivial and falls outside the scope of this work.
However, we still provide a discussion on the learning performance of the top-$k$ routing strategy later in Section 5.2.

In each round $t$, as depicted in Figure 1, for task $n_{t}$, the router selects the expert with the maximum gate output $h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})$, denoted as $m_{t}$, from the $M$ experts.
In practice, to encourage exploration across experts and stabilize MoE training, we add perturbations to the router ([, , ]). Specifically, task $n_{t}$ will be routed to the expert that satisfies

$$ $\displaystyle\textstyle m_{t}=\arg\max_{m}\{h_{m}(\mathbf{X}_{t},\bm{\theta}_{ t}^{(m)})+r_{t}^{(m)}\},$ (1) $$

where $r_{t}^{(m)}$ for any $m\in[M]$ is drawn independently from the uniform distribution $\text{Unif}[0,\lambda]$. We analyze in Appendix B that routing strategy Eq. 1 ensures continuous and stable transitions for tasks.
Additionally, the router calculates the softmaxed gate outputs, derived by

$$ $\displaystyle\textstyle\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})=\frac{\text {exp}(h_{m}(\mathbf{X}_{t},\bm{\theta}^{(m)}_{t}))}{\sum_{m^{\prime}=1}^{M} \text{exp}(h_{m^{\prime}}(\mathbf{X}_{t},\bm{\theta}^{(m)}_{t}))},\quad\forall m \in[M],$ (2) $$

for the MoE to update the gating network parameter $\mathbf{\Theta}_{t+1}$ for all experts.

### 3.3 Training of the MoE model with key designs

Expert model. Let $\bm{w}_{t}^{(m)}$ denote the model of expert $m$ in the $t$-th training round, where each model is initialized from zero, i.e., $\bm{w}_{0}^{(m)}=0$ for any $m\in[M]$.
After the router determines the expert $m_{t}$ by Eq. 1, it transfers the dataset $\mathcal{D}_{t}=(\mathbf{X}_{t},y_{t})$ to this expert for updating $\bm{w}^{(m_{t})}_{t}$. For any other expert $m\in[M]$ not selected ( i.e., $m\neq m_{t}$), its model $\bm{w}_{t}^{(m)}$ remains unchanged from $\bm{w}_{t-1}^{(m)}$.
In each round $t$, the training loss is defined by the mean-squared error (MSE) relative to dataset $\mathcal{D}_{t}$:

$$ $\displaystyle\textstyle\mathcal{L}_{t}^{tr}(\bm{w}_{t}^{(m_{t})},\mathcal{D}_{ t})=\frac{1}{s_{t}}\|(\mathbf{X}_{t})^{\top}\bm{w}_{t}^{(m_{t})}-\mathbf{y}_{t }\|_{2}^{2}.$ (3) $$

Since we focus on the overparameterized regime, there exist infinitely many solutions that perfectly satisfy $\mathcal{L}_{t}^{tr}(\bm{w}_{t}^{(m_{t})},\mathcal{D}_{t})=0$ in Eq. 3.
Among these solutions, gradient descent (GD) starting from the previous expert model $\bm{w}_{t-1}^{(m_{t})}$ at the convergent point provides a unique solution for minimizing $\mathcal{L}_{t}^{tr}(\bm{w}_{t}^{(m_{t})},\mathcal{D}_{t})$ in Eq. 3, which is determined by the following optimization problem [, , ]:

$$ $\displaystyle\min_{\bm{w}_{t}}\ \ \|\bm{w}_{t}-\bm{w}_{t-1}^{(m_{t})}\|_{2}, \quad\text{s.t.}\ \ \mathbf{X}_{t}^{\top}\bm{w}_{t}=\mathbf{y}_{t}.$ (4) $$

Solving Eq. 4, we update the selected expert in the MoE model for the current task arrival $n_{t}$ as follows, while keeping the other experts unchanged:

$$ $\displaystyle\bm{w}_{t}^{(m_{t})}=\bm{w}_{t-1}^{(m_{t})}+\mathbf{X}_{t}( \mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1}(\mathbf{y}_{t}-\mathbf{X}_{t}^{\top} \bm{w}_{t-1}^{(m_{t})}).$ (5) $$

Gating network parameters.
After obtaining $\bm{w}_{t}^{(m_{t})}$ in Eq. 5, the MoE updates the gating network parameter from $\bm{\Theta}_{t}$ to $\bm{\Theta}_{t+1}$ using GD for the next training round. On one hand, we aim for $\bm{\theta}_{t+1}^{(m)}$ of each expert $m$ to specialize in a specific task, which helps mitigate learning loss caused by the incorrect routing of distinct tasks. On the other hand, the router needs to balance the load among all experts [, , ] to reduce the risk of model overfitting and enhance the learning performance in CL. To achieve this, we introduce the following key designs for gating network updates.

Key design I: Multi-objective training loss. First, based on the updated expert model $\bm{w}_{t}^{(m)}$ in Eq. 5, we propose the following locality loss function for updating $\mathbf{\Theta}_{t}$:

$$ $\displaystyle\textstyle\mathcal{L}_{t}^{loc}(\bm{\Theta}_{t},\mathcal{D}_{t})= \sum_{m\in[M]}\pi_{m}(\mathbf{X}_{t},\bm{\Theta}_{t})\|\bm{w}_{t}^{(m)}-\bm{w} _{t-1}^{(m)}\|_{2},$ (6) $$

where $\pi_{m}(\mathbf{X}_{t},\bm{\Theta}_{t})$ is the softmax output defined in Eq. 2. Since our designed locality loss in Eq. 6 is minimized when the tasks with similar ground truths are routed to the same expert $m$ (e.g., $\bm{w}_{t}^{(m)}=\bm{w}_{t-1}^{(m)}$), it enjoys several benefits as shown later in our theoretical results: each expert will specialize in a particular set of tasks which leads to fast convergence of expert model $\bm{w}^{(m)}_{t}$, and the performance of CL in terms of forgetting and generalization error will be improved.
Note that in Eq. 6, we only need to calculate the locality loss for the single expert $m_{t}$, as $\|\bm{w}_{t}^{(m)}-\bm{w}_{t-1}^{(m)}\|_{2}=0$ for any expert $m\neq m_{t}$ that has not updated its model, leading to low computational complexity.

In addition to the novel locality loss in Eq. 6, we follow the existing MoE literature (e.g., [, , ]) where an auxiliary loss is typically defined to characterize load balance among the experts:

$$ $\displaystyle\textstyle\mathcal{L}_{t}^{aux}(\mathbf{\Theta}_{t},\mathcal{D}_{ t})=\alpha\cdot M\cdot\sum_{m\in[M]}f_{t}^{(m)}\cdot P_{t}^{(m)},$ (7) $$

where $\alpha$ is constant, $f_{t}^{(m)}=\frac{1}{t}\sum_{\tau=1}^{t}\mathds{1}\{m_{\tau}=m\}$ is the fraction of tasks dispatched to expert $m$ since $t=1$, and $P_{t}^{(m)}=\frac{1}{t}\sum_{\tau=1}^{t}\pi_{m}(\mathbf{X}_{\tau},\mathbf{
\Theta}_{\tau})\cdot\mathds{1}\{m_{\tau}=m\}$ is the average probability that the router chooses expert $m$ since $t=1$. The auxiliary loss in Eq. 7 encourages exploration across all experts since it is minimized under a uniform routing with $f_{t}^{(m)}=\frac{1}{M}$ and $P_{t}^{(m)}=\frac{1}{M}$.
Although the definition of auxiliary loss in Eq. 7 is not new, it is necessary and plays a crucial role for balancing the load across experts in the MoE model for CL.

Based on Eq. 3, Eq. 6 and Eq. 7, we finally define the task loss for each task arrival $n_{t}$ as follows:

$$ $\displaystyle\mathcal{L}_{t}^{task}(\mathbf{\Theta}_{t},\bm{w}_{t}^{(m_{t})}, \mathcal{D}_{t})=\mathcal{L}_{t}^{tr}(\bm{w}_{t}^{(m_{t})},\mathcal{D}_{t})+ \mathcal{L}_{t}^{loc}(\mathbf{\Theta}_{t},\mathcal{D}_{t})+\mathcal{L}_{t}^{ aux}(\mathbf{\Theta}_{t},\mathcal{D}_{t}).$ (8) $$

Commencing from the initialization $\mathbf{\Theta}_{0}$, the gating network is updated based on GD:

$$ $\displaystyle\textstyle\bm{\theta}_{t+1}^{(m)}=\bm{\theta}_{t}^{(m)}-\eta\cdot \nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}(\mathbf{\Theta}_{t},\bm{w }_{t}^{(m_{t})},\mathcal{D}_{t}),\forall m\in[M],$ (9) $$

Figure: Algorithm 1 Training of the MoE model for CL

where $\eta>0$ is the learning rate. Note that $\bm{w}_{t}^{(m_{t})}$ in Eq. 5 is also the optimal solution for minimizing $\mathcal{L}_{t}^{task}(\mathbf{\Theta}_{t},\bm{w}_{t}^{(m_{t})},\mathcal{D}_{t})$ in Eq. 8. This is because both $\mathcal{L}_{t}^{loc}(\mathbf{\Theta}_{t},\mathcal{D}_{t})$ and $\mathcal{L}_{t}^{aux}(\mathbf{\Theta}_{t},\mathcal{D}_{t})$ are derived after updating $\bm{w}_{t}^{(m_{t})}$, making $\mathcal{L}_{t}^{tr}(\bm{w}_{t}^{(m_{t})},\mathcal{D}_{t})$ the sole objective for $\bm{w}_{t}^{(m_{t})}$ in Eq. 8.

Key design II: Early termination. To ensure the stable convergence of the system with balanced loads among experts (which we will theoretically justify in Section 4), after training sufficient (i.e., $T_{1}$) rounds for expert exploration, we introduce an early termination strategy in Algorithm 1 by evaluating a convergence flag $I^{(m)}$ for each expert $m$. This flag assesses the output gap, defined as $|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t})-h_{m_{t}}(\mathbf{X}_{t},\bm{\theta}_{t
})|$, between the expert itself and any selected expert $m_{t}$ for $t>T_{1}$. If this gap exceeds threshold $\Gamma$ for expert $m$, which indicates that gating network parameter $\bm{\theta}_{t}^{(m)}$ has not converged, then the MoE model continues updating $\bm{\Theta}_{t}$ for all experts based on Eq. 9. Otherwise, the update of $\bm{\Theta}_{t}$ is permanently terminated.

## 4 Theoretical results on MoE training for CL

In this section, we provide theoretical analysis for the training of expert models and the gating network in Algorithm 1, which further justifies our key designs in Section 3. Specifically, (i) we first support our key design I by proving that the expert model converges fast via updating $\bm{\Theta}_{t}$ under our designed locality loss in Eq. 6.
(ii) We then show that our key design II, early termination in updating $\bm{\Theta}_{t}$ for MoE in CL, is necessary to ensure a stable convergence system state with balanced loads among all experts.
For clarity, we study the case with $M>N$ in this section (where the results are labeled as $M>N$ version), and
further extend the results to the case with $M<N$ in appendices.

To characterize the expert specialization, we first show that the gate output of each expert is determined by the input feature signal $\bm{v}_{n}$ of $\mathbf{X}_{t}$.

###### Lemma 1 ( $M>N$ version) .

For any two feature matrices $\mathbf{X}$ and $\tilde{\mathbf{X}}$ with the same feature signal $\bm{v}_{n}$, with probability at least $1-o(1)$, their corresponding gate outputs of the same expert $m$ satisfy

$$ $\displaystyle\textstyle\big{|}h_{m}(\mathbf{X},\bm{\theta}_{t}^{(m)})-h_{m}( \tilde{\mathbf{X}},\bm{\theta}_{t}^{(m)})\big{|}=\mathcal{O}(\sigma_{0}^{1.5}).$ (10) $$

The full version and the proof of Lemma 1 are given in Appendix C. According to Lemma 1, the router decides expert $m_{t}$ for task $n_{t}$ based primarily on its feature signal $\bm{v}_{n_{t}}$. Consequently, given $N$ tasks, all experts can be grouped into $N$ sets according to their specialty, i.e., their gating parameter $\bm{\theta}^{(m)}_{t}$’s to identify feature signal $\bm{v}_{n}$, where each expert set is defined as:

$$ $\displaystyle\textstyle\mathcal{M}_{n}=\big{\{}m\in[M]\big{|}n=\arg\max_{j\in[ N]}(\bm{\theta}^{(m)}_{t})^{\top}\bm{v}_{j}\big{\}}.$ (11) $$

The following proposition indicates the convergence of the expert model after sufficient training rounds under Algorithm 1.

###### Proposition 1 ( $M>N$ version) .

Under Algorithm 1, with probability at least $1-o(1)$, for any $t>T_{1}$, where $T_{1}=\lceil\eta^{-1}M\rceil$, each expert $m\in[M]$ stabilizes within an expert set $\mathcal{M}_{n}$, and its expert model remains unchanged beyond time $T_{1}$, satisfying $\bm{w}^{(m)}_{T_{1}+1}=\cdots=\bm{w}^{(m)}_{T}$.

The full version and the proof of Proposition 1 are given in Appendix E. Proposition 1 demonstrates that after $T_{1}$ rounds of expert exploration, each expert will specialize in a specific task, enforced by minimizing locality loss in Eq. 6. After that, expert models remain unchanged until the end of $T$.

Next, the following proposition characterizes the dynamics of gate outputs if there is no termination of updating gating network parameters $\mathbf{\Theta}_{t}$ in Algorithm 1.

###### Proposition 2 ( $M>N$ version) .

If the MoE keeps updating $\bm{\Theta}_{t}$ by Eq. 9 at any round $t\in[T]$, we obtain:
1) At round $t_{1}=\lceil\eta^{-1}\sigma_{0}^{-0.25}M\rceil$, the following property holds

$$ $\displaystyle\big{|}h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}^{(m)}_{t_{1}})-h_{m^{ \prime}}(\mathbf{X}_{t_{1}},\bm{\theta}^{(m^{\prime})}_{t_{1}})\big{|}=\begin{ cases}\mathcal{O}(\sigma_{0}^{1.75}),&\text{if }m,m^{\prime}\in\mathcal{M}_{n} ,\\ \Theta(\sigma_{0}^{0.75}),&\text{otherwise}.\end{cases}$ (12) $$

2) At round $t_{2}=\lceil\eta^{-1}\sigma_{0}^{-0.75}M\rceil$, the following property holds

$$ $\displaystyle\big{|}h_{m}(\mathbf{X}_{t_{2}},\bm{\theta}^{(m)}_{t_{2}})-h_{m^{ \prime}}(\mathbf{X}_{t_{2}},\bm{\theta}^{(m^{\prime})}_{t_{2}})\big{|}= \mathcal{O}(\sigma_{0}^{1.75}),\forall m,m^{\prime}\in[M].$ (13) $$

The full version and the proof of Proposition 2 are given in Appendix F. According to Proposition 2, if the MoE keeps updating $\bm{\Theta}_{t}$ at any round $t$, the gap between gate outputs of any two experts within the same expert set converges to $\mathcal{O}(\sigma_{0}^{1.75})$ at round $t_{1}$ in Eq. 12.
In contrast, for any two experts in different expert sets, their output gap is sufficiently large, i.e., $\Theta(\sigma_{0}^{0.75})$, indicating that the MoE has successfully diversified experts into different sets at round $t_{1}$ as in Eq. 11.
However, unlike MoE in single-task learning that can stop training at any time after the expert models converge (e.g., [, ]),
MoE in CL requires both the gating network and the experts to be suitably updated with the continuous arrival of new tasks. This is necessary to balance the load on each expert and maximize the system capacity utilization.
However, continuing updating $\bm{\Theta}_{t}$ according to Eq. 9 will eventually reduce the output gap between any two experts to $\mathcal{O}(\sigma_{0}^{1.75})$ in Eq. 13 at training round $t_{2}$,
causing the router to select wrong experts for subsequent task arrivals and incurring additional training errors.

Based on Proposition 2, it is necessary to terminate the update of $\mathbf{\Theta}_{t}$ to preserve a sufficiently large output gap between any two experts in different sets, ensuring expert diversity as in Eq. 12 at round $t_{1}$.
This motivates our design of early termination in Algorithm 1, outlined from Line 7 to Line 13.
In the next proposition, we prove the benefit of terminating updating $\bm{\Theta}_{t}$ in Algorithm 1.

###### Proposition 3 ( $M>N$ version) .

Under Algorithm 1, the MoE terminates updating $\bm{\Theta}_{t}$ since round $T_{2}=\mathcal{O}(\eta^{-1}\sigma_{0}^{-0.25}M)$. Then for any task arrival $n_{t}$ at $t>T_{2}$, the router selects any expert $m\in\mathcal{M}_{n_{t}}$ with an identical probability of $\frac{1}{|\mathcal{M}_{n_{t}}|}$, where $|\mathcal{M}_{n_{t}}|$ is the number of experts in set $\mathcal{M}_{n}$.

The full version and the proof of Proposition 3 are given in Appendix G. According to Algorithm 1, once the MoE terminates updating $\mathbf{\Theta}_{t}$,
the random noise $r_{t}^{(m)}$ in Eq. 1 will guide the router to select experts in the same expert set with identical probability, effectively balancing the loads across experts therein. Our theoretical analysis will be further corroborated by the experiments later in Section 6.

###### Lemma 1 ( M > N 𝑀 𝑁 M>N italic_M > italic_N version) .

###### Proposition 1 ( M > N 𝑀 𝑁 M>N italic_M > italic_N version) .

###### Proposition 2 ( M > N 𝑀 𝑁 M>N italic_M > italic_N version) .

###### Proposition 3 ( M > N 𝑀 𝑁 M>N italic_M > italic_N version) .

## 5 Theoretical results on forgetting and generalization

For the MoE model described in Section 3, we define $\mathcal{E}_{t}(\bm{w}_{t}^{(m_{t})})$ as the model error in the $t$-th round:

$$ $\displaystyle\textstyle\mathcal{E}_{t}(\bm{w}_{t}^{(m_{t})})=\|\bm{w}_{t}^{(m_ {t})}-\bm{w}_{n_{t}}\|^{2}_{2},$ (14) $$

which characterizes the generalization performance of the selected expert $m_{t}$ with model $\bm{w}_{t}^{(m_{t})}$ for task $n_{t}$ at round $t$. Following the existing literature on CL (e.g., [, ]), we assess the performance of MoE in CL using the metrics of *forgetting* and *overall generalization error*, defined as follows:

(1) *Forgetting:* Define $F_{t}$ as the forgetting of old tasks after learning task $n_{t}$ for $t\in\{2,\cdots,T\}$:

$$ $\displaystyle\textstyle F_{t}=\frac{1}{t-1}\sum_{\tau=1}^{t-1}(\mathcal{E}_{ \tau}(\bm{w}_{t}^{(m_{\tau})})-\mathcal{E}_{\tau}(\bm{w}_{\tau}^{(m_{\tau})})).$ (15) $$

(2) *Overall generalization error:* We evaluate the generalization performance of the model $\bm{w}_{T}^{(m)}$ from the last training round $T$ by computing the average model error across all tasks:

$$ $\displaystyle\textstyle G_{T}=\frac{1}{T}\sum_{\tau=1}^{T}\mathcal{E}_{\tau}( \bm{w}_{T}^{(m_{\tau})}).$ (16) $$

In the following, we present explicit forms of the above two metrics for learning with a single expert (i.e., $M=1$) as a benchmark []. Here we define $r:=1-\frac{s}{d}$ as the overparameterization ratio.

###### Proposition 4 .

If $M=1$, for any training round $t\in\{2,\cdots,T\}$, we have

$$ $\displaystyle\textstyle\mathbb{E}[F_{t}]$ $\displaystyle\textstyle=\frac{1}{t-1}\sum_{\tau=1}^{t-1}\Big{\{}\frac{r^{t}-r^ {\tau}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{r^{\tau}-r^{t}}{N^{2}}\sum_{n \neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}\Big{\}},$ (17) $\displaystyle\textstyle\mathbb{E}[G_{T}]$ $\displaystyle\textstyle=\frac{r^{T}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{ 1-r^{T}}{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n}-\bm{w}_{n}^{\prime}\|^{2}.$ (18) $$

Note that the setting here (with $M=1$) is slightly different from that in [], because we have $N$ tasks in total. Hence a proof of Proposition 4 is provided in Appendix H.
Proposition 4 implies that distinct tasks with large model gap $\sum_{n\neq n^{\prime}}\|\bm{w}_{n}-\bm{w}_{n}^{\prime}\|^{2}$ lead to poor performance of both $\mathbb{E}[F_{t}]$ in Eq. 17 and $\mathbb{E}[G_{t}]$ in Eq. 18.

Next, we investigate the impact of MoE on CL under two cases: (I) when there are more experts than tasks ($M>N$), and (II) when there are fewer experts than tasks ($M<N$). The benefit of MoE will be characterized by comparing our results with the single-expert baseline in Proposition 4.

###### Proposition 4 .

### 5.1 Case I: More experts than tasks

Based on Proposition 1, we derive the explicit upper bounds for both forgetting and overall generalization error in the following theorem. To simplify notations, we define $L_{t}^{(m)}:=t\cdot f_{t}^{(m)}$ as the cumulative number of task arrivals routed to expert $m$ up to round $t$, where $f_{t}^{(m)}$ is given in Eq. 7.

###### Theorem 1 .

If $M=\Omega(N\ln(N))$, for each round $t\in\{2,\cdots,T_{1}\}$, the expected forgetting satisfies

$$ $\displaystyle\textstyle\mathbb{E}[F_{t}]<\frac{1}{t-1}\sum_{\tau=1}^{t-1}\Big{ \{}\frac{r^{L_{t}^{(m_{\tau})}}-r^{L_{\tau}^{(m_{\tau})}}}{N}\sum_{n=1}^{N}\| \bm{w}_{n}\|^{2}+\frac{r^{L_{\tau}^{(m_{\tau})}}-r^{L_{t}^{(m_{\tau})}}}{N^{2} }\sum_{n\neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}\Big{\}}.$ (19) $$

For each $t\in\{T_{1}+1,\cdots,T\}$, we have $\mathbb{E}[F_{t}]=\frac{T_{1}-1}{t-1}\mathbb{E}[F_{T_{1}}]$.
Further, after training task $n_{T}$ in the last round $T$, the overall generalization error satisfies

$$ $\displaystyle\textstyle\mathbb{E}[G_{T}]$ $\displaystyle\textstyle<\frac{1}{T}\sum_{\tau=1}^{T}\Big{\{}\frac{r^{L_{T_{1}} ^{(m_{\tau})}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{1-r^{L_{T_{1}}^{(m_{ \tau})}}}{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2} \Big{\}}.$ (20) $$

The proof of Theorem 1 is given in Appendix I, and we have the following insights.

1) *Forgetting.* If $t\leq T_{1}$, in Eq. 19, the coefficient $r^{L_{t}^{(m_{\tau})}}-r^{L_{\tau}^{(m_{\tau})}}$ of the term $\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}$ is smaller than 0 0 because $L_{t}^{(m_{\tau})}\geq L_{\tau}^{(m_{\tau})}$ and $r<1$, indicating that the training of new tasks enhances the performance of old tasks due to the repeated task arrivals in this phase.
Meanwhile, the coefficient of model gap $\sum_{n\neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ is greater than 0 0, indicating that the forgetting is due to experts’ exploration of distinct tasks.
However, as stated in Proposition 1, once the expert models converge at $t=T_{1}$, subsequent training on new task arrivals does not lead to forgetting of previous tasks.
Therefore, for $t\in\{T_{1}+1,\cdots,T\}$, $\mathbb{E}[F_{t}]=\frac{T_{1}-1}{t-1}\mathbb{E}[F_{T_{1}}]$ decreases with $t$ and converges to zero as $T\rightarrow\infty$.
This trend indicates that, compared to the oscillated forgetting in Eq. 17 of a single expert, the MoE model can significantly reduce expected forgetting for CL. Furthermore, a decrease in *task similarity*, i.e., larger model gaps, further amplifies the learning benefit of the MoE model.

2) *Generalization error.* Note that the second term $\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ dominates the generalization error when tasks are *less similar* with large model gaps.
In Eq. 22, the coefficient $1-r^{L_{T_{1}}^{(m_{\tau})}}$ of the model gaps $\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ is smaller than $1-r^{T}$ in Eq. 18, due to the convergence of expert models after round $T_{1}$.
Therefore, the generalization error under MoE is reduced compared to that of a single expert, especially as $T$ increases (where $1-r^{T}$ approaches $1$ in Eq. 18).

3) *Expert number.* According to Theorem 1, for $t>T_{1}$, $\mathbb{E}[F_{t}]$ increases with $T_{1}$ as additional rounds of expert exploration accumulate more model errors in Eq. 19. Regarding $\mathbb{E}[G_{T}]$ in Eq. 20, a longer exploration period $T_{1}$ for experts increases the coefficient $1-r^{L_{T_{1}}^{(m_{\tau})}}$ of the model gaps, leading to an increase in $\mathbb{E}[G_{T}]$ when the model gaps across tasks are large.
Since $T_{1}$ increases with expert number $M$, adding more experts does not enhance learning performance but delays convergence. Note that if $M=1$ in Theorem 1, $L_{t}^{(m_{\tau})}$ becomes $t$ for the single expert, causing Eq. 19 and Eq. 20 to specialize to Eq. 17 and Eq. 18, respectively.

###### Theorem 1 .

### 5.2 Case II: Fewer experts than tasks

Next, we consider a more general case with fewer experts than tasks, i.e., $M<N$, where Algorithm 1 still works efficiently.
In particular, we assume that the $N$ ground truths in $\mathcal{W}$ can be classified into $K$ clusters, where $K<M$, based on the task similarity.
Let $\mathcal{W}_{k}$ denote the $k$-th task cluster. For any two tasks $n,n^{\prime}\in[N]$ in the same cluster with $\bm{w}_{n},\bm{w}_{n^{\prime}}\in\mathcal{W}_{k}$, we assume $\|\bm{w}_{n}-\bm{w}_{n^{\prime}}\|_{\infty}=\mathcal{O}(\sigma_{0}^{1.5})$.
Then we let set $\mathcal{M}_{k}$ include all experts that specialize in tasks within the $k$-th task cluster.

Recall Proposition 1 indicates that expert models converge after $T_{1}$ rounds of exploration if $M>N$.
However, in the case of fewer experts than tasks ($M<N$), each expert has to specialize in learning a cluster of similar tasks. Consequently, as similar tasks within the same cluster are continuously routed to each expert, the expert models keep updating after round $T_{1}$, behaving differently from the $M>N$ case in Proposition 1.
Given the above understanding, we have the following theorem.

###### Theorem 2 .

If $M<N$ and $M=\Omega(K\ln(K))$, for any $t\in\{1,\cdots,T_{1}\}$, the expected forgetting $\mathbb{E}[F_{t}]$ is the same as Eq. 19. While for any $t\in\{T_{1}+1,\cdots,T\}$, the expected forgetting satisfies

$$ $\displaystyle\textstyle\mathbb{E}[F_{t}]$ $\displaystyle\textstyle<\frac{1}{t-1}\sum_{\tau=1}^{t-1}\frac{r^{L_{t}^{(m_{ \tau})}}-r^{L_{\tau}^{(m_{\tau})}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{1 }{t-1}\sum_{\tau=1}^{T_{1}}\frac{r^{L_{i}^{(m_{\tau})}}-r^{L_{T_{1}}^{(m_{\tau })}}}{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle\textstyle\quad+\frac{\Psi_{1}}{t-1}\sum_{\tau=T_{1}+1}^{t}(1-r^{ L_{t}^{(m_{\tau})}-L_{\tau}^{(m_{\tau})}})r^{L_{t}^{(m_{\tau})}-L_{T_{1}}^{(m_ {\tau})}-1},$ (21) $$

where $\Psi_{1}=\frac{1}{N}\sum_{n=1}^{N}\sum_{n,n^{\prime}\in\mathcal{W}_{k}}\frac{
\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}}{|\mathcal{W}_{k}|}$ is the expected model gap between any two tasks in the same task cluster.
After training task $n_{T}$ in round $T$, the overall generalization error satisfies

$$ $\displaystyle\textstyle\mathbb{E}[G_{T}]$ $\displaystyle\textstyle<\frac{1}{T}\sum_{{\tau}=1}^{T}\frac{r^{L_{T}^{(m_{\tau })}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{1}{T}\sum_{{\tau}=1}^{T_{1}} \frac{r^{L_{T}^{(m_{\tau})}-L_{T_{1}}^{(m_{\tau})}}(1-r^{L_{T_{1}}^{(m_{\tau}) }})}{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle\textstyle\quad+\frac{\Psi_{2}}{T}\Big{\{}\sum_{{\tau}=1}^{T_{1}} (1-r^{L_{T}^{(m_{\tau})}-L_{T_{1}}^{(m_{\tau})}})+\sum_{{\tau}=T_{1}+1}^{T}r^{ L_{T}^{(m_{\tau})}-L_{T_{1}}^{(m_{\tau})}}(1-r^{L_{T_{1}}^{(m_{\tau})}})\Big{\}}$ $\displaystyle\textstyle\quad+\frac{\Psi_{1}}{T}\sum_{\tau=T_{1}+1}^{T}(1-r^{L_ {T}^{(m_{\tau})}-L_{T_{1}}^{(m_{\tau})}}),$ (22) $$

where $\Psi_{2}=\frac{1}{N}\sum_{n=1}^{N}\frac{1}{K}\sum_{k=1}^{K}\frac{1}{|\mathcal{
W}_{k}|}\sum_{n^{\prime}\in\mathcal{W}_{k}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^
{2}$ is the expected model gap between a randomly chosen task in $\mathcal{W}$ and any task in a fixed ground-truth cluster $\mathcal{W}_{k}$.

The proof of Theorem 2 is given in Appendix J, and we provide the following insights.

1) *Forgetting.* Compared to Theorem 1, $\mathbb{E}[F_{t}]$ in Eq. 21 introduces an additional term $\Psi_{1}$, which measures the forgetting of task arrivals during $\{T_{1}+1,\cdots,\tau\}$ caused by updating expert models for new task arrival in round $\tau\in\{T_{1}+1,\cdots,T\}$.
However, since tasks routed to the same expert during $\{T_{1}+1,\cdots,T\}$ belong to the same cluster, their small model gaps lead to minimal forgetting.
If there is only one task in each cluster, $\Psi$ becomes 0 0 and $\mathbb{E}[F_{t}]$ becomes the same as Eq. 19.

2) *Generalization error.* As expert models continuously update at any $t$, $\mathbb{E}[G_{T}]$ in Eq. 22 comprises three terms:
a) the expected model gap $\frac{1}{N^{2}}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ between any two random task arrivals for $t<T_{1}$,
b) the expected model gap $\Psi_{1}$ between two tasks in the same cluster for $t>T_{1}$, and
c) the expected model gap $\Psi_{2}$ between a random task arrival for $t<T_{1}$ and any task arrival in a fixed ground-truth cluster $\mathcal{W}_{k}$ for $t>T_{1}$.
If each cluster contains only one task, the coefficient of $\Psi_{2}$ simplifies to $\sum_{\tau=T_{1}+1}^{T}(1-r^{L_{T_{1}}^{(m_{\tau})}})$, given $L_{T}^{(m_{\tau})}=L_{T_{1}}^{(m_{\tau})}$ without updates after $T_{1}$.
Moreover, $\Psi_{2}=\frac{1}{N^{2}}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w
}_{n}\|^{2}$ and $\Psi_{1}=0$, resulting in Eq. 22 specializing to Eq. 20.

Note that under our assumption $\|\bm{w}_{n}-\bm{w}_{n^{\prime}}\|_{\infty}=\mathcal{O}(\sigma_{0}^{1.5})$, the router cannot distinguish between similar tasks $n$ and $n^{\prime}$ within the same cluster. Consequently, adding more experts cannot avoid the errors $\Psi_{1}$ and $\Psi_{2}$ in Eq. 21 and Eq. 22. Therefore, similar to our insights of Theorem 1, when there are enough experts than clusters (i.e., $M=\Omega(K\ln(K))$), adding more experts does not enhance learning performance but delays convergence. Although the learning performance degrades compared to Theorem 1, it still benefits from MoE compared to the single expert in Proposition 4.

Note that if we extend to the top-$k$ routing strategy in Eq. 1, the router will select $k$ experts to train the same data at a time. In this case, the forgetting described in Eq. 21 may decrease, as each expert may handle a smaller cluster of tasks compared to the case with top-$1$ routing strategy.
However, similar tasks that belong to the same cluster in the top-$1$ case now may be divided into different clusters and handled by different expert, which may reduce the potential positive knowledge transfer among these tasks. Consequently,
the generalization error in Eq. 22 may not be smaller for the top-$k$ case.

###### Theorem 2 .

## 6 Experiments

In this section, we conduct extensive experiments for both linear models and DNNs to support our theoretical analysis.
Note that compared to most theoretical studies in CL (e.g., [, ]), our work has already included a more comprehensive experimental investigation.
Due to the space limit, we delegate the experimental details and additional experiments on the impact of the termination threshold and load balancing to Appendix A.

Key design of early termination.
In the first experiment, we aim to check the necessity of terminating the update of $\mathbf{\Theta}_{t}$ in Line 11 of Algorithm 1. Here we set $T=2000,N=7,K=3$ and vary expert number $M\in\{1,5,10,20\}$.
As depicted in Figure 2(a) and Figure 2(c),
both forgetting and generalization error first increase due to the expert exploration and then converge to almost zero for all MoE models with termination of update, verifying Theorem 1 and Theorem 2. In stark contrast, learning without termination leads to poor performance with large oscillations in Figure 2(b) and Figure 2(d), as the router selects the wrong expert for a new task arrival after the continual update of $\mathbf{\Theta}_{t}$. In addition, in both Figure 2(a) and Figure 2(c), the MoE model significantly improves the performance of CL compared to a single model. The
comparison between $M=10$ and $M=20$ also indicates that adding extra experts delays the convergence if $M>N$, which does not improve learning performance, verifying our analysis in Theorem 1 and Theorem 2.

Figure: (a) With termination.
Refer to caption: x2.png

Real-data validation. Finally, we extend our Algorithm 1 and insights from linear models to DNNs by conducting experiments on the MNIST dataset []. We set $N=3$ and vary $M\in\{1,4,7\}$. In each training round, we obtain the feature matrix by averaging $s=100$ training data samples. To diversify the model gaps of different tasks, we transform the $d\times d$ matrix into a $d\times d$ dimensional normalized vector to serve as input for the gating network. Then we calculate the variance $\sigma_{0}$ of each element across all tasks from the input vector, which is then used for parameter setting in Algorithm 1. Figure 3 illustrates that our theoretical insights from linear models also hold for DNNs, in terms of the impact of MoE and early termination on the performance of CL in practice.

Figure: (a) With termination.
Refer to caption: x6.png

## 7 Conclusion

In this work, we conducted the first theoretical analysis of MoE and its impact on learning performance in CL, focusing on an overparameterized linear regression problem. We proved that the MoE model can diversify experts to specialize in different tasks, while its router can learn to select the right expert for each task and balance the loads across all experts. Then we demonstrated that, under CL, terminating the updating of gating network parameters after sufficient training rounds is necessary for system convergence. Furthermore, we provided explicit forms of the expected forgetting and overall generalization error to assess the impact of MoE. Finally, we conducted experiments on real datasets using DNNs to show that certain insights can extend beyond linear models.

## Appendix A Experimental details and additional experiments

### A.1 Experiments compute resources

Operating system: macOS Sonoma 14.2.1.

Type of CPU: 2.6 GHz 6-Core Intel Core i7

Type of GPU: Intel UHD Graphics 630 1536 MB

Memory: 16 GB 2667 MHz DDR4

Time of Execution: $40$ minutes for Figure 2, $100$ minutes for Figure 3, and $80$ minutes for Figure 4 and Figure 5.

### A.2 Experimental details of Figure 2

Synthetic data generation. We first generate $N$ ground truths and their corresponding feature signals. For each ground truth $\bm{w}_{n}\in\mathbb{R}^{d}$, where $n\in[N]$, we randomly generate $d$ elements by a normal distribution $\mathcal{N}(0,\sigma_{0})$. These ground truths are then scaled by a constant to obtain their feature signals $\bm{v}_{n}$.
In each training round $t$, we generate $(\mathbf{X}_{t},\mathbf{y}_{t})$ according to Definition 1 based on ground-truth pool $\mathcal{W}$ and feature signals. Specifically, after drawing $\bm{w}_{n_{t}}$ from $\mathcal{W}$, for $\mathbf{X}_{t}\in\mathbb{R}^{d\times s}$, we randomly select one out of $s$ samples to fill with $\mathbf{v}_{n_{t}}$. The other $s-1$ samples are generated from $\mathcal{N}(\bm{0},\sigma_{t}^{2}\bm{I}_{d})$. Finally, we compute the output $\mathbf{y}_{t}=\mathbf{X}_{t}^{\top}\bm{w}_{n_{t}}$.
Here we set $\sigma_{0}=0.4,\sigma_{t}=0.1,d=10$ and $s=6$. In Figure 2, we set $\eta=0.5,\alpha=0.5$ and $\lambda=0.3$.

### A.3 Experimental details of Figure 3

*Datasets.* We use the MNIST dataset, selecting $100$ samples randomly for training and $1000$ samples for testing at each training round.

*DNN architecture and training details.* We use a five-layer neural network, consisting of two convolutional layers and three fully connected layers. ReLU activation is applied to the first four layers, while Sigmoid is used for the final layer. The first convolutional layer is followed by a 2D max-pooling operation with a stride of $2$. Each task is learned using SGD with a learning rate of $0.2$ for $600$ epochs. The forgetting and overall generalization error are evaluated as described in Eq. 15 and Eq. 16, respectively. Here, $\mathcal{E}_{t}(\bm{w}_{t}^{(m_{t})})$ is defined as the mean-squared test error instead of Eq. 14.

*Task setups.* We set ground truth pool $\mathcal{W}=\{(1),(4),(7)\}$ with $N=3$ tasks and $T=60$ training rounds. Before conducting the experiments in Figure 3, we first randomly generate the order of task arrivals $[n_{t}]_{t\in[T]}$, where $n_{t}$ at each round $t$ is randomly drawn from $\{1,2,3\}$ with equal probability $\frac{1}{3}$. Then, we conduct the two experiments (i.e., with and without termination) under the same order of task arrivals.

### A.4 Experiments on termination threshold and load balance

In additional experiments, we vary termination threshold $\Gamma\in\{\sigma_{0}^{0.75},\sigma_{0},\sigma_{0}^{1.25},\sigma_{0}^{1.5}\}$ in Line 7 of Algorithm 1 to investigate its effect on load balance and learning performance, under the same synthetic data generation as Figure 2 in Section A.2.

Initially, we set $\sigma_{0}=0.4$, $\lambda=\sigma_{0}^{1.25}$, $M=5$, and $N=6$ with $K=3$ task clusters: $\mathcal{W}_{1}=\{1,4\},\mathcal{W}_{2}=\{2,5\}$, and $\mathcal{W}_{3}=\{3,6\}$. Figure 4 illustrates the recorded task arrivals per round and their routed experts. Figure 4(a) and Figure 4(b) depict that if the MoE model terminates the update based on $\Gamma>\lambda$, the small noise $r_{t}^{(m)}$ cannot alter the router’s decision from the expert with the maximum gate output for each task cluster (e.g., expert 5 for $\mathcal{W}_{2}=\{2,5\}$ in Figure 4(a)) in Eq. 1, leading to imbalanced expert load.
While for $\Gamma\leq\lambda$ in Figure 4(c) and Figure 4(d), the random noise $r_{t}^{(m)}$ in Eq. 1 can mitigate the gaps of gate outputs among experts within the same expert set, ensuring load balance (e.g., experts 3 and 4 for $\mathcal{W}_{2}=\{2,5\}$ in Figure 4(c)).

Figure: (a) Threshold $=\sigma_{0}^{0.75}$.
Refer to caption: x10.png

Figure: Figure 5: We run the experiment for $100$ times to take the average learning performance under four termination thresholds: $\Gamma\in\{\sigma_{0}^{0.75},\sigma_{0},\sigma_{0}^{1.25},\sigma_{0}^{1.5}\}$. Here we set $M=5,N=30$ and $K=3$.
Refer to caption: x14.png

To further examine how load balance affects learning performance, we increase the task number to $N=30$. We repeat the experiment $100$ times and plot the average forgetting and generalization errors in Figure 5. Figure 5 illustrates that the forgetting is robust to a wide range of $\Gamma$, due to the convergence of expert models after $T_{1}$ rounds’ exploration. However, Figure 5 shows that balanced loads under $\Gamma\in\{\sigma_{0}^{1.25},\sigma_{0}^{1.5}\}$ lead to smaller generalization errors compared to imbalanced loads under $\Gamma\in\{\sigma_{0}^{0.75},\sigma_{0}^{1}\}$. This is because diverse expert models help mitigate model errors compared to a single overfitted model.

## Appendix B Smooth router

We first prove that Eq. 1 ensures a smooth transition between different routing behaviors, which makes the router more stable. Suppose that there are two different datasets $(\mathbf{X},\mathbf{y})$ and $(\hat{\mathbf{X}},\hat{\mathbf{y}})$ simultaneously acting as input of the MoE. Let $\mathbf{h}$ and $\hat{\mathbf{h}}$ denote the corresponding output of the gating network, respectively. Denote the probability vectors by $\mathbf{p}$ and $\hat{\mathbf{p}}$, which tell the probabilities that each expert gets routed for the two datasets. For example, $p_{m}=\mathbb{P}(\arg\max_{m^{\prime}\in[M]}\{h_{m^{\prime}}+r^{(m^{\prime})}
\}=m)$ and $\hat{p}_{m}=\mathbb{P}(\arg\max_{m^{\prime}\in[M]}\{\hat{h}_{m^{\prime}}+r^{(m
^{\prime})}\}=m)$ according to Eq. 1. Then we propose the following lemma to prove the smooth router.

###### Lemma 2 .

The two probability vectors satisfy $\|\mathbf{p}-\hat{\mathbf{p}}\|_{\infty}\leq\lambda M^{2}\|\mathbf{h}-\hat{
\mathbf{h}}\|_{\infty}$.

###### Proof.

Let $m_{1}=\arg\max_{m}\{h_{m}+r^{(m)}\}$ and $m_{2}=\arg\max_{m}\{\hat{h}_{m}+r^{(m)}\}$.
We first consider the event that $m_{1}\neq m_{2}$. In this case, we have

$$ $\displaystyle h_{m_{1}}+r^{(m_{1})}\geq h_{m_{2}}+r^{(m_{2})},\hat{h}_{m_{2}}+ r^{(m_{2})}\geq\hat{h}_{m_{1}}+r^{(m_{1})},$ $$

which implies that

$$ $\displaystyle\hat{h}_{m_{2}}-\hat{h}_{m_{1}}>r^{(m_{1})}-r^{(m_{2})}\geq h_{m_ {2}}-h_{m_{1}}.$ (23) $$

Define $C(m_{1},m_{2})=\frac{\hat{h}_{m_{2}}-\hat{h}_{m_{1}}+h_{m_{2}}-h_{m_{1}}}{2}$. Based on Eq. 23, we obtain

$$ $\displaystyle|r^{(m_{1})}-r^{(m_{2})}-C(m_{1},m_{2})|\leq\frac{\hat{h}_{m_{2}} -\hat{h}_{m_{1}}-h_{m_{2}}+h_{m_{1}}}{2}\leq\|\hat{\mathbf{h}}-\mathbf{h}\|_{ \infty}.$ (24) $$

Therefore, we calculate that $m_{1}\neq m_{2}$ below

$$ $\displaystyle\mathbb{P}(\arg\max_{m}\{h_{m}+r^{(m)}\}\neq\arg\max_{m}\{\hat{h} _{m}+r^{(m)}\})$ $\displaystyle\leq$ $\displaystyle\mathbb{P}(\exists\ m_{1}\neq m_{2}\in[M],\text{s.t. }|r^{(m_{1}) }-r^{(m_{2})}-C(m_{1},m_{2})|\leq\|\hat{\mathbf{h}}-\mathbf{h}\|_{\infty})$ $$

$$ $\displaystyle\leq$ $\displaystyle\sum_{m_{1}<m_{2}}\mathbb{P}\big{(}|r^{(m_{1})}-r^{(m_{2})}-C(m_{ 1},m_{2})|\leq\|\hat{\mathbf{h}}-\mathbf{h}\|_{\infty}\big{)}$ $\displaystyle=$ $\displaystyle\sum_{m_{1}<m_{2}}\mathbb{E}\big{[}\mathbb{P}(r^{(m_{2})}+C(m_{1} ,m_{2})-\|\hat{\mathbf{h}}-\mathbf{h}\|_{\infty}\leq r^{(m_{1})}\leq r^{(m_{2} )}+C(m_{1},m_{2})+\|\hat{\mathbf{h}}-\mathbf{h}\|_{\infty})|r^{(m_{2})}\big{]}$ $\displaystyle\leq$ $\displaystyle\lambda M^{2}\|\hat{\mathbf{h}}-\mathbf{h}\|_{\infty},$ $$

where the first inequality is derived by Eq. 24, the second inequality is because of union bound, and the last inequality is due to the fact that $r^{(m)}$ is drawn from Unif $[0,\lambda]$.

Then for any $j\in[M]$, we have

$$ $\displaystyle|\hat{p}_{i}-p_{i}|\leq$ $\displaystyle\left|\mathbb{E}\left[\mathds{1}(\arg\max_{m}\{\hat{h}_{m}+r^{(m) }=i\})-\mathds{1}(\arg\max_{m}\{\hat{h}_{m}+r^{(m)}=i\})\right]\right|$ $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\left|\mathds{1}(\arg\max_{m}\{\hat{h}_{m}+r^{(m) }=i\})-\mathds{1}(\arg\max_{m}\{\hat{h}_{m}+r^{(m)}=i\})\right|\right]$ $\displaystyle\leq$ $\displaystyle\mathbb{P}(\arg\max_{m}\{h_{m}+r^{(m)}\}\neq\arg\max_{m}\{\hat{h} _{m}+r^{(m)}\})$ $\displaystyle\leq$ $\displaystyle M^{2}\|\hat{\mathbf{h}}-\mathbf{h}\|_{\infty}.$ $$

This completes the proof of Lemma 2.
∎

Intuitively, Lemma 2 tells that if the outputs $\mathbf{h}$ and $\hat{\mathbf{h}}$ of the gating network are similar for two tasks, their data sets $(\mathbf{X},\mathbf{y})$ and $(\hat{\mathbf{X}},\hat{\mathbf{y}})$ will be routed to the same expert with a high probability. It means that the router transitions are smooth and continuous.

###### Lemma 2 .

###### Proof.

## Appendix C Full version and proof of Lemma 1

###### Lemma 1 (Full version) .

For any two feature matrices $\mathbf{X}$ and $\tilde{\mathbf{X}}$ with feature signals $\bm{v}_{n}$ and $\bm{v}^{\prime}_{n}$, if $\bm{w}_{n}=\bm{w}_{n^{\prime}}$ under $M>N$ or $\bm{w}_{n},\bm{w}_{n^{\prime}}\in\mathcal{W}_{k}$ under $M<N$, with probability at least $1-o(1)$, their corresponding gate outputs of the same expert $m$ satisfy

$$ $\displaystyle\textstyle\big{|}h_{m}(\mathbf{X},\bm{\theta}_{t}^{(m)})-h_{m}( \tilde{\mathbf{X}},\bm{\theta}_{t}^{(m)})\big{|}=\mathcal{O}(\sigma_{0}^{1.5}).$ (25) $$

###### Proof.

We first focus on the $M>N$ case to prove Lemma 1. Then we consider the $M<N$ case to prove Lemma 1. For dataset $(\mathbf{X}_{t},\mathbf{y}_{t})$ generated in Definition 1 per round $t$, we can assume that the first sample of $\mathbf{X}_{t}$ is the signal vector. Therefore, we rewrite $\mathbf{X}_{t}=[\beta_{t}\bm{v}_{n}\ \mathbf{X}_{t,2}\ \cdots\ \mathbf{X}_{t,s}]$. Let $\tilde{\mathbf{X}}_{t}=[\beta_{t}\bm{v}_{n_{t}}\ 0\ \cdots\ 0]$ represents the matrix that only keeps the feature signal.

Based on the definition of the gating network in Section 3,
we have $h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})=\sum_{i=1}^{s}(\bm{\theta}_{t}^{(m
)})^{\top}\mathbf{X}_{t,i}$.
Then we calculate

$$ $\displaystyle\left|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m}(\tilde{ \mathbf{X}}_{t},\bm{\theta}_{t}^{(m)})\right|$ $\displaystyle=\left|(\bm{\theta}_{t}^{(m)})^{\top}\sum_{i=2}^{s}\mathbf{X}_{t, i}\right|$ $\displaystyle=\left|\sum_{i=2}^{s}\sum_{j=1}^{d}(\theta_{t,j}^{(m)})^{\top}X_{ t,(i,j)}\right|$ $\displaystyle\leq\Big{|}\max_{t,j}\{\theta_{t,j}^{(m)}\}\Big{|}\cdot\Big{|} \sum_{i=2}^{s}\sum_{j=1}^{d}X_{t,(i,j)}\Big{|},$ $$

where $\theta_{t,j}^{(m)}$ is the $j$-th element of vector $\bm{\theta}_{t}^{(m)}$ and $X_{t,(i,j)}$ is the $(i,j)$-th element of matrix $\mathbf{X}_{t}$.

Then we apply Hoeffding’s inequality to obtain

$$ $\displaystyle\mathbb{P}\Big{(}|\sum_{i=2}^{s}\sum_{j=1}^{d}X_{t,(i,j)}|<s\cdot d \cdot\sigma_{0}\Big{)}\geq 1-2\exp{(-\frac{\sigma_{0}^{2}s^{2}d^{2}}{\|\mathbf {X}_{t,i}\|_{\infty}})}.$ $$

As $X_{t,(i,j)}\sim\mathcal{N}(0,\sigma_{t}^{2})$, we have $\|\mathbf{X}_{t,i}\|_{\infty}=\mathcal{O}(\sigma_{t})$, indicating $\exp{(-\frac{\sigma_{0}^{2}s^{2}d^{2}}{\|\mathbf{X}_{t,i}\|_{\infty}})}=o(1)$. Therefore, with probability at least $1-o(1)$, we have $\big{|}\sum_{i=2}^{s}\sum_{j=1}^{d}X_{t,(i,j)}\big{|}=\mathcal{O}(\sigma_{0})$.
Consequently, we obtain
$\big{|}h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m}(\tilde{\mathbf{X}}_{t
},\bm{\theta}_{t}^{(m)})\big{|}=\mathcal{O}(\sigma_{0}^{1.5})$ due to the fact that $\big{|}\sum_{i=2}^{s}\sum_{j=1}^{d}X_{t,(i,j)}\big{|}=\mathcal{O}(\sigma_{0})$ and $\theta_{t,j}^{(m)}=\mathcal{O}(\sigma_{0}^{0.5})$ proven in Lemma 6 later.

If $M<N$, we calculate

$$ $\displaystyle\Big{|}h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m}(\tilde{ \mathbf{X}}_{t},\bm{\theta}_{t}^{(m)})\Big{|}$ $\displaystyle=\Big{|}(\bm{\theta}_{t}^{(m)})^{\top}\sum_{i=1}^{s}\mathbf{X}_{t ,i}\Big{|}$ $\displaystyle\leq\Big{|}(\bm{\theta}_{t}^{(m)})^{\top}\sum_{i=2}^{s}\mathbf{X} _{t,i}\Big{|}+\Big{|}(\bm{\theta}_{t}^{(m)})^{\top}(\bm{v}_{n}-\bm{v}_{n^{ \prime}})\Big{|}$ $\displaystyle\leq\Big{|}\max_{t,j}\{\theta_{t,j}^{(m)}\}\Big{|}\cdot\Big{|} \sum_{i=2}^{s}\sum_{j=1}^{d}X_{t,(i,j)}\Big{|}+\mathcal{O}(\sigma_{0}^{2})$ $\displaystyle=\mathcal{O}(\sigma_{0}^{1.5}),$ $$

where the second inequality is based on the union bound, the third inequality is because of $\theta_{t,j}^{(m)}=\mathcal{O}(\sigma_{0}^{0.5})$ and our assumption $\|\bm{v}_{n}-\bm{v}_{n^{\prime}}\|_{\infty}=\mathcal{O}(\sigma_{0}^{1.5})$, and the last inequality is based on our proof of the $M>N$ case above. This completes the proof of the full version of Lemma 1.
∎

Based on Lemma 1, we revisit Lemma 2 to obtain the following conclusion for the smooth router.

###### Corollary 1 .

If datasets $(\mathbf{X},\mathbf{y})$ and $(\hat{\mathbf{X}},\hat{\mathbf{y}})$ are generated by the same ground truth, then the two probability vectors in Lemma 2 satisfy $\|\mathbf{p}-\hat{\mathbf{p}}\|_{\infty}=\mathcal{O}\left(\lambda M^{2}\sigma_
{0}^{1.5}\right)$.

###### Lemma 1 (Full version) .

###### Proof.

###### Corollary 1 .

## Appendix D Analysis of loss function

In this section, we analyze the loss function for both gating network parameters and expert models before analyzing MoE.

###### Lemma 3 .

Under update rule Eq. 5, if the current task $n_{t}$ routed to expert $m_{t}$ have the same ground truth with the last task $n_{\tau}$, where $\tau<t$, routed to expert $m_{t}$, i.e., $\bm{w}_{n_{t}}=\bm{w}_{n_{\tau}}$, then the model of expert $m_{t}$ satisfies $\bm{w}_{t}^{(m_{t})}=\bm{w}_{t-1}^{(m_{t})}=\cdots=\bm{w}_{\tau}^{(m_{t})}$.

It is easy to prove Lemma 3 by the updating rule Eq. 5 such that we skip the proof here.

Next, we examine the training of the gating network parameter.

###### Lemma 4 .

For any training round $t\geq 1$, we have that $\sum_{m=1}^{M}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}=\mathbf{0}$.

###### Proof.

As the training loss $\nabla_{\bm{\theta}^{(m)}}\mathcal{L}_{t}^{tr}=0$, we obtain

$$ $\displaystyle\nabla_{\bm{\theta}^{(m)}}\mathcal{L}_{t}^{task}=\nabla_{\bm{ \theta}^{(m)}}\mathcal{L}_{t}^{loc}+\nabla_{\bm{\theta}^{(m)}}\mathcal{L}_{t}^ {aux}.$ (26) $$

Next, we will prove $\sum_{m=1}^{M}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}=\mathbf{0}$ and $\sum_{m=1}^{M}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}=\mathbf{0}$, respectively. Based on the two equations, we can prove Lemma 4.

According to the definition of locality loss in Eq. 6, we calculate

$$ $\displaystyle\nabla_{\bm{\theta}^{(m)}_{t}}\mathcal{L}_{t}^{loc}=\frac{ \partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{ (m)}_{t}}\|\bm{w}_{t}^{(m_{t})}-\bm{w}_{t-1}^{(m_{t})}\|_{2}.$ (27) $$

If $m=m_{t}$, we obtain

$$ $\displaystyle\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{ \partial\bm{\theta}^{(m)}_{t}}$ $\displaystyle=\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\Big{(}\sum_ {m^{\prime}\neq m_{t}}\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\Big {)}\cdot\frac{\partial h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})}{\partial \bm{\theta}^{(m)}_{t}}$ $\displaystyle=\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\Big{(}\sum_ {m^{\prime}\neq m_{t}}\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\Big {)}\cdot\sum_{i\in[s_{t}]}\mathbf{X}_{t,i}.$ (28) $$

If $m\neq m_{t}$, we obtain

$$ $\displaystyle\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{ \partial\bm{\theta}^{(m)}_{t}}$ $\displaystyle=-\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\pi_{m}( \mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\sum_{i\in[s_{t}]}\mathbf{X}_{t,i}.$ (29) $$

Based on Eq. 27, Eq. 28 and Eq. 29, we obtain

$$ $\displaystyle\sum_{m=1}^{M}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc} =\|\bm{w}_{t}^{(m_{t})}-\bm{w}_{t-1}^{(m_{t})}\|_{2}\sum_{m=1}^{M}\frac{ \partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{ (m)}_{t}}=\mathbf{0}.$ $$

According to the definition of auxiliary loss in Eq. 7, we calculate

$$ $\displaystyle\nabla_{\bm{\theta}^{(m)}_{t}}\mathcal{L}_{t}^{aux}$ $\displaystyle=\alpha M\sum_{m^{\prime}=1}^{M}f_{t}^{(m^{\prime})}\cdot\frac{ \partial P_{t}^{(m^{\prime})}}{\partial\bm{\theta}^{(m)}_{t}}$ $\displaystyle=\frac{\alpha M}{t}f_{t}^{(m_{t})}\cdot\frac{\partial\pi_{m_{t}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{(m)}_{t}},$ (30) $$

where the second equality is due to the fact that $\frac{\partial P_{t}^{(m_{t})}}{\partial\bm{\theta}^{(m)}_{t}}=\frac{1}{t}
\cdot\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial
\bm{\theta}^{(m)}_{t}}$ and $\frac{\partial P_{t}^{(m^{\prime})}}{\partial\bm{\theta}^{(m)}_{t}}=0$ for any $m^{\prime}\neq m_{t}$ by Eq. 7. Then based on Eq. 28 and Eq. 29, we similarly obtain

$$ $\displaystyle\sum_{m=1}^{M}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux} =\frac{\alpha M}{t}f_{t}^{(m_{t})}\sum_{m=1}^{M}\frac{\partial\pi_{m_{t}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{(m)}_{t}}=\mathbf{0}.$ $$

In summary, we finally prove $\sum_{m=1}^{M}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}=\mathbf{0}$ in Eq. 26.
∎

In the following lemma, we analyze the gradient of loss function with respect to each expert.

###### Lemma 5 .

For any training round $t\in\{1,\cdots,T\}$, the following property holds

$$ $\displaystyle\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}\|_{\infty} =\begin{cases}\Omega(\sigma_{0}),&\text{if }t\in\{1,\cdots,T_{1}\},\\ \mathcal{O}(\sigma_{0}),&\text{if }t\in\{T_{1}+1,\cdots,T\}\end{cases}$ (31) $$

for any expert $m\in[M]$, where $T_{1}=\lceil\eta^{-1}M\rceil$ is the length of the exploration stage.

###### Proof.

We prove Eq. 31 by analyzing $\nabla_{\bm{\theta}^{(m)}}\mathcal{L}_{t}^{loc}=\mathcal{O}(\sigma_{0})$ and $\nabla_{\bm{\theta}^{(m)}}\mathcal{L}_{t}^{aux}=\mathcal{O}(\frac{\alpha M}{t})$ in Eq. 26, respectively.

First, we calculate $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}\|_{\infty}$. Based on Eq. 27, we have

$$ $\displaystyle\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}$ $\displaystyle=\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{ \partial\bm{\theta}^{(m)}_{t}}\|\bm{w}_{t}^{(m_{t})}-\bm{w}_{t-1}^{(m_{t})}\|_ {2}$ $\displaystyle=\mathds{1}\{\bm{w}_{n_{\tau}}=\bm{w}_{n_{t}}\}\cdot 0+\mathds{1} \{\bm{w}_{n_{\tau}}\neq\bm{w}_{n_{t}}\}\cdot\|\bm{w}^{(m_{t})}_{t}-\bm{w}^{(m_ {t})}_{t-1}\|_{2}\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t}) }{\partial\bm{\theta}^{(m)}_{t}}$ $\displaystyle\leq\|\bm{w}^{(m_{t})}_{t}-\bm{w}^{(m_{t})}_{t-1}\|_{2}\frac{ \partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{ (m)}_{t}},$ $$

where $\tau$ is the index of the last task that routed to expert $m_{t}$, the second equality is derived by Lemma 3. As $\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{
\theta}^{(m)}_{t}}=\mathcal{O}(1)$ and $\bm{w}_{n}\sim\mathcal{N}(\mathbf{0},\bm{\sigma}_{0}^{2})$, we finally obtain

$$ $\displaystyle\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}\|_{\infty}= \mathcal{O}(\sigma_{0}).$ $$

Next, we further calculate $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux}\|_{\infty}$, which contains the following two cases.

If $t\in\{1,\cdots,T_{1}\}$, by Eq. 30, we have

$$ $\displaystyle\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux}\|_{\infty}$ $\displaystyle\geq\|\frac{\alpha M}{T_{1}}f_{t}^{(m_{t})}\cdot\frac{\partial\pi _{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{(m)}_{t}}\| _{\infty}$ $\displaystyle\geq\|\sigma_{0}f_{t}^{(m_{t})}\cdot\frac{\partial\pi_{m_{t}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{(m)}_{t}}\|_{\infty} =\Omega(\sigma_{0}),$ $$

where the second inequality is derived by setting $\eta=\Omega(\sigma_{0}^{0.5})$ to make $T_{1}=\lceil\sigma_{0}^{-0.5}M\rceil$.

If $t\in\{T_{1}+1,\cdots,T\}$, we calculate

$$ $\displaystyle\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux}\|_{\infty}$ $\displaystyle\leq\|\frac{\alpha M}{T_{1}}f_{t}^{(m_{t})}\cdot\frac{\partial\pi _{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial\bm{\theta}^{(m)}_{t}}\| _{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}).$ $$

Based on the derived $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}\|_{\infty}$ and $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux}\|_{\infty}$ above, we can finally calculate $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}\|_{\infty}$ based on Eq. 26.

For $t\in\{1,\cdots,T_{1}\}$, if $m\neq m_{t}$, we have

$$ $\displaystyle\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}\|_{\infty}$ $\displaystyle=\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}+\nabla_{ \bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux}\|_{\infty}$ $\displaystyle\leq\|\mathcal{O}(\sigma_{0})+\frac{\alpha M}{T_{1}}f_{t}^{(m_{t} )}\cdot\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial \bm{\theta}^{(m)}_{t}}\|_{\infty}$ $\displaystyle=\Omega(\sigma_{0}).$ $$

Similarly, for any $t\in\{T_{1}+1,\cdots,T\}$, we can can obtain

$$ $\displaystyle\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}\|_{\infty}$ $\displaystyle=\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}+\nabla_{ \bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{aux}\|_{\infty}$ $\displaystyle\geq\|\mathcal{O}(\sigma_{0})+\frac{\alpha M}{T_{1}}f_{t}^{(m_{t} )}\cdot\frac{\partial\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}{\partial \bm{\theta}^{(m)}_{t}}\|_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}).$ $$

This completes the proof of Eq. 31.
∎

Given $\bm{\theta}^{(m)}_{0}=\mathbf{0}$ for any expert $m\in[M]$, in the next lemma, we obtain the upper bound of $\bm{\theta}^{(m)}_{t}$ at any round $t\in\{1,\cdots,T\}$.

###### Lemma 6 .

For any training round $t\in\{1,\cdots,T\}$, the gating network parameter of any expert $m$ satisfies $\|\bm{\theta}^{(m)}_{t}\|_{\infty}=\mathcal{O}(\sigma_{0}^{0.5})$.

###### Proof.

Based on Lemma 5, for any $t\in\{1,\cdots,T_{1}\}$ the accumulated update of $\bm{\theta}^{(m)}_{t}$ throughout the exploration stage satisfies

$$ $\displaystyle\|\bm{\theta}_{t}^{(m)}\|_{\infty}\leq\eta\cdot T_{1}\cdot\alpha M =\mathcal{O}(\sigma_{0}^{0.5}).$ $$

For any $t\in\{T_{1}+1,\cdots,T\}$, the accumulated update of $\bm{\theta}^{(m)}_{t}$ throughout the router learning phase satisfies

$$ $\displaystyle\|\bm{\theta}_{t}^{(m)}\|_{\infty}$ $\displaystyle\leq\|\bm{\theta}_{T_{1}}^{(m)}\|_{\infty}+\eta\cdot(T-T_{1}) \cdot\frac{\alpha M}{T_{1}}$ $\displaystyle=\mathcal{O}(\sigma_{0}^{0.5})+\mathcal{O}(\sigma_{0}^{0.5}- \sigma_{0})=\mathcal{O}(\sigma_{0}^{0.5}).$ $$

In summary, $\|\bm{\theta}^{(m)}_{t}\|_{\infty}=\mathcal{O}(\sigma_{0}^{0.5})$ for any round $t\in\{1,\cdots,T\}$.
∎

###### Lemma 3 .

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

## Appendix E Full version and proof of Proposition 1

###### Proposition 1 (Full version) .

Under Algorithm 1, with probability at least $1-o(1)$, for any $t>T_{1}$, where $T_{1}=\lceil\eta^{-1}M\rceil$, each expert $m\in[M]$ satisfies the following properties:

1) If $M>N$, expert $m$ stabilizes within an expert set $\mathcal{M}_{n}$, and its expert model
remains unchanged beyond time $T_{1}$, satisfying $\bm{w}^{(m)}_{T_{1}+1}=\cdots=\bm{w}^{(m)}_{T}$.

2) If $M<N$, expert $m$ stabilizes within an expert set $\mathcal{M}_{k}$, and its expert model satisfies $\|\bm{w}_{t}^{(m)}-\bm{w}_{T_{1}+1}^{(m)}\|_{\infty}=\mathcal{O}(\sigma_{0}^{1
.5})$ for any $t\in\{T_{1}+2,\cdots,T\}$.

We first propose the following lemmas before formally proving Proposition 1. Then we prove Proposition 1 in Section E.8.

###### Lemma 7 .

At any training round $t\in\{1,\cdots,T_{1}\}$, for any feature signal $\bm{v}_{n}$, the gating network parameter of expert $m\in[M]$ satisfies

$$ $\displaystyle\langle\bm{\theta}_{t+1}^{(m)}-\bm{\theta}_{t}^{(m)},\bm{v}_{n} \rangle=\begin{cases}-\mathcal{O}(\sigma_{0}),&\text{if }m=m_{t},\\ \mathcal{O}(M^{-1}\sigma_{0}),&\text{if }m\neq m_{t}.\end{cases}$ $$

Lemma 7 tells that for any expert $m_{t}$ being selected by the router, its softmax value under the updated $\bm{\theta}^{m_{t}}_{t+1}$ is reduced since the next task $t$. While for any expert $m$ without being selected, its softmax value is increased. This is to ensure fair exploration of each expert $m$ under the auxiliary loss function in Eq. 7.
In addition, for any expert $m$ without being selected, its gating network parameter $\bm{\theta}_{t}^{(m)}$ is updated at the same speed with others for any signal vector $\bm{v}_{n}$.

###### Lemma 8 .

At the end of the exploration stage, with probability at least $1-\delta$, the fraction of tasks dispatched to any expert $m\in[M]$ satisfies

$$ $\displaystyle\Big{|}f_{T_{1}}^{(m)}-\frac{1}{M}\Big{|}=\mathcal{O}(\eta^{0.5}M ^{-1}).$ (32) $$

Lemma 8 tells that during the exploration stage, all the $M$ experts are expected to be evenly explored by all tasks. Therefore, the gating network parameter $\bm{\theta}^{(m)}_{t}$ of expert $m$ is updated similarly to all the others.

###### Lemma 9 .

At the end of the exploration stage, i.e., $t=T_{1}$, the following property holds

$$ $\displaystyle\Big{\|}\bm{\theta}_{T_{1}}^{(m)}-\bm{\theta}_{T_{1}}^{(m^{\prime })}\Big{\|}_{\infty}=\mathcal{O}(\eta^{-0.5}\sigma_{0}),$ $$

for any $m,m^{\prime}\in[M]$ and $m\neq m^{\prime}$.

Define $\delta_{\mathbf{\Theta}}=|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{
\prime}}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})|$. Then we obtain the following lemma.

###### Lemma 10 .

At any round $t$, if $\delta_{\mathbf{\Theta}_{t}}$ is close to 0 0, it satisfies $|\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{m^{\prime}}(\mathbf{X}_{t},
\mathbf{\Theta}_{t})|=\mathcal{O}(\delta_{\mathbf{\Theta}})$. Otherwise, $|\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{m^{\prime}}(\mathbf{X}_{t},
\mathbf{\Theta}_{t})|=\Omega(\delta_{\mathbf{\Theta}})$.

###### Lemma 11 .

If $M=\Omega(N\ln(N))$, we have $|\mathcal{M}_{n}|\geq 1$ for all $n\in[N]$ with probability at least $1-o(1)$. If $M<N$, given $M=\Omega(K\ln(K))$, we have $|\mathcal{M}_{k}|\geq 1$ for all $k\in[K]$ with probability at least $1-o(1)$.

###### Lemma 12 .

At any round $t$, we have the following properties:

1) for task arrival $n_{t}$ with ground truth $\bm{w}_{n_{t}}=\bm{w}_{n}$ under $M>N$, if it is routed to a correct expert $m_{t}\in\mathcal{M}_{n}$, then $\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}=\bm{0}$ for any expert $m\in[M]$.

2) for task arrival $n_{t}$ with ground truth $\bm{w}_{n_{t}}\in\mathcal{W}_{k}$ under $M<N$, if it is routed to a correct expert $m_{t}\in\mathcal{M}_{k}$, then $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}\|_{\infty}=\mathcal{O}(
\sigma_{0}^{1.5})$ for any expert $m\in[M]$.

Let $\mathbf{X}_{n}$ and $\mathbf{X}_{n^{\prime}}$ denote two feature matrices containing feature signals $\bm{v}_{n}$ and $\bm{v}_{n^{\prime}}$, respectively.

###### Lemma 13 .

If $n$ and $n^{\prime}$ satisfy: 1) $n\neq n^{\prime}$ under $M>N$ or 2) $\bm{w}_{n}\in\mathcal{W}_{k}$ and $\bm{w}_{n^{\prime}}\in\mathcal{W}_{k^{\prime}}$ with $k\neq k^{\prime}$ under $M<N$, then if expert $m$ satisfies 1) $m\in\mathcal{M}_{n}$ under $M>N$ or 2) $m\in\mathcal{M}_{k}$ under $M<N$, at the beginning of the router learning stage $t=T_{1}+1$, then the following property holds at any round $t\in\{T_{1}+2,\cdots,T\}$:

$$ $\displaystyle\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{n ^{\prime}},\mathbf{\Theta}_{t}),\forall m\in[M].$ (33) $$

Based on these lemmas, the proof of Proposition 1 is given in Section E.8.

###### Proposition 1 (Full version) .

###### Lemma 7 .

###### Lemma 8 .

###### Lemma 9 .

###### Lemma 10 .

###### Lemma 11 .

###### Lemma 12 .

###### Lemma 13 .

### E.1 Proof of Lemma 7

###### Proof.

According to Lemma 5, for any round $t\in\{1,\cdots,T_{1}\}$, the auxiliary loss is the primary loss to update $\bm{\Theta}_{t}$ of the gating network.
Then based on the update rule of $\bm{\theta}_{t}^{(m)}$ in Eq. 9 and the gradient of $\nabla_{\bm{\theta}^{(m_{t})}_{t}}\mathcal{L}^{(aux)}_{t}$ in Eq. 30, we obtain

$$ $\displaystyle\|\bm{\theta}_{t+1}^{(m_{t})}-\bm{\theta}_{t}^{(m_{t})}\|_{\infty}=$ $\displaystyle\|\eta\cdot\nabla_{\bm{\theta}^{(m_{t})}_{t}}\mathcal{L}^{(aux)}_ {t}\|_{\infty}$ $\displaystyle=$ $\displaystyle\mathcal{O}(\sigma_{0}^{0.5}\eta)\cdot\Big{\|}\pi_{m_{t}}(\mathbf {X}_{t},\mathbf{\Theta}_{t})\cdot\sum_{m^{\prime}\neq m_{t}}\pi_{m^{\prime}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\sum_{i\in[s_{t}]}\mathbf{X}_{t,i}\Big {\|}_{\infty}$ $\displaystyle=$ $\displaystyle\mathcal{O}(\sigma_{0}),$ $$

based on the fact that $\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\sum_{m^{\prime}\neq m_{t}
}\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})=\pi_{m_{t}}(\mathbf{X}_{
t},\mathbf{\Theta}_{t})\cdot(1-\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})
)\leq\frac{1}{4}$ and $\|X_{t}\|_{\infty}=\mathcal{O}(1)$.

While for any $m\neq m_{t}$, we calculate

$$ $\displaystyle\|\bm{\theta}_{t+1}^{(m)}-\bm{\theta}_{t}^{(m)}\|_{\infty}=$ $\displaystyle\|\eta\cdot\nabla_{\bm{\theta}^{(m)}_{t}}\mathcal{L}^{(aux)}_{t} \|_{\infty}$ $\displaystyle=$ $\displaystyle\mathcal{O}(\sigma_{0}^{0.5}\eta)\cdot\Big{\|}\pi_{m_{t}}(\mathbf {X}_{t},\mathbf{\Theta}_{t})\cdot\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t}) \cdot\sum_{i\in[s_{t}]}\mathbf{X}_{t,i}\Big{\|}_{\infty}$ $\displaystyle=$ $\displaystyle\mathcal{O}(M^{-1}\sigma_{0}),$ $$

due to the fact that $\pi_{m_{t}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\cdot\pi_{m}(\mathbf{X}_{t},
\mathbf{\Theta}_{t})=\mathcal{O}(M^{-1})$.

Note that by Eq. 30, we have $\nabla_{\bm{\theta}^{(m_{t})}_{t}}\mathcal{L}^{(aux)}_{t}>0$ and $\nabla_{\bm{\theta}^{(m)}_{t}}\mathcal{L}^{(aux)}_{t}<0$ for any $m\neq m_{t}$. Consequently, for expert $m_{t}$, its corresponding output $h_{m_{t}}$ at the gating network will be reduced by $\mathcal{O}(\sigma_{0})$ for the same feature signal $\bm{v}_{n}$ since task $t+1$. While for any expert $m\neq m_{t}$, its corresponding output $h_{m}$ is increased by $\mathcal{O}(M^{-1}\sigma_{0})$.
∎

###### Proof.

### E.2 Proof of Lemma 8

###### Proof.

By the symmetric property, we have that for any $m\in[M]$, $\mathbb{E}[f_{T_{1}}^{(m)}]=\frac{1}{M}$.

By Hoeffding’s inequality, we obtain

$$ $\displaystyle\mathbb{P}(|f_{T_{1}}^{(m)}-\frac{1}{M}|\leq\epsilon)\geq 1-2\exp {(-2\epsilon^{2}T_{1})}.$ $$

Then we further obtain

$$ $\displaystyle\mathbb{P}(|f_{T_{1}}^{(m)}-\frac{1}{M}|\leq\epsilon,\forall m\in [M])\geq$ $\displaystyle(1-2\exp{(-2\epsilon^{2}T_{1})})^{M}$ $\displaystyle\geq$ $\displaystyle 1-2M\exp{(-2\epsilon^{2}T_{1})}).$ $$

Let $\delta=1-2M\exp{(-2\epsilon^{2}T_{1})})$. Then we obtain $\epsilon=\mathcal{O}(\eta^{0.5}M^{-1})$. Subsequently, there is a probability of at least $1-\delta$ that $\big{|}f_{T_{1}}^{(m)}-\frac{1}{M}\big{|}=\mathcal{O}(\eta^{0.5}M^{-1})$.
∎

###### Proof.

### E.3 Proof of Lemma 9

###### Proof.

Based on Lemma 7 and Lemma 8 and their corresponding proofs above, we can prove Lemma 9 below.

For experts $m$ and $m^{\prime}$, they are selected by the router for $T_{1}\cdot f_{T_{1}}^{(m)}$ and $T_{1}\cdot f_{T_{1}}^{(m^{\prime})}$ times during the exploration stage, respectively. Therefore, we obtain

$$ $\displaystyle\|\bm{\theta}_{T_{1}}^{(m)}\|_{\infty}$ $\displaystyle=f_{T_{1}}^{(m)}\cdot T_{1}\cdot\mathcal{O}(\sigma_{0})-(1-f_{T_{ 1}}^{(m)})\cdot T_{1}\cdot\mathcal{O}(M^{-1}\sigma_{0}),$ $\displaystyle\|\bm{\theta}_{T_{1}}^{(m^{\prime})}\|_{\infty}$ $\displaystyle=f_{T_{1}}^{(m^{\prime})}\cdot T_{1}\cdot\mathcal{O}(\sigma_{0})- (1-f_{T_{1}}^{(m^{\prime})})\cdot T_{1}\cdot\mathcal{O}(M^{-1}\sigma_{0}).$ $$

Then by Eq. 9 and Lemma 7, we calculate

$$ $\displaystyle\Big{\|}\bm{\theta}_{T_{1}}^{(m)}-\bm{\theta}_{T_{1}}^{(m^{\prime })}\big{\|}_{\infty}$ $\displaystyle=\Big{|}\big{(}f_{T_{1}}^{(m)}-f_{T_{1}}^{(m^{\prime})}\big{)} \cdot T_{1}\cdot\mathcal{O}(\sigma_{0})-\big{(}(1-f_{T_{1}}^{(m)})-(1-f_{T_{1} }^{(m^{\prime})})\big{)}\cdot T_{1}\cdot\mathcal{O}(M^{-1}\sigma_{0})\big{|}$ $\displaystyle=|f_{T_{1}}^{(m)}-f_{T_{1}}^{(m^{\prime})}|\cdot T_{1}\cdot \mathcal{O}(\sigma_{0})$ $\displaystyle=\mathcal{O}(\eta^{-0.5}\sigma_{0}),$ $$

where the first equality is derived based on the update steps in Lemma 7, and the last equality is because of $T_{1}\cdot|f_{T_{1}}^{(m)}-f_{T_{1}}^{(m^{\prime})}|=\mathcal{O}(\eta^{-0.5})$ by Eq. 32 in Lemma 8.
∎

###### Proof.

### E.4 Proof of Lemma 10

###### Proof.

At any round $t$, we calculate

$$ $\displaystyle|\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{m^{\prime}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})|$ $\displaystyle=\Big{|}\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\exp{ (h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm {\theta}_{t}^{(m^{\prime})})}-\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_ {t})\Big{|}$ $\displaystyle=\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})\Big{|}\exp{ (h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm {\theta}_{t}^{(m^{\prime})}))}-1\Big{|},$ $$

where the first equality is by solving Eq. 2. Then if $\delta_{\mathbf{\Theta}_{t}}$ is close to 0 0, by applying Taylor series with sufficiently small $\delta_{\mathbf{\Theta}}$, we obtain

$$ $\displaystyle|\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{m^{\prime}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})|$ $\displaystyle\approx\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})|h_{m} (\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm{ \theta}_{t}^{(m^{\prime})})|$ $\displaystyle=\mathcal{O}(\delta_{\mathbf{\Theta}}),$ $$

where the last equality is because of $\pi_{m}(\tilde{\mathbf{X}}_{t},\mathbf{\Theta}_{t})\leq 1$.

While if $\delta_{\mathbf{\Theta}_{t}}$ is not sufficiently small, we obtain

$$ $\displaystyle|\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{m^{\prime}}( \mathbf{X}_{t},\mathbf{\Theta}_{t})|$ $\displaystyle>\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})|h_{m}( \mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm{\theta }_{t}^{(m^{\prime})})|$ $\displaystyle=\Omega(\delta_{\mathbf{\Theta}}).$ $$

This completes the proof.
∎

###### Proof.

### E.5 Proof of Lemma 11

###### Proof.

If $M>N$, by the symmetric property, we have that for all $n\in[N],m\in[M]$,

$$ $\displaystyle\mathbb{P}(m\in\mathcal{M}_{n})=\frac{1}{N}.$ $$

Therefore, the probability that $|\mathcal{M}_{n}|$ at least includes one expert is

$$ $\displaystyle\mathbb{P}(|\mathcal{M}_{n}|\geq 1)\geq 1-\Big{(}1-\frac{1}{N} \Big{)}^{M}.$ $$

By applying union bound, we obtain

$$ $\displaystyle\mathbb{P}(|\mathcal{M}_{n}|\geq 1,\forall n)\geq\Big{(}1-\Big{(} 1-\frac{1}{N}\Big{)}^{M}\Big{)}^{N}\geq 1-N\Big{(}1-\frac{1}{N}\Big{)}^{M}\geq 1 -N\exp{\Big{(}-\frac{M}{N}\Big{)}}\geq 1-\delta,$ $$

where the second inequality is because $(1-N^{-1})^{M}$ is small enough, and the last inequality is because of $M=\Omega\big{(}N\ln\big{(}\frac{N}{\delta}\big{)}\big{)}$.

While if $M<N$, we can use the same method to prove that $\mathbb{P}(|\mathcal{M}_{k}|\geq 1,\forall k)\geq 1-\delta$, given $M=\Omega\big{(}K\ln\big{(}\frac{K}{\delta}\big{)}\big{)}$ and $\mathbb{P}(m\in\mathcal{M}_{k})=\frac{1}{K}$ by the symmetric property.
∎

###### Proof.

### E.6 Proof of Lemma 12

###### Proof.

In the case of $M>N$, as $|\mathcal{M}_{n}|=1$, if task $n_{t}$ with $n_{t}=n$ is routed to the correct expert $m_{t}\in\mathcal{M}_{n}$, we have $\bm{w}^{m_{t}}_{t}=\bm{w}^{m_{t}}_{t-1}$ by (5). Consequently, the caused locality loss $\mathcal{L}^{loc}_{t}(\bm{\Theta}_{t},\mathcal{D}_{t})=0$, based on its definition in Eq. 6.

In the case of $M<N$, as $|\mathcal{M}_{k}|\geq 1$ for each cluster $k$, if task $n_{t}$ with $\bm{w}_{n_{t}}\in\mathcal{W}_{k}$ is routed to the correct expert $m_{t}\in\mathcal{M}_{k}$, we have

$$ $\displaystyle\|\bm{w}^{(m_{t})}_{t}-\bm{w}^{(m_{t})}_{t-1}\|_{\infty}$ $\displaystyle=\|\mathbf{X}_{t}(\mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1}( \mathbf{y}_{t}-\mathbf{X}_{t}^{\top}\bm{w}_{t-1}^{(m_{t})})\|_{\infty}$ $\displaystyle=\|\mathbf{X}_{t}(\mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1} \mathbf{X}_{t}^{\top}(\bm{w}_{n_{t}}-\bm{w}_{t-1}^{(m_{t})})\|_{\infty}$ $\displaystyle=\mathcal{O}(\|\bm{w}_{t}-\bm{w}_{t-1}^{(m_{t})}\|_{\infty})$ $\displaystyle=\mathcal{O}(\sigma_{0}^{1.5}),$ $$

where the second equality is because of $\mathbf{y}_{t}=\mathbf{X}_{t}^{\top}\bm{w}_{t}$, and the third equality is because of $\|\mathbf{X}_{t}\|_{\infty}=\mathcal{O}(1)$. Therefore, we obtain $\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}^{loc}_{t}=\mathcal{O}(\sigma_{0}^{1.
5})$ by solving Eq. 27, for any $m\in[M]$.
∎

###### Proof.

### E.7 Proof of Lemma 13

###### Proof.

We first focus on the $M>N$ case to prove Lemma 13. Based on Eq. 35 in Proposition 1, we obtain $\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})-\pi_{m}(\mathbf{X}_{n^{\prime}
},\mathbf{\Theta}_{T_{1}})=\Omega(\sigma_{0}^{0.5})$ for $m\in\mathcal{M}_{n}$, given $\|\bm{\theta}_{t}^{(m)}\|_{\infty}=\mathcal{O}(\sigma_{0}^{0.5})$ derived in Lemma 6. To prove Eq. 33, we will prove that $\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})-\pi_{m}(\mathbf{X}_{n^{\prime}},
\mathbf{\Theta}_{t})=\Omega(\sigma_{0}^{0.5})$ holds for any $t\geq T_{1}+1$.

Based on Lemma 5, we have $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}\|_{\infty}=\mathcal{O}(
\sigma_{0})$, leading to $\langle\bm{\theta}_{t+1}^{(m_{t})}-\bm{\theta}_{t}^{(m_{t})},\bm{v}_{n}\rangle
=-\mathcal{O}(\sigma_{0}^{1.5})$ for expert $m_{t}$ and $\langle\bm{\theta}_{t+1}^{(m)}-\bm{\theta}_{t}^{(m)},\bm{v}_{n}\rangle=
\mathcal{O}(\sigma_{0}^{1.5})$ for any other expert $m\neq m_{t}$. As $T_{2}=\lceil\sigma_{0}^{-0.5}\eta^{-1}M\rceil$, we calculate

$$ $\displaystyle\|\bm{\theta}_{T_{2}}^{(m)}-\bm{\theta}_{T_{1}+1}^{(m)}\|_{\infty}$ $\displaystyle<\mathcal{O}(\sigma_{0}^{0.5})-\|\nabla_{\bm{\theta}_{T_{1}}^{(m) }}\mathcal{L}_{T_{1}}^{task}\|_{\infty}\cdot\eta\cdot(T_{2}-T_{1})$ $\displaystyle\leq\mathcal{O}(\sigma_{0}^{0.5})-\mathcal{O}(\sigma_{0})\cdot \mathcal{O}(\sigma_{0}^{-0.25})$ $\displaystyle=\mathcal{O}(\sigma_{0}^{0.5}).$ $$

Therefore, $\|\bm{\theta}_{t}^{(m)}\|_{\infty}=\mathcal{O}(\sigma_{0}^{0.5})$ is always true for $t\in\{T_{1}+1,\cdots,T_{2}\}$, and thus $\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})-\pi_{m}(\mathbf{X}_{n^{\prime}},
\mathbf{\Theta}_{t})=\Omega(\sigma_{0}^{0.5})$ holds, meaning $\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{n^{\prime}},
\mathbf{\Theta}_{t}),\forall m\in[M]$.

For the case of $M<N$, we can use the same method to prove Eq. 33. This completes the proof.
∎

###### Proof.

### E.8 Final proof of Proposition 1

###### Proof.

In the case of $M>N$, to prove Proposition 1, we equivalently prove that at the end of the exploration stage with $t=T_{1}$, for any two experts $m\in\mathcal{M}_{n}$ and $m^{\prime}\in\mathcal{M}_{n^{\prime}}$ with $n\neq n^{\prime}$, the following properties hold:

$$ $\displaystyle\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m^{\prime}}( \mathbf{X}_{n},\mathbf{\Theta}_{t}),\ \ \pi_{m^{\prime}}(\mathbf{X}_{n^{\prime }},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{n^{\prime}},\mathbf{\Theta}_{t}),$ (34) $$

where $\mathbf{X}_{n}$ and $\mathbf{X}_{n^{\prime}}$ contain feature signals $\bm{v}_{n}$ and $\bm{v}_{n^{\prime}}$, respectively.
Based on Eq. 34, we have each expert $m\in[M]$ stabilizes within an expert set $\mathcal{M}_{n}$.

According to Lemma 1, the gating network only focuses on feature signals. Then for each expert $m$, we calculate

$$ $\displaystyle|h_{m}(\mathbf{X}_{n},\bm{\theta}_{t}^{(m)})-h_{m}(\mathbf{X}_{n^ {\prime}},\bm{\theta}_{t}^{(m)})|$ $\displaystyle=|\langle\bm{\theta}_{t}^{(m)},\bm{v}_{n}-\bm{v}_{n^{\prime}}\rangle|$ $\displaystyle=\|\bm{\theta}_{t}^{(m)}\|_{\infty}\cdot\|\bm{v}_{n}-\bm{v}_{n^{ \prime}}\|_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}^{0.5}),$ $$

where the last equality is because of $\|\bm{\theta}_{t}^{(m)}\|_{\infty}=\mathcal{O}(\sigma_{0}^{0.5})$ in Lemma 6 and $\|\bm{v}_{n}-\bm{v}_{n^{\prime}}\|_{\infty}=\mathcal{O}(1)$.

Then based on Lemma 10, we obtain

$$ $\displaystyle|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})-\pi_{m}(\mathbf{X}_{ n^{\prime}},\mathbf{\Theta}_{t})|=\Omega(\sigma_{0}^{0.5}).$ (35) $$

Next, we prove Eq. 34 by contradiction. Assume there exist two experts $m\in\mathcal{M}_{n}$ and $m^{\prime}\in\mathcal{M}_{n^{\prime}}$ such that

$$ $\displaystyle\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m^{\prime}}( \mathbf{X}_{n},\mathbf{\Theta}_{t}),\ \ \pi_{m}(\mathbf{X}_{n^{\prime}}, \mathbf{\Theta}_{t})>\pi_{m^{\prime}}(\mathbf{X}_{n^{\prime}},\mathbf{\Theta}_ {t}),$ $$

which is equivalent to

$$ $\displaystyle\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{n ^{\prime}},\mathbf{\Theta}_{t})>\pi_{m^{\prime}}(\mathbf{X}_{n^{\prime}}, \mathbf{\Theta}_{t})>\pi_{m^{\prime}}(\mathbf{X}_{n},\mathbf{\Theta}_{t}),$ (36) $$

because of $\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{n^{\prime}},
\mathbf{\Theta}_{t})$ and $\pi_{m^{\prime}}(\mathbf{X}_{n^{\prime}},\mathbf{\Theta}_{t})>\pi_{m^{\prime}}
(\mathbf{X}_{n},\mathbf{\Theta}_{t})$ based on the definition of expert set $\mathcal{M}_{n}$ in Eq. 11. Then we prove Eq. 36 does not exist at $t=T_{1}$.

For task $t=T_{1}$, we calculate

$$ $\displaystyle|h_{m}(\mathbf{X}_{n},\bm{\theta}_{T_{1}}^{(m)})-h_{m^{\prime}}( \mathbf{X}_{n},\bm{\theta}_{T_{1}}^{(m)})|$ $\displaystyle\leq\|\bm{\theta}_{T_{1}}^{(m)}-\bm{\theta}_{T_{1}}^{(m^{\prime}) }\|_{\infty}\|\bm{v}_{n}\|_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}\eta^{-0.5}),$ (37) $$

where the first inequality is derived by union bound, and the second equality is because of $\|\bm{v}_{n}\|_{\infty}=\mathcal{O}(1)$ and $\|\bm{\theta}_{T_{1}}^{(m)}-\bm{\theta}_{T_{1}}^{(m^{\prime})}\|_{\infty}=
\mathcal{O}(\sigma_{0}\eta^{-0.5})$ derived in Lemma 9 at the end of the exploration phase.

Then according to Lemma 10 and Eq. 37, we obtain

$$ $\displaystyle|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})-\pi_{m^{\prime}} (\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})|=\mathcal{O}(\sigma_{0}\eta^{-0.5}).$ (38) $$

Based on Eq. 36, we further calculate

$$ $\displaystyle|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})-\pi_{m^{\prime}} (\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})|$ $\displaystyle\geq|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})-\pi_{m}( \mathbf{X}_{n^{\prime}},\mathbf{\Theta}_{T_{1}})|$ $\displaystyle=\Omega(\sigma_{0}^{0.5}),$ $$

where the first inequality is derived by Eq. 36, and the last equality is derived in Eq. 35. This contradicts with Eq. 38 as $\sigma_{0}\eta^{-0.5}<\sigma_{0}^{0.5}$ given $\eta=\mathcal{O}(\sigma_{0}^{0.5})$. Therefore, Eq. 36 does not exist for $t=T_{1}$, and Eq. 34 is true for $t=T_{1}$.

Based on Lemma 13, we obtain that each expert set $\mathcal{M}_{n}$ is stable during the router learning stage. Therefore, at any round $t\in\{T_{1}+1,\cdots,T\}$, task $n_{t}$ with ground truth $\bm{w}_{n_{t}}$ will be routed to one of its best experts in $\mathcal{M}_{n_{t}}$. Then based on Lemma 12, we have that $\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{loc}=0$ holds in the router learning stage. Subsequently, $\bm{w}_{t}^{(m)}$ of any expert $m$ remains unchanged, based on Lemma 3.

In the case of $M<N$, we similarly obtain that at the end of the exploration phase with $t=T_{1}$, for any two experts $m\in\mathcal{M}_{k}$ and $m^{\prime}\in\mathcal{M}_{k^{\prime}}$ with $k\neq k^{\prime}$, the following property holds

$$ $\displaystyle\pi_{m}(\mathbf{X}_{k},\mathbf{\Theta}_{t})>\pi_{m^{\prime}}( \mathbf{X}_{k},\mathbf{\Theta}_{t}),\ \ \pi_{m^{\prime}}(\mathbf{X}_{k^{\prime }},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{k^{\prime}},\mathbf{\Theta}_{t}),$ $$

where $\mathbf{X}_{k}$ and $\mathbf{X}_{k^{\prime}}$ contain feature signals $\bm{v}_{k}$ and $\bm{v}_{k^{\prime}}$, respectively.

Then during the router learning stage with $t>T_{1}$, any task $n_{t}$ with $\bm{w}_{n_{t}}\in\mathcal{W}_{k}$ will be routed to the correct expert $m\in\mathcal{M}_{k}$. Let $\bm{w}^{(m)}$ denote the minimum $\ell^{2}$-norm offline solution for expert $m$. Based on the update rule of $\bm{w}_{t}^{(m_{t})}$ in Eq. 5, we calculate

$$ $\displaystyle\bm{w}^{(m_{t})}_{t}-\bm{w}^{(m_{t})}$ $\displaystyle=\bm{w}_{t-1}^{(m_{t})}+\mathbf{X}_{t}(\mathbf{X}_{t}^{\top} \mathbf{X}_{t})^{-1}(\mathbf{y}_{t}-\mathbf{X}_{t}^{\top}\bm{w}_{t-1}^{(m_{t}) })-\bm{w}^{(m_{t})}$ $$

$$ $\displaystyle=(\bm{I}-\mathbf{X}_{t}(\mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1} \mathbf{X}_{t}^{\top})\bm{w}_{t-1}^{(m_{t})}+\mathbf{X}_{t}(\mathbf{X}_{t}^{ \top}\mathbf{X}_{t})^{-1}\mathbf{X}^{\top}_{t}\bm{w}^{(m_{t})}-\bm{w}^{(m_{t})}$ $\displaystyle=(\bm{I}-\mathbf{X}_{t}(\mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1} \mathbf{X}_{t}^{\top})(\bm{w}_{t-1}^{(m_{t})}-\bm{w}^{(m_{t})}),$ $$

where the second equality is because of $\mathbf{y}_{t}=\mathbf{X}^{\top}_{t}\bm{w}^{(m_{t})}$. Define $\bm{P}_{t}=\mathbf{X}_{t}(\mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1}\mathbf{X}_
{t}^{\top}$ for task $n_{t}$, which is the projection operator on the solution space $\bm{w}_{n_{t}}$. Then we obtain

$$ $\displaystyle\bm{w}^{(m)}_{t}-\bm{w}^{(m)}=(\bm{I}-\bm{P}_{t})\cdots(\bm{I}- \bm{P}_{T_{1}+1})(\bm{w}_{T_{1}}^{(m)}-\bm{w}^{(m)})$ $$

for each expert $m\in[M]$.

Since orthogonal projections $\bm{P}_{t}$’s are non-expansive operators, it also follows that

$$ $\displaystyle\forall t\in\{T_{1}+1,\cdots,T\},\|\bm{w}^{(m)}_{t}-\bm{w}^{(m)} \|\leq\|\bm{w}^{(m)}_{t-1}-\bm{w}^{(m)}\|\leq\cdots\leq\|\bm{w}^{(m)}_{T_{1}}- \bm{w}^{(m)}\|.$ $$

As the solution spaces $\mathcal{W}_{k}$ is fixed for each expert $m\in\mathcal{M}_{k}$, we further obtain

$$ $\displaystyle\|\bm{w}_{t}^{(m)}-\bm{w}_{T_{1}+1}^{(m)}\|_{\infty}$ $\displaystyle=\|\bm{w}_{t}^{(m)}-\bm{w}^{(m)}+\bm{w}^{(m)}-\bm{w}_{T_{1}+1}^{( m)}\|_{\infty}$ $\displaystyle\leq\|\bm{w}_{t}^{(m)}-\bm{w}^{(m)}\|_{\infty}+\|\bm{w}_{T_{1}+1} ^{(m)}-\bm{w}^{(m)}\|_{\infty}$ $\displaystyle\leq\max_{\bm{w}_{n},\bm{w}_{n^{\prime}}\in\mathcal{W}_{k}}\|\bm{ w}_{n}-\bm{w}_{n^{\prime}}\|_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}^{1.5}),$ $$

where the first inequality is derived by the union bound, the second inequality is because of the orthogonal projections for the update of $\bm{w}_{t}^{(m)}$ per task, and the last equality is because of $\|\bm{w}_{n}-\bm{w}_{n^{\prime}}\|_{\infty}=\mathcal{O}(\sigma_{0}^{1.5})$ for any two ground truths in the same set $\mathcal{W}_{k}$.
∎

###### Proof.

## Appendix F Full version and proof of Proposition 2

###### Proposition 2 (Full version) .

If the MoE keeps updating $\bm{\Theta}_{t}$ by Eq. 9 at any round $t\in[T]$, we obtain:
1) At round $t_{1}=\lceil\eta^{-1}\sigma_{0}^{-0.25}M\rceil$, the following property holds

$$ $\displaystyle\big{|}h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}^{(m)}_{t_{1}})-h_{m^{ \prime}}(\mathbf{X}_{t_{1}},\bm{\theta}^{(m^{\prime})}_{t_{1}})\big{|}=\begin{ cases}\mathcal{O}(\sigma_{0}^{1.75}),&\text{if }m,m^{\prime}\in\mathcal{M}_{n} \text{ under }M>N\\ &\text{ or }m,m^{\prime}\in\mathcal{M}_{k}\text{ under }M<N,\\ \Theta(\sigma_{0}^{0.75}),&\text{otherwise}.\end{cases}$ $$

2) At round $t_{2}=\lceil\eta^{-1}\sigma_{0}^{-0.75}M\rceil$, the following property holds

$$ $\displaystyle\big{|}h_{m}(\mathbf{X}_{t_{2}},\bm{\theta}^{(m)}_{t_{2}})-h_{m^{ \prime}}(\mathbf{X}_{t_{2}},\bm{\theta}^{(m^{\prime})}_{t_{2}})\big{|}= \mathcal{O}(\sigma_{0}^{1.75}),\forall m,m^{\prime}\in[M].$ $$

We first propose the following lemmas as preliminaries to prove Proposition 2. Then we prove Proposition 2 in Section F.3.

For any two experts $m,m^{\prime}$, define $\Delta_{\mathbf{\Theta}}=|\pi_{m}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{m^{
\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})|$.

###### Lemma 14 .

At any round $t\in\{T_{1}+1,\cdots,t_{1}\}$, $\forall m\neq m_{t}$, the following property holds

$$ $\displaystyle\big{\|}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}- \nabla_{\bm{\theta}_{t}^{(m_{t})}}\mathcal{L}_{t}^{task}\big{\|}_{\infty}= \mathcal{O}\big{(}\sigma_{0}\big{)}.$ (39) $$

Let $\mathbf{X}_{n}$ and $\mathbf{X}_{n^{\prime}}$ denote two feature matrices containing feature signals $\bm{v}_{n}$ and $\bm{v}_{n^{\prime}}$, respectively.

###### Lemma 15 .

In the router learning stage with $t\in\{T_{1}+1,\cdots,t_{1}\}$, for any two experts satisfying 1) $m\in\mathcal{M}_{n}$ and $m^{\prime}\in\mathcal{M}_{n^{\prime}}$ with $n\neq n^{\prime}$ under $M>N$, or 2) $m\in\mathcal{M}_{k}$ and $m^{\prime}\in\mathcal{M}_{k^{\prime}}$ with $\bm{w}_{n}\in\mathcal{W}_{k},\bm{w}_{n^{\prime}}\in\mathcal{W}_{k^{\prime}}$ and $k\neq k^{\prime}$ under $M<N$, the following properties hold:

$$ $\displaystyle\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})>\pi_{m^{\prime}}( \mathbf{X}_{n},\mathbf{\Theta}_{t}),\ \ \pi_{m^{\prime}}(\mathbf{X}_{n^{\prime }},\mathbf{\Theta}_{t})>\pi_{m}(\mathbf{X}_{n^{\prime}},\mathbf{\Theta}_{t}).$ (40) $$

###### Proposition 2 (Full version) .

###### Lemma 14 .

###### Lemma 15 .

### F.1 Proof of Lemma 14

###### Proof.

Based on the proof of Lemma 5, for any $m\neq m_{t}$, we calculate

$$ $\displaystyle\big{\|}\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}_{t}^{task}- \nabla_{\bm{\theta}_{t}^{(m_{t})}}\mathcal{L}_{t}^{task}\big{\|}_{\infty}$ $\displaystyle=\big{\|}(\|\bm{w}_{t}^{(m_{t})}-\bm{w}_{t-1}^{(m_{t})}\|_{2}+ \frac{\alpha M}{t}f_{t}^{m_{t}})\big{(}\frac{\partial\pi_{m_{t}}}{\partial\bm{ \theta}^{(m)}_{t}}-\frac{\partial\pi_{m_{t}}}{\partial\bm{\theta}^{(m_{t})}_{t }}\big{)}\big{\|}_{\infty}$ $\displaystyle=\mathcal{O}\big{(}\sigma_{0}+\frac{\alpha M}{t}\big{)}\cdot\big{ \|}\frac{\partial\pi_{m_{t}}}{\partial\bm{\theta}^{(m)}_{t}}-\frac{\partial\pi _{m_{t}}}{\partial\bm{\theta}^{(m_{t})}_{t}}\big{\|}_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}),$ $$

where the last equality is because of $\pi_{m_{t}(\mathbf{X}_{t},\mathbf{\Theta}_{t})}<1$, $\|\mathbf{X}_{t}\|_{\infty}=\mathcal{O}(1)$ and $\frac{\alpha M}{t}\leq\sigma_{0}$ for any $t\in\{T_{1}+1,\cdots,t_{1}\}$.
∎

###### Proof.

### F.2 Proof of Lemma 15

###### Proof.

We will use the same method as in Section E.8 to prove Lemma 15 by contradiction. Here, we only prove the case of $M>N$. The proof for the case of $M<N$ is similar.

Recall Proposition 1 that Eq. 40 is true at $t=T_{1}+1$. Based on Lemma 13, we have $|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})-\pi_{m}(\mathbf{X}_{n^{\prime}},
\mathbf{\Theta}_{t})|=\Omega(\sigma_{0}^{0.5})$. Then in the following, we aim to prove $|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{T_{1}})-\pi_{m^{\prime}}(\mathbf{X}_{
n},\mathbf{\Theta}_{T_{1}})|=\mathcal{O}(\sigma_{0}\eta^{-0.5})$ in Eq. 38 is always true for any $m\in\mathcal{M}_{n}$ and $m^{\prime}\in\mathcal{M}_{n^{\prime}}$ during the router learning stage. Then according to the proof of Proposition 1 in Section E.8, Eq. 40 is also true.

Under Eq. 40 at $t=T_{1}+1$, the router will route task $t$ to its best expert $m_{t}\in\mathcal{M}_{n_{t}}$, leading to $\nabla_{\bm{\theta}_{t}^{(m)}}^{*}\mathcal{L}_{t}^{loc}=0$ by Lemma 12. Therefore, $\nabla_{\bm{\theta}_{t}^{(m)}}^{*}\mathcal{L}_{t}^{task}=\mathcal{O}(\sigma_{0})$ makes $\langle\bm{\theta}_{t+1}^{(m_{t})}-\bm{\theta}_{t}^{(m_{t})},\bm{v}_{n}\rangle
=-\mathcal{O}(\sigma_{0}^{1.5})$ for expert $m_{t}$ and $\langle\bm{\theta}_{t+1}^{(m)}-\bm{\theta}_{t}^{(m)},\bm{v}_{n}\rangle=
\mathcal{O}(\sigma_{0}^{1.5})$ any other expert $m\neq m_{t}$ at task $t=T_{1}+1$.

Subsequently, for any two experts $m\in\mathcal{M}_{n}$ and $m^{\prime}\in\mathcal{M}_{n^{\prime}}$, we calculate

$$ $\displaystyle\|\bm{\theta}_{t_{1}}^{(m)}-\bm{\theta}_{t_{1}}^{(m^{\prime})}\|_ {\infty}$ $\displaystyle\leq\|\bm{\theta}_{T_{1}+2}^{(m)}-\bm{\theta}_{T_{1}+2}^{(m^{ \prime})}\|_{\infty}+(t_{1}-T_{1})\cdot\mathcal{O}(\sigma_{0}^{1.5})$ $\displaystyle\leq\mathcal{O}(\sigma_{0}\eta^{-0.5})+\mathcal{O}(\eta^{-1} \sigma_{0}^{-0.25})\cdot\mathcal{O}(\sigma_{0}^{1.5})$ $\displaystyle=\mathcal{O}(\sigma_{0}\eta^{-0.5}),$ $$

where the first inequality is because of $\langle\bm{\theta}_{t+1}^{(m)}-\bm{\theta}_{t}^{(m)},\bm{v}_{n}\rangle=
\mathcal{O}(\sigma_{0}^{1.5})$, and the second inequality is because of $t_{1}-T_{1}\leq t_{1}$.

As $\|\bm{\theta}_{t_{1}}^{(m)}-\bm{\theta}_{t_{1}}^{(m^{\prime})}\|_{\infty}=
\mathcal{O}(\sigma_{0}\eta^{-0.5})$ and $|\pi_{m}(\mathbf{X}_{n},\mathbf{\Theta}_{t})-\pi_{m}(\mathbf{X}_{n^{\prime}},
\mathbf{\Theta}_{t})|=\Omega(\sigma_{0}^{0.5})$, Eq. 40 is true for any $t\in\{T_{1}+2,\cdots,t_{1}\}$, based on our proof of Proposition 1.
∎

###### Proof.

### F.3 Final proof of Proposition 2

###### Proof.

We first focus on the $M>N$ case to prove $|h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m)})-h_{m^{\prime}}(\mathbf{X}
_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{\prime})})|=\mathcal{O}(\sigma_{0}^{1.75})$ for any two different experts $m,m^{\prime}\in\mathcal{M}_{n}$ in the same expert set in Eq. 12. Then we prove $|h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m)})-h_{m^{\prime}}(\mathbf{X}
_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{\prime})})|=\Theta(\sigma_{0}^{0.75})$ for any two experts $m\in\mathcal{M}_{n}$ and $m\in\mathcal{M}_{n^{\prime}}$ in different expert sets in Eq. 12. After that, we prove Eq. 13 at round $t_{2}=\lceil\eta^{-1}\sigma_{0}^{-0.75}M\rceil$. Finally, we prove that the above analysis can be generalized to the case of $M<N$.

In the case of $M>N$, let $M^{\prime}$ and $m^{\prime}$ denote the two experts within set $\mathcal{M}_{n}$ with the maximum and minimum softmax values, respectively. In other words, we have

$$ $\displaystyle M^{\prime}=\arg\max_{m\in\mathcal{M}_{n}}\{\pi_{m}(\mathbf{X}_{t },\mathbf{\Theta}_{t})\},\ m^{\prime}=\arg\min_{m\in\mathcal{M}_{n}}\{\pi_{m}( \mathbf{X}_{t},\mathbf{\Theta}_{t})\},$ (41) $$

where $\bm{v}_{n}\in\mathbf{X}_{t}$. If the two experts satisfies $|h_{M^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(M^{\prime})})-h_{m^{
\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{\prime})})|=\mathcal{O}(
\sigma_{0}^{1.75})$, then this equation holds for any two experts in $\mathcal{M}_{t}$.

At the beginning of the router learning stage, we have

$$ $\displaystyle|\pi_{M^{\prime}}(\mathbf{X}_{T_{1}},\mathbf{\Theta}_{T_{1}})-\pi _{m^{\prime}}(\mathbf{X}_{T_{1}},\mathbf{\Theta}_{T_{1}})|=\mathcal{O}(\sigma_ {0}\eta^{-0.5})=\mathcal{O}(\sigma_{0}^{0.75}),$ $$

based on Proposition 1.

According to the routing strategy in Eq. 1, if the new task $t$ has ground truth $\bm{w}_{n}$, it is always routed to expert $M^{\prime}$ until its softmax value is reduced to smaller than others.
Therefore, we calculate the reduced output of gating network for expert $M^{\prime}$ in the router learning stage:

$$ $\displaystyle\langle\bm{\theta}_{T_{1}+1}^{(M^{\prime})}-\bm{\theta}_{t_{1}}^{ (M^{\prime})},\bm{v}_{n}\rangle$ $\displaystyle\leq\mathcal{O}(\sigma_{0})\cdot\eta\cdot(t_{1}-T_{1})$ $\displaystyle=\mathcal{O}(\sigma_{0}^{0.75}).$ $$

While for expert $m^{\prime}$, it will not be routed until its softmax value increased to the maximum. Therefore, we similarly calculate the increased gating output $\langle\bm{\theta}_{t_{1}}^{(m^{\prime})}-\bm{\theta}_{T_{1}+1}^{(m^{\prime})}
,\bm{v}_{n}\rangle=\mathcal{O}(\sigma_{0}^{0.75})$ for expert $m^{\prime}$.

Based on Lemma 4 and Lemma 14, the gating network parameters of experts $m^{\prime}$ and $M^{\prime}$ will converge to the same value, with an error smaller than the update step of $\bm{\Theta}_{t}$. Therefore, we obtain

$$ $\displaystyle\|\bm{\theta}_{t_{1}}^{(M^{\prime})}-\bm{\theta}_{t_{1}}^{(m^{ \prime})}\|_{\infty}$ $\displaystyle=\|\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{ task}_{t_{1}-1}\cdot\eta\|_{\infty}$ $\displaystyle=\|\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{aux }_{t_{1}-1}\cdot\eta\|_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}^{1.75}),$ $$

based on the fact that $\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{aux}_{t_{1}-1}=
\mathcal{O}(\sigma_{0}^{1.25})$ and $\eta=\mathcal{O}(\sigma_{0}^{0.5})$. Then according to Lemma 10, we obtain $|h_{M^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(M^{\prime})})-h_{m^{
\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{\prime})})|=\mathcal{O}(
\sigma_{0}^{1.75})$, which also holds for any two experts in the same expert set $\mathcal{M}_{n}$.

Next, we prove $|h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m)})-h_{m^{\prime}}(\mathbf{X}
_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{\prime})})|=\Theta(\sigma_{0}^{0.75})$ in Eq. 12 for expert $m^{\prime}$ in Eq. 41 and another expert $m\notin\mathcal{M}_{n}$.

Let $\bar{m}\in\mathcal{M}_{n^{\prime}}$ denote the index of the expert in other expert sets with the maximum softmax value of dataset $\mathbf{X}_{n}$, where $\bm{v}_{n}\in\mathbf{X}_{t}$. In other words, $\bar{m}=\arg\max_{m\notin\mathcal{M}_{n}}\{\pi_{m}(\mathbf{X}_{t},\mathbf{
\Theta}_{t})\}$. According to the proof of Proposition 1, we obtain $\pi_{m^{\prime}}(\mathbf{X}_{T_{1}},\mathbf{\Theta}_{T_{1}})-\pi_{\bar{m}}(
\mathbf{X}_{T_{1}},\mathbf{\Theta}_{T_{1}})=\mathcal{O}(\sigma_{0}^{0.75})$.
This equation indicates that during the router learning stage with $t\in\{T_{1}+1,\cdots,t_{1}\}$, any task arrival $n_{t}$ with ground truth $\bm{w}_{n_{t}}=\bm{w}_{n}$ will not be routed to expert $\bar{m}$. Therefore, $\pi_{\bar{m}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})$ keeps increasing with $t$.
Then we calculate the difference between the parameter gradient of expert $\bar{m}$ and expert $m^{\prime}$ per round $t$:

$$ $\displaystyle\textstyle\nabla_{\bm{\theta}_{t}^{(\bar{m})}}\mathcal{L}^{task}_ {t}-\nabla_{\bm{\theta}_{t}^{(m^{\prime})}}\mathcal{L}^{task}_{t}$ $\displaystyle\textstyle=\frac{\alpha M}{t}f_{t}^{m_{t}}\pi_{m_{t}}(\mathbf{X}_ {t},\mathbf{\Theta}_{t})(\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})- \pi_{\bar{m}}(\mathbf{X}_{t},\mathbf{\Theta}_{t}))\cdot\sum_{i\in[s_{t}]} \mathbf{X}_{t,i}$ $\displaystyle\geq 0,$ $$

based on the fact that $\pi_{m^{\prime}}(\mathbf{X}_{t},\mathbf{\Theta}_{t})-\pi_{\bar{m}}(\mathbf{X}_
{t},\mathbf{\Theta}_{t})>0$ under Lemma 13. As $\nabla_{\bm{\theta}_{t}^{(\bar{m})}}\mathcal{L}^{task}_{t}<0$ and $\nabla_{\bm{\theta}_{t}^{(m^{\prime})}}\mathcal{L}^{task}_{t}<0$, we obtain that $h_{m^{\prime}}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})-h_{\bar{m}}(
\mathbf{X}_{t},\bm{\theta}_{t}^{(\bar{m})})$ increases with $t$ during the router learning stage. According to our former analysis of $h_{m^{\prime}}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})$, we obtain

$$ $\displaystyle|h_{m^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{ \prime})})-h_{\bar{m}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(\bar{m})})|$ $\displaystyle=$ $\displaystyle|h_{m^{\prime}}(\mathbf{X}_{T_{1}},\bm{\theta}_{T_{1}}^{(m^{ \prime})})-h_{\bar{m}}(\mathbf{X}_{T_{1}},\bm{\theta}_{T_{1}}^{(\bar{m})})|+\| \nabla_{\bm{\theta}_{t}^{(\bar{m})}}\mathcal{L}^{task}_{t}-\nabla_{\bm{\theta} _{t}^{(m^{\prime})}}\mathcal{L}^{task}_{t}\|_{\infty}\cdot\eta\cdot(t_{1}-T_{1})$ $\displaystyle=$ $\displaystyle\mathcal{O}(\sigma_{0}^{0.75})+\Theta(\sigma_{0}^{0.75})=\Theta( \sigma_{0}^{0.75}),$ $$

where the first equality is because of $\|\nabla_{\bm{\theta}_{t}^{(\bar{m})}}\mathcal{L}^{task}_{t}-\nabla_{\bm{
\theta}_{t}^{(m^{\prime})}}\mathcal{L}^{task}_{t}\|_{\infty}=\mathcal{O}(
\sigma_{0})$. This completes the proof of Eq. 12.

Subsequently, we prove $\big{|}h_{m}(\mathbf{X}_{t_{2}},\bm{\theta}^{(m)}_{t_{2}})-h_{m^{\prime}}(
\mathbf{X}_{t_{2}},\bm{\theta}^{(m^{\prime})}_{t_{2}})\big{|}=\mathcal{O}(
\sigma_{0}^{1.75}),\forall m,m^{\prime}\in[M]$ in Eq. 13 by proving $|h_{M^{\prime}}(\mathbf{X}_{t_{2}},\bm{\theta}^{(M^{\prime})}_{t_{2}})-h_{m}(
\mathbf{X}_{t_{2}},\bm{\theta}^{(m)}_{t_{2}})|=\mathcal{O}(\sigma_{0}^{1.75})$ between expert $M^{\prime}\in\mathcal{M}_{n}$ in Eq. 41 and any other expert $m\notin\mathcal{M}_{n}$.

Based on Lemma 7, we obtain

$$ $\displaystyle\langle\bm{\theta}_{t+1}^{(m)}-\bm{\theta}_{t}^{(m)},\bm{v}_{n} \rangle=\begin{cases}-\mathcal{O}(\sigma_{0}^{1.25}),&\text{if }m=m_{t},\\ \mathcal{O}(M^{-1}\sigma_{0}^{1.25}),&\text{if }m\neq m_{t}.\end{cases}$ $$

According to our analysis above, expert $M^{\prime}\in\mathcal{M}_{n}$ is periodically selected by the router for training task arrivals $n_{t}=n$ during $t\in\{t_{1},\cdots,t_{2}\}$. After each training of task $n$ at expert $M^{\prime}$, its gate output $h_{M^{\prime}}(\mathbf{X}_{t},\bm{\theta}^{(M^{\prime})}_{t})$ is reduced by $\mathcal{O}(\sigma_{0}^{1.25})$. While at other rounds without being selected, its gate output is increased by $\mathcal{O}(M^{-1}\sigma_{0}^{1.25})$. Under such training behavior, we obtain

$$ $\displaystyle\big{|}h_{M^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}^{(M^{\prime} )}_{t_{1}})-h_{M^{\prime}}(\mathbf{X}_{t_{2}},\bm{\theta}^{(M^{\prime})}_{t_{2 }})\big{|}=\mathcal{O}(\sigma_{0}^{1.75}),$ $$

by assuming $\bm{v}_{n}\in\mathbf{X}_{t_{1}}$ and $\bm{v}_{n}\in\mathbf{X}_{t_{2}}$.

While for expert $m\notin\mathcal{M}_{n}$, its gate output $h_{m}(\mathbf{X}_{t},\bm{\theta}^{(m)}_{t})$ keeps increasing for any data $\mathbf{X}_{t}$ of task $n$.
For any $t\in\{t_{1},\cdots,t_{2}\}$, we have $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}^{aux}_{t}\|_{\infty}=\mathcal{O}(
\sigma_{0}^{1.25})$ for expert $m$. Assuming that expert $m$ is never selected by the router for training task $n_{t}=n$ in the period, we obtain

$$ $\displaystyle|h_{m}(\mathbf{X}_{t_{2}},\bm{\theta}^{(m)}_{t_{2}})-h_{m}( \mathbf{X}_{t_{1}},\bm{\theta}^{(m)}_{t_{1}})|$ $\displaystyle=\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}^{aux}_{t}\|_{\infty} \cdot(t_{2}-t_{1})\cdot\eta$ $\displaystyle>|h_{M^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}^{(M^{\prime})}_{t _{1}})-h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}^{(m)}_{t_{1}})|$ $$

where the inequality is because of $\|\nabla_{\bm{\theta}_{t}^{(m)}}\mathcal{L}^{aux}_{t}\|_{\infty}\cdot(t_{2}-t_
{1})\cdot\eta=\mathcal{O}(\sigma_{0}^{0.5})$ and $|h_{M^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}^{(M^{\prime})}_{t_{1}})-h_{m}(
\mathbf{X}_{t_{1}},\bm{\theta}^{(m)}_{t_{1}})|=\Theta(\sigma_{0}^{0.75})$.
This inequality indicates that there exists a training round $t^{\prime}\in\{t_{1},\cdots,t_{2}\}$ such that $h_{m}(\mathbf{X}_{t^{\prime}},\bm{\theta}^{(m)}_{t^{\prime}})>h_{M^{\prime}}(
\mathbf{X}_{t^{\prime}},\bm{\theta}^{(M^{\prime})}_{t^{\prime}})$ for task arrival $n_{t^{\prime}}=n$.
Consequently, expert $m^{\prime}$ is selected to train task $n$ again, meaning that $m^{\prime}\in\mathcal{M}_{n}$ at round $t^{\prime}$. Then the gating network parameters of experts $m$ and $M^{\prime}$ will converge to the same value, with an error of $\mathcal{O}(\sigma_{0}^{1.75})$, based on Lemma 4 and Lemma 14. This completes the proof of Eq. 13 in the case of $M>N$.

In the case of $M<N$, let $M^{\prime}$ and $m^{\prime}$ denote the experts of set $\mathcal{M}_{k}$ with the maximum and minimum softmax values, respectively. In other words, we have

$$ $\displaystyle M^{\prime}=\arg\max_{m\in\mathcal{M}_{k}}\{\pi_{m}(\mathbf{X}_{t },\mathbf{\Theta}_{t})\},\ m^{\prime}=\arg\min_{m\in\mathcal{M}_{k}}\{\pi_{m}( \mathbf{X}_{t},\mathbf{\Theta}_{t})\},$ $$

where the ground truth of task $t$ satisfies $\bm{w}_{n}\in\mathcal{W}_{k}$.

According to the proof of Proposition 2 in Section F.3, the gating network parameters of experts $m^{\prime}$ and $M^{\prime}$ will converge to the same value at the end of the router learning stage, with an error smaller than the update step of $\bm{\Theta}_{t}$. Therefore, we obtain

$$ $\displaystyle\|\bm{\theta}_{t_{1}}^{(M^{\prime})}-\bm{\theta}_{t_{1}}^{(m^{ \prime})}\|_{\infty}$ $\displaystyle=\|\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{ task}_{t_{1}-1}\cdot\eta\|_{\infty}$ $\displaystyle=\|(\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{ loc}_{t_{1}-1}+\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{aux} _{t_{1}-1})\cdot\eta\|_{\infty}$ $\displaystyle=\mathcal{O}(\sigma_{0}^{1.75}),$ $$

based on the fact that $\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{aux}_{t_{1}-1}=
\mathcal{O}(\sigma_{0}^{1.25})$ and $\nabla_{\bm{\theta}_{t_{1}-1}^{(m_{t_{1}-1})}}\mathcal{L}^{loc}_{t_{1}-1}=
\mathcal{O}(\sigma_{0}^{1.5})$ derived in Lemma 12.
Then we obtain $|h_{M^{\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(M^{\prime})})-h_{m^{
\prime}}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m^{\prime})})|=\mathcal{O}(
\sigma_{0}^{1.75})$, which also holds for any two experts in the same expert set $\mathcal{M}_{k}$.

Similarly, for any two experts in different expert sets, we can derive $\Big{|}h_{m}(\mathbf{X}_{t_{1}},\bm{\theta}_{t_{1}}^{(m)})-h_{m^{\prime}}(
\mathbf{X}_{t_{1}},\bm{\theta}_{t-1}^{(m^{\prime})})\Big{|}=\Theta(\sigma_{0}^
{0.75})$. For training round $t_{2}$, the proof for the case of $M<N$ is the same as the case of $M>N$ above, and thus we skip it here.
∎

###### Proof.

## Appendix G Full version and proof of Proposition 3

###### Proposition 3 (Full version) .

Under Algorithm 1, the MoE terminates updating $\bm{\Theta}_{t}$ since round $T_{2}=\mathcal{O}(\eta^{-1}\sigma_{0}^{-0.25}M)$. Then for any task arrival $n_{t}$ at $t>T_{2}$, the following property holds:

1) If $M>N$, the router selects any expert $m\in\mathcal{M}_{n_{t}}$ with an identical probability of $\frac{1}{|\mathcal{M}_{n_{t}}|}$, where $|\mathcal{M}_{n_{t}}|$ is the number of experts in set $\mathcal{M}_{n}$.

2) If $M<N$ and $\bm{w}_{n_{t}}\in\mathcal{W}_{k}$, the router selects any expert $m\in\mathcal{M}_{k}$, with an identical probability of $\frac{1}{|\mathcal{M}_{k}|}$, where $|\mathcal{M}_{k}|$ is the number of experts in set $\mathcal{M}_{k}$.

###### Proof.

In the case of $M>N$, according to Algorithm 1 and Proposition 2, after the termination of gating network update, the following properties hold: 1) $|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm
{\theta}_{t}^{(m^{\prime})})|=\Theta(\sigma_{0}^{0.75})$ for any $m\in\mathcal{M}_{n}$ and $m^{\prime}\in\mathcal{M}_{n^{\prime}}$ and 2) $|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm
{\theta}_{t}^{(m^{\prime})})|=\mathcal{O}(\Gamma)$ for any $m,m^{\prime}\in\mathcal{M}_{n}$, where $\Gamma=\mathcal{O}(\sigma_{0}^{1.25}).$

If the ground truth of task arrival $n_{t}$ satisfies $\bm{w}_{n_{t}}=\bm{w}_{n}$, for any experts $m\in\mathcal{M}_{n}$ and $m^{\prime}\notin\mathcal{M}_{n}$, we have

$$ $\displaystyle h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})+r_{t}^{(m)}-(h_{m^{ \prime}}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})+r_{t}^{(m^{\prime})})$ $\displaystyle\geq h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}( \mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})+r_{t}^{(m^{\prime})}$ $\displaystyle=\Theta(\sigma_{0}^{0.75}),$ $$

given $r_{t}^{(m^{\prime})}=\Theta(\sigma_{0}^{1.25})$ and $h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm{
\theta}_{t}^{(m^{\prime})})=\Theta(\sigma_{0}^{0.75})$. Therefore, any expert $m^{\prime}\notin\mathcal{M}_{n}$ will not be selected to learn task $t$, and only experts in set $\mathcal{M}_{n}$ will be selected.

For any experts $m\in\mathcal{M}_{n}$, we calculate

$$ $\displaystyle\mathbb{P}\Big{(}m_{t}=m|m\in\mathcal{M}_{n}\Big{)}$ $\displaystyle=\mathbb{P}\Big{(}m=\arg\max_{m^{\prime}\in\mathcal{M}_{n}}\Big{ \{}h_{m^{\prime}}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})+r_{t}^{(m^{ \prime})}\Big{\}}\Big{)}$ $\displaystyle=\mathbb{P}\Big{(}h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})+r_{ t}^{(m)}-(h_{m^{\prime}}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})+r_{t}^ {(m^{\prime})})>0,\forall m^{\prime}\in\mathcal{M}_{n}\Big{)}$ $\displaystyle=\mathbb{P}\Big{(}r_{t}^{(m)}>r_{t}^{(m^{\prime})},\forall m^{ \prime}\in\mathcal{M}_{n}\Big{)}=\frac{1}{|\mathcal{M}_{n}|},$ $$

where the third equality is because of $r_{t}^{(m)}=\Theta(\sigma_{0}^{1.25})$ and $|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm
{\theta}_{t}^{(m^{\prime})})|=\mathcal{O}(\sigma_{0}^{1.25})$ derived under Algorithm 1, and the last equality is due to the fact that $r_{t}^{(m)}$ satisfies a uniform distribution $\text{Unif}[0,\lambda]$.

In the case of $M<N$, we similarly derive the following properties: 1) $|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm
{\theta}_{t}^{(m^{\prime})})|=\Theta(\sigma_{0}^{0.75})$ for any $m\in\mathcal{M}_{k}$ and $m^{\prime}\in\mathcal{M}_{k^{\prime}}$ and 2) $|h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})-h_{m^{\prime}}(\mathbf{X}_{t},\bm
{\theta}_{t}^{(m^{\prime})})|=\mathcal{O}(\Gamma)$ for any $m,m^{\prime}\in\mathcal{M}_{k}$. Based on the two properties, $h_{m}(\mathbf{X}_{t},\bm{\theta}_{t}^{(m)})+r_{t}^{(m)}-(h_{m^{\prime}}(
\mathbf{X}_{t},\bm{\theta}_{t}^{(m^{\prime})})+r_{t}^{(m^{\prime})})=\Theta(
\sigma_{0}^{0.75})$ is always true for any two experts $m$ and $m^{\prime}$ not in the same expert set $\mathcal{M}_{k}$. Furthermore, we can similarly calculate

$$ $\displaystyle\mathbb{P}\Big{(}m_{t}=m|m\in\mathcal{M}_{k}\Big{)}=\mathbb{P} \Big{(}r_{t}^{(m)}>r_{t}^{(m^{\prime})},\forall m^{\prime}\in\mathcal{M}_{k} \Big{)}=\frac{1}{|\mathcal{M}_{k}|}.$ $$

This completes the proof of Proposition 3.
∎

###### Proposition 3 (Full version) .

###### Proof.

## Appendix H Proof of Proposition 4

###### Proof.

In the single-expert system, based on the definition of forgetting in Eq. 15 and Eq. 42 in Lemma 16, for any training rounds $t\in[T]$ and $i\in\{1,\cdots,t\}$, we calculate:

$$ $\displaystyle\mathbb{E}[F_{t}]$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\mathbb{E}\Big{[}\|\bm{w}_{t}^{(m_{ i})}-\bm{w}_{n_{i}}\|^{2}-\|\bm{w}_{n_{i}}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}\Big{]}$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\Big{\{}(r^{t}-r^{i})\mathbb{E}[\| \bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{t}(1-r)r^{t-l}\mathbb{E}[\|\bm{w}_{n_{l}}- \bm{w}_{n_{i}}\|^{2}]$ $\displaystyle\quad\quad\quad\quad\quad\quad-\sum_{j=1}^{i}(1-r)r^{i-j}\mathbb{ E}[\|\bm{w}_{n_{j}}-\bm{w}_{n_{i}}\|^{2}]\Big{\}}$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\Big{\{}\frac{r^{T}-r^{i}}{N}\sum_{ n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{r^{i}-r^{t}}{N^{2}}\sum_{n\neq n^{\prime}}^{N }\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}\Big{\}},$ $$

where we let $\bm{w}_{n_{i}}$ denote the ground truth of the task arrival at round $i$.
Here the last equality is derived by $\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]=\frac{1}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}$ and

$$ $\displaystyle\textstyle\mathbb{E}[\|\bm{w}_{n_{j}}-\bm{w}_{n_{i}}\|^{2}]= \mathbb{E}[\frac{1}{N}\sum_{n=1}^{N}\|\bm{w}_{n_{j}}-\bm{w}_{n}\|^{2}]=\frac{1 }{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $$

when there is only a single expert.

Similarly, we can calculate the generalization error

$$ $\displaystyle\textstyle\mathbb{E}[G_{T}]$ $\displaystyle\textstyle=\frac{1}{T}\sum_{i=1}^{T}\mathbb{E}[\|\bm{w}_{T}^{(m_{ i})}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle\textstyle=\frac{1}{T}\sum_{i=1}^{T}\Big{(}r^{T}\mathbb{E}[\|\bm{ w}_{n_{i}}\|^{2}]+\sum_{l=1}^{T}(1-r)r^{T-l}\mathbb{E}[\|\bm{w}_{n_{l}}-\bm{w} _{n_{i}}\|^{2}]\Big{)}$ $\displaystyle\textstyle=\frac{r^{T}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{ 1-r^{T}}{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n}-\bm{w}_{n}^{\prime}\|^{2},$ $$

where the second equality is because of Eq. 42 in Lemma 16.
This completes the proof of Proposition 4.
∎

###### Proof.

## Appendix I Proof of Theorem 1

Before proving Theorem 1, we first propose the following lemma. Then we formally prove Theorem 1 in Section I.2.

For expert $m$, let $\tau^{(m)}(l)\in\{1,\cdots,T_{1}\}$ represent the training round of the $l$-th time that the router selects expert $m$ during the exploration stage. For instance, $\tau^{(1)}(2)=5$ indicates that round $t=5$ is the second time the router selects expert 1.

###### Lemma 16 .

At any round $t\in\{T_{1}+1,\cdots,T\}$, for $i\in\{T_{1}+1,\cdots,t\}$, we have

$$ $\displaystyle\|\bm{w}_{t}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}=\|\bm{w}_{T_{1}}^{(m_ {i})}-\bm{w}_{n_{i}}\|^{2}.$ $$

While at any round $t\in\{1,\cdots,T_{1}\}$, for any $i\in\{1,\cdots,t\}$, we have

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{t}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}]=r^{L_{t}^ {(m_{i})}}\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{L_{t}^{(m_{i})}}(1-r) r^{L_{t}^{(m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^ {2}],$ (42) $$

where $L^{(m_{i})}_{t}=t\cdot f_{t}^{(m_{i})}$ and $r=1-\frac{s}{d}$.

###### Lemma 16 .

### I.1 Proof of Lemma 16

###### Proof.

At any round $t\in\{T_{1}+1,\cdots,T\}$, we have $\bm{w}_{t}^{(m)}=\bm{w}_{T_{1}}^{(m)}$, based on Proposition 1 and Proposition 2. Therefore, $\|\bm{w}_{t}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}=\|\bm{w}_{T_{1}}^{(m_{i})}-\bm{w}_
{n_{i}}\|^{2}$ is true for any round $t\in\{T_{1}+1,\cdots,T\}$ and $i\in\{T_{1}+1,\dots,t\}$.

Next, we prove Eq. 42 for round $t\in\{1,\cdots,T_{1}\}$.
Define $\mathbf{P}_{t}=\mathbf{X}_{t}(\mathbf{X}_{t}^{\top}\mathbf{X}_{t})^{-1}\mathbf
{X}_{t}^{\top}$ for task $t$. At current task $t$, there are totally $L_{t}^{(m)}=t\cdot f_{t}^{(m)}$ tasks routed to expert $m$, where $f_{t}^{(m)}$ is in Eq. 7.

Based on the update rule of $\bm{w}_{t}^{(m)}$ in Eq. 5, we calculate

$$ $\displaystyle\|\bm{w}_{t}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}$ $\displaystyle=\|\bm{w}_{\tau^{(m_{i})}(L_{t}^{(m_{i})})}^{(m_{i})}-\bm{w}_{n_{ i}}\|^{2}$ $\displaystyle=\|(\mathbf{I}-\mathbf{P}_{t})\bm{w}_{\tau^{(m_{i})}(L_{t}^{(m_{i })}-1)}^{(m_{i})}+\mathbf{P}_{t}\bm{w}_{\tau^{m_{i}}(L_{t}^{(m_{i})})}-\bm{w}_ {n_{i}}\|^{2}$ $\displaystyle=\|(\mathbf{I}-\mathbf{P}_{t})(\bm{w}_{\tau^{(m_{i})}(L_{t}^{(m_{ i})}-1)}^{(m_{i})}-\bm{w}_{n_{i}})+\mathbf{P}_{t}(\bm{w}_{\tau^{m_{i}}(L_{t}^{ (m_{i})})}-\bm{w}_{n_{i}})\|^{2},$ $$

where the first equality is because there is no update of $\bm{w}_{t}^{(m_{i})}$ for $t\in\{\tau^{(m_{i})}(L_{t}^{(m_{i})}),\cdots,t\}$, and the second equality is by Eq. 5.

As $\mathbf{P}_{t}$ is the orthogonal projection matrix for the row space of $\mathbf{X}_{t}$, based on the rotational symmetry of the standard normal distribution, it follows that $\mathbb{E}\|\mathbf{P}_{t}(\bm{w}_{\tau^{m_{i}}(L_{t}^{(m_{i})})}-\bm{w}_{n_{i
}})\|=\frac{s}{d}\|\bm{w}_{\tau^{m_{i}}(L_{t}^{(m_{i})})}-\bm{w}_{n_{i}}\|^{2}$. Then we further calculate

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{t}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=(1-\frac{s}{d})\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(L_{t}^{(m_{i} )}-1)}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}]+\frac{s}{d}\mathbb{E}[\|\bm{w}_{\tau^{( m_{i})}(L_{t}^{(m_{i})})}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=(1-\frac{s}{d})^{L_{t}^{(m_{i})}}\mathbb{E}[\|\bm{w}_{0}^{(m_{i} )}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle\quad+\sum_{l=1}^{L_{t}^{(m_{i})}}(1-\frac{s}{d})^{L_{t}^{(m_{i}) }-l}\frac{s}{d}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(L_{t}^{(m_{i})})}-\bm{w}_{n _{i}}\|^{2}]$ $\displaystyle=r^{L_{t}^{(m_{i})}}\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]+\sum_{l=1} ^{L_{t}^{(m_{i})}}(1-r)r^{L_{t}^{(m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i}) }(l)}-\bm{w}_{n_{i}}\|^{2}],$ $$

where the second equality is derived by iterative calculation, and the last equality is because of $\bm{w}_{0}^{(m)}=\mathbf{0}$ for any expert $m$. Here we denote by $r=1-\frac{s}{d}$ to simplify notations.
∎

###### Proof.

### I.2 Final proof of Theorem 1

###### Proof.

Based on Eq. 42 in Lemma 16, we obtain

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{i}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}]=r^{L_{i}^ {(m_{i})}}\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{L_{i}^{(m_{i})}}(1-r) r^{L_{i}^{(m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^ {2}],$ $$

where $\tau^{(m_{i})}(L_{i}^{(m_{i})})=i$.

Then at any round $t\in\{2,\cdots,T_{1}\}$, we calculate the expected forgetting as:

$$ $\displaystyle\mathbb{E}[F_{t}]$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\mathbb{E}\Big{[}\|\bm{w}_{t}^{(m_{ i})}-\bm{w}_{n_{i}}\|^{2}-\|\bm{w}_{i}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}\Big{]}$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\Big{\{}(r^{L_{t}^{(m_{i})}}-r^{L_{ i}^{(m_{i})}})\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{L_{t}^{(m_{i})}}( 1-r)r^{L_{t}^{(m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i} }\|^{2}]$ $\displaystyle\quad-\sum_{j=1}^{L_{i}^{(m_{i})}}(1-r)r^{L_{i}^{(m_{i})}-j} \mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(j)}-\bm{w}_{n_{i}}\|^{2}]\Big{\}}$ $$

where $c_{i,j}=(1-r)(r^{L_{t}^{(m_{i})}-L_{i}^{(m_{i})}}+r^{L_{t}^{(m_{i})}-j}-r^{j-L
_{i}^{(m_{i})}})$.

As task $i$’s ground truth $\bm{w}_{n_{i}}$ is randomly drawn from ground truth pool $\mathcal{W}$ with identical probability $\frac{1}{N}$, we have

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]=\frac{1}{N}\sum_{n=1}^{N}\|\bm {w}_{n}\|^{2}.$ $$

According to Lemma 8 and Proposition 1, each expert $m$ will converge to an expert set $\mathcal{M}_{n}$ before $t=T_{1}$. Therefore, we obtain

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=\mathbb{E}[\frac{1}{N}\sum_{n=1}^{N}\|\bm{w}_{\tau^{(m_{i})}(l)} -\bm{w}_{n}\|^{2}]$ $\displaystyle<\frac{1}{N}\sum_{n=1}^{N}\frac{1}{N}\sum_{n^{\prime}=1}^{N}\|\bm {w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle=\frac{1}{N^{2}}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}- \bm{w}_{n}\|^{2},$ (43) $$

where the inequality is because the expected error $\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n}\|^{2}]$ per round for $t<T_{1}$ is smaller than the uniformly random routing strategy with expected error $\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n}\|^{2}]=\frac{1}{N}\sum_{n^{
\prime}=1}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$, and the last equality is because of $\|\bm{w}_{n}-\bm{w}_{n^{\prime}}\|^{2}=0$ for $n^{\prime}=n$.

Therefore, we finally obtain

$$ $\displaystyle\mathbb{E}[F_{t}]$ $\displaystyle\textstyle<\frac{1}{t-1}\sum_{i=1}^{t-1}\Big{\{}\frac{r^{L_{t}^{( m_{i})}}-r^{L_{i}^{(m_{i})}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{1-r}{N^ {2}}\sum_{l=1}^{L_{t}^{(m_{i})}}r^{L_{t}^{(m_{i})}-l}\sum_{n\neq n^{\prime}}^{ N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle\textstyle\quad-\frac{1-r}{N^{2}}\sum_{j=1}^{L_{i}^{(m_{i})}}r^{L _{i}^{(m_{i})}-j}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\| ^{2}\Big{\}}$ $\displaystyle\textstyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\Big{\{}\frac{r^{L_{t}^{( m_{i})}}-r^{L_{i}^{(m_{i})}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{1-r^{L_ {t}^{(m_{i})}}}{N^{2}}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_ {n}\|^{2}\Big{\}}$ $\displaystyle\textstyle\quad-\frac{1-r^{L_{i}^{(m_{i})}}}{N^{2}}\sum_{n\neq n^ {\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}\Big{\}}$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\Big{\{}\frac{r^{L_{t}^{(m_{i})}}-r ^{L_{i}^{(m_{i})}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{r^{L_{i}^{(m_{i}) }}-r^{L_{t}^{(m_{i})}}}{N^{2}}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}} -\bm{w}_{n}\|^{2}\Big{\}}.$ $$

For any $t\in\{T_{1}+1,\cdots,T\}$, based on Proposition 2, the expert model $\bm{w}_{t}^{(m)}=\bm{w}_{T_{1}}^{(m)}$ for any expert $m\in[M]$. Therefore, we calculate the caused forgetting

$$ $\displaystyle\mathbb{E}[F_{t}]$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{t-1}\mathbb{E}\Big{[}\|\bm{w}_{t}^{(m_{ i})}-\bm{w}_{n_{i}}\|^{2}-\|\bm{w}_{i}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}\Big{]}$ $\displaystyle=\frac{1}{t-1}\sum_{i=1}^{T_{1}}\mathbb{E}\Big{[}\|\bm{w}_{T_{1}} ^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}-\|\bm{w}_{i}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2} \Big{]}$ $\displaystyle=\frac{T_{1}-1}{t-1}\mathbb{E}[F_{t}].$ $$

Based on Eq. 42, we can also calculate the close form of the generalization error:

$$ $\displaystyle\mathbb{E}[G_{T}]$ $\displaystyle=\frac{1}{T}\sum_{i=1}^{T}\mathbb{E}[\|\bm{w}_{T}^{(m_{i})}-\bm{w }_{n_{i}}\|^{2}]$ $\displaystyle=\frac{1}{T}\sum_{i=1}^{T}\mathbb{E}[\|\bm{w}_{T_{1}}^{(m_{i})}- \bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=\frac{1}{T}\sum_{i=1}^{T}\Big{(}r^{L_{T_{1}}^{(m_{i})}}\mathbb{E }[\|\bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{L_{T_{1}}^{(m_{i})}}(1-r)r^{L_{T_{1}}^{( m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]\Big{)}$ $\displaystyle<\frac{\sum_{i=1}^{T}r^{L_{T_{1}}^{(m_{i})}}}{NT}\sum_{n=1}^{N}\| \bm{w}_{n}\|^{2}+\frac{1-r}{N^{2}T}\sum_{i=1}^{T}\sum_{l=1}^{L_{T_{1}}^{(m_{i} )}}r^{L_{T_{1}}^{(m_{i})}-l}\sum_{n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}- \bm{w}_{n}\|^{2}$ $\displaystyle=\frac{\sum_{i=1}^{T}r^{L_{T_{1}}^{(m_{i})}}}{NT}\sum_{n=1}^{N}\| \bm{w}_{n}\|^{2}+\frac{\sum_{i=1}^{T}(1-r^{L_{T_{1}}^{(m_{i})}})}{N^{2}T}\sum_ {n\neq n^{\prime}}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2},$ $$

where the inequality is because of Eq. 43.
∎

###### Proof.

## Appendix J Proof of Theorem 2

###### Proof.

For any round $t\in\{1,\cdots,T_{1}\}$, the forgetting is the same as the case of $M>N$ in Theorem 1, as tasks randomly arrive and are routed to different experts. Therefore, we skip the proof for $t<T_{1}$.

For $t\in\{T_{1}+1,\cdots,T\}$, the router will route tasks in the same cluster to each expert per round. Therefore, we divide the $t$ rounds into two subintervals: $i\in\{1,\cdots,T_{1}\}$ and $i\in\{T_{1}+1,\cdots,t\}$ to calculate the forgetting as

$$ $\displaystyle\mathbb{E}[F_{t}]$ $\displaystyle\textstyle=\frac{1}{t-1}\sum_{i=1}^{t}\mathbb{E}\Big{[}\|\bm{w}_{ t}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2}-\|\bm{w}_{i}^{(m_{i})}-\bm{w}_{n_{i}}\|^{2} \Big{]}$ $\displaystyle\textstyle=\frac{1}{t-1}\sum_{i=1}^{T_{1}}\Big{\{}(r^{L_{t}^{(m_{ i})}}-r^{L_{i}^{(m_{i})}})\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{L_{t} ^{(m_{i})}}(1-r)r^{L_{t}^{(m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}- \bm{w}_{n_{i}}\|^{2}]$ $\displaystyle\textstyle\quad-\sum_{j=1}^{L_{i}^{(m_{i})}}(1-r)r^{L_{i}^{(m_{i} )}-j}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(j)}-\bm{w}_{n_{i}}\|^{2}]\Big{\}}+$ $\displaystyle\textstyle\quad\frac{1}{t-1}\sum_{i=T_{1}+1}^{T}\Big{\{}(r^{L_{t} ^{(m_{i})}}-r^{L_{i}^{(m_{i})}})\mathbb{E}[\|\bm{w}_{n_{i}}\|^{2}]+\underbrace {\sum_{l=L_{T_{1}}^{(m_{i})}+1}^{L_{t}^{(m_{i})}}(1-r)r^{L_{t}^{(m_{i})}-l} \mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]}_{\text{term a}}$ $\displaystyle\textstyle\quad-\underbrace{\sum_{j=L_{T_{1}}^{(m_{i})}+1}^{L_{i} ^{(m_{i})}}(1-r)r^{L_{i}^{(m_{i})}-j}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(j)}- \bm{w}_{n_{i}}\|^{2}]}_{\text{term b}}\Big{\}}$ $$

where the first term in the second equality is similarly derived as forgetting in Eq. 19. For the $\text{term a}-\text{term b}$ in the second equality, we calculate

$$ $\displaystyle\text{term a}-\text{term b}$ $\displaystyle=$ $\displaystyle\sum_{l=L_{T_{1}}^{(m_{i})}+1}^{L_{t}^{(m_{i})}-L_{i}^{(m_{i})}+L _{T_{1}}^{(m_{i})}+1}(1-r)r^{L_{t}^{(m_{i})}-l}\mathbb{E}[\|\bm{w}_{\tau^{(m_{ i})}(l)}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=$ $\displaystyle r^{L_{t}^{(m_{i})}-L_{T_{1}}^{(m_{i})}}(1-r^{L_{t}^{(m_{i})}-L_{ i}^{(m_{i})}})\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=$ $\displaystyle\frac{r^{L_{t}^{(m_{i})}-L_{T_{1}}^{(m_{i})}-1}(1-r^{L_{t}^{(m_{i })}-L_{i}^{(m_{i})}})}{N}\sum_{n=1}^{N}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)} -\bm{w}_{n}\|^{2}]$ $\displaystyle=$ $\displaystyle\frac{r^{L_{t}^{(m_{i})}-L_{T_{1}}^{(m_{i})}-1}(1-r^{L_{t}^{(m_{i })}-L_{i}^{(m_{i})}})}{N}\sum_{n=1}^{N}\sum_{n,n^{\prime}\in\mathcal{W}_{k}} \frac{\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}}{|\mathcal{W}_{k}|},$ $$

where the third equality is derived by $\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]=\frac{1}{N}\sum_
{n=1}^{N}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n}\|^{2}]$, and the last equality is because the router always routes task $\bm{w}_{\tau^{(m_{i})}(l)}=\bm{w}_{n^{\prime}}$ within the same cluster $\mathcal{W}_{k}$ to expert $m_{i}$. Taking the result of $\text{term a}-\text{term b}$ into $\mathbb{E}[F_{t}]$, we obtain

$$ $\displaystyle\mathbb{E}[F_{t}]$ $\displaystyle<\frac{1}{t-1}\sum_{i=1}^{t-1}\frac{r^{L_{t}^{(m_{i})}}-r^{L_{i}^ {(m_{i})}}}{N}\sum_{n=1}^{N}\|\bm{w}_{n}\|^{2}+\frac{1}{t-1}\sum_{i=1}^{T_{1}} \frac{r^{L_{i}^{(m_{i})}}-r^{L_{T_{1}}^{(m_{i})}}}{N^{2}}\sum_{n\neq n^{\prime }}^{N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle\quad+\frac{1}{t-1}\sum_{i=T_{1}+1}^{t}\frac{r^{L_{t}^{(m_{i})}-L _{T_{1}}^{(m_{i})}-1}(1-r^{L_{t}^{(m_{i})}-L_{i}^{(m_{i})}})}{N}\sum_{n=1}^{N} \sum_{n,n^{\prime}\in\mathcal{W}_{k}}\frac{\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^ {2}}{|\mathcal{W}_{k}|}.$ $$

Similarly, we can calculate the overall generalization error as

$$ $\displaystyle\mathbb{E}[G_{T}]$ $\displaystyle=\frac{1}{T}\sum_{i=1}^{T}\mathbb{E}[\|\bm{w}_{T}^{(m_{i})}-\bm{w }_{n_{i}}\|^{2}]$ $\displaystyle=\frac{1}{T}\sum_{i=1}^{T}\Big{(}r^{L_{T}^{(m_{i})}}\mathbb{E}[\| \bm{w}_{n_{i}}\|^{2}]+\sum_{l=1}^{L_{T}^{(m_{i})}}(1-r)r^{L_{T}^{(m_{i})}-l} \mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]\Big{)}$ $\displaystyle=\frac{1}{T}\sum_{i=1}^{T}r^{L_{T}^{(m_{i})}}\mathbb{E}[\|\bm{w}_ {n_{i}}\|^{2}]+\frac{1}{T}\sum_{i=1}^{T_{1}}\Big{\{}\sum_{l=1}^{L_{T_{1}}^{(m_ {i})}}(1-r)r^{L_{T}^{(m_{i})}-l}\underbrace{\mathbb{E}[\|\bm{w}_{\tau^{(m_{i}) }(l)}-\bm{w}_{n_{i}}\|^{2}]}_{\text{term 1}}$ $\displaystyle\quad+\sum_{l=L_{T_{1}}^{(m_{i})}+1}^{L_{T}^{(m_{i})}}(1-r)r^{L_{ T}^{(m_{i})}-l}\underbrace{\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{ i}}\|^{2}]}_{\text{term 2}}\Big{\}}$ $\displaystyle\quad+\frac{1}{T}\sum_{i=T_{1}+1}^{T}\Big{\{}\sum_{l=1}^{L_{T_{1} }^{(m_{i})}}(1-r)r^{L_{T}^{(m_{i})}-l}\underbrace{\mathbb{E}[\|\bm{w}_{\tau^{( m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]}_{\text{term 2}}$ $\displaystyle\quad+\sum_{l=L_{T_{1}}^{(m_{i})}+1}^{L_{T}^{(m_{i})}}(1-r)r^{L_{ T}^{(m_{i})}-l}\underbrace{\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{ i}}\|^{2}]}_{\text{term 3}}\Big{\}},$ $$

where the second equality is derived by Eq. 42, and the third equality is derived by dividing $T$ rounds into two subintervals $\{1,\cdots,T_{1}\}$ and $\{T_{1}+1,\cdots,T\}$.

In the above equation, term 1 means both $\bm{w}_{n_{i}}$ and $\bm{w}_{\tau^{(m_{i})}(l)}$ are randomly drawn from the $N$ ground truths, due to the fact that $i\leq T_{1}$ and $\tau^{(m_{i})}(l)\leq T_{1}$. Term 2 means one of $\bm{w}_{n_{i}}$ and $\bm{w}_{\tau^{(m_{i})}(l)}$ is randomly drawn from the $N$ ground truths before the $T_{1}$-th round, while the other one has fixed to a cluster $\mathcal{M}_{k}$ after the $T_{1}$-th round (i.e., $i\leq T_{1}$ and $\tau^{(m_{i})}(l)>T_{1}$ or $i>T_{1}$ and $\tau^{(m_{i})}(l)\leq T_{1}$). Term 3 means $\bm{w}_{n_{i}}$ and $\bm{w}_{\tau^{(m_{i})}(l)}$ are in the same cluster $\mathcal{M}_{k}$, as $i>T_{1}$ and $\tau^{(m_{i})}(l)>T_{1}$.

For $i\in\{1,\cdots,T_{1}\}$, based on the proof of Theorem 1 in Appendix I, we obtain term 1:

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]< \frac{1}{N^{2}}\sum_{n\neq n^{\prime}}\|\bm{w}_{n}-\bm{w}_{n^{\prime}}\|^{2}.$ $$

While for $i\in\{T_{1}+1,\cdots,t\}$, we calculate term 3 as:

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=\frac{1}{N}\sum_{n=1}^{N}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)} -\bm{w}_{n}\|^{2}]$ $\displaystyle=\frac{1}{N}\sum_{n=1}^{N}\sum_{n,n^{\prime}\in\mathcal{W}_{k}} \frac{\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}}{|\mathcal{W}_{k}|}.$ $$

Finally, we calculate term 2:

$$ $\displaystyle\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)}-\bm{w}_{n_{i}}\|^{2}]$ $\displaystyle=\frac{1}{N}\sum_{n=1}^{N}\mathbb{E}[\|\bm{w}_{\tau^{(m_{i})}(l)} -\bm{w}_{n}\|^{2}]$ $\displaystyle<\frac{1}{N}\sum_{n=1}^{N}\frac{1}{K}\sum_{k=1}^{K}\frac{1}{| \mathcal{W}_{k}|}\sum_{n^{\prime}\in\mathcal{W}_{k}}\|\bm{w}_{n^{\prime}}-\bm{ w}_{n}\|^{2}.$ $$

Based on the expressions of the three terms above, we obtain

$$ $\displaystyle\mathbb{E}[G_{T}]$ $\displaystyle<\frac{1}{T}\sum_{i=1}^{T}\frac{r^{L_{T}^{(m_{i})}}}{N}\sum_{n=1} ^{N}\|\bm{w}_{n}\|^{2}+\frac{1}{T}\sum_{i=1}^{T_{1}}\frac{r^{L_{T}^{(m_{i})}-L _{T_{1}}^{(m_{i})}}(1-r^{L_{T_{1}}^{(m_{i})}})}{N^{2}}\sum_{n\neq n^{\prime}}^ {N}\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle\quad+\frac{1}{T}\sum_{i=1}^{T_{1}}\frac{1-r^{L_{T}^{(m_{i})}-L_{ T_{1}}^{(m_{i})}-1}}{N}\sum_{n=1}^{N}\frac{1}{K}\sum_{k=1}^{K}\frac{1}{| \mathcal{W}_{k}|}\sum_{n^{\prime}\in\mathcal{W}_{k}}\|\bm{w}_{n^{\prime}}-\bm{ w}_{n}\|^{2}$ $\displaystyle\quad+\frac{1}{T}\sum_{i=T_{1}+1}^{T}\frac{r^{L_{T}^{(m_{i})}-L_{ T_{1}}^{(m_{i})}}(1-r^{L_{T_{1}}^{(m_{i})}})}{N}\sum_{n=1}^{N}\frac{1}{K}\sum_ {k=1}^{K}\frac{1}{|\mathcal{W}_{k}|}\sum_{n^{\prime}\in\mathcal{W}_{k}}\|\bm{w }_{n^{\prime}}-\bm{w}_{n}\|^{2}$ $\displaystyle\quad+\frac{1}{T}\sum_{i=T_{1}+1}^{T}\frac{1-r^{L_{T}^{(m_{i})}-L _{T_{1}}^{(m_{i})}-1}}{N}\sum_{n=1}^{N}\sum_{n,n^{\prime}\in\mathcal{W}_{k}} \frac{\|\bm{w}_{n^{\prime}}-\bm{w}_{n}\|^{2}}{|\mathcal{W}_{k}|},$ $$

which completes the proof.
∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: -  is expert specialization necessary for CL with MoEs? 
- are modern-day large-scale AI systems operating in an overparameterized regime?
- for load balancing loss, why not use entropy maximization? What are the benefits of the proposed load balancing loss compared to entropy maximization?
- is cross-expert and cross-task transfer possible in the proposed system design?
soundness: 3
strengths: **Originality**: 
- the idea that forgetting in MoE can be mitigated solely through specialized experts and correct routing is not entirely new, e.g. see [1]
- this paper is original in its theoretical contribution (to the best of my knowledge), providing proofs and bounds on Cl metrics with MoEs
- the proposed locality loss and load balancing loss provide clear mechanisms for task clustering and specialization (even though load balancing loss is not a contribution of this work)

**Quality**: 
I think the quality of this work is decent, due to the rigorous theoretical work and relevant experiments. Even though the focus of the work is mainly on the theoretical side, further validation on more complex datasets would be interesting and benefit the credibility of the paper's contributions. 

**Clarity**: while the theoretical analysis appears to be rigorous and well presented, I think the presentation would benefit a lot from incorporating more **intuitive explanations**. E.g. authors could explicitly state the idea that forgetting may be prevented solely through correct routing. Also the MNIST experiment's design is somewhat hard to follow.

**Significance**:
Despite the small scale of the experiments, I think this paper opers some interesting directions for future research, mainly among the lines of scaling these ideas to larger systems.

Overall, I appreciate how this paper demonstrates how under proper specialization and routing CL can be addressed with modular solutions like MoEs.

[1] Ostapenko, Oleksiy, et al. "From IID to the Independent Mechanisms assumption in continual learning." AAAI Bridge Program on Continual Causality. PMLR, 2023.
summary: This paper provides a theoretical study of Mixture-of-Experts (MoE) models for Continual Learning (CL). Specifically, it examines the CL of linear regression tasks in an overparameterized regime. The benefit of this regime is that each task has multiple possible solutions, increasing the likelihood of expert specialization and transfer.

This paper implements a one-layer MoE architecture with the following design choices:

- **Experts**: Each expert is implemented as a linear model.
- **Router**: A top-1 router is implemented as a linear model.
- **Router Training**: The router is trained using gradient descent.
- **Expert Parameters**: Expert parameters are found through a closed-form solution
- **Training regime**: routing is performed at a per-task level, at each new trainign iteration a new task is sampled from a limited pool of tasks. 

Authors propose two key design choices to facilitate learning in their MoE:
	
- Training loss: in addition to the standard load balancing loss (eq. 7), they propose to use a **locality loss** (is a novel contribution afaik), that facilitates routing of the similar tasks to the same experts
- Early termination: intuitively, once an expert has specialized sufficiently (expected to be the case after T_1 updates), further updates of the routing parameters can result in instabilities. This is achieved by terminating training of the router if the current expert's routing "dominates sufficiently" the other experts' routing.

Authors address the following setting:
- at each update step t, a feature matrix X is randomly sampled following the data generating process described in Definition 1
- among the s_t examples in the feature matrix, there is one example that contains the feature signal
- in the addressed setting, identical tasks can reoccur, as tasks are sampled independently in each update step

Authors derive the following properties of the MoE with previously mentioned design choices:
- the router routes experts primarily based on feature signal, and all experts can be clustered into experts sets, with specialized experts in each expert set
- therefore, under the proposed algorithm (due to the locality loss and termination criteria), experts will likely specialize on certain task clusters after sufficient training round T_1 minimizing the effect of forgetting
- if no termination criteria is applied, proposition 2 states that the specialization will break at round t_2 (the gap between any two experts is predicted to be the same)
- if early termination is applied, then experts within the same expert set are chosen uniformly after T2 updates

The authors derive upper bounds on forgetting and generalization error for the MoE, showcasing that **both are reduced compared to a monolithic single-expert model**. When there are more tasks than experts, forgetting is bounded due to the router’s tendency to route similar tasks to the same experts.

Overall, the intuition that MoE models, with correct routing and module specialization, can address the challenges of CL is natural and compelling. This paper effectively demonstrates how this intuition can be implemented and validated in a controlled, toy setting. The findings can offer a useful starting point for scaling these ideas to settings more relevant for practical AI applications, a very relevant work in this context is [2].

[2] Rypeść, Grzegorz, et al. "Divide and not forget: Ensemble of selectively trained experts in Continual Learning." arXiv preprint arXiv:2401.10191 (2024).
weaknesses: - the scale of the experiments is small, while one has to uknowledge that the contributions are mainly theoretical
- I would appreciate more intuitive lingo and explanations
- the current implementation is essentially on the one extreme of the parameter sharing trade-off where no transfer happens between tasks? 
- it is not exactly clear how these ideas can be extended to large scale MoE with multiple expert layers and per-token routing, where correct routing as well as expert specialization is not guaranteed

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1) Line 56-57 “One learning task arrives in each round and its dataset is generated with ground truth randomly drawn from a shared pool encompassing N unknown linear model”. What is the intuition behind generating the ground truth from the linear model?

2) It might make sense if the number of experts is less than the number of tasks But in Line Line 69 if M > N implies the number of experts more than the number of tasks. This is not continual learning if you are training task-specific experts. Furthermore, in Section 4, you have done the main study with more experts than tasks (Line 296).

3) In Figure 2, on which datasets the experiment is performed?

4) For MNIST which DNN model is used? As from the setup number of task N = 3, how did the 10 classes were split?


## After Reading Comments

I raised my score to 6 as an experiment on MNIST and CIFAR10 is not enough.

Again, thank you for your contributions.
soundness: 3
strengths: 1) Theoretical Foundations: The paper provides a comprehensive theoretical analysis of MoE in the context of continual learning, establishing clear benefits over single-expert models through explicit expressions for expected forgetting and generalization error.

2) Load Balancing: The model ensures balanced utilization of experts, which can lead to improved generalization performance as it reduces the risk of overloading any single expert with too many tasks.

3) Empirical Validation: Experiments conducted on both synthetic and real datasets support the theoretical findings, demonstrating that MoE can effectively improve learning performance across diverse scenarios. It is interesting to note that even with a higher number of experts than tasks, the model might not perform well.
summary: The paper "Theory on Mixture-of-Experts in Continual Learning" analyzes the Mixture-of-Experts (MoE) model's effectiveness in addressing catastrophic forgetting in continual learning (CL). It establishes that MoE can enhance learning by diversifying expert specialization through a gating network, which routes tasks efficiently. The study provides theoretical insights into expected forgetting and generalization error, demonstrating that MoE outperforms single-expert models, especially with diverse data distributions. However, it notes that adding more experts requires additional training rounds before achieving convergence. Empirical results support the theoretical claims, extending the findings to deep neural networks (DNNs) for practical algorithms
weaknesses: 1) Validity of Proposition (4): The model gap term ∑n≠n′∥wn−wn′∥2\sum_{n \neq n'} \|w_n - w_{n'}\|^2∑n=n′​∥wn​−wn′​∥2 only considers the Euclidean distance between weights. This may not fully capture the complex relationships between tasks. In practice, tasks could overlap in non-trivial ways (e.g., in feature space or output space), and simple weight differences do not reflect true "task divergence" accurately.

2) Limited Experiments: Though the main contribution is to present the theoretical analysis of forgetting and generalization error for MoE in CL, the main objective of the model is to reduce catastrophic forgetting. Without presenting enough empirical evaluation in terms of accuracy in continual learning settings for benchmark datasets like CIFAR10/100, ImageNet is not enough. I would encourage the authors to extend the simulation to the more complex dataset. For example, SEED [1] uses a mixture of expert networks and selects a single expert to finetune downstream tasks. If the authors could provide details of this work by forgetting a generalization error it would provide better judgment of where the current state-of-the-art MoE methods for CL stands in terms of forgetting and generalization error and strengthen the contribution of the work.

[1] Rypeść, Grzegorz, et al. "Divide and not forget: Ensemble of selectively trained experts in Continual Learning." arXiv preprint arXiv:2401.10191 (2024).

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: (1) In Line 76-78, it sates the MoE enhances performance over the single expert case, which seems trivial. Is the condition, such as with the same model complexity, missing in the statement?

(2) In Line221-224, it seems the update of model parameterizes use the inversion matrix, which brings more computational overhead over gradient-based methods.

(3) In Line 293-294, it seems the early termination achieves stable convergence, but the motivation is also related to overfitting for alleviating imbalanced loads. So does the early termination improve balanced loads?

(4) In Line 532, “the first theoretical analysis of MoE” is overstated considering the existing work [1]. And I am also wondering how the developed strategy works in more complicated experiments.
soundness: 3
strengths: This work is written clearly and well structured. Overall, the theoretical analysis over MoEs is necessary in developing MoE-based large models, and this work discusses some insights into the catastrophic forgetting and generalization. The experiments include the overparameterized linear regression and MNIST cases.
summary: This work studies the theoretical understanding of mixture-of-experts (MoEs) module in continual learning. To examine the role of MoEs, the authors conduct experiments on overparameterized linear regression tasks. Theoretically, this work identifies the importance of the gating network update’s termination and analyzes the catastrophic forgetting and generalization.
weaknesses: (1) The scope of this work seems a bit wide according to the title. I suggest to use terms like “theoretical understanding” to modify.

(2) The theoretical analysis is mainly on overparameterized linear regression cases, which might be a limitation in this work as nonlinear deep neural network cases can be more practical.

(3) There are some related work on MoE theories, continual learning with MoEs or MoEs for adaptation in the field that require discussions [1-4]. 

Reference:

[1] Nguyen H D, Chamroukhi F. Practical and theoretical aspects of mixture‐of‐experts modeling: An overview[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2018, 8(4): e1246.

[2] Jerfel, Ghassen, et al. "Reconciling meta-learning and continual learning with online mixtures of tasks." Advances in neural information processing systems 32 (2019).

[3] Wang Q, Van Hoof H. Learning expressive meta-representations with mixture of expert neural processes[J]. Advances in neural information processing systems, 2022, 35: 26242-26255.

[4] Lee S, Ha J, Zhang D, et al. A neural dirichlet process mixture model for task-free continual learning[J]. arXiv preprint arXiv:2001.00689, 2020.

---

***Post Rebuttal**

After reading the rebuttal, all my questions are well answered. I updated the score.

Meta-review: This paper provides a theoretical study of Mixture-of-Experts (MoE) models for Continual Learning (CL). Specifically, it examines the CL of linear regression tasks in an over-parameterized regime. The benefit of this regime is that each task has multiple possible solutions, increasing the likelihood of expert specialization and transfer.

Decision: Accept (Spotlight)