Theory on Mixture-of-Experts in Continual Learning

0. 摘要

连续学习（CL）因其能够适应随时间到来的新任务而受到广泛关注。在模型适应新任务时，旧任务的灾难性遗忘（catastrophic forgetting）被确定为 CL 中的一个主要问题。最近，专家混合（MoE）模型已被证明可以通过使用门控网络来稀疏化和分配多个专家之间的不同任务，从而有效减轻 CL 中的灾难性遗忘。然而，对于 MoE 及其对 CL 学习性能影响的理论分析还比较缺乏。本文提供了第一个理论结果，通过过参数化线性回归任务的视角来表征 MoE 在 CL 中的影响。我们通过证明 MoE 模型可以使其专家多样化，专门处理不同任务，同时其路由器学习为每个任务选择正确的专家并在所有专家之间平衡负载，从而确立了 MoE 相对于单一专家的优势。我们的研究进一步表明了一个有趣的事实，即 MoE 在 CL 中需要在足够的训练轮次后终止门控网络的更新以实现系统收敛，这在不考虑连续任务到达的现有 MoE 研究中是不需要的。此外，我们提供了预期遗忘和整体泛化误差的显式表达式，以表征 MoE 在 CL 学习性能中的好处。有趣的是，增加更多专家需要额外的轮次才能收敛，这可能不会增强学习性能。最后，我们在合成数据和真实数据集上进行了实验，将这些来自线性模型的见解扩展到深度神经网络（DNNs），这也为 MoE 在 CL 中的实际算法设计提供了见解。

1. 引言

连续学习（CL）已成为机器学习中的一个重要范式，其中专家的目标是随时间逐一学习一系列任务。预计专家将利用从旧任务中获得的知识来促进新任务的学习，同时通过从新任务中获得的知识提升旧任务的性能。鉴于 CL 的动态性质，这里的一个主要挑战被称为灾难性遗忘，即专家在学习新任务时可能会在（即，容易忘记）之前的任务上表现不佳，如果任务的数据分布发生大的变化。当单个专家继续服务越来越多的任务时，这成为一个更严重的问题。

最近，稀疏门控的专家混合（MoE）模型在深度学习中取得了惊人的成功，特别是在大型语言模型（LLMs）的发展中。通过自适应地将不同的输入数据路由到多个专家中的一个，MoE 模型中的不同专家将专门掌握数据中的不同知识。因此，有了一些尝试利用 MoE 来减轻 CL 中的遗忘问题，通过训练每个专家处理特定的一组任务。然而，这些研究主要关注实验调查，而对 MoE 及其对 CL 学习性能影响的理论理解仍然缺乏。在本文中，我们的目标是通过提供第一个明确的理论结果来填补这一空白，全面理解 CL 中的 MoE。

为此，我们研究了 CL 中具有 M 个专家的稀疏门控 MoE 模型，通过过参数化线性回归任务的视角。在我们的 CL 设置中，每个回合有一个学习任务到达，其数据集是随机从包含 N 个未知线性模型的共享池中抽取的真实数据生成的。随后，数据被输入到参数化的门控网络中，由该网络引导的 softmax 基路由器将任务路由到 M 个专家中的一个进行模型训练。训练后的 MoE 模型然后通过梯度下降（GD）进一步更新门控网络。之后，新的任务到达，上述过程重复，直到 CL 结束。值得注意的是，分析线性模型是理解深度神经网络（DNNs）性能的重要第一步，正如许多最近研究所显示的。

我们的主要贡献总结如下：

我们提供了第一个理论分析，通过过参数化线性回归任务的视角，理解 CL 中 MoE 的行为。通过使用精心设计的损失函数更新门控网络，我们展示了在 CL 中经过足够的训练轮次（专家探索和路由器学习的顺序为 $O(M)$）后，MoE 模型将多样化并进入一个平衡的系统状态：每个专家将专门处理特定任务（如果 M > N），或者专门处理一组类似任务（如果 M < N），路由器将始终为每个任务选择正确的专家。另一个有趣的发现是，与不考虑连续任务到达的现有 MoE 研究不同，由于 CL 中任务到达的动态性，更新 MoE 的门控网络是必要的。这将确保学习系统最终收敛到一个稳定的平衡负载状态。

我们提供了预期遗忘和泛化误差的显式表达式，以表征 MoE 对 CL 性能的好处。1）与单一专家情况（M = 1）相比，其中任务由单一发散模型学习，具有多样化专家的 MoE 模型显著提高了学习性能，特别是在任务间数据分布变化大的情况下。2）无论专家更多（M > N）还是更少（M < N），遗忘和泛化误差都收敛到一个小常数。这是因为路由器在 MoE 模型收敛后始终为每个任务选择正确的专家，从长远来看有效地最小化模型误差。3）在 MoE 中，增加更多专家需要额外的探索轮次才能收敛，这不一定增强学习性能。

最后，我们进行了广泛的实验来验证我们的理论结果。具体来说，我们在合成数据上的实验结果不仅支持我们上述的理论发现，而且还表明负载平衡降低了平均泛化误差。这有效地提高了 MoE 模型与不平衡情况相比的能力。更重要的是，对真实数据集的实验表明，我们的理论发现可以进一步超越线性模型扩展到 DNNs，这也为 MoE 在 CL 中的实际算法设计提供了见解。

2. 相关工作

2.1 连续学习

在过去的十年中，提出了各种实证方法来解决 CL 中的灾难性遗忘问题，这些方法通常分为三类：1）基于正则化的方法，通过在之前任务训练的关键模型参数上引入显式的正则化项来平衡旧任务和新任务。2）基于参数隔离的方法，隔离与不同任务相关的参数以防止参数之间的干扰。3）基于记忆的方法，存储旧任务的数据或梯度信息，并在新任务的训练中重放它们。

另一方面，对 CL 的理论研究非常有限。其中，[36] 和 [37] 引入了 NTK 重叠矩阵来衡量任务相似性，并提出了正交梯度下降方法的变体来解决灾难性遗忘问题。[38] 考虑了一个教师 - 学生框架来检验任务相似性对学习性能的影响。[39] 提出了一个理想的 CL 框架，通过假设所有任务的数据分布为 i.i.d.来实现无遗忘。[19] 提供了过参数化线性模型中不同任务顺序的遗忘界限。进一步，[20] 基于测试误差提供了遗忘和整体泛化误差的显式形式。这些作品共同表明，当后续任务表现出显著多样化时，单一专家的学习性能往往会恶化。相比之下，我们的工作是第一个进行理论分析，以理解多个专家对 CL 的好处。

2.2 专家混合模型

MoE 模型多年来已被广泛研究，以增强深度学习中的模型容量。最近，它在大型语言模型（LLMs）等新兴领域中找到了广泛应用。为了提高训练稳定性和简化 MoE 结构，[10] 提出了稀疏化门控网络的输出。随后，[22] 建议将每个数据样本路由到单个专家而不是多个专家，这降低了计算成本，同时保持了模型质量。[21] 在分类问题的混合设置下，从理论上分析了深度学习中 MoE 的机制。请注意，这项研究侧重于单一任务设置，因此没有分析 CL 中训练一系列任务的动态。相比之下，我们的工作深入研究了 CL 中的 MoE，导致了与 [21] 不同的门控网络训练阶段。此外，我们提供了遗忘和整体泛化误差的显式表达式。

2.3 MoE 在 CL 中的应用

最近，MoE 模型已被应用于减少 CL 中的灾难性遗忘。例如，[12] 集成了多个专家的合作，基于特征表示的加权和来进行预测。[14] 提出通过将数据路由到分布重叠最小的每个专家来多样化专家，然后在任务预测期间结合专家的知识以增强学习稳定性。此外，[15] 将 MoE 应用于扩展视觉 - 语言模型的容量，减轻 CL 中的长期遗忘。然而，这些工作仅关注实证方法，缺乏对 MoE 在 CL 中表现的理论分析。

3. 问题设置和 MoE 模型设计

3.1 符号表示

对于向量 $\mathbf{w}$，让 $|\mathbf{w}|2$ 和 $|\mathbf{w}|\infty$ 分别表示其 $\ell_2$ 和 $\ell_\infty$ 范数。对于某些正常数 $c_1$ 和 $c_2$，我们定义 $x = \Omega(y)$ 如果 $x > c_2|y|$，$x = \Theta(y)$ 如果 $c_1|y| < x < c_2|y|$，和 $x = O(y)$ 如果 $x < c_1|y|$。我们还表示 $x = o(y)$ 如果 $x/y \to 0$。

3.2 线性模型中的 CL

一般设置

我们考虑有 T 个训练轮次的 CL 设置。在每个轮次 $t \in [T]$ 中，N 个任务中的一个随机到达，由具有 M 个专家的 MoE 模型学习。对于每个任务，我们考虑拟合一个线性模型 $f(X) = X^\top \mathbf{w}$，其中真实情况为 $\mathbf{w} \in \mathbb{R}^d$。然后，对于第 t 个训练轮次中的任务到达，它对应于一个线性回归问题，其中训练数据集由 $D_t = (X_t, y_t)$ 表示。这里 $X_t \in \mathbb{R}^{d \times s_t}$ 是具有 $s_t$ 个样本的特征矩阵，$y_t \in \mathbb{R}^{s_t}$ 是输出向量。在本研究中，我们关注过参数化区域，其中 $s_t < d$。因此，存在许多可以完美拟合数据的线性模型。

真实情况和数据集

让 $W = {w_1, \cdots, w_N}$ 表示所有 N 个任务的真实向量集合。对于任何两个任务 $n, n’ \in [N]$，我们假设 $|w_n - w_{n’}|\infty = O(\sigma_0)$，其中 $\sigma_0 > 0$ 表示方差。此外，我们假设任务 $n$ 具有一个独特的特征信号 $v_n \in \mathbb{R}^d$，且 $|v_n|\infty = O(1)$。

在每个训练轮次 $t \in [T]$ 中，让 $n_t \in [N]$ 表示当前任务到达的索引，其真实情况为 $w_{n_t} \in W$。以下，我们正式定义每个训练轮次的数据集生成。

定义 1. 在每个训练轮次 $t \in [T]$ 的开始，新任务到达 $n_t$ 的数据集 $D_t = (X_t, y_t)$ 是通过以下步骤生成的：

从真实池 $W$ 中均匀抽取一个真实情况 $w_n$ 并让 $w_{n_t} = w_n$。
独立生成一个随机变量 $\beta_t \in (0, C]$，其中 C 是一个常数，满足 $C = O(1)$。
生成 $X_t$ 作为 $s_t$ 个样本的集合，其中一个样本由 $\beta_t v_{n_t}$ 给出，其余的 $s_t - 1$ 个样本从正态分布 $N(0, \sigma_t^2 I_d)$ 中抽取，其中 $\sigma_t \geq 0$ 是噪声水平。
生成输出 $y_t = X_t^\top w_{n_t}$。

在任何训练轮次 $t \in [T]$ 中，任务到达 $n_t$ 的实际真实情况 $w_{n_t}$ 是未知的。然而，根据定义 1，任务 $n_t$ 可以根据其特征信号 $v_{n_t}$ 被分类为 N 个簇中的一个。尽管 $v_{n_t}$ 在特征矩阵 $X_t$ 中的位置对于每个任务 $n_t$ 没有指定，我们可以使用 MoE 中的单个门控网络来解决 $X_t$ 上的这个二元分类子问题。在这种情况下，我们旨在研究 MoE 模型是否能增强 CL 中的学习性能。为了方便起见，我们假设 $s_t = s$ 对于所有 $t \in [T]$ 在本文中。然后我们将在以下小节中介绍 MoE 模型。

3.3 MoE 模型的关键设计

专家模型

让 $\mathbf{w}^{(m)}_t$ 表示第 t 个训练轮次中专家 m 的模型，其中每个模型从零开始初始化，即 $\mathbf{w}^{(m)}_0 = 0$ 对于任何 $m \in [M]$。在路由器确定专家 $m_t$ 后，它将数据集 $D_t = (X_t, y_t)$ 传输给该专家以更新 $\mathbf{w}^{(m_t)}t$。对于任何其他未被选中的专家 $m \in [M]$（即 $m \neq m_t$），其模型 $\mathbf{w}^{(m)}t$ 保持不变，从 $\mathbf{w}^{(m)}{t-1}$ 开始。在每个轮次 $t$ 中，训练损失由相对于数据集 $D_t$ 的均方误差（MSE）定义：
$$
L{\text{tr}}^t(\mathbf{w}^{(m_t)}t, D_t) = \frac{1}{s_t} |(X_t^\top \mathbf{w}^{(m_t)}t - y_t)|2^2.
$$
由于我们关注过参数化区域，存在无限多的解决方案可以完美满足 $L{\text{tr}}^t(\mathbf{w}^{(m_t)}t, D_t) = 0$。在这些解决方案中，从收敛点的前一个专家模型 $\mathbf{w}^{(m_t)}{t-1}$ 开始的梯度下降（GD）提供了一个独特的解决方案，用于最小化 $L{\text{tr}}^t(\mathbf{w}^{(m_t)}t, D_t)$，由以下优化问题确定：
$$
\min{\mathbf{w}} |\mathbf{w} - \mathbf{w}^{(m_t)}{t-1}|2^2, \text{ s.t. } X_t^\top \mathbf{w} = y_t.
$$
解决上述方程，我们更新 MoE 模型中选定的专家，以应对当前任务到达 $n_t$，同时保持其他专家不变：
$$
\mathbf{w}^{(m_t)}t = \mathbf{w}^{(m_t)}{t-1} + X_t (X_t^\top X_t)^{-1} (y_t - X_t^\top \mathbf{w}^{(m_t)}{t-1}).
$$

门控网络参数

在获得 $\mathbf{w}^{(m_t)}t$ 后，MoE 使用 GD 从 $\Theta_t$ 更新门控网络参数到 $\Theta{t+1}$，以供下一轮训练使用。一方面，我们希望每个专家 $m$ 的 $\theta^{(m)}_t$ 专门处理特定任务，这有助于减轻由于不同任务的错误路由而导致的学习损失。另一方面，路由器需要在所有专家之间平衡负载，以减少模型过拟合的风险，并增强 CL 中的学习性能。为了实现这一点，我们引入了以下关键设计，用于门控网络更新。

关键设计 I：多目标训练损失。首先，基于更新的专家模型 $\mathbf{w}^{(m)}t$，我们提出了以下本地损失函数，用于更新 $\Theta_t$：
$$
L{\text{loc}}^t(\Theta_t, D_t) = \sum_{m \in [M]} \pi_m(X_t, \Theta_t) |\mathbf{w}^{(m)}t - \mathbf{w}^{(m)}{t-1}|_2^2,
$$
其中 $\pi_m(X_t, \Theta_t)$ 是在方程（2）中定义的 softmax 输出。由于我们设计的本地损失在任务具有相似真实情况时被路由到同一专家 $m$（例如，$\mathbf{w}^{(m)}t = \mathbf{w}^{(m)}{t-1}$）时被最小化，它享有几个好处，如我们后面的理论结果所示：每个专家将专门处理特定任务，这导致专家模型 $\mathbf{w}^{(m)}_t$ 快速收敛，CL 的遗忘和泛化误差性能将得到改善。注意，在方程（6）中，我们只需要计算单个专家 $m_t$ 的本地损失，因为对于任何没有更新其模型的专家 $m \neq m_t$，$|\mathbf{w}^{(m)}t - \mathbf{w}^{(m)}{t-1}|_2^2 = 0$，导致计算复杂度低。

除了新颖的本地损失外，我们还遵循现有的 MoE 文献，其中通常定义一个辅助损失来表征专家之间的负载平衡：
$$
L_{\text{aux}}^t(\Theta_t, D_t) = \alpha \cdot M \cdot \sum_{m \in [M]} f(m)t \cdot P(m)t,
$$
其中 $\alpha$ 是常数，$f(m)t = \frac{1}{t} \sum{\tau=1}^t 1{m\tau = m}$ 是自 $t=1$ 以来分配给专家 m 的任务比例，$P(m)t = \frac{1}{t} \sum{\tau=1}^t \pi_m(X\tau, \Theta_\tau) \cdot 1{m_\tau = m}$ 是路由器自 $t=1$ 以来选择专家 m 的平均概率。方程（7）中的辅助损失鼓励所有专家的探索，因为它在均匀路由下被最小化，其中 $f(m)_t = \frac{1}{M}$ 和 $P(m)_t = \frac{1}{M}$。尽管方程（7）中辅助损失的定义并不新颖，但它是必要的，并且在 MoE 模型中为 CL 平衡专家之间的负载中起着至关重要的作用。

基于方程（3），（6）和（7），我们最终定义每个任务到达 $n_t$ 的任务损失如下：
$$
L_{\text{task}}^t(\Theta_t, \mathbf{w}^{(m_t)}t, D_t) = L{\text{tr}}^t(\mathbf{w}^{(m_t)}t, D_t) + L{\text{loc}}^t(\Theta_t, D_t) + L_{\text{aux}}^t(\Theta_t, D_t).
$$
从初始化 $\Theta_0$ 开始，门控网络基于 GD 更新：
$$
\theta^{(m)}_{t+1} = \theta^{(m)}t - \eta \cdot \nabla{\theta(m)t} L{\text{task}}^t(\Theta_t, \mathbf{w}^{(m_t)}t, D_t), \forall m \in [M],
$$
其中 $\eta > 0$ 是学习率。注意 $\mathbf{w}^{(m_t)}t$ 在方程（5）中也是最小化 $L{\text{task}}^t(\Theta_t, \mathbf{w}^{(m_t)}t, D_t)$ 的唯一解。这是因为 $L{\text{loc}}^t(\Theta_t, D_t)$ 和 $L{\text{aux}}^t(\Theta_t, D_t)$ 都是在更新 $\mathbf{w}^{(m_t)}t$ 之后派生的，使得 $L{\text{tr}}^t(\mathbf{w}^{(m_t)}_t, D_t)$ 成为方程（8）中 $\mathbf{w}^{(m_t)}_t$ 的唯一目标。

关键设计 II：提前终止。为确保系统在专家之间平衡负载的稳定收敛状态（我们将在第 4 节中从理论上证明），在足够的（即，$T_1$）轮次专家探索后，我们在算法 1 中引入了提前终止策略，通过评估每个专家 m 的收敛标志 $I(m)$。

这个标志评估输出间隙，定义为 $|h_m(X_t, \theta_t) - h_{m_t}(X_t, \theta_t)|$，专家本身和任何选定专家 $m_t$ 之间的差距，对于 $t > T_1$。如果这个差距超过阈值 $\Gamma$ 对于专家 m，表明门控网络参数 $\theta^{(m)}_t$ 尚未收敛，则 MoE 模型继续根据方程（9）更新所有专家的 $\Theta_t$。否则，$\Theta_t$ 的更新被永久终止。

4. MoE 训练的理论结果

在本节中，我们提供了对算法 1 中专家模型和门控网络训练的理论分析，进一步证明了我们在第 3 节中的关键设计。具体来说，（i）我们首先支持我们的关键设计 I，通过证明在设计的局部损失下，专家模型通过更新 $\Theta_t$ 快速收敛。（ii）然后我们展示了我们的关键设计 II，即在 CL 中提前终止更新 $\Theta_t$ 对于确保稳定收敛系统状态和所有专家之间的平衡负载是必要的。为了清晰起见，我们在本节中研究了 $M > N$ 的情况（结果标记为 $M > N$ 版本），并将结果扩展到 $M < N$ 的情况在附录中。

为了表征专家专业化，我们首先展示每个专家的门控输出由 $X_t$ 的输入特征信号 $v_{n_t}$ 决定。

引理 1（M > N 版本）：对于任何两个具有相同特征信号 $v_n$ 的特征矩阵 $X$ 和 $\tilde{X}$，以至少 $1 - o(1)$ 的概率，它们对应的同一专家 $m$ 的门控输出满足
$$
|h_m(X, \theta^{(m)}t) - h_m(\tilde{X}, \theta^{(m)}t)| = O(\sigma{1.5}^0).
$$
引理 1 的完整版本和证明在附录 C 中给出。根据引理 1，路由器根据其特征信号 $v{n_t}$ 决定任务 $n_t$ 的专家 $m_t$。因此，给定 N 个任务，所有专家可以被分为 N 个集合，根据它们的专业化，即它们的门控参数 $\theta^{(m)}t$ 识别特征信号 $v_n$，其中每个专家集合定义为：
$$
M_n = { m \in [M] \mid n = \arg\max{j \in [N]} (\theta^{(m)}_t)^\top v_j }.
$$
以下命题表明，在算法 1 下，经过足够训练轮次后，专家模型在 $T_1$ 后稳定，并保持不变直到结束 $T$。

命题 1（M > N 版本）：在算法 1 下，以至少 $1 - o(1)$ 的概率，对于任何 $t > T_1$，其中 $T_1 = \lceil \eta^{-1}M \rceil$，每个专家 $m \in [M]$ 在专家集合 $M_n$ 中稳定，并且其专家模型保持不变，满足 $\mathbf{w}^{(m)}_{T_1+1} = \cdots = \mathbf{w}^{(m)}_T$。

命题 1 的完整版本和证明在附录 E 中给出。命题 1 表明，在 $T_1$ 轮专家探索后，每个专家将专门处理特定任务，通过最小化方程（6）中的局部损失来强制执行。之后，专家模型直到结束 $T$ 保持不变。

接下来，以下命题描述了如果在算法 1 中 MoE 在任何轮次 $t$ 继续更新 $\Theta_t$，则门控输出的动态。

命题 2（M > N 版本）：如果 MoE 在任何轮次 $t \in [T]$ 继续通过方程（9）更新 $\Theta_t$，我们得到：1）在轮次 $t_1 = \lceil \eta^{-1}\sigma^{-0.25}0 M \rceil$，以下属性成立
$$
|h_m(X{t_1}, \theta^{(m)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = \begin{cases} O(\sigma{1.75}^0), & \text{if } m, m’ \in M_n, \ \Theta(\sigma_{0.75}^0), & \text{otherwise}. \end{cases}
$$
2）在轮次 $t_2 = \lceil \eta^{-1}\sigma^{-0.75}0 M \rceil$，以下属性成立
$$
|h_m(X{t_2}, \theta^{(m)}{t_2}) - h{m’}(X_{t_2}, \theta^{(m’)}{t_2})| = O(\sigma{1.75}^0), \forall m, m’ \in [M].
$$
命题 2 的完整版本和证明在附录 F 中给出。根据命题 2，如果 MoE 在任何轮次 $t$ 继续更新 $\Theta_t$，同一专家集合中的任意两个专家的门控输出差距在轮次 $t_1$ 收敛到 $O(\sigma_{1.75}^0)$。相比之下，任何两个在不同专家集合中的专家，它们的输出差距足够大，即 $\Theta(\sigma_{0.75}^0)$，表明 MoE 在轮次 $t_1$ 成功地将专家多样化到不同的集合中。然而，与单任务学习中的 MoE 可以在专家模型收敛后随时停止训练不同，CL 中的 MoE 需要随着新任务的连续到达，适当更新门控网络和专家。这是必要的，以平衡每个专家上的负载并最大化系统容量利用。然而，继续根据方程（9）更新 $\Theta_t$ 最终将任意两个专家的输出差距减少到 $O(\sigma_{1.75}^0)$，在训练轮次 $t_2$，导致路由器为后续任务到达选择错误的专家，并产生额外的训练错误。

基于命题 2，提前终止更新 $\Theta_t$ 是必要的，以保持不同集合中任意两个专家之间的足够大的输出差距，确保专家多样性，如轮次 $t_1$ 的方程（12）。这激发了我们在算法 1 中设计的提前终止，从第 7 行到第 13 行概述。在下一个命题中，我们证明了在算法 1 中提前终止更新 $\Theta_t$ 的好处。

命题 3（M > N 版本）：在算法 1 下，MoE 从轮次 $T_2 = O(\eta^{-1}\sigma^{-0.25}0 M)$ 开始终止更新 $\Theta_t$。然后对于任何任务到达 $n_t$ 在 $t > T_2$，路由器以相同的 $\frac{1}{|M{n_t}|}$ 概率选择任何专家 $m \in M_{n_t}$，其中 $|M_{n_t}|$ 是集合 $M_{n_t}$ 中的专家数量。

命题 3 的完整版本和证明在附录 G 中给出。根据算法 1，一旦 MoE 终止更新 $\Theta_t$，方程（1）中的随机噪声 $r(m)t$ 将引导路由器以相同的 $\frac{1}{|M{n_t}|}$ 概率选择同一专家集合中的专家，有效地平衡专家之间的负载。我们的理论分析将通过后面的实验进一步证实。

5. 遗忘和泛化的理论结果

对于在第 3 节中描述的 MoE 模型，我们定义 $E_t(\mathbf{w}^{(m_t)}_t)$ 为第 t 轮的模型误差：
$$
E_t(\mathbf{w}^{(m_t)}_t) = |\mathbf{w}^{(m_t)}t - w{n_t}|_2^2,
$$
它表征了在第 t 轮中，被选中的专家 $m_t$ 与模型 $\mathbf{w}^{(m_t)}_t$ 针对任务 $n_t$ 的泛化性能。根据 CL 领域的现有文献，我们使用遗忘和整体泛化误差的指标来评估 MoE 在 CL 中的表现，定义如下：

遗忘：定义 $F_t$ 为在学习任务 $n_t$ 后遗忘旧任务的程度，对于 $t \in {2, \cdots, T}$：
$$
F_t = \frac{1}{t-1} \sum_{\tau=1}^{t-1} (E_\tau(\mathbf{w}^{(m_\tau)}t) - E\tau(\mathbf{w}^{(m_\tau)}_\tau)).
$$
整体泛化误差：我们通过计算所有任务的平均模型误差来评估最后一轮训练 T 中模型 $\mathbf{w}^{(m)}T$ 的泛化性能：
$$
G_T = \frac{1}{T} \sum{\tau=1}^T E_\tau(\mathbf{w}^{(m_\tau)}_T).
$$
接下来，我们为使用单一专家（即，$M = 1$）的学习提供了上述两个指标的显式形式，作为基准。这里我们定义 $r := 1 - \frac{s}{d}$ 为过参数化比率。

命题 4：如果 $M = 1$，对于任何训练轮次 $t \in {2, \cdots, T}$，我们有
$$
E[F_t] = \frac{1}{t-1} \sum_{\tau=1}^{t-1} \left( \frac{r^{t-\tau}}{N} \sum_{n=1}^N |w_n|2^2 + \frac{r^\tau - r^t}{N^2} \sum{n=n’} |w_{n’} - w_n|_2^2 \right),
$$

$$
E[G_T] = \frac{r^T}{N} \sum_{n=1}^N |w_n|2^2 + \frac{1 - r^T}{N^2} \sum{n=n’} |w_{n’} - w_n|2^2.
$$
命题 4 的证明在附录 H 中给出。命题 4 意味着不同任务之间的大模型差距 $|w{n’} - w_n|_2^2$ 导致 $E[F_t]$ 和 $E[G_T]$ 的性能差。

接下来，我们研究了 MoE 在 CL 中的影响，分为两种情况：（I）专家数量多于任务（M > N），和（II）专家数量少于任务（M < N）。通过与命题 4 中的单专家基线比较，MoE 的好处将被表征。

5.1 情况 I：专家多于任务

基于命题 1，我们得出以下定理中遗忘和整体泛化误差的显式上界。为了简化符号，我们定义 $L(m)_t := t \cdot f(m)_t$ 作为直到轮次 $t$ 路由到专家 $m$ 的累计任务到达次数，其中 $f(m)_t$ 在方程（7）中给出。

定理 1：如果 $M = \Omega(N \ln(N))$，对于每个轮次 $t \in {2, \cdots, T_1}$，预期遗忘满足
$$
E[F_t] < \frac{1}{t-1} \sum_{\tau=1}^{t-1} \left( \frac{r^{L(m_\tau)t} - r^{L(m\tau)\tau}}{N} \sum{n=1}^N |w_n|2^2 + \frac{r^{L(m\tau)\tau} - r^{L(m\tau)t}}{N^2} \sum{n=n’} |w_{n’} - w_n|2^2 \right).
$$
对于每个 $t \in {T_1 + 1, \cdots, T}$，我们有 $E[F_t] = \frac{T_1 - 1}{t-1} E[F{T_1}]$。进一步，在训练最后一轮 $T$ 的任务 $n_T$ 后，整体泛化误差满足
$$
E[G_T] < \frac{1}{T} \sum_{\tau=1}^T \left( \frac{r^{L(m_\tau){T_1}}}{N} \sum{n=1}^N |w_n|2^2 + \frac{1 - r^{L(m\tau){T_1}}}{N^2} \sum{n=n’} |w_{n’} - w_n|_2^2 \right).
$$
定理 1 的证明在附录 I 中给出，我们有以下见解：

遗忘：如果 $t \leq T_1$，在方程（19）中，项$\sum_{n=1}^N |w_n|^2$ 系数$r_{t}^{L_{t}^{\left(m_{\tau}\right)}}-r^{L_{\tau}^{\left(m_{\tau}\right)}}$ 于 0，因为 $L(m_\tau)t \geq L(m\tau)\tau$ 且 $r < 1$，表明新任务的训练增强了旧任务的性能，由于这一阶段的重复任务到达。与此同时，模型差距 $\sum{n=n’} |w_{n’} - w_n|2^2$ 的系数大于 0，表明遗忘是由于专家探索不同任务。然而，如命题 1 所述，一旦专家模型在 $t = T_1$ 收敛，后续新任务到达的训练不会导致先前任务的遗忘。因此，对于 $t \in {T_1 + 1, \cdots, T}$，$E[F_t] = \frac{T_1 - 1}{t-1} E[F{T_1}]$ 随着 $t$ 的增加而减少，并随着 $T \to \infty$ 收敛到零。这一趋势表明，与单一专家的振荡遗忘（方程 17）相比，MoE 模型可以显著减少 CL 的预期遗忘。此外，任务相似性的降低，即更大的模型差距，进一步放大了 MoE 模型的学习好处。
泛化误差：注意当任务不太相似且模型差距大时，第二项 $\sum_{n=n’} |w_{n’} - w_n|2^2$ 主导泛化误差。在方程（22）中，模型差距 $\sum{n=n’} |w_{n’} - w_n|2^2$ 的系数 $1 - r^{L(m\tau)_{T_1}}$ 小于方程（18）中的 $1 - r^T$，由于专家模型在 $T_1$ 后收敛。因此，与单一专家相比，MoE 下的泛化误差减少，特别是随着 $T$ 增加（其中 $1 - r^T$ 接近 1）。
专家数量：根据定理 1，对于 $t > T_1$，$E[F_t]$ 随着 $T_1$ 的增加而增加，因为额外的专家探索轮次累积了更多的模型误差（方程 19）。关于 $E[G_T]$ 在方程（20）中，更长的专家探索期 $T_1$ 增加了模型差距的系数 $1 - r^{L(m_\tau){T_1}}$，导致当任务之间的模型差距大时 $E[G_T]$ 增加。由于 $T_1$ 随着专家数量 $M$ 增加，增加更多专家并不增强学习性能，但延迟了收敛。注意，如果定理 1 中的 $M = 1$，$L(m\tau)_t$ 变为 $t$ 单一专家，导致方程（19）和方程（20）分别专门化为方程（17）和方程（18）。

5.2 情况 II：专家少于任务

接下来，我们考虑一个更一般的情况，即专家少于任务，即 $M < N$，其中算法 1 仍然有效。特别是，我们假设 $N$ 个真实情况在 $W$ 中可以根据任务相似性被分类为 $K$ 个簇，其中 $K < M$。让 $W_k$ 表示第 $k$ 个任务簇。对于任何两个在同一个簇 $W_k$ 中的任务 $n, n’$，我们假设 $|w_n - w_{n’}|\infty = O(\sigma{1.5}^0)$。然后我们让集合 $M_k$ 包括所有专门处理 $k$- 簇任务的专家。

回想命题 1 表明，如果 $M > N$，专家模型在 $T_1$ 轮探索后收敛。然而，在专家少于任务（$M < N$）的情况下，每个专家必须专门处理学习一组类似的任务。因此，随着相似任务持续路由到每个专家，专家模型在 $T_1$ 轮后继续更新，与命题 1 中的 $M > N$ 情况不同。基于上述理解，我们有以下定理。

定理 2：如果 $M < N$ 且 $M = \Omega(K \ln(K))$，对于任何 $t \in {1, \cdots, T_1}$，预期遗忘 $E[F_t]$ 与方程（19）相同。而对于一些 $t \in {T_1 + 1, \cdots, T}$，预期遗忘满足
$$
E[F_t] < \frac{1}{t-1} \sum_{\tau=1}^{t-1} \left( \frac{r^{L(m_\tau)t} - r^{L(m\tau)\tau}}{N} \sum{n=1}^N |w_n|2^2 + \frac{1}{t-1} \sum{\tau=1}^{T_1} \frac{r^{L(m_\tau)i} - r^{L(m\tau){T_1}}}{N^2} \sum{n=n’} |w_{n’} - w_n|2^2 \
+ \Psi_1 \frac{1}{t-1} \sum{\tau=T_1+1}^t (1 - r^{L(m_\tau)t} - L(m\tau)\tau) r^{L(m\tau)t} - L(m\tau){T_1} -1, \right)
$$
其中 $\Psi_1 = \frac{1}{N} \sum{n=1}^N \frac{1}{|W_k|} \sum_{n’ \in W_k} |w_{n’} - w_n|2^2$ 是同一任务簇中任意两个任务之间的预期模型差距。在训练最后一轮 $T$ 的任务 $n_T$ 后，整体泛化误差满足
$$
E[G_T] < \frac{1}{T} \sum{\tau=1}^T r^{L(m_\tau)T} \left( \frac{1}{N} \sum{n=1}^N |w_n|2^2 + \frac{1}{T_1} \sum{\tau=1}^{T_1} r^{L(m_\tau)T - L(m\tau){T_1}} (1 - r^{L(m\tau){T_1}}) \frac{1}{N^2} \sum{n=n’} |w_{n’} - w_n|2^2 \right) \+ \Psi_2 \frac{1}{T} \sum{\tau=T_1+1}^T (1 - r^{L(m_\tau)T - L(m\tau){T_1}}) + \Psi_1 \frac{1}{T} \sum{\tau=T_1+1}^T (1 - r^{L(m_\tau)T - L(m\tau){T_1}}),
$$
其中 $\Psi_2 = \frac{1}{N} \sum{n=1}^N \frac{1}{K} \sum_{k=1}^K \frac{1}{|W_k|} \sum_{n’ \in W_k} |w_{n’} - w_n|_2^2$ 是随机选择的任务 $W$ 中的任何任务与固定真实情况簇 $W_k$ 中的任何任务之间的预期模型差距。

定理 2 的证明在附录 J 中给出，我们提供以下见解：

遗忘：与定理 1 相比，方程（21）中的 $E[F_t]$ 引入了一个额外的项 $\Psi_1$，它测量了在 ${T_1 + 1, \cdots, \tau}$ 期间由于新任务到达而更新专家模型导致的遗忘。然而，由于在 ${T_1 + 1, \cdots, T}$ 期间路由到同一专家的任务属于同一簇，它们的小模型差距导致最小的遗忘。如果每个簇中只有一个任务，$\Psi$ 变为 0，且 $E[F_t]$ 与方程（19）相同。
泛化误差：由于专家模型在任何 $t$ 持续更新，方程（22）中的 $E[G_T]$ 包括三个项：a) $t < T_1$ 时任意两个随机任务到达之间的预期模型差距 $\frac{1}{N^2} \sum_{n=n’} |w_{n’} - w_n|2^2$，b) $t > T_1$ 时同一簇中两个任务之间的预期模型差距 $\Psi_1$，以及 c) $t < T_1$ 时随机任务到达与固定真实情况簇 $W_k$ 中的任何任务之间的预期模型差距 $\Psi_2$。如果每个簇中只包含一个任务，$\Psi_2$ 的系数简化为 $\sum{\tau=T_1+1}^T (1 - r^{L(m_\tau){T_1}})$，给定 $L(m\tau)T = L(m\tau){T_1}$ 在 $T_1$ 后没有更新。此外，$\Psi_2 = \frac{1}{N^2} \sum{n=n’} |w_{n’} - w_n|_2^2$ 且 $\Psi_1 = 0$，导致方程（22）专门化为方程（20）。

注意，根据我们的假设 $|w_n - w_{n’}|\infty = O(\sigma{1.5}^0)$，路由器无法区分同一簇中的相似任务 $n$ 和 $n’$。因此，增加更多专家不能避免方程（21）和方程（22）中的误差 $\Psi_1$ 和 $\Psi_2$。因此，与定理 1 类似，当有足够的专家比簇多时（即，$M = \Omega(K \ln(K))$），增加更多专家并不增强学习性能，但延迟了收敛。尽管与定理 1 相比学习性能有所下降，但它仍然从 MoE 中受益，与命题 4 中的单一专家相比。

注意，如果我们扩展到方程（1）中的 top-k 路由策略，路由器将选择 k 个专家同时训练相同的数据。在这种情况下，方程（21）中描述的遗忘可能会减少，因为每个专家可能处理比 top-1 路由策略中更小的任务簇。然而，现在属于同一簇的相似任务可能被划分为不同的簇，并由不同的专家处理，这可能会减少这些任务之间的潜在正向知识转移。因此，top-k 情况下的泛化误差可能不比 top-1 情况小。

6. 实验

在本节中，我们对线性模型和 DNNs 进行了广泛的实验，以支持我们的理论分析。与大多数 CL 理论研究相比，我们的工作已经包括了更全面的实验调查。由于空间限制，我们将实验细节和关于终止阈值和负载平衡影响的额外实验委托给附录 A。

关键设计的提前终止。在第一个实验中，我们旨在检查算法 1 中终止 $\Theta_t$ 更新的必要性。这里我们设置 $T = 2000$，$N = 7$，$K = 3$ 并变化专家数量 $M \in {1, 5, 10, 20}$。如图 2(a) 和图 2(c) 所示，MoE 模型的遗忘和泛化误差首先由于专家探索而增加，然后在终止更新的情况下对所有 MoE 模型收敛到几乎零，验证了定理 1 和定理 2。与此形成鲜明对比的是，图 2(b) 和图 2(d) 中没有终止的学习导致性能差且大振荡，因为路由器在持续更新 $\Theta_t$ 后为新任务到达选择错误的专家。此外，在图 2(a) 和图 2(c) 中，MoE 模型与单一模型相比显著提高了 CL 的性能。M = 10 和 M = 20 之间的比较也表明，如果 $M > N$，增加额外的专家会延迟收敛，而不会改善学习性能，验证了我们在定理 1 和定理 2 中的分析。

真实数据验证。最后，我们将算法 1 和线性模型的见解扩展到 DNNs，通过在 MNIST 数据集上进行实验。我们设置 $N = 3$ 并变化 $M \in {1, 4, 7}$。在每个训练轮次中，我们通过平均 s = 100 个训练样本获得特征矩阵。为了使不同任务的模型差距多样化，我们将 d×d 矩阵转换为 d×d 维的归一化向量，作为门控网络的输入。然后我们计算输入向量中每个元素的方差 $\sigma_0$，这将用于算法 1 中的参数设置。图 3 显示，我们从线性模型中的理论见解也适用于 DNNs，就 MoE 和提前终止对 CL 性能的影响而言。

7. 结论

在这项工作中，我们进行了 MoE 及其对 CL 学习性能影响的首次理论分析，重点关注过参数化线性回归问题。我们证明了 MoE 模型可以使专家多样化，专门处理不同任务，同时其路由器可以学习为每个任务选择正确的专家并在所有专家之间平衡负载。然后我们展示了，在 CL 中，终止门控网络参数更新在足够的训练轮次后是系统收敛的必要条件。此外，我们提供了预期遗忘和整体泛化误差的显式形式，以评估 MoE 的影响。最后，我们在真实数据集上使用 DNNs 进行实验，表明某些见解可以超越线性模型。

附录

A 实验细节和额外实验

A.1 实验计算资源

操作系统：macOS Sonoma 14.2.1。
CPU 类型：2.6 GHz 6-Core Intel Core i7。
GPU 类型：Intel UHD Graphics 630 1536 MB。
内存：16 GB 2667 MHz DDR4。
执行时间：图 2 为 40 分钟，图 3 为 100 分钟，图 4 和图 5 为 80 分钟。

A.2 图 2 的实验细节

合成数据生成：我们首先生成 N 个真实情况及其对应的特征信号。对于每个真实情况 $w_n \in \mathbb{R}^d$，其中 $n \in [N]$，我们通过正态分布 $N(0, \sigma_0)$ 随机生成 d 个元素。然后通过常数缩放这些真实情况以获得它们的特征信号 $v_n$。在每个训练轮次 $t$ 中，我们根据真实情况池 $W$ 和特征信号生成 $(X_t, y_t)$。具体来说，在抽取 $w_{n_t}$ 后，对于 $X_t \in \mathbb{R}^{d \times s}$，我们随机选择一个 $s$ 样本填充 $v_{n_t}$。其余 $s - 1$ 个样本从 $N(0, \sigma_t^2 I_d)$ 中生成。最后，我们计算输出 $y_t = X_t^\top w_{n_t}$。这里我们设置 $\sigma_0 = 0.4$，$\sigma_t = 0.1$，$d = 10$ 和 $s = 6$。在图 2 中，我们设置 $\eta = 0.5$，$\alpha = 0.5$ 和 $\lambda = 0.3$。

A.3 图 3 的实验细节

数据集：我们使用 MNIST 数据集，每个训练轮次随机选择 100 个样本进行训练，1000 个样本用于测试。
DNN 架构和训练细节：我们使用一个包含两个卷积层和三个全连接层的五层神经网络。第一个卷积层后跟一个步长为 2 的 2D 最大池化操作。每个任务使用 SGD 进行学习，学习率为 0.2，训练 600 个周期。遗忘和整体泛化误差分别按照方程（15）和方程（16）进行评估。这里，$E_t(\mathbf{w}^{(m_t)}_t)$ 定义为均方测试误差，而不是方程（14）。

A.4 关于终止阈值和负载平衡的实验

在额外的实验中，我们变化终止阈值 $\Gamma \in {\sigma_{0.75}^0, \sigma_0, \sigma_{1.25}^0, \sigma_{1.5}^0}$ 来研究其对负载平衡和学习性能的影响，使用与图 2 相同的合成数据生成方法。

最初，我们设置 $\sigma_0 = 0.4$，$\lambda = \sigma_{1.25}^0$，$M = 5$，和 $N = 6$ 与 $K = 3$ 任务簇：$W_1 = {1, 4}$，$W_2 = {2, 5}$，和 $W_3 = {3, 6}$。图 4 展示了每轮任务到达及其路由专家的记录。图 4(a) 和图 4(b) 展示了如果 MoE 模型基于 $\Gamma > \lambda$ 终止更新，小噪声 $r(m)_t$ 不能改变路由器对于每个任务簇（例如，专家 5 对于 $W_2 = {2, 5}$）在方程（1）中的决策，导致专家负载不平衡。而对于 $\Gamma \leq \lambda$ 的图 4(c) 和图 4(d)，方程（1）中的随机噪声 $r(m)_t$ 可以减少同一专家集中专家之间的门控输出差距，确保负载平衡（例如，专家 3 和 4 对于 $W_2 = {2, 5}$）。

为了进一步检查负载平衡如何影响学习性能，我们将任务数量增加到 $N = 30$。我们重复实验 100 次，并在图 5 中绘制平均遗忘和泛化误差。图 5(a) 展示了遗忘对于广泛的 $\Gamma$ 是稳健的，这是由于专家模型在 $T_1$ 轮探索后收敛。然而，图 5(b) 显示 $\Gamma \in {\sigma_{1.25}^0, \sigma_{1.5}^0}$ 下的平衡负载导致较小的泛化误差，与 $\Gamma \in {\sigma_{0.75}^0, \sigma_0}$ 下的不平衡负载相比。这是因为多样化的专家模型有助于减少与单一过拟合模型相比的模型误差。

B 平滑路由器

我们首先证明方程（1）确保了不同路由行为之间的平滑过渡，这使得路由器更加稳定。假设有两个不同的数据集 $(X, y)$ 和 $(\hat{X}, \hat{y})$ 同时作为 MoE 的输入。让 $h$ 和 $\hat{h}$ 分别表示两个数据集对应的门控网络输出。用 $p$ 和 $\hat{p}$ 表示概率向量，它们告诉每个专家为这两个数据集被路由的概率。例如，$p_m = P(\arg\max_{m’\in[M]}{h_{m’} + r(m’)} = m)$ 和 $\hat{p}m = P(\arg\max{m’\in[M]}{\hat{h}_{m’} + r(m’)} = m)$ 根据方程（1）。然后我们提出以下引理来证明平滑路由器。

引理 2：两个概率向量满足 $|p - \hat{p}|\infty \leq \frac{\lambda}{M^2} |h - \hat{h}|\infty$。

证明：设 $m_1 = \arg\max_m {h_m + r(m)}$ 和 $m_2 = \arg\max_m {\hat{h}m + r(m)}$。我们首先考虑 $m_1 \neq m_2$ 的情况。在这种情况下，我们有 $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)$，这意味着 $\hat{h}{m_2} - \hat{h}{m_1} > r(m_1) - r(m_2) \geq h_{m_2} - h_{m_1}$。

定义 $C(m_1, m_2) = \frac{\hat{h}{m_2} - \hat{h}{m_1} + h_{m_2} - h_{m_1}}{2}$。根据上述不等式，我们得到
$$
|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{h} - h|\infty.
$$
因此，我们计算
$$
P(\arg\max_m {h_m + r(m)} \neq \arg\max_m {\hat{h}m + r(m)}) \leq 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{h} - h|\infty) \leq \sum{m_1 < m_2} E[P(r(m_2) + C(m_1, m_2) - |\hat{h} - h|\infty \leq r(m_1) \leq r(m_2) + C(m_1, m_2) + |\hat{h} - h|\infty)|r(m_2)|] \leq \lambda M^2 |\hat{h} - h|_\infty,
$$
其中第一个不等式由上述不等式得出，第二个不等式是由于并集界限，最后一个不等式是因为 $r(m)$ 是从 Unif [0, $\lambda$] 中抽取的。

然后对于任何 $j \in [M]$，我们有
$$
|\hat{p}_i - p_i| \leq E[|1(\arg\max_m {\hat{h}_m + r(m) = i}) - 1(\arg\max_m {\hat{h}_m + r(m) = i})|] \leq E[P(\arg\max_m {h_m + r(m)} \neq \arg\max_m {\hat{h}m + r(m)})] \leq M^2 |\hat{h} - h|\infty.
$$
这完成了引理 2 的证明。

直观上，引理 2 告诉我们，如果两个任务的数据集 $(X, y)$ 和 $(\hat{X}, \hat{y})$ 由相同的真实情况生成，那么这两个概率向量在引理 2 中满足 $|p - \hat{p}|\infty = O(\lambda M^2 \sigma{1.5}^0)$。

C 引理 1 的完整版本和证明

引理 1（完整版本）：对于任何两个具有特征信号 $v_n$ 和 $v’n$ 的特征矩阵 $X$ 和 $\tilde{X}$，如果 $w_n = w{n’}$ 在 $M > N$ 下，或 $w_n, w_{n’} \in W_k$ 在 $M < N$ 下，以至少 $1 - o(1)$ 的概率，它们对应的同一专家 $m$ 的门控输出满足
$$
|h_m(X, \theta^{(m)}t) - h_m(\tilde{X}, \theta^{(m)}t)| = O(\sigma{1.5}^0).
$$
证明：我们首先关注 $M > N$ 情况来证明引理 1。然后我们考虑 $M < N$ 情况来证明引理 1。对于每轮 $t$ 根据定义 1 生成的数据集 $(X_t, y_t)$，我们可以假设 $X_t$ 的第一个样本是信号向量。因此，我们重写 $X_t = [\beta_t v_n, X{t,2}, \cdots, X_{t,s}]$。让 $\tilde{X}t = [\beta_t v{n_t}, 0, \cdots, 0]$ 表示只保留特征信号的矩阵。

根据第 3 节中门控网络的定义，我们有 $h_m(X_t, \theta^{(m)}t) = \sum{i=1}^s (\theta^{(m)}t)^\top X{t,i}$。然后我们计算
$$
|h_m(X_t, \theta^{(m)}t) - h_m(\tilde{X}t, \theta^{(m)}t)| = \left| \sum{i=2}^s (\theta^{(m)}t)^\top X{t,i} \right| \leq \max{t,j} {\theta^{(m)}{t,j}} \cdot \left| \sum_{i=2}^s \sum_{j=1}^d X_{t,(i,j)} \right|,
$$
其中 $\theta^{(m)}_{t,j}$ 是向量 $\theta^{(m)}t$ 的第 j 个元素，$X{t,(i,j)}$ 是矩阵 $X_t$ 的第 $(i, j)$ 个元素。

然后我们应用 Hoeffding 不等式来获得
$$
P\left( \left| \sum_{i=2}^s \sum_{j=1}^d X_{t,(i,j)} \right| < s \cdot d \cdot \sigma_0 \right) \geq 1 - 2 \exp \left( -\frac{\sigma_0^2 s^2 d^2}{|X_{t,i}|\infty} \right).
$$
由于 $X{t,(i,j)} \sim N(0, \sigma_t^2)$，我们有 $|X_{t,i}|\infty = O(\sigma_t)$，表明 $\exp \left( -\frac{\sigma_0^2 s^2 d^2}{|X{t,i}|\infty} \right) = o(1)$。因此，以至少 $1 - o(1)$ 的概率，我们有 $\left| \sum{i=2}^s \sum_{j=1}^d X_{t,(i,j)} \right| = O(\sigma_0)$。因此，我们得到
$$
|h_m(X_t, \theta^{(m)}t) - h_m(\tilde{X}t, \theta^{(m)}t)| = O(\sigma{1.5}^0)
$$
由于 $\left| \sum{i=2}^s \sum{j=1}^d X_{t,(i,j)} \right| = O(\sigma_0)$ 和 $\theta^{(m)}{t,j} = O(\sigma{0.5}^0)$ 在稍后证明的引理 6 中。

如果 $M < N$，我们计算
$$
|h_m(X_t, \theta^{(m)}_t) - h_m(\tilde{X}_t, \theta^{(m)}_t)| = |(\theta^{(m)}_t)^\top \sum_{i=1}^s X_{t,i}| \leq |(\theta^{(m)}_t)^\top \sum_{i=2}^s X_{t,i}| + |(\theta^{(m)}_t)^\top (v_n - v’_n)| \leq \max_{t,j} {\theta^{(m)}_{t,j}} \cdot \left| \sum_{i=2}^s \sum_{j=1}^d X_{t,(i,j)} \right| + O(\sigma_0^2) = O(\sigma_{1.5}^0),
$$
其中第二个不等式是基于并集界限，第三个不等式是因为 $\theta^{(m)}_{t,j} = O(\sigma_{0.5}^0)$ 和我们的假设 $|v_n - v’_n|_\infty = O(\sigma_{1.5}^0)$，最后一个不等式是基于我们上述 $M > N$ 情况的证明。这完成了引理 1 的完整证明。

基于引理 1，我们重新审视引理 2，得到以下结论，关于平滑路由器。

推论 1：如果数据集 $(X, y)$ 和 $(\hat{X}, \hat{y})$ 由相同的真实情况生成，那么引理 2 中的两个概率向量满足 $|p - \hat{p}|\infty = O(\lambda M^2 \sigma{1.5}^0)$。

D 损失函数分析

在分析 MoE 之前，我们分析了门控网络参数和专家模型的损失函数。

引理 3：根据方程（5）的更新规则，如果当前任务 $n_t$ 路由到专家 $m_t$ 与上一个任务 $n_\tau$ 路由到专家 $m_t$ 有相同的真实情况，即 $w_{n_t} = w_{n_\tau}$，那么专家 $m_t$ 的模型满足 $\mathbf{w}^{(m_t)}t = \mathbf{w}^{(m_t)}{t-1} = \cdots = \mathbf{w}^{(m_t)}_\tau$。

引理 3 很容易通过方程（5）的更新规则证明，因此我们在这里省略证明。

接下来，我们检查门控网络参数的训练。

引理 4：对于任何训练轮次 $t \geq 1$，我们有 $\sum_{m=1}^M \nabla_{\theta(m)t} L{\text{task}}^t = 0$。

证明：由于训练损失 $\nabla_{\theta(m)} L_{\text{tr}}^t = 0$，我们得到 $\nabla_{\theta(m)t} L{\text{task}}^t = \nabla_{\theta(m)t} L{\text{loc}}^t + \nabla_{\theta(m)t} L{\text{aux}}^t$。接下来，我们将分别证明 $\sum_{m=1}^M \nabla_{\theta(m)t} L{\text{loc}}^t = 0$ 和 $\sum_{m=1}^M \nabla_{\theta(m)t} L{\text{aux}}^t = 0$。

根据局部损失的定义（方程 6），我们计算
$$
\nabla_{\theta(m)t} L{\text{loc}}^t = \frac{\partial \pi_{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} |\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m_t)}{t-1}|2^2.
$$
如果 $m = m_t$，我们得到 $\frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} = \pi{m_t}(X_t, \Theta_t) \cdot \left( \sum{m’ \neq m_t} \pi_{m’}(X_t, \Theta_t) \right) \cdot \sum_{i \in [s_t]} X_{t,i}$。

如果 $m \neq m_t$，我们得到 $\frac{\partial \pi_{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} = -\pi{m_t}(X_t, \Theta_t) \cdot \pi_m(X_t, \Theta_t) \cdot \sum_{i \in [s_t]} X_{t,i}$。

基于上述，我们得到 $\sum_{m=1}^M \nabla_{\theta(m)t} L{\text{loc}}^t = |\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m_t)}{t-1}|2^2 \sum{m=1}^M \frac{\partial \pi_{m_t}(X_t, \Theta_t)}{\partial \theta(m)_t} = 0$。

根据辅助损失的定义（方程 7），我们计算
$$
\nabla_{\theta(m)t} L{\text{aux}}^t = \alpha M \sum_{m’=1}^M f(m’)_t \frac{\partial P(m’)_t}{\partial \theta(m)_t} = \alpha M t f(m_t)t \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)_t},
$$
其中第二个等式是因为 $\frac{\partial P(m_t)_t}{\partial \theta(m)t} = \frac{1}{t} \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t}$ 且 $\frac{\partial P(m’)t}{\partial \theta(m)t} = 0$ 对于任何 $m’ \neq m_t$ 由方程（7）。然后基于上述，我们同样得到 $\sum{m=1}^M \nabla{\theta(m)t} L{\text{aux}}^t = \alpha M t f(m_t)t \sum{m=1}^M \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)_t} = 0$。

总结，我们最终证明了 $\sum_{m=1}^M \nabla_{\theta(m)t} L{\text{task}}^t = 0$。

在接下来的引理中，我们分析每个专家的损失函数梯度。

引理 5：对于任何训练轮次 $t \in {1, \cdots, T}$，以下性质成立
$$
|\nabla_{\theta(m)t} L{\text{task}}^t|_\infty = \begin{cases} \Omega(\sigma_0), & \text{if } t \in {1, \cdots, T_1}, \ O(\sigma_0), & \text{if } t \in {T_1 + 1, \cdots, T} \end{cases}
$$
对于任何专家 $m \in [M]$，其中 $T_1 = \lceil \eta^{-1}M \rceil$ 是探索阶段的长度。

证明：我们通过分析 $\nabla_{\theta(m)t} L{\text{loc}}^t = O(\sigma_0)$ 和 $\nabla_{\theta(m)t} L{\text{aux}}^t = O(\alpha M / t)$ 来证明引理 5，分别基于方程（26）。

首先，我们计算 $|\nabla_{\theta(m)t} L{\text{loc}}^t|\infty$。基于方程（27），我们有
$$
\nabla{\theta(m)t} L{\text{loc}}^t = \frac{\partial \pi_{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} |\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m_t)}{t-1}|2^2 \leq |\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m_t)}{t-1}|2^2 \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t},
$$
其中 $\tau$ 是最后一个路由到专家 $m_t$ 的任务索引，第二个等式是基于引理 3。由于 $\frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} = O(1)$ 且 $w_n \sim N(0, \sigma_0^2)$，我们最终得到
$$
|\nabla{\theta(m)t} L{\text{loc}}^t|\infty = O(\sigma_0).
$$
接下来，我们进一步计算 $|\nabla{\theta(m)t} L{\text{aux}}^t|_\infty$，它包含以下两种情况。

如果 $t \in {1, \cdots, T_1}$，根据方程（30），我们有
$$
|\nabla_{\theta(m)t} L{\text{aux}}^t|\infty \geq |\alpha M / T_1 f(m_t)t \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t}|\infty \geq |\sigma_0 f(m_t)t \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t}|\infty = \Omega(\sigma_0),
$$
其中第二个不等式是通过设置 $\eta = \Omega(\sigma{0.5}^0)$ 来使 $T_1 = \lceil \sigma_{-0.5}^0 M \rceil$。

如果 $t \in {T_1 + 1, \cdots, T}$，我们计算
$$
|\nabla_{\theta(m)t} L{\text{aux}}^t|\infty \leq |\alpha M / T_1 f(m_t)t \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t}|\infty = O(\sigma_0).
$$
基于上述推导出的 $|\nabla{\theta(m)t} L{\text{loc}}^t|\infty$ 和 $|\nabla{\theta(m)t} L{\text{aux}}^t|\infty$，我们可以根据方程（26）最终计算 $|\nabla{\theta(m)t} L{\text{task}}^t|_\infty$。

对于 $t \in {1, \cdots, T_1}$，如果 $m \neq m_t$，我们有 $|\nabla_{\theta(m)t} L{\text{task}}^t|\infty = |\nabla{\theta(m)t} L{\text{loc}}^t + \nabla_{\theta(m)t} L{\text{aux}}^t|_\infty \leq |O(\sigma_0) + \alpha M / T_1 f(m_t)t \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t}|\infty = \Omega(\sigma_0)$。

类似地，对于任何 $t \in {T_1 + 1, \cdots, T}$，我们可以得出 $|\nabla_{\theta(m)t} L{\text{task}}^t|\infty = |\nabla{\theta(m)t} L{\text{loc}}^t + \nabla_{\theta(m)t} L{\text{aux}}^t|_\infty \geq |O(\sigma_0) + \alpha M / T_1 f(m_t)t \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t}|\infty = O(\sigma_0)$。这完成了引理 5 的证明。

给定 $\theta(m)_0 = 0$ 对于任何专家 $m \in [M]$，在下一个引理中，我们得到了任何轮次 $t \in {1, \cdots, T}$ 中门控网络参数 $\theta(m)_t$ 的上界。

引理 6：对于任何训练轮次 $t \in {1, \cdots, T}$，任何专家 $m$ 的门控网络参数满足 $|\theta(m)t|\infty = O(\sigma_{0.5}^0)$。

证明：基于引理 5，对于任何 $t \in {1, \cdots, T_1}$，门控网络参数 $\theta(m)t$ 在探索阶段的累积更新满足 $|\theta(m)t|\infty \leq \eta \cdot T_1 \cdot \alpha M = O(\sigma{0.5}^0)$。

对于任何 $t \in {T_1 + 1, \cdots, T}$，门控网络参数 $\theta(m)t$ 在路由器学习阶段的累积更新满足
$$
|\theta(m)t|\infty \leq |\theta(m){T_1}|\infty + \eta \cdot (T - T_1) \cdot \alpha M / T_1 = O(\sigma{0.5}^0) + O(\sigma_{0.5}^0 - \sigma_0) = O(\sigma_{0.5}^0).
$$
总结，$|\theta(m)t|\infty = O(\sigma_{0.5}^0)$ 对于任何轮次 $t \in {1, \cdots, T}$。

E 引理 1 的完整版本和证明

引理 1（完整版本）：在算法 1 下，以至少 $1 - o(1)$ 的概率，对于任何 $t > T_1$，其中 $T_1 = \lceil \eta^{-1}M \rceil$，每个专家 $m \in [M]$ 满足以下属性：

如果 $M > N$，专家 $m$ 在专家集合 $M_n$ 中稳定，其专家模型在时间 $T_1$ 之后保持不变，满足 $\mathbf{w}^{(m)}_{T_1+1} = \cdots = \mathbf{w}^{(m)}_T$。
如果 $M < N$，专家 $m$ 在专家集合 $M_k$ 中稳定，其专家模型满足 $|\mathbf{w}^{(m)}t - \mathbf{w}^{(m)}{T_1+1}|\infty = O(\sigma{1.5}^0)$ 对于任何 $t \in {T_1 + 2, \cdots, T}$。

我们首先提出以下引理作为预备，然后正式在附录 E.8 中证明引理 1。

引理 7：在任何训练轮次 $t \in {1, \cdots, T_1}$ 中，对于任何特征信号 $v_n$，专家 $m \in [M]$ 的门控网络参数满足
$$
\langle \theta^{(m)}_{t+1} - \theta^{(m)}t, v_n \rangle = \begin{cases} -O(\sigma_0), & \text{if } m = m_t, \ O(M^{-1}\sigma_0), & \text{if } m \neq m_t. \end{cases}
$$
引理 7 告诉我们，对于任何被路由器选中的专家 $m_t$，其在更新 $\theta^{(m_t)}{t+1}$ 时的 softmax 值由于下一个任务而减少，而对于任何未被选中的专家 $m$，其 softmax 值增加。这是为了确保在辅助损失函数（方程 7）下每个专家 $m$ 的公平探索。此外，对于任何未被选中的专家 $m$，其门控网络参数 $\theta^{(m)}_t$ 对所有其他信号向量 $v_n$ 的更新速度与其他人相同。

引理 8：在探索阶段结束时，以至少 $1 - \delta$ 的概率，任何专家 $m \in [M]$ 被分配的任务比例满足
$$
\left| f(m)_{T_1} - \frac{1}{M} \right| = O(\eta^{0.5}M^{-1}).
$$
引理 8 告诉我们，在探索阶段，所有 $M$ 个专家预计将被均匀探索。因此，门控网络参数 $\theta^{(m)}_t$ 的专家 $m$ 在所有其他人中更新相似。

引理 9：在探索阶段结束时，即 $t = T_1$，以下属性成立
$$
\left| \theta^{(m)}{T_1} - \theta^{(m’)}{T_1} \right|_\infty = O(\eta^{-0.5}\sigma_0),
$$
对于任何 $m, m’ \in [M]$ 且 $m \neq m’$。

定义 $\delta_\Theta = |h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m)}_t)|$。然后我们得到以下引理。

引理 10：在任何轮次 $t$，如果 $\delta_\Theta^t$ 接近 0，它满足 $|\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)| = O(\delta_\Theta)$。否则，$|\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)| = \Omega(\delta_\Theta)$。

引理 11：如果 $M = \Omega(N \ln(N))$，我们有 $|M_n| \geq 1$ 对于所有 $n \in [N]$ 以至少 $1 - o(1)$ 的概率。如果 $M < N$，给定 $M = \Omega(K \ln(K))$，我们有 $|M_k| \geq 1$ 对于所有 $k \in [K]$ 以至少 $1 - o(1)$ 的概率。

引理 12：在任何轮次 $t$，我们有以下属性：

对于具有真实情况 $w_{n_t} = w_n$ 的任务到达 $n_t$ 在 $M > N$ 下，如果它被路由到正确的专家 $m_t \in M_n$，则对于任何专家 $m \in [M]$，$\nabla_{\theta(m)t} L{\text{loc}}^t = 0$。
对于具有真实情况 $w_{n_t} \in W_k$ 的任务到达 $n_t$ 在 $M < N$ 下，如果它被路由到正确的专家 $m_t \in M_k$，则对于任何专家 $m \in [M]$，$|\nabla_{\theta(m)t} L{\text{loc}}^t|\infty = O(\sigma{1.5}^0)$。

让 $X_n$ 和 $X_{n’}$ 表示包含特征信号 $v_n$ 和 $v_{n’}$ 的两个特征矩阵。

引理 13：如果 $n$ 和 $n’$ 满足：1) $n \neq n’$ 在 $M > N$ 下，或 2) $w_n \in W_k$ 和 $w_{n’} \in W_{k’}$ 与 $k \neq k’$ 在 $M < N$ 下，那么如果专家 $m$ 满足 1) $m \in M_n$ 在 $M > N$ 下，或 2) $m \in M_k$ 在 $M < N$ 下，在路由器学习阶段开始时 $t = T_1 + 1$，则以下属性在任何轮次 $t \in {T_1 + 2, \cdots, T}$ 成立：
$$
\pi_m(X_n, \Theta_t) > \pi_m(X_{n’}, \Theta_t), \forall m \in [M].
$$
基于这些引理，引理 1 的证明在附录 E.8 中给出。

引理 1 证明（E.1）

证明：根据引理 5，对于任何轮次 $t \in {1, \cdots, T_1}$，辅助损失是更新 $\Theta_t$ 的主要损失。然后基于 $\theta^{(m)}t$ 的更新规则（方程 9）和 $\nabla{\theta(m_t)t} L{\text{aux}}^t$ 的梯度（方程 30），我们得到
$$
|\theta^{(m_t)}{t+1} - \theta^{(m_t)}t|\infty = |\eta \cdot \nabla{\theta(m_t)t} L{\text{aux}}^t|\infty = O(\sigma{0.5}^0 \eta) \cdot \left( \pi_{m_t}(X_t, \Theta_t) \cdot \left(1 - \pi_{m_t}(X_t, \Theta_t) \right) \cdot \sum_{i \in [s_t]} X_{t,i} \right)\infty = O(\sigma_0),
$$
其中 $\pi{m_t}(X_t, \Theta_t) \cdot (1 - \pi_{m_t}(X_t, \Theta_t)) \leq \frac{1}{4}$ 且 $|X_t|_\infty = O(1)$。

对于任何 $m \neq m_t$，我们计算 $|\theta^{(m)}{t+1} - \theta^{(m)}t|\infty = |\eta \cdot \nabla{\theta(m)t} L{\text{aux}}^t|\infty = O(\sigma{0.5}^0 \eta) \cdot \left( \pi_{m_t}(X_t, \Theta_t) \cdot \pi_m(X_t, \Theta_t) \cdot \sum_{i \in [s_t]} X_{t,i} \right)\infty = O(M^{-1}\sigma_0)$，由于 $\pi{m_t}(X_t, \Theta_t) \cdot \pi_m(X_t, \Theta_t) = O(M^{-1})$。

注意，根据方程（30），我们有 $\nabla_{\theta(m_t)t} L{\text{aux}}^t > 0$ 和 $\nabla_{\theta(m)t} L{\text{aux}}^t < 0$ 对于任何 $m \neq m_t$。因此，对于专家 $m_t$，其在门控网络中的相应输出 $h_{m_t}$ 将因为任务 $t + 1$ 而减少 $O(\sigma_0)$。而对于任何专家 $m \neq m_t$，其相应输出 $h_m$ 增加 $O(M^{-1}\sigma_0)$。

引理 8 证明（E.2）

证明：通过对称性，我们有对于任何 $m \in [M]$，$E[f(m){T_1}] = \frac{1}{M}$。通过 Hoeffding 不等式，我们得到
$$
P\left( \left| f(m){T_1} - \frac{1}{M} \right| \leq \epsilon \right) \geq 1 - 2 \exp \left( -2\epsilon^2 T_1 \right).
$$
然后我们进一步得到
$$
P\left( \left| f(m){T_1} - \frac{1}{M} \right| \leq \epsilon, \forall m \in [M] \right) \geq \left( 1 - 2 \exp \left( -2\epsilon^2 T_1 \right) \right)^M \geq 1 - 2M \exp \left( -2\epsilon^2 T_1 \right).
$$
让 $\delta = 1 - 2M \exp \left( -2\epsilon^2 T_1 \right)$。然后我们得到 $\epsilon = O(\eta^{0.5}M^{-1})$。随后，至少有 $1 - \delta$ 的概率 $\left| f(m){T_1} - \frac{1}{M} \right| = O(\eta^{0.5}M^{-1})$。

引理 9 证明（E.3）

证明：基于引理 7 和引理 8 及其相应证明，我们可以证明引理 9 如下。

对于专家 $m$ 和 $m’$，它们在探索阶段分别被路由器选择 $T_1 \cdot f(m){T_1}$ 和 $T_1 \cdot f(m’){T_1}$ 次。因此，我们得到 $|\theta(m){T_1}|\infty = f(m){T_1} \cdot T_1 \cdot O(\sigma_0) - (1 - f(m){T_1}) \cdot T_1 \cdot O(M^{-1}\sigma_0)$，$|\theta(m’){T_1}|\infty = f(m’){T_1} \cdot T_1 \cdot O(\sigma_0) - (1 - f(m’){T_1}) \cdot T_1 \cdot O(M^{-1}\sigma_0)$。

然后根据方程（9）和引理 7，我们计算 $\left| \theta(m){T_1} - \theta(m’){T_1} \right|\infty = \left| f(m){T_1} - f(m’){T_1} \right| \cdot T_1 \cdot O(\sigma_0) = O(\eta^{-0.5}\sigma_0)$，其中第一个等式是基于引理 7 中的更新步骤，最后一个等式是因为 $T_1 \cdot \left| f(m){T_1} - f(m’)_{T_1} \right| = O(\eta^{-0.5})$ 由方程（32）在引理 8 中得出。

引理 10 证明（E.4）

证明：在任何轮次 $t$，我们计算
$$
|\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)| = \pi_{m’}(X_t, \Theta_t) \left| \exp(h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t) - \pi{m’}(X_t, \Theta_t)) - 1 \right|,
$$
其中第一个等式是通过解方程（2）得到的。然后如果 $\delta_\Theta^t$ 接近 0，通过应用足够小的 $\delta_\Theta$ 的泰勒级数，我们得到
$$
|\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)| \approx \pi_{m’}(X_t, \Theta_t) |h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t)| = O(\delta\Theta),
$$
最后一个等式是因为 $\pi_m(\tilde{X}_t, \Theta_t) \leq 1$。

如果 $\delta_\Theta^t$ 不是足够小，我们得到
$$
|\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)| > \pi_{m’}(X_t, \Theta_t) |h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t)| = \Omega(\delta\Theta).
$$
这完成了引理 10 的证明。

引理 11 证明（E.5）

证明：如果 $M > N$，通过对称性，我们有对于所有 $n \in [N]$，$m \in [M]$，$P(m \in M_n) = \frac{1}{N}$。因此，$|M_n|$ 至少包含一个专家的概率是
$$
P(|M_n| \geq 1) \geq 1 - \left( 1 - \frac{1}{N} \right)^M.
$$
通过应用并集界限，我们得到
$$
P(|M_n| \geq 1, \forall n) \geq \left( 1 - \left( 1 - \frac{1}{N} \right)^M \right)^N \geq 1 - N \exp \left( -\frac{M}{N} \right) \geq 1 - \delta,
$$
其中第二个不等式是因为 $\left( 1 - \frac{1}{N} \right)^M$ 足够小，最后一个不等式是因为 $M = \Omega \left( \frac{N \ln(N)}{\delta} \right)$。

如果 $M < N$，我们可以用同样的方法证明 $P(|M_k| \geq 1, \forall k) \geq 1 - \delta$，给定 $M = \Omega \left( \frac{K \ln(K)}{\delta} \right)$ 和 $P(m \in M_k) = \frac{1}{K}$ 通过对称性。

引理 12 证明（E.6）

证明：在 $M > N$ 的情况下，由于 $|M_n| = 1$，如果任务 $n_t$ 与 $n_t = n$ 被路由到正确的专家 $m_t \in M_n$，我们有 $\mathbf{w}^{(m_t)}t = \mathbf{w}^{(m_t)}{t-1}$ 通过（5）。因此，引起的局部损失 $L_{\text{loc}}^t(\Theta_t, D_t) = 0$，基于它在方程（6）中的定义。

在 $M < N$ 的情况下，由于每个簇 $k$ 中 $|M_k| \geq 1$，如果任务 $n_t$ 与 $w_{n_t} \in W_k$ 被路由到正确的专家 $m_t \in M_k$，我们有 $|\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m_t)}{t-1}|\infty = |X_t (X_t^\top X_t)^{-1} (y_t - X_t^\top \mathbf{w}^{(m_t)}{t-1})|\infty = |X_t (X_t^\top X_t)^{-1} X_t^\top (w{n_t} - \mathbf{w}^{(m_t)}{t-1})|\infty = O(|\mathbf{w}{t} - \mathbf{w}^{(m_t)}{t-1}|\infty) = O(\sigma{1.5}^0)$，其中第二个等式是因为 $y_t = X_t^\top w_{n_t}$，第三个等式是因为 $|X_t|\infty = O(1)$。因此，我们通过解方程（27）得到 $\nabla{\theta(m)t} L{\text{loc}}^t = O(\sigma_{1.5}^0)$，对于任何 $m \in [M]$。

引理 13 证明（E.7）

证明：我们首先关注 $M > N$ 情况来证明引理 13。基于方程（35）在引理 1 中，我们得到 $\pi_m(X_n, \Theta_{T_1}) - \pi_m(X_{n’}, \Theta_{T_1}) = \Omega(\sigma_{0.5}^0)$ 对于 $m \in M_n$，给定 $|\theta^{(m)}t|\infty = O(\sigma_{0.5}^0)$ 从引理 6 得出。为了证明方程（33），我们将证明 $\pi_m(X_n, \Theta_t) - \pi_m(X_{n’}, \Theta_t) = \Omega(\sigma_{0.5}^0)$ 对任何 $t \geq T_1 + 1$ 成立。

基于引理 5，我们有 $|\nabla_{\theta(m)t} L{\text{task}}^t|\infty = O(\sigma_0)$，导致 $\langle \theta^{(m_t)}{t+1} - \theta^{(m_t)}t, v_n \rangle = -O(\sigma{1.5}^0)$ 对于专家 $m_t$ 和 $\langle \theta^{(m)}_{t+1} - \theta^{(m)}t, v_n \rangle = O(\sigma{1.5}^0)$ 对于任何其他专家 $m \neq m_t$ 在任务 $t = T_1 + 1$。

随后，对于任何两个专家 $m \in M_n$ 和 $m’ \in M_{n’}$，我们计算
$$
|\theta(m){t_1} - \theta(m’){t_1}|\infty \leq |\theta(m){T_1+2} - \theta(m’){T_1+2}|\infty + (t_1 - T_1) \cdot O(\sigma_{1.5}^0) \leq O(\sigma_0 \eta^{-0.5}) + O(\eta^{-1} \sigma_{-0.25}^0) \cdot O(\sigma_{1.5}^0) = O(\sigma_0 \eta^{-0.5}),
$$
其中第一个不等式是因为 $\langle \theta^{(m)}_{t+1} - \theta^{(m)}t, v_n \rangle = O(\sigma{1.5}^0)$，第二个不等式是因为 $t_1 - T_1 \leq t_1$。

由于 $|\theta(m){t_1} - \theta(m’){t_1}|\infty = O(\sigma_0 \eta^{-0.5})$ 且 $|\pi_m(X_n, \Theta{T_1}) - \pi_m(X_{n’}, \Theta_{T_1})| = \Omega(\sigma_{0.5}^0)$，方程（33）对任何 $t \in {T_1 + 2, \cdots, t_1}$ 成立，基于我们在引理 1 的证明。

对于 $M < N$ 的情况，我们可以用相同的方法证明方程（33）。这完成了引理 13 的证明。

引理 1 最终证明（E.8）

证明：在 $M > N$ 的情况下，为了证明引理 1，我们等价地证明在探索阶段结束时 $t = T_1$，对于任何两个专家 $m \in M_n$ 和 $m’ \in M_{n’}$ 且 $n \neq n’$，以下属性成立：$\pi_m(X_n, \Theta_t) > \pi_{m’}(X_n, \Theta_t)$，$\pi_{m’}(X_{n’}, \Theta_t) > \pi_m(X_{n’}, \Theta_t)$。基于方程（34），我们有每个专家 $m \in [M]$ 在专家集合 $M_n$ 中稳定。

根据引理 1，门控网络只关注特征信号。然后对于每个专家 $m$，我们计算 $|h_m(X_n, \theta^{(m)}t) - h_m(X{n’}, \theta^{(m)}t)| = |\langle \theta^{(m)}t, v_n - v{n’} \rangle| = |\theta^{(m)}t|\infty \cdot |v_n - v{n’}|\infty = O(\sigma_0.5^0)$，其中最后一个等式是因为 $|\theta^{(m)}t|\infty = O(\sigma_0.5^0)$ 在引理 6 中得出和 $|v_n - v{n’}|_\infty = O(1)$。

然后基于引理 10，我们得到 $|\pi_m(X_n, \Theta_t) - \pi_{m’}(X_n, \Theta_t)| = \Omega(\sigma_0.5^0)$。（方程 35）

接下来，我们通过反证法证明方程（34）。假设存在两个专家 $m \in M_n$ 和 $m’ \in M_{n’}$ 使得 $\pi_m(X_n, \Theta_t) > \pi_{m’}(X_n, \Theta_t)$，$\pi_{m’}(X_{n’}, \Theta_t) > \pi_m(X_{n’}, \Theta_t)$，这等同于 $\pi_m(X_n, \Theta_t) > \pi_m(X_{n’}, \Theta_t) > \pi_{m’}(X_{n’}, \Theta_t) > \pi_{m’}(X_n, \Theta_t)$，（方程 36）因为 $\pi_m(X_n, \Theta_t) > \pi_{m’}(X_n, \Theta_t)$ 和 $\pi_{m’}(X_{n’}, \Theta_t) > \pi_{m’}(X_n, \Theta_t)$ 基于专家集合 $M_n$ 的定义在方程（11）中。然后我们证明方程（36）在 $t = T_1$ 不存在。

对于任务 $t = T_1$，我们计算 $|h_m(X_n, \theta^{(m)}{T_1}) - h{m’}(X_n, \theta^{(m’)}{T_1})| \leq |\theta^{(m)}{T_1} - \theta^{(m’)}{T_1}|\infty |v_n|\infty = O(\sigma_0 \eta^{-0.5})$，其中第一个不等式是基于并集界限，第二个等式是因为 $|v_n|\infty = O(1)$ 和 $|\theta^{(m)}{T_1} - \theta^{(m’)}{T_1}|_\infty = O(\sigma_0 \eta^{-0.5})$ 从引理 9 在探索阶段结束时得出。

然后根据引理 10 和上述不等式，我们得到 $|\pi_m(X_n, \Theta_{T_1}) - \pi_{m’}(X_n, \Theta_{T_1})| = O(\sigma_0 \eta^{-0.5})$。（方程 38）

基于方程（36），我们进一步计算 $|\pi_m(X_n, \Theta_{T_1}) - \pi_{m’}(X_n, \Theta_{T_1})| \geq |\pi_m(X_n, \Theta_{T_1}) - \pi_m(X_{n’}, \Theta_{T_1})| = \Omega(\sigma_0.5^0)$，其中第一个不等式是基于方程（36），最后一个等式是基于方程（35）。这与方程（38）矛盾，因为 $\sigma_0 \eta^{-0.5} < \sigma_0.5^0$ 给定 $\eta = O(\sigma_0.5^0)$。因此，方程（36）在 $t = T_1$ 不存在，方程（34）对 $t = T_1$ 成立。

基于引理 13，我们得到每个专家集合 $M_n$ 在路由器学习阶段是稳定的。因此，对于任何轮次 $t \in {T_1 + 1, \cdots, T}$，任务 $n_t$ 与真实情况 $w_{n_t}$ 将被路由到其最佳专家之一 $M_{n_t}$。然后基于引理 12，我们有 $\nabla_{\theta(m)t} L{\text{loc}}^t = 0$ 在路由器学习阶段。随后，任何专家 $m$ 的 $\mathbf{w}^{(m)}_t$ 保持不变，基于引理 3。

在 $M < N$ 的情况下，我们类似地得到在探索阶段结束时 $t = T_1$，对于任何两个专家 $m \in M_k$ 和 $m’ \in M_{k’}$ 且 $k \neq k’$，以下属性成立 $\pi_m(X_k, \Theta_t) > \pi_{m’}(X_k, \Theta_t)$，$\pi_{m’}(X_{k’}, \Theta_t) > \pi_m(X_{k’}, \Theta_t)$，其中 $X_k$ 和 $X_{k’}$ 包含特征信号 $v_k$ 和 $v_{k’}$。

然后，在路由器学习阶段 $t > T_1$，任何任务 $n_t$ 与 $w_{n_t} \in W_k$ 将被路由到正确的专家 $m \in M_k$。让 $\mathbf{w}^{(m)}$ 表示专家 $m$ 的最小 $\ell_2$- 范数离线解。基于 $\mathbf{w}^{(m_t)}t$ 的更新规则（方程 5），我们计算 $\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m)} = \mathbf{w}^{(m_t)}{t-1} + X_t (X_t^\top X_t)^{-1} (y_t - X_t^\top \mathbf{w}^{(m_t)}{t-1}) - \mathbf{w}^{(m)} = (I - X_t (X_t^\top X_t)^{-1} X_t^\top) \mathbf{w}^{(m_t)}{t-1} + X_t (X_t^\top X_t)^{-1} X_t^\top \mathbf{w}^{(m)} - \mathbf{w}^{(m)} = (I - P_t) \cdots (I - P{T_1+1}) (\mathbf{w}^{(m)}_{T_1} - \mathbf{w}^{(m)})$ 对于每个专家 $m \in [M]$。

由于正交投影矩阵 $P_t$ 是非扩张算子，因此 $\forall t \in {T_1 + 1, \cdots, T}, |\mathbf{w}^{(m)}t - \mathbf{w}^{(m)}|\infty \leq |\mathbf{w}^{(m)}{t-1} - \mathbf{w}^{(m)}|\infty \leq \cdots \leq |\mathbf{w}^{(m)}{T_1} - \mathbf{w}^{(m)}|\infty$。由于每个专家 $m \in M_k$ 的解空间 $W_k$ 是固定的，我们进一步得到 $|\mathbf{w}^{(m)}t - \mathbf{w}^{(m)}{T_1+1}|\infty = |\mathbf{w}^{(m)}t - \mathbf{w}^{(m)} + \mathbf{w}^{(m)} - \mathbf{w}^{(m)}{T_1+1}|\infty \leq \max_{w_n, w_{n’} \in W_k} |w_n - w_{n’}|\infty = O(\sigma{1.5}^0)$，其中第一个不等式是基于并集界限，第二个不等式是因为每个任务的正交投影更新 $\mathbf{w}^{(m)}t$，最后一个等式是因为 $|w_n - w{n’}|\infty = O(\sigma{1.5}^0)$ 对于任何两个在相同集合 $W_k$ 中的真实情况。

F 引理 2 的完整版本和证明

引理 2（完整版本）：如果 MoE 在任何轮次 $t \in [T]$ 继续通过方程（9）更新 $\Theta_t$，我们得到：1）在轮次 $t_1 = \lceil \eta^{-1}\sigma^{-0.25}0 M \rceil$，以下属性成立
$$
|h_m(X{t_1}, \theta^{(m)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = \begin{cases} O(\sigma{1.75}^0), & \text{if } m, m’ \in M_n \text{ under } M > N \text{ or } m, m’ \in M_k \text{ under } M < N, \ \Theta(\sigma_{0.75}^0), & \text{otherwise}. \end{cases}
$$
2）在轮次 $t_2 = \lceil \eta^{-1}\sigma^{-0.75}0 M \rceil$，以下属性成立
$$
|h_m(X{t_2}, \theta^{(m)}{t_2}) - h{m’}(X_{t_2}, \theta^{(m’)}{t_2})| = O(\sigma{1.75}^0), \forall m, m’ \in [M].
$$
我们首先提出以下引理作为预备，然后在附录 F.3 中证明引理 2。

对于任何两个专家 $m, m’$，定义 $\Delta_\Theta = |\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)|$。

引理 15：在路由器学习阶段 $t \in {T_1 + 1, \cdots, t_1}$，对于任何两个满足以下条件的专家：1）$m \in M_n$ 和 $m’ \in M_{n’}$ 且 $n \neq n’$ 在 $M > N$ 下，或 2）$m \in M_k$ 和 $m’ \in M_{k’}$ 且 $w_n \in W_k$，$w_{n’} \in W_{k’}$ 且 $k \neq k’$ 在 $M < N$ 下，以下属性成立：
$$
\pi_m(X_n, \Theta_t) > \pi_{m’}(X_n, \Theta_t), \pi_{m’}(X_{n’}, \Theta_t) > \pi_m(X_{n’}, \Theta_t).
$$
引理 14 证明（F.1）

证明：基于引理 5 的证明，对于任何 $m \neq m_t$，我们计算 $|\nabla_{\theta(m)t} L{\text{task}}^t - \nabla_{\theta(m_t)t} L{\text{task}}^t|\infty = |(|\mathbf{w}^{(m_t)}t - \mathbf{w}^{(m_t)}{t-1}|2^2 + \alpha M / t f(m_t)t) \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} - \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m_t)t}|\infty$。
$$
= O(\sigma_0 + \alpha M / t) \cdot \left| \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} - \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m_t)t} \right|\infty = O(\sigma_0),
$$
最后一个等式是因为 $\pi{m_t}(X_t, \Theta_t) < 1$，$|X_t|_\infty = O(1)$ 和 $\alpha M / t \leq \sigma_0$ 对于任何 $t \in {T_1 + 1, \cdots, t_1}$。

引理 15 证明（F.2）

证明：我们将使用与引理 1 证明中相同的方法，通过反证法证明引理 15。这里，我们只证明 $M > N$ 的情况。$M < N$ 的证明是类似的。

回想引理 1，方程（40）在 $t = T_1 + 1$ 时成立。基于引理 13，我们有 $|\pi_m(X_n, \Theta_{T_1}) - \pi_m(X_{n’}, \Theta_{T_1})| = \Omega(\sigma_0.5^0)$。然后接下来，我们
$$
\leq \max_{w_n, w_{n’} \in W_k} |w_n - w_{n’}|\infty = O(\sigma{1.5}^0),
$$
其中第一个不等式是基于并集界限，第二个不等式是因为每个任务的正交投影更新 $\mathbf{w}^{(m)}t$，最后一个等式是因为 $|w_n - w{n’}|\infty = O(\sigma{1.5}^0)$ 对于任何两个在同一集合 $W_k$ 中的真实情况。

这完成了引理 1 的证明。

F 引理 2 的完整版本和证明

对于任何两个专家 $m, m’$，定义 $\Delta_\Theta = |\pi_m(X_t, \Theta_t) - \pi_{m’}(X_t, \Theta_t)|$。

引理 14：在任何轮次 $t \in {T_1 + 1, \cdots, t_1}$，对于所有 $m \neq m_t$，以下属性成立
$$
|\nabla_{\theta(m)t} L{\text{task}}^t - \nabla_{\theta(m_t)t} L{\text{task}}^t|\infty = O(\sigma_0).
$$
引理 15：在路由器学习阶段 $t \in {T_1 + 1, \cdots, t_1}$，对于任何两个满足以下条件的专家：1）$m \in M_n$ 和 $m’ \in M{n’}$ 且 $n \neq n’$ 在 $M > N$ 下，或 2）$m \in M_k$ 和 $m’ \in M_{k’}$ 且 $w_n \in W_k$，$w_{n’} \in W_{k’}$ 且 $k \neq k’$ 在 $M < N$ 下，以下属性成立：
$$
\pi_m(X_n, \Theta_t) > \pi_{m’}(X_n, \Theta_t), \pi_{m’}(X_{n’}, \Theta_t) > \pi_m(X_{n’}, \Theta_t).
$$
引理 2 证明（F.1）

证明：基于引理 5，对于任何 $m \neq m_t$，我们计算 $|\nabla_{\theta(m)t} L{\text{task}}^t - \nabla_{\theta(m_t)t} L{\text{task}}^t|_\infty = |(|w^{(m_t)}t - w^{(m_t)}{t-1}|2^2 + \alpha M / t f(m_t)t) \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m)t} - \frac{\partial \pi{m_t}(X_t, \Theta_t)}{\partial \theta(m_t)}|\infty$。

由于 $\pi_{m_t}(X_t, \Theta_t) < 1$，$|X_t|\infty = O(1)$ 和 $\alpha M / t \leq \sigma_0$ 对于任何 $t \in {T_1 + 1, \cdots, t_1}$，我们最终得到 $|\nabla{\theta(m)t} L{\text{task}}^t - \nabla_{\theta(m_t)t} L{\text{task}}^t|_\infty = O(\sigma_0)$。

引理 15 证明（F.2）

证明：我们将使用与引理 1 证明相同的方法，通过反证法来证明引理 15。这里，我们仅证明 $M > N$ 的情况。$M < N$ 的情况证明类似。

回顾引理 1，方程（40）在 $t = T_1 + 1$ 时成立。基于引理 13，我们有 $|\pi_m(X_n, \Theta_{T_1}) - \pi_m(X_{n’}, \Theta_{T_1})| = \Omega(\sigma_0.5^0)$。然后，我们的目标是证明 $|\pi_m(X_n, \Theta_{T_1}) - \pi_{m’}(X_n, \Theta_{T_1})| = O(\sigma_0 \eta^{-0.5})$ 在方程（38）中对任何 $m \in M_n$ 和 $m’ \in M_{n’}$ 在路由器学习阶段始终成立。然后根据引理 1 的证明，方程（40）也是真的。

在方程（40）在 $t = T_1 + 1$ 时，路由器将任务 $t$ 路由到其最佳专家 $m_t \in M_{n_t}$，导致 $\nabla_{\theta(m)t} L{\text{loc}}^t = 0$ 通过引理 12。因此，$\nabla_{\theta(m)t} L{\text{task}}^t = O(\sigma_0)$ 使得 $\langle \theta^{(m_t)}{t+1} - \theta^{(m_t)}t, v_n \rangle = -O(\sigma{1.5}^0)$ 对于专家 $m_t$ 和 $\langle \theta^{(m)}{t+1} - \theta^{(m)}t, v_n \rangle = O(\sigma{1.5}^0)$ 对于任何其他专家 $m \neq m_t$ 在任务 $t = T_1 + 1$。

由于 $|\theta(m){t_1} - \theta(m’){t_1}|\infty = O(\sigma_0 \eta^{-0.5})$ 且 $|\pi_m(X_n, \Theta{T_1}) - \pi_m(X_{n’}, \Theta_{T_1})| = \Omega(\sigma_{0.5}^0)$，方程（40）对任何 $t \in {T_1 + 2, \cdots, t_1}$ 成立，基于我们在引理 1 的证明。

对于 $M < N$ 的情况，我们可以用相同的方法证明方程（40）。这完成了引理 15 的证明。

引理 2 最终证明（F.3）

证明：我们首先关注 $M > N$ 的情况来证明 $|h_m(X_{t_1}, \theta^{(m)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = O(\sigma{1.75}^0)$ 对于任何两个不同的专家 $m, m’ \in M_n$ 在同一个专家集合中在方程（12）中成立。然后我们证明 $|h_m(X_{t_1}, \theta^{(m)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = \Theta(\sigma{0.75}^0)$ 对于任何两个专家 $m \in M_n$ 和 $m’ \in M_{n’}$ 在不同专家集合中的方程（12）。之后，我们证明在训练轮次 $t_2 = \lceil \eta^{-1}\sigma^{-0.75}_0 M \rceil$ 的方程（13）。最后，我们证明上述分析可以推广到 $M < N$ 的情况。

在 $M > N$ 的情况下，让 $M’$ 和 $m’$ 分别表示集合 $M_n$ 中具有最大和最小 softmax 值的两个专家。换句话说，我们有 $M’ = \arg\max_{m \in M_n} \pi_m(X_t, \Theta_t)$，$m’ = \arg\min_{m \in M_n} \pi_m(X_t, \Theta_t)$，其中 $v_n \in X_t$。如果这两个专家满足 $|h_{M’}(X_{t_1}, \theta^{(M’)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = O(\sigma{1.75}^0)$，则这个方程对任何两个在 $M_n$ 中的专家都成立。

在路由器学习阶段开始时，我们有 $|\pi_{M’}(X_{T_1}, \Theta_{T_1}) - \pi_{m’}(X_{T_1}, \Theta_{T_1})| = O(\sigma_0.75^0)$，基于引理 1。

根据方程（1）中的路由策略，如果新任务 $t$ 有真实情况 $w_n$，它总是被路由到专家 $M’$ 直到其 softmax 值减小到比其他专家小。因此，我们计算路由器学习阶段中专家 $M’$ 的减少门控输出：
$$
\langle \theta^{(M’)}_{T_1+1} - \theta^{(M’)}_t1, v_n \rangle \leq O(\sigma_0) \cdot \eta \cdot (t_1 - T_1) = O(\sigma_0.75^0).
$$
而对于专家 $m’$，它将不会被路由直到其 softmax 值增加到最大。因此，我们同样计算增加的门控输出 $\langle \theta^{(m’)}t1 - \theta^{(m’)}{T_1+1}, v_n \rangle = O(\sigma_0.75^0)$ 对于专家 $m’$。

基于引理 4 和引理 14，专家 $m’$ 和 $M’$ 的门控网络参数将收敛到相同的值，误差小于 $\Theta_t$ 的更新步骤。因此，我们得到
$$
|\theta^{(M’)}t1 - \theta^{(m’)}t1|\infty = |\nabla{\theta(m_t1-1)} L_{\text{task}}^{t1-1} \cdot \eta|\infty = |\nabla{\theta(m_t1-1)} L_{\text{aux}}^{t1-1} \cdot \eta|\infty = O(\sigma{1.75}^0),
$$
基于 $\nabla_{\theta(m_t1-1)} L_{\text{aux}}^{t1-1} = O(\sigma_{1.25}^0)$ 和 $\eta = O(\sigma_{0.5}^0)$ 的事实。然后根据引理 10，我们得到 $|h_{M’}(X_{t_1}, \theta^{(M’)}t1) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = O(\sigma{1.75}^0)$，这也适用于任何两个在同一个专家集合 $M_n$ 中的专家。

接下来，我们证明 $|h_m(X_{t_1}, \theta^{(m)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = \Theta(\sigma{0.75}^0)$ 在方程（12）中对于专家 $m’$ 在方程（41）中的另一个专家 $m \notin M_n$。

让 $\bar{m} \in M_{n’}$ 表示具有最大 softmax 值的专家，对于其他专家集合中的任何数据 $X_n$，其中 $v_n \in X_t$。根据引理 1 的证明，我们得到 $\pi_{m’}(X_{T_1}, \Theta_{T_1}) - \pi_{\bar{m}}(X_{T_1}, \Theta_{T_1}) = O(\sigma_{0.75}^0)$。这个方程表明，在路由器学习阶段 $t \in {T_1 + 1, \cdots, t_1}$，任何任务到达 $n_t$ 与真实情况 $w_{n_t} = w_n$ 不会被路由到专家 $\bar{m}$。因此，$\pi_{\bar{m}}(X_t, \Theta_t)$ 随着 $t$ 持续增加。然后我们计算专家 $\bar{m}$ 和 $m’$ 每轮 $t$ 的参数梯度差异：
$$
\nabla_{\theta(\bar{m})t} L{\text{task}}^t - \nabla_{\theta(m’)t} L{\text{task}}^t = \alpha M / t f(m_t)t \pi{m_t}(X_t, \Theta_t)(\pi_{m’}(X_t, \Theta_t) - \pi_{\bar{m}}(X_t, \Theta_t)) \cdot \sum_{i \in [s_t]} X_{t,i} \geq 0,
$$
基于 $\pi_{m’}(X_t, \Theta_t) - \pi_{\bar{m}}(X_t, \Theta_t) > 0$ 通过引理 13。由于 $\nabla_{\theta(\bar{m})t} L{\text{task}}^t < 0$ 和 $\nabla_{\theta(m’)t} L{\text{task}}^t < 0$，我们得到 $h_{m’}(X_t, \theta^{(m’)}t) - h{\bar{m}}(X_t, \theta^{(\bar{m})}t)$ 随着 $t$ 增加。根据我们对 $h{m’}(X_t, \theta^{(m’)}t)$ 的先前分析，我们得到
$$
|h{m’}(X_{t_1}, \theta^{(m’)}{t_1}) - h{\bar{m}}(X_{t_1}, \theta^{(\bar{m})}{t_1})| = |h{m’}(X_{T_1}, \theta^{(m’)}{T_1}) - h{\bar{m}}(X_{T_1}, \theta^{(\bar{m})}{T_1})| + |\nabla{\theta(\bar{m})t} L{\text{task}}^t - \nabla_{\theta(m’)t} L{\text{task}}^t|\infty \cdot \eta \cdot (t_1 - T_1) = O(\sigma{0.75}^0) + \Theta(\sigma_{0.75}^0) = \Theta(\sigma_{0.75}^0),
$$
其中第一个等式是因为 $|\nabla_{\theta(\bar{m})t} L{\text{task}}^t - \nabla_{\theta(m’)t} L{\text{task}}^t|_\infty = O(\sigma_0)$。这完成了方程（12）的证明。

随后，我们证明 $|h_m(X_{t_2}, \theta^{(m)}{t_2}) - h{m’}(X_{t_2}, \theta^{(m’)}{t_2})| = O(\sigma{1.75}^0)$ 对于任何 $m, m’ \in [M]$ 在方程（13）中

通过证明 $|h_{M’}(X_{t_2}, \theta^{(M’)}{t_2}) - h_m(X{t_2}, \theta^{(m)}{t_2})| = O(\sigma{1.75}^0)$ 在 $M’ \in M_n$ 的方程（41）中和任何其他专家 $m \notin M_n$ 之间。

基于引理 7，我们得到
$$
\langle \theta^{(m)}{t+1} - \theta^{(m)}t, v_n \rangle = \begin{cases} -O(\sigma{1.25}^0), & \text{if } m = m_t, \ O(M^{-1}\sigma{1.25}^0), & \text{if } m \neq m_t. \end{cases}
$$
根据我们的分析，专家 $M’ \in M_n$ 在 $t \in {t_1, \cdots, t_2}$ 期间定期被路由器选中以训练任务 $n_t = n$。在专家 $M’$ 训练任务 $n$ 后，其门控输出 $h_{M’}(X_t, \theta^{(M’)}t)$ 减少了 $O(\sigma{1.25}^0)$。而在没有被选中的其他轮次中，其门控输出增加了 $O(M^{-1}\sigma_{1.25}^0)$。在这样的训练行为下，我们得到 $|h_{M’}(X_{t_1}, \theta^{(M’)}t1) - h{M’}(X_{t_2}, \theta^{(M’)}t2)| = O(\sigma{1.75}^0)$，假设 $v_n \in X_{t_1}$ 和 $v_n \in X_{t_2}$。

而对于专家 $m \notin M_n$，其门控输出 $h_m(X_t, \theta^{(m)}t)$ 对于任何任务 $n$ 的数据 $X_t$ 持续增加。对于任何 $t \in {t_1, \cdots, t_2}$，我们有 $|\nabla{\theta(m)t} L{\text{aux}}^t|\infty = O(\sigma{1.25}^0)$ 对于专家 $m$。假设专家 $m$ 在 $t \in {t_1, \cdots, t_2}$ 期间从未被路由器选中以训练任务 $n_t = n$，我们得到 $|h_m(X_{t_2}, \theta^{(m)}{t_2}) - h_m(X{t_1}, \theta^{(m)}{t_1})| = |\nabla{\theta(m)t} L{\text{aux}}^t|\infty \cdot (t_2 - t_1) \cdot \eta > |h{M’}(X_{t_1}, \theta^{(M’)}t1) - h_m(X{t_1}, \theta^{(m)}{t_1})|$，其中不等式是因为 $|\nabla{\theta(m)t} L{\text{aux}}^t|\infty \cdot (t_2 - t_1) \cdot \eta = O(\sigma_0.5^0)$ 且 $|h{M’}(X_{t_1}, \theta^{(M’)}t1) - h_m(X{t_1}, \theta^{(m)}{t_1})| = \Theta(\sigma{0.75}^0)$。这个不等式表明存在一个训练轮次 $t’ \in {t_1, \cdots, t_2}$ 使得 $h_m(X_{t’}, \theta^{(m)}{t’}) > h{M’}(X_{t’}, \theta^{(M’)}t’)$ 对于任务到达 $n{t’} = n$。因此，专家 $m’$ 被选中再次训练任务 $n$，意味着 $m’ \in M_n$ 在轮次 $t’$。然后专家 $m$ 和 $M’$ 的门控网络参数将收敛到相同的值，误差为 $O(\sigma_{1.75}^0)$，基于引理 4 和引理 14。这完成了方程（13）在 $M > N$ 情况下的证明。

在 $M < N$ 的情况下，让 $M’$ 和 $m’$ 分别表示集合 $M_k$ 中具有最大和最小 softmax 值的专家。换句话说，我们有 $M’ = \arg\max_{m \in M_k} \pi_m(X_t, \Theta_t)$，$m’ = \arg\min_{m \in M_k} \pi_m(X_t, \Theta_t)$，其中任务 $t$ 的真实情况满足 $w_n \in W_k$。

根据引理 2 的证明，门控网络参数的专家 $m’$ 和 $M’$ 将在路由器学习阶段结束时收敛到相同的值，误差小于 $\Theta_t$ 的更新步骤。因此，我们得到
$$
|\theta^{(M’)}t1 - \theta^{(m’)}t1|\infty = |\nabla{\theta(m_t1-1)} L_{\text{task}}^{t1-1} \cdot \eta|\infty = |(\nabla{\theta(m_t1-1)} L_{\text{loc}}^{t1-1} + \nabla_{\theta(m_t1-1)} L_{\text{aux}}^{t1-1}) \cdot \eta|\infty = O(\sigma{1.75}^0),
$$
基于 $\nabla_{\theta(m_t1-1)} L_{\text{aux}}^{t1-1} = O(\sigma_{1.25}^0)$ 和 $\nabla_{\theta(m_t1-1)} L_{\text{loc}}^{t1-1} = O(\sigma_{1.5}^0)$ 从引理 12 得出。然后我们得到 $|h_{M’}(X_{t_1}, \theta^{(M’)}t1) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = O(\sigma{1.75}^0)$，这也适用于任何两个在同一个专家集合 $M_k$ 中的专家。

类似地，对于任何两个在不同专家集合中的专家，我们可以推导出 $|h_m(X_{t_1}, \theta^{(m)}{t_1}) - h{m’}(X_{t_1}, \theta^{(m’)}{t_1})| = \Theta(\sigma{0.75}^0)$。对于训练轮次 $t_2$，$M < N$ 的情况证明与 $M > N$ 的情况相同，因此我们在这里省略。

G 引理 3 的完整版本和证明

引理 3（完整版本）：在算法 1 下，MoE 从轮次 $T_2 = O(\eta^{-1}\sigma^{-0.25}_0 M)$ 开始终止更新 $\Theta_t$。然后对于任何任务到达 $n_t$ 在 $t > T_2$，以下属性成立：

如果 $M > N$，路由器选择任何专家 $m \in M_{n_t}$ 的概率相同，为 $\frac{1}{|M_{n_t}|}$，其中 $|M_{n_t}|$ 是集合 $M_{n_t}$ 中的专家数量。
如果 $M < N$ 且 $w_{n_t} \in W_k$，路由器选择任何专家 $m \in M_k$ 的概率相同，为 $\frac{1}{|M_k|}$，其中 $|M_k|$ 是集合 $M_k$ 中的专家数量。

引理 3 证明

在 $M > N$ 的情况下，根据算法 1 和引理 2，停止更新 $\Theta_t$ 后，以下属性成立：1）对于任何 $m \in M_n$ 和 $m’ \in M_{n’}$，$|h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t)| = \Theta(\sigma{0.75}^0)$；2）对于任何 $m, m’ \in M_n$，$|h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t)| = O(\Gamma)$，其中 $\Gamma = O(\sigma{1.25}^0)$。

如果任务到达 $n_t$ 的真实情况满足 $w_{n_t} = w_n$，对于任何专家 $m \in M_n$ 和 $m’ \notin M_n$，我们有
$$
h_m(X_t, \theta^{(m)}_t) + r(m)t - (h{m’}(X_t, \theta^{(m’)}_t) + r(m’)_t) \geq h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}_t) + r(m’)t = \Theta(\sigma{0.75}^0),
$$
给定 $r(m’)t = \Theta(\sigma{1.25}^0)$ 和 $h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t) = \Theta(\sigma{0.75}^0)$。因此，任何专家 $m’ \notin M_n$ 都不会被选中来学习任务 $t$，只有集合 $M_n$ 中的专家会被选中。

对于任何专家 $m \in M_n$，我们计算
$$
P(m_t = m \mid m \in M_n) = P\left( \max_{m’ \in M_n} {h_{m’}(X_t, \theta^{(m’)}_t) + r(m’)_t} = h_m(X_t, \theta^{(m)}_t) + r(m)_t \right) = \frac{1}{|M_n|},
$$
其中第三个等式是因为 $r(m)t = \Theta(\sigma{1.25}^0)$ 和 $|h_m(X_t, \theta^{(m)}t) - h{m’}(X_t, \theta^{(m’)}t)| = O(\sigma{1.25}^0)$ 由算法 1 得出，最后一个等式是因为 $r(m)_t$ 服从均匀分布 Unif[0, $\lambda$]。

在 $M < N$ 的情况下，我们类似地得出以下属性：1）对于任何 $m \in M_k$ 和 $m’ \in M_{k’}$，$|h_m(X_t, \theta^{(m)}_t) - h_{m’}(X_t, \theta^{(m’)}_t)| = \Theta(\sigma_{0.75}^0)$；2）对于任何 $m, m’ \in M_k$，$|h_m(X_t, \theta^{(m)}_t) - h_{m’}(X_t, \theta^{(m’)}_t)| = O(\Gamma)$。基于这两个属性，$h_m(X_t, \theta^{(m)}_t) + r(m)_t - (h_{m’}(X_t, \theta^{(m’)}_t) + r(m’)_t) = \Theta(\sigma_{0.75}^0)$ 始终对任何两个不在同一个专家集合 $M_k$ 中的专家 $m$ 和 $m’$ 成立。进一步，我们可以类似地计算
$$
P(m_t = m \mid m \in M_k) = P\left( r(m)_t > r(m’)_t, \forall m’ \in M_k \right) = \frac{1}{|M_k|}.
$$
这完成了引理 3 的证明。

H 引理 4 的证明

引理 4：在单专家系统中，基于方程（15）和（42）在引理 16 中，对于任何训练轮次 $t \in [T]$ 和 $i \in {1, \cdots, t}$，我们计算：
$$
E[F_t] = \frac{1}{t-1} \sum_{i=1}^{t-1} E \left[ |\mathbf{w}^{(m_i)}t - w{n_i}|2^2 - |\mathbf{w}^{(m_i)}i - w{n_i}|2^2 \right] = \frac{1}{t-1} \sum{i=1}^{t-1} \left[ (r^t - r^i) E[|w{n_i}|2^2] + \sum{l=1}^t (1 - r)r^{t-l} E[|w_{n_l} - w_{n_i}|2^2] - i \sum{j=1}^{i} (1 - r)r^{i-j} E[|w_{n_j} - w_{n_i}|_2^2] \right],
$$

$$
E[G_T] = \frac{1}{T} \sum_{i=1}^T E[|\mathbf{w}^{(m_i)}T - w{n_i}|2^2] = \frac{1}{T} \sum{i=1}^T \left[ r^T E[|w_{n_i}|2^2] + \sum{l=1}^T (1 - r)r^{T-l} E[|w_{n_l} - w_{n_i}|2^2] \right].
$$
这里，我们让 $w{n_i}$ 表示第 $i$ 轮任务到达的真实情况。最后的等式是基于 $E[|w_{n_i}|2^2] = \frac{1}{N} \sum{n=1}^N |w_n|2^2$ 和 $E[|w{n_j} - w_{n_i}|2^2] = E\left[ \frac{1}{N} \sum{n=1}^N |w_{n_j} - w_n|2^2 \right] = \frac{1}{N^2} \sum{n=n’} |w_{n’} - w_n|_2^2$ 当只有一个专家时。

I 定理 1 的证明

在证明定理 1 之前，我们首先提出以下引理。然后我们在附录 I.2 中正式证明定理 1。

对于专家 $m$，让 $\tau(m)(l) \in {1, \cdots, T_1}$ 表示路由器在探索阶段第 $l$ 次选择专家 $m$ 的训练轮次。例如，$\tau(1)(2) = 5$ 表示第 5 轮是路由器第二次选择专家 1。

引理 16：在任何轮次 $t \in {T_1 + 1, \cdots, T}$，对于 $i \in {T_1 + 1, \cdots, t}$，我们有 $|\mathbf{w}^{(m_i)}t - w{n_i}|2^2 = |\mathbf{w}^{(m_i)}{T_1} - w_{n_i}|_2^2$。而在任何轮次 $t \in {1, \cdots, T_1}$，对于任何 $i \in {1, \cdots, t}$，我们有
$$
E[|\mathbf{w}^{(m_i)}t - w{n_i}|_2^2] = r^{L(m_i)t} E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - r)r^{L(m_i)t - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w{n_i}|_2^2],
$$
其中 $L(m_i)_t = t \cdot f(m_i)_t$ 且 $r = 1 - \frac{s}{d}$。

引理 16 证明（I.1）

证明：在任何轮次 $t \in {T_1 + 1, \cdots, T}$，我们有 $\mathbf{w}^{(m)}t = \mathbf{w}^{(m)}{T_1}$，基于命题 1 和命题 2。因此，对于任何轮次 $t \in {T_1 + 1, \cdots, T}$ 和 $i \in {T_1 + 1, \cdots, t}$，$|\mathbf{w}^{(m_i)}t - w{n_i}|2^2 = |\mathbf{w}^{(m_i)}{T_1} - w_{n_i}|_2^2$ 成立。

接下来，我们证明方程（42）对于轮次 $t \in {1, \cdots, T_1}$。定义 $P_t = X_t (X_t^\top X_t)^{-1} X_t^\top$ 对于任务 $t$。在当前任务 $t$，共有 $L(m)_t = t \cdot f(m)_t$ 个任务被路由到专家 $m$，其中 $f(m)_t$ 在方程（7）中给出。

基于 $\mathbf{w}^{(m)}_t$ 的更新规则（方程 5），我们计算
$$
|\mathbf{w}^{(m_i)}t - w{n_i}|2^2 = |\mathbf{w}^{(m_i)}{\tau(m_i)(L(m_i)t)} - w{n_i}|2^2 = |(I - P_t)\mathbf{w}^{(m_i)}{\tau(m_i)(L(m_i)t - 1)} + P_t w{\tau(m_i)(L(m_i)t)} - w{n_i}|_2^2,
$$
其中第一个等式是因为在 $\tau(m_i)(L(m_i)_t), \cdots, t$ 之间没有更新 $\mathbf{w}^{(m_i)}_t$，第二个等式是基于方程（5）。

由于 $P_t$ 是 $X_t$ 行空间的正交投影矩阵，基于标准正态分布的旋转对称性，我们有 $E|P_t(w_{\tau(m_i)(L(m_i)t)} - w{n_i})| = \frac{s}{d} |w_{\tau(m_i)(L(m_i)t)} - w{n_i}|_2^2$。然后我们进一步计算
$$
E[|\mathbf{w}^{(m_i)}t - w{n_i}|2^2] = (1 - \frac{s}{d}) E[|\mathbf{w}^{(m_i)}{\tau(m_i)(L(m_i)t - 1)} - w{n_i}|2^2] + \frac{s}{d} E[|w{\tau(m_i)(L(m_i)t)} - w{n_i}|_2^2] = (1 - \frac{s}{d}) L(m_i)t E[|\mathbf{w}^{(m_i)}0 - w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - \frac{s}{d}) \frac{s}{d} E[|w{\tau(m_i)(l)} - w{n_i}|_2^2] = r^{L(m_i)t} E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - r)r^{L(m_i)t - l} E[|w{\tau(m_i)(l)} - w{n_i}|_2^2],
$$
其中第二个等式是基于迭代计算，最后一个等式是因为 $\mathbf{w}^{(m)}_0 = 0$ 对于任何专家 $m$。这里我们用 $r = 1 - \frac{s}{d}$ 简化符号。

定理 1 最终证明（I.2）

证明：基于引理 16 中的方程（42），我们得到
$$
E[|\mathbf{w}^{(m_i)}i - w{n_i}|_2^2] = r^{L(m_i)i} E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)i} (1 - r)r^{L(m_i)i - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w{n_i}|_2^2],
$$
其中 $\tau(m_i)(L(m_i)_i) = i$。

然后在任何轮次 $t \in {2, \cdots, T_1}$，我们计算预期遗忘为：
$$
E[F_t] = \frac{1}{t-1} \sum_{i=1}^{t-1} E \left[ |\mathbf{w}^{(m_i)}t - w{n_i}|_2^2 - |\mathbf{w}^{(m_i)}i - w{n_i}|2^2 \right] = \frac{1}{t-1} \sum{i=1}^{t-1} \left[ (r^{L(m_i)_t} - r^{L(m_i)i}) E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - r)r^{L(m_i)t - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w{n_i}|2^2] - \sum{j=1}^{L(m_i)i} (1 - r)r^{L(m_i)i - j} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(j)} - w{n_i}|2^2] \right],
$$
其中 $c{i,j} = (1 - r)(r^{L(m_i)_t} - L(m_i)_i + r^{L(m_i)_t} - j - r^j - L(m_i)_i)$。

由于任务 $i$ 的真实情况 $w_{n_i}$ 是从 $N$ 个真实情况中随机抽取的，我们有
$$
E[|w_{n_i}|2^2] = \frac{1}{N} \sum{n=1}^N |w_n|2^2.
$$
根据引理 8 和命题 1，每个专家 $m$ 将在 $T_1$ 轮探索后收敛到一个专家集合 $M_n$。因此，我们得到
$$
E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w_{n_i}|2^2] < \frac{1}{N^2} \sum{n=n’} |w_{n’} - w_n|2^2.
$$
而对于 $t \in {T_1 + 1, \cdots, T}$，基于命题 2，专家模型 $\math\mathbf{w}^{(m)}t = \mathbf{w}^{(m)}{T_1}$ 对于任何专家 $m \in [M]$。因此，我们计算在最后一轮训练 $T$ 的任务 $n_T$ 后的整体泛化误差：
$$
E[G_T] = \frac{1}{T} \sum{i=1}^T E[|\mathbf{w}^{(m_i)}T - w{n_i}|2^2] = \frac{1}{T} \sum{i=1}^T \left[ r^{L(m_i)T} E[|w{n_i}|2^2] + \sum{l=1}^T (1 - r)r^{L(m_i)T - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w_{n_i}|_2^2] \right].
$$
在上述方程中，第一项表示所有任务的平均模型误差，第二项则是基于任务相似性和模型差距的平均误差。

J 定理 2 的证明

证明：对于任何轮次 $t \in {1, \cdots, T_1}$，遗忘与定理 1 中的情况相同，因此我们在这里省略证明。

对于 $t \in {T_1 + 1, \cdots, T}$，路由器将任务在同一簇中路由到每个专家。为此，我们将 $t$ 轮分为两个子区间：$i \in {1, \cdots, T_1}$ 和 $i \in {T_1 + 1, \cdots, t}$，以计算遗忘：
$$
E[F_t] = \frac{1}{t-1} \sum_{i=1}^{t-1} E \left[ |\mathbf{w}^{(m_i)}t - w{n_i}|_2^2 - |\mathbf{w}^{(m_i)}i - w{n_i}|2^2 \right] = \frac{1}{t-1} \sum{i=1}^{T_1} \left[ (r^{L(m_i)_t} - r^{L(m_i)i}) E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - r)r^{L(m_i)t - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w{n_i}|_2^2] \right] +
$$

$$
\frac{1}{t-1} \sum_{i=T_1 + 1}^{t} \left[ (r^{L(m_i)_t} - r^{L(m_i)i}) E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - r)r^{L(m_i)t - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w{n_i}|_2^2] \right].
$$
在这里，第一部分表示在探索阶段的遗忘，第二部分表示在路由器学习阶段的遗忘。对于 $t \in {1, \cdots, T_1}$，我们有
$$
E[|\mathbf{w}^{(m_i)}t - w{n_i}|_2^2] = r^{L(m_i)t} E[|w{n_i}|2^2] + \sum{l=1}^{L(m_i)t} (1 - r)r^{L(m_i)t - l} E[|\mathbf{w}^{(m_i)}{\tau(m_i)(l)} - w{n_i}|_2^2].
$$
对于 $t \in {T_1 + 1, \cdots, T}$，我们可以得到类似的表达式。