联合集群的机器遗忘

摘要

联合集群（FC）是一个无监督学习问题，出现在许多实际应用中，包括个性化推荐和医疗保健系统。 随着最近确保“被遗忘权”的法律的通过，FC方法的机器遗忘问题变得非常重要。 我们首次引入了 FC 的机器遗忘问题，并为定制的安全 FC 框架提出了一种有效的遗忘机制。 我们的 FC 框架利用了特殊的初始化过程，我们证明这些过程非常适合遗忘。 为了保护客户端数据隐私，我们开发了安全压缩多集聚合（SCMA）框架，该框架可以解决集群过程中遇到的稀疏安全联邦学习（FL）问题以及更常见的问题。 为了同时促进低通信复杂性和秘密共享协议，我们将具有特殊评估点的 Reed-Solomon 编码集成到我们的 SCMA 管道中，并证明客户端通信成本在向量维度上是对数。 此外，为了证明我们的忘却机制相对于完全再训练的优势，我们为我们的方法的忘却性能提供了理论分析。 仿真结果表明，当集群大小高度不平衡时，与之前报道的 FC 基线相比，新的 FC 框架表现出优异的集群性能。 与针对每个删除请求在本地和全局完全重新训练 $K$-means++ 相比，我们的取消学习过程在七个数据集上提供了大约 $84$x 的平均加速。 我们对所提出方法的实现可在 https://github.com/thupchnsky/mufc 上找到。

1简介

大量用户训练数据的可用性有助于现代机器学习模型的成功。 例如，大多数最先进的计算机视觉模型都是在大规模图像数据集上进行训练的，包括 Flickr （Thomee 等人，2016） 和 ImageNet （Deng 等人，2009） 。 收集和存储用户数据的组织和存储库必须遵守隐私法规，例如最近的欧盟通用数据保护条例（GDPR）、加州消费者隐私法案（CCPA）和加拿大消费者隐私保护法案（CPPA），所有其中保证用户从数据集中删除其数据的权利(被遗忘的权利)。 数据删除请求在实践中经常出现，特别是与医疗记录相关的敏感数据集（计算生物学中的许多机器学习模型都是使用英国生物银行（Sudlow等人，2015）进行训练的，该银行托管着一系列遗传和大约 50 万患者的医疗记录（Ginart 等人，2019）)。 从数据集中删除用户数据不足以确保足够的隐私，因为训练数据通常可以从经过训练的模型重建（Fredrikson等人，2015；Veale等人，2018）。 这激发了机器取消学习 （Cao & Yang，2015）的研究，旨在有效消除某些数据点对模型的影响。 天真地，人们可以从头开始重新训练模型以确保完全删除，但重新训练的计算成本很高，因此在适应频繁的删除请求时并不实用。 为了避免完全的再训练，必须为每个不可学习的应用开发专门的方法（Ginart 等人，2019；Guo 等人，2020；Bourtoule 等人，2021；Sekhari 等人，2021）。

与此同时，联邦学习（FL）已成为一种有前途的方法，可以在大量用户上进行分布式训练，同时保护他们的隐私（McMahan 等人，2017；Chen 等人，2020；Kairouz 等人， 2021；王等人，2021；博纳维茨等人，2021）。 FL 的关键思想是将用户数据保留在其设备上，并通过以通信高效且安全的方式聚合本地模型来训练全局模型。 由于模型反转攻击（Zhu等人，2019；Geiping等人，2020），服务器端的安全本地模型聚合是FL中的一个关键考虑因素，因为它保证服务器无法获取特定信息基于本地模型的客户数据（Bonawitz 等人，2017；Bell 等人，2020；So 等人，2022；Chen 等人，2022）。 由于数据隐私是 FL 的主要目标，因此 FL 框架自然应该允许在跨孤岛设置中频繁删除客户端数据子集的数据（例如，当多个患者请求在医院数据库），或跨设备设置中客户端的整个本地数据集（例如，当用户请求应用程序不要跟踪其手机上的数据时）。 这导致了一个很大程度上未被研究的问题，称为联合失学习（Liu等人，2021；Wu等人，2022；Wang等人，2022）。 然而，现有的联合取消学习方法在模型更新后并没有理论上的性能保证，而且通常容易受到对抗性攻击。

我们的贡献总结如下。 1) 我们引入了FC中的机器失学习问题，并设计了一种新的端到端系统（图1)，该系统能够执行具有隐私性和低功耗的高效FC。沟通成本保证，在需要时还可以实现简单而有效的忘却。 2) 作为具有不可学习特征的 FC 方案的一部分，我们描述了一种新颖的一次性 FC 算法，该算法为联合 $K$ 均值聚类目标提供阶次最优近似，并且也优于少数现有的相关方法（Dennis等人，2021；Ginart等人，2019），特别是对于集群大小高度不平衡的情况。 3) 对于FC，我们还描述了一种新颖的稀疏压缩多集聚合（SCMA）方案，该方案确保服务器只能访问各个集群中点的聚合计数，但没有有关点分布的信息在个人客户。 SCMA 安全地恢复了输入稀疏向量的精确总和，通信复杂度在向量维度上为对数，优于现有的稀疏安全聚合工作（Beguier 等人，2020；Ergun 等人，2021），具有线性复杂度。 4) 我们从理论上建立了 FC 方法的遗忘复杂度，并表明它明显低于完全再训练的复杂度。 5) 我们编译了一系列数据集，用于对联合集群的遗忘进行基准测试，其中包括两个新数据集，其中包含癌症基因组中的甲基化模式和肠道微生物组信息，这对于计算生物学家和医学研究人员来说可能非常重要经常面临忘记学习的要求。 实验结果表明，与跨七个数据集的完全再训练相比，我们的一次性算法的平均速度提高了大约 $84$x。

图1： 我们提出的 FC 框架概述。 $K$-means++ 初始化和量化在每个客户端并行执行。 SCMA 过程确保只有服务器知道客户端的汇总统计数据，而不会泄露每个集群中谁贡献了积分。 服务器从具有规定权重的量化仓中生成点，并执行完整的 $K$-means++ 聚类来推断全局模型。

2相关作品

由于篇幅限制，相关工作的完整讨论包含在附录A中。

联合集群。 此学习任务的目标是使用驻留在不同边缘设备上的数据执行聚类。 大多数 FC 方法都以发送精确的 （Dennis 等人，2021） 或量化客户端（本地）质心 （Ginart 等人，2019） 为中心直接发送到服务器，这可能无法确保所需的隐私级别，因为它们会泄露每个客户端的数据统计或集群信息。 为了避免发送精确的质心，Li 等人（2022）建议将数据点和质心之间的距离发送到服务器，而不向任何相关方透露数据点的成员资格，但他们的方法带有很大的风险。计算和通信开销。 我们的工作引入了一种新颖的通信高效的安全 FC 框架，具有直观上有吸引力的新隐私标准，因为它涉及将客户端的模糊点计数通信到服务器，并且经常在 FL 文献中使用（Bonawitz 等人，2017） 。

机器忘却。 先前的工作提出了两种类型的忘却要求：精确忘却(Cao & Yang, 2015; Ginart 等人, 2019; Bourtoule 等人, 2021; Chen 等人, 2021)和近似忘却(Guo 等人, 2020; Golatkar 等人, 2020a; b; Sekhari 等人, 2021; Fu 等人, 2022; Chien 等人, 2022)。 为了实现精确的遗忘，未学习的模型需要与完全重新训练的模型具有相同的性能。 对于近似遗忘，未学习模型和完全再训练模型之间的行为“差异”应适当限制。 最近的一些工作也研究了 FL 设置中的数据删除（Liu 等人，2021；Wu 等人，2022；Wang 等人，2022）；然而，它们大多数都是经验方法，并没有对去除后的模型性能和/或遗忘效率提供理论保证。 相比之下，我们提出的 FC 框架不仅能够在实践中实现高效的数据删除，而且还为未学习模型的性能和未学习过程的预期时间复杂度提供了理论保证。

3 预赛

我们从集中式 $K$ 均值问题的正式定义开始。 给定${ℝ}^d$ $𝒳$中的一组$n$点排列成矩阵$X\in {ℝ}^{n\times d}$，以及簇数$K$,$K$ - 意味着问题要求找到一组点 $𝐂=\{c_1,\mathrm{\dots },c_K\},c_k\in {ℝ}^d,\forall k\in [K]$ 来最小化目标

$${\varphi }_c(𝒳;𝐂)={\Vert X-C\Vert }_F^2,$$ (1)

其中$||\cdot |{|}_F$表示矩阵的Frobenius范数，$\parallel \cdot \parallel$表示向量的${\mathrm{\ell }}_2$范数，$C\in {ℝ}^{n\times d}$记录最接近的质心$𝐂$ 到每个数据点 $x_i\in 𝒳$（即 $c_i={\arg \min }_{c_j\in 𝐂}\Vert x_i-c_j\Vert$)。 不失一般性，为了便于更简单的分析和讨论，我们假设最优解是唯一的，并用${𝐂}^{*}=\{c_1^{*},\mathrm{\dots },c_K^{*}\}$表示最优解。 质心集 ${𝐂}^{*}$ 在 $𝒳$ 上产生最佳划分 ${\bigcup }_{k=1}^K{𝒞}_k^{*}$，其中 $\forall k\in [K],{𝒞}_k^{*}=\{x_i:\Vert x_i-c_k^{*}\Vert \le \Vert x_i-c_j^{*}\Vert \forall i\in [n],j\in [K]\}$。 我们使用 ${\varphi }_c^{*}(𝒳)$ 表示集中式 $K$ 均值问题的目标函数的最优值。 稍微滥用了符号，我们还使用 ${\varphi }_c^{*}({𝒞}_k^{*})$ 来表示最佳集群 ${𝒞}_k^{*}$ 贡献的目标值。 附录B中提供了解决$K$-means问题的常用方法$K$-means++的详细描述。

在 FC 中，数据集 $𝒳$ 在集中式服务器上不再可用。 相反，数据存储在$L$边缘设备（客户端）上，FC的目标是在服务器上学习一组全局$K$质心${𝐂}_s$客户发送的信息。 为简单起见，我们假设客户端之间不存在相同的数据点，并且整个数据集 $𝒳$ 是排列为 $X^{(l)}\in {ℝ}^{n^{(l)}\times d}$ 的数据集 ${𝒳}^{(l)}$ 的并集。设备$l,\forall l\in [L]$。 服务器将以安全的方式接收所有客户端的聚合集群统计信息，并生成集合${𝐂}_s$。 在这种情况下，联合 $K$-means 问题要求找到最小化目标的 $K$ 全局质心 ${𝐂}_s$

$${\varphi }_f(𝒳;{𝐂}_s)=\sum _{l=1}^L{\Vert X^{(l)}-C_s^{(l)}\Vert }_F^2,$$ (2)

其中$C_s^{(l)}\in {ℝ}^{n^{(l)}\times d}$记录客户端$l$上的数据点${\{x_i^{(l)}\}}_{i=1}^{n^{(l)}}$所属的诱导全局簇的质心。 请注意，集中式 $K$-means 的分配矩阵 $C$ 的定义与通过联邦 $K$-means $C_s^{(l)}$ 获得的分配矩阵不同。 ：$C$的第$i$行仅取决于$x_i$的位置，而$C_s^{(l)}$中的行对应于$x_i$ 取决于 $x_i$ 所属的诱导全局簇（正式定义参见 3.1 在附录L中，我们提供了一个简单的示例，进一步说明了$C$和$C_s^{(l)}$之间的区别。 请注意，Dennis 等人 (2021) 中也使用了诱导全局簇的概念。

Definition 3.1。

假设客户端$l$处的本地集群用${𝒞}_k^{\mathrm{(}l\mathrm{)}}\mathrm{,}\mathrm{\forall }k\mathrm{\in }\mathrm{[}K\mathrm{]}\mathrm{,}l\mathrm{\in }\mathrm{[}L\mathrm{]}$表示，服务器端的集群用${𝒞}_k^s\mathrm{,}\mathrm{\forall }k\mathrm{\in }\mathrm{[}K\mathrm{]}$表示。 全局聚类等于 ${𝒫}_k\mathrm{=}\mathrm{\{}{x}_i^{\mathrm{(}l\mathrm{)}}\mathrm{|}{x}_i^{\mathrm{(}l\mathrm{)}}\mathrm{\in }{𝒞}_j^{\mathrm{(}l\mathrm{)}}\mathrm{,}{c}_j^{\mathrm{(}l\mathrm{)}}\mathrm{\in }{𝒞}_k^s\mathrm{,}\mathrm{\forall }j\mathrm{\in }\mathrm{[}K\mathrm{]}\mathrm{,}l\mathrm{\in }\mathrm{[}L\mathrm{]}\mathrm{\}}\mathrm{,}$，其中 $c_j^{\mathrm{(}l\mathrm{)}}$ 是客户端 $l$ 上 ${𝒞}_j^{\mathrm{(}l\mathrm{)}}$ 的质心。请注意，$\mathrm{(}{𝒫}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{𝒫}_K\mathrm{)}$形成整个数据集$𝒳$的分区，${𝒫}_k$的代表性质心定义为$c_{s\mathrm{,}k}\mathrm{\in }{𝐂}_s$。

完全不学习。 对于聚类问题，精确遗忘标准可以表述如下。 令 $𝒳$ 为给定数据集，$𝒜$ 为在 $𝒳$ 上训练并输出一组质心 $𝐂\in ℳ$ 的（随机）聚类算法，其中 $ℳ$ 是选择的模型空间。 令 $𝒰$ 为一种取消学习算法，应用于 $𝒜(𝒳)$ 以消除一个数据点 $x\in 𝒳$ 的影响。 如果$\forall 𝐂\in ℳ,x\in 𝒳,\mathbb{P}(𝒰(𝒜(𝒳),𝒳,x)=𝐂)=\mathbb{P}(𝒜(𝒳\backslash x)=𝐂)$，那么$𝒰$就是一个精确的遗忘算法。 为了避免混淆，在某些情况下，该标准被称为 概率（模型）等价。

隐私-准确性-效率三难困境。 如何权衡数据隐私、模型性能、通信和计算效率是分布式学习中长期存在的问题（Acharya & Sun, 2019; Chen 等人, 2020; Gandikota 等人, 2021）这也适用于 FL 和 FC。 仍然缺乏同时解决后一种情况下所有这些挑战的解决方案。 例如，Dennis 等人 (2021) 提出了一种一次性算法，通过将每个客户端的精确质心发送到服务器来考虑模型性能和通信效率一种非匿名时尚。 在严格的隐私约束下，这种方法可能并不理想，因为服务器可以获得有关各个客户端数据的信息。 另一方面，Li 等人 (2022) 中通过执行 $K$ 解决了隐私问题 - 意味着 Lloyd 通过在不同客户端之间分配计算来匿名进行迭代。 由于该方法依赖于混淆每个客户端的成对距离，因此它会产生计算开销来隐藏服务器上贡献客户端的身份，并且会产生由于交互计算而产生的通信开销。 上述方法都不适合取消学习应用程序。 为了同时实现忘却并解决忘却环境中的三难困境，我们的隐私标准涉及传输本地客户端集群内的客户端数据点数量，使得服务器无法了解任何特定的数据统计信息客户端，但仅是客户端数据集并集的总体统计数据。 在这种情况下，计算量是有限的，并且客户端可以执行有效的取消学习，这与提供数据点/质心距离时的情况不同。

算法1 安全联合集群

1: input: Dataset $𝒳$ distributed on $L$ clients (${𝒳}^{(1)},\mathrm{\dots },{𝒳}^{(L)}$).

2: Run $K$-means++ initialization on each client $l$ in parallel, obtain the initial centroid sets ${𝐂}^{(l)}$, and record the corresponding cluster sizes $(|{𝒞}_1^{(l)}|,\mathrm{\dots },|{𝒞}_K^{(l)}|),\forall l\in [L]$.

3: Perform uniform quantization of ${𝐂}^{(l)}$ on each dimension, and flatten the quantization bins into a vector $q^{(l)}$, $\forall l\in [L]$.

4: Set $q_j^{(l)}=\left|{𝒞}_k^{(l)}\right|$ with $j$ being the index of the quantization bin where $c_k^{(l)}$ lies in for $\forall k\in [K]$, and $c_k^{(l)}$ is the centroid of ${𝒞}_k^{(l)}$. Set $q_j^{(l)}=0$ for all other indices.

5: Securely sum up $q^{(l)}$ at server by Algorithm 2, with the aggregated vector denoted as $q$.

6: For index $j\in \{t:q_t\ne 0\}$, sample $q_j$ points based on pre-defined distribution and denote their union as new dataset ${𝒳}_s$ at server.

7: Run full $K$-means++ clustering at server with ${𝒳}_s$ to obtain the centroid set ${𝐂}_s$ at server.

8: return Each client retains its own centroid set ${𝐂}^{(l)}$, server retains ${𝒳}_s,q$ and ${𝐂}_s$.

随机和对抗性删除。 大多数遗忘文献都关注所有数据点都同样可能被删除的情况，这种设置称为随机删除。 然而，当用户恶意忘记对模型训练至关重要的某些点（即最佳集群中的边界点）时，可能会出现对抗性数据删除请求。 我们将此类删除请求称为对抗性删除。 在第5节中，我们为这两种类型的去除提供了理论分析。

4 具有安全模型聚合的联合集群

我们的 FC 框图（Alg. 1)如图1所示。 它由五个组件组成：客户端集群、客户端本地信息处理、安全压缩聚合、服务器数据生成和服务器端集群模块。 接下来我们解释系统每个组件的作用。

对于客户端和服务器端集群（Alg. 的 $2$ 和 $7$ 行） 1)，我们采用 $K$-means++，因为它有助于高效的忘却，如 5 节中所述。 具体来说，我们只在每个客户端运行 $K$-means++ 初始化过程，但在服务器上运行完整的 $K$-means++ 集群（初始化和 Lloyd 算法）。

Alg 的 $3$ 行和 $4$ 行。 1描述了用于处理本地客户端集群信息的过程。 如图1所示，我们首先将局部质心量化到量化仓的最近中心，量化仓的空间位置自然形成一个张量，其中存储局部簇的大小。 为每个客户端 $l$ 生成一个张量，然后将其展平以形成向量 $q^{(l)}$。 为简单起见，我们对每个维度使用步长 $\gamma$ 的统一量化（Alg.1 的第 3 行）。 1，更多详细信息请参见附录H)。 参数$\gamma >0$确定每个维度中量化仓的数量。 如果客户端数据不限于以原点为中心的单位超立方体，我们会对数据进行缩放以满足此要求。 那么每个维度的量化仓数量等于$B={\gamma }^{-1}$，而$d$维度的量化仓总数为$B^d={\gamma }^{-d}$。

Alg 的 $5$ 行。 1描述了如何在服务器上有效聚合信息而不泄露单个客户端数据统计信息。 该方案在4.1节中讨论。 第 $6$ 行涉及根据相应的空间位置为第 $j$ 个量化仓生成 $q_j$ 点。 最简单的想法是选择量化仓的中心作为代表点并为其分配权重$q_j$。 然后，在$7$行中，我们可以在服务器端使用加权$K$-means++算法来进一步降低计算复杂度。

Alg 的简化版本。 1 在附录 I 中讨论，适用于隐私标准不是必需的应用程序。

4.1 服务器上的 SCMA

算法2 SCMA

1: input: $L$ different vectors $q^{(l)}$ of length $B^d$ to be securely aggregated, a finite field ${𝔽}_p$.

2: Each client $l\in [L]$ communicates $(S_1^{(l)},\mathrm{\dots },S_{2KL}^{(l)})$ to the server, where $S_i^{(l)}=({\sum }_{j:q_j^{(l)}\ne 0}{q}_j^{(l)}\cdot j^{i-1}+z_i^{(l)})\text{mod}p,i\in [2KL]$ and $z_i^{(l)}$ is a random key uniformly distributed over ${𝔽}_p$ and hidden from the server. The keys ${\{z_i^{(l)}\}}_{l\in [L],i\in [2KL]}$ are generated offline using standard secure model aggregation so that $({\sum }_l{z}_i^{(l)})\text{mod}p=0$.

3: The server first computes the sum $S_i=({\sum }_{l\in [L]}{S}_i^{(l)})\text{mod}p$. Given $S_i$, the server computes the coefficients of the polynomial $g(x)={\prod }_{j:q_j\ne 0}(1-j\cdot x)$ using the Berlekamp-Massey algorithm (Berlekamp, 1968; Massey, 1969). Then, the server factorizes $g(x)$ over the field ${𝔽}_p$ to determine the roots $j^{-1}$, $q_j\ne 0$, using the polynomial factorizing algorithm (Kedlaya & Umans, 2011). Finally, the server solves a set of $2KL$ linear equations $S_i={\sum }_{l\in [L]}{S}_i^{(l)}={\sum }_{j:q_j\ne 0}{q}_j\cdot j^{i-1}$ for $i\in [2KL]$, by considering $q_j$ as unknowns and $j^{i-1}$ as known coefficients for $q_j\ne 0$.

4: return $q$ reconstructed at the server.

一旦生成了客户端$l$的长度为$B^d$的向量表示$q^{(l)}$（Alg.的第$4$行）。 1)，我们可以使用标准安全模型聚合方法（Bonawitz 等人，2017；Bell 等人，2020；So 等人，2022）来总结所有$q^{(l)}$ 安全地在服务器上获取聚合结果$q$。 然而，由于每个向量 $q^{(l)}$ 的长度为 $B^d$，因此安全地聚合整个向量将导致每个客户端的通信复杂性呈指数级增长。 此外，每个 $q^{(l)}$ 都是一个稀疏向量，因为客户端质心的数量远小于量化仓的数量（即 $K\ll B^d$)。 每个客户端都发送带有噪声掩码的整个 $q^{(l)}$ 进行聚合是低效且不必要的。 这促使我们首先压缩向量，然后执行安全聚合，我们将此过程称为 SCMA（Alg.1）。 2)，如图2所示的一个示例。

通过观察 $q^{(l)},\forall l\in [L]$ 中最多可以有 $K$ 个非零条目，$q$ 中最多可以有 $KL$ 个非零条目，我们调用 Reed -用于设计 SCMA 的 Solomon 代码构造（Reed & Solomon，1960）。 令${𝔽}_p=\{0,1,\mathrm{\dots },p-1\}$为素数阶$p\ge \max \{n,B^d\}$的有限域。 我们将量化仓的索引视为与底层有限域不同的元素，并将它们用作编码器多项式的评估点。 此外，我们将向量 $q^{(l)}$ 中的非零条目 $q_j^{(l)}$ 视为代码字中第 $j$ 条目的替换错误。 然后，我们使用 Alg 中所示的 SCMA 方案。 2，其中客户端发送到服务器的消息可以被视为Reed-Solomon解码中的综合症。 请注意，在我们的方案中，除了 ${\sum }_{l\in [L]}{q}^{(l)}=q$ 之外，服务器不知道 $q^{(l)},l\in [L]$，这符合我们的隐私标准。 这是因为 $z_i^{(l)}$ 均匀分布在 ${𝔽}_p$ 上，并为不同的 $l\in [L],i\in [2KL]$ 独立选择。 详情请参阅附录J。

4.2性能分析

接下来我们描述 Alg 的性能保证。 1 w.r.t. 方程中定义的目标(2)。

图2： $K=2,L=2,B^d=4,n=12,p=13$ 的 SCMA 过程示例。

Theorem 4.1.

假设我们在算法1中执行步长$\gamma$的均匀量化。 然后我们有

定理4.1中的性能保证涉及两项：最优目标值的近似和量化误差（Alg.1的$3$行）。 1)。 对于第一项，近似因子 $O({\log }^{2}K)$ 对于单次 FC 算法来说是顺序最优的，因为总是需要执行两轮聚类，并且每轮将贡献一个因子 $O(\log K)$ 。 使第二项成为常数 w.r.t. $n$，我们可以选择$\gamma =\mathrm{\Theta }(1/\sqrt{n})$，这对于测试数据集来说在实践中也是一个不错的选择。 上述结论适用于跨客户端的任何数据分布。 请注意，SCMA 不会造成失真，因为它始终返回精确的总和，而基于稀疏化的其他稀疏安全聚合方法（Han 等人，2020）可能会引入错误并降低 FC 目标。 有关更多详细信息，请参阅附录D。

4.3复杂度分析

我们对我们提出的 FC 框架（Alg.1）的计算和通信复杂性进行了一系列深入分析。 1)。 由于篇幅限制，这些结果总结在附录C中。

5 机器通过专门的播种进行忘却

我们首先描述了一种直观的精确忘却机制（Alg. 3) for $K$ - 表示集中设置中的集群，稍后将用作 5.3。 Alg 背后的想法。 3 很简单：需要重新运行 $K$-means++ 初始化，对应于仅当当前质心集 $𝐂$ 包含至少一个请求的点时才重新训练移动。 这是从两个观察得出的。 首先，由于通过 $K$-means++ 初始化选择的质心是真实的数据点，因此 Alg 返回更新的质心集 ${𝐂}^{\prime }$。 3 保证不包含有关已删除的数据点的信息。 其次，我们将在下一节中解释，Alg。 3 还满足确切的遗忘标准（在 3 节中定义）。

算法3 通过 $K$ 取消学习 - 意味着 ++ Init。

1: input: Dataset $𝒳$, centroid set $𝐂$ obtained by $K$-means++ initialization on $𝒳$, removal request set ${𝒳}_R=\{x_{r_1},\mathrm{\dots },x_{r_R}\}$.

2: if $c_j\notin {𝒳}_R\forall c_j\in 𝐂$ then

3: ${𝐂}^{\prime }\leftarrow 𝐂$

4: else

5: $i\leftarrow ({\arg \min }_j{c}_j\in {𝒳}_R)-1$

6: if $i=0$ then

7: ${𝐂}^{\prime }\leftarrow \mathrm{\varnothing }$, ${𝒳}^{\prime }\leftarrow 𝒳\backslash {𝒳}_R$.

8: else

9: ${𝐂}^{\prime }\leftarrow \{c_1,\mathrm{\dots },c_i\}$, ${𝒳}^{\prime }\leftarrow 𝒳\backslash {𝒳}_R$.

10: end if

11: for $j=i+1,\mathrm{\dots },K$ do

12: Sample $x$ from ${𝒳}^{\prime }$ with prob $\frac{d^2(x,{𝐂}^{\prime })}{{\varphi }_c({𝒳}^{\prime };{𝐂}^{\prime })}$.

13: ${𝐂}^{\prime }\leftarrow {𝐂}^{\prime }\cup \{x\}$.

14: end for

15: end if

16: return ${𝐂}^{\prime }$

5.1性能分析

为了验证 Alg. 3 是一种精确的非学习方法，我们需要检查 ${𝐂}^{\prime }$ 是否与在 上重新运行 $K$-means++ 初始化过程生成的模型在概率上等价，${𝒳}^{\prime }$ 是移除后剩余的点集合。 这是由引理5.1保证的，并且在附录E中提供了正式的证明。

Lemma 5.1.

对于任何数据点集$𝒳$和移除集${𝒳}_R$，假设剩余数据集为${𝒳}^{\mathrm{\prime }}\mathrm{=}𝒳\mathrm{\backslash }{𝒳}_R$并且算法返回的质心集3 是 ${𝐂}^{\mathrm{\prime }}$，我们有

$$\mathbb{P}(𝒰(𝒜(𝒳),𝒳,{𝒳}_R)=𝐂)=\mathbb{P}(𝒜({𝒳}^{\prime })=𝐂);𝔼({\varphi }_c({𝒳}^{\prime };{𝐂}^{\prime }))\le 8(\ln K+2){\varphi }_c^{*}({𝒳}^{\prime }),$$

其中$𝒜$代表算法1,$𝒰$代表算法3中的遗忘机制。

5.2复杂度分析

我们提出了通过我们的算法同时删除一批 $R$ 数据点的预期时间复杂度的下一个分析结果。 3. 为此，我们考虑随机和对抗性删除场景。 虽然随机删除的分析相当简单，但对对抗性删除请求的分析要求我们确定哪些删除会迫使从头开始频繁地重新训练。 在这方面，我们提出了关于最佳簇大小和异常值的两个假设，这将使我们能够描述最坏情况的去除设置。

Assumption 5.2.

令${ϵ}_{\mathrm{1}}\mathrm{=}\frac{n}{K\mathit{}{s}_{\min }}$为常量，表示聚类大小不平衡，其中$s_{\min }$等于最佳聚类中最小聚类的大小；当 ${ϵ}_{\mathrm{1}}\mathrm{=}\mathrm{1}$ 时，所有簇的大小均为 $\frac{n}{K}$。

Assumption 5.3.

假设${ϵ}_{\mathrm{2}}\mathrm{\ge }\mathrm{1}$是固定常数。 $𝒳$ 中的离群值 $x_i$ 满足 $\mathrm{\Vert }{x}_i\mathrm{-}{c}_j^{\mathrm{*}}\mathrm{\Vert }\mathrm{\le }\mathrm{\Vert }{x}_i\mathrm{-}{c}_k^{\mathrm{*}}\mathrm{\Vert }\mathrm{,}\mathrm{\forall }k\mathrm{\in }\mathrm{[}K\mathrm{]}$ 和 $\mathrm{\Vert }{x}_i\mathrm{-}{c}_j^{\mathrm{*}}\mathrm{\Vert }\mathrm{>}\sqrt{{ϵ}_{\mathrm{2}}\mathit{}{\varphi }_c^{\mathrm{*}}\mathit{}\mathrm{(}{𝒞}_j^{\mathrm{*}}\mathrm{)}\mathrm{/}\mathrm{|}{𝒞}_j^{\mathrm{*}}\mathrm{|}}$ 。

根据假设5.2和5.3，我们得出了下面定理5.4中给出的预期移除时间的估计值。 值得注意的是，预期删除时间并不取决于数据集大小$n$。

Theorem 5.4.

假设$𝒳$中的数据点数量为$n$，并且数据集包含至少一个异常值的概率上限为$O\mathit{}\mathrm{\left(}\mathrm{1}\mathrm{/}n\mathrm{\right)}$。 算法 3 支持在单个请求中删除 $R$ 点，随机删除的预期时间为 $\min \mathit{}\mathrm{\{}O\mathit{}\mathrm{(}R\mathit{}{K}^{\mathrm{2}}\mathit{}d\mathrm{)}\mathrm{,}O\mathit{}\mathrm{(}n\mathit{}K\mathit{}d\mathrm{)}\mathrm{\}}$，预期的预期时间为 $\min \mathit{}\mathrm{\{}O\mathit{}\mathrm{(}R\mathit{}{K}^{\mathrm{3}}\mathit{}{ϵ}_{\mathrm{1}}\mathit{}{ϵ}_{\mathrm{2}}\mathit{}d\mathrm{)}\mathrm{,}O\mathit{}\mathrm{(}n\mathit{}K\mathit{}d\mathrm{)}\mathrm{\}}$敌对性移除。 完整再训练的复杂度等于$O\mathit{}\mathrm{(}n\mathit{}K\mathit{}d\mathrm{)}$。

Remark。

由于基于距离的$K$-means++初始化过程，数据集中异常值的存在不可避免地导致更高的再训练概率。 情况就是如此，因为异常值更有可能位于初始质心集中。 因此，出于分析目的，我们在定理5.4中假设数据集包含至少一个异常值的概率的上限为$O\mathit{}\mathrm{\left(}\mathrm{1}\mathrm{/}n\mathrm{\right)}$。 这并不是一个过度限制性的假设，因为在聚类之前存在许多不同的方法来删除异常值 Chawla & Gionis (2013)；甘和吴 (2017); Hautamäki 等人 (2005)，这有效地使异常值的概率可以忽略不计。

5.3 忘记联邦集群

接下来我们将描述使用 Alg 的新 FC 框架的完整遗忘算法。 3 用于客户端级集群。 在FL设置中，数据驻留在客户端存储设备上，因此联合取消学习的基本假设是删除请求只会出现在客户端，并且其他不受影响的客户端和服务器不会知道删除集。 我们在 FC 设置中考虑两种类型的删除请求：从一个客户端 $l$ 中删除 $R$ 点（跨孤岛，单客户端删除），以及从 $R$ 客户端$l_1,\mathrm{\dots },l_R$（跨设备、多客户端删除）。 对于多个客户端只想忘记一部分数据的情况，该方法类似于单客户端删除，可以通过简单的联合边界来处理。

Alg 中描述了遗忘过程。 4. 对于单客户端数据删除，算法将首先在 Alg 之后的客户端（例如客户端 $l$)执行取消学习。 3. 如果客户端的本地集群发生变化（即客户端$l$重新运行初始化），则会生成一个新的向量$q^{(l)}$并通过SCMA将其发送到服务器。 服务器将使用新的聚合向量$q^{\prime }$重新运行聚类过程，并生成一组新的全局质心${𝐂}_s^{\prime }$。 请注意，其他客户端在此阶段不需要执行额外的计算。 对于多客户端删除，我们遵循类似的策略，只是没有客户端需要执行额外的计算。 与引理 5.1 中描述的集中式取消学习相同，我们可以证明 Alg. 4也是一种精确的忘却方法。

移除时间复杂度。 对于单客户端删除，我们从定理5.4知道，客户端$l$的预期删除时间复杂度为$\min \{O(R{K}^{2}d),O(n^{(l)}Kd)\}$和$\min \{O(R{K}^3{ϵ}_1{ϵ}_{2}d),O(n^{(l)}Kd)\}$分别是随机删除和对抗性删除。 $n^{(l)}$表示客户端$l$上的数据点数量。其他客户端不需要额外的计算，因为它们的质心不会受到删除请求的影响。 同时，服务器的去除时间复杂度上限为$O(K^{2}LTd)$，其中$T$是Lloyd算法在收敛之前在服务器上的最大迭代次数。 对于多客户端删除，客户端不需要执行额外的计算，服务器的删除时间复杂度等于$O((L-R)K^{2}Td)$。

算法4 忘记联邦集群

1: input: Dataset $𝒳$ distributed on $L$ clients (${𝒳}^{(1)},\mathrm{\dots },{𝒳}^{(L)}$), (${𝐂}^{(l)},{𝒳}_s,q,{𝐂}_s$) obtained by Algorithm 1 on $𝒳$, removal request set ${𝒳}_R^{(l)}$ for single-client removal or ${ℒ}_R$ for multi-client removal.

2: if single-client removal then

3: Run Algorithm 3 on client $l$ and update $q^{(l)}$ if client $l$ has to perform retraining.

4: else

5: $q^{(l)}\leftarrow \mathrm{𝟎}$ on client $l$, $\forall l\in {ℒ}_R$.

6: end if

7: Securely sum up $q^{(l)}$ at server by Algorithm 2, with the aggregated vector denoted as $q^{\prime }$.

8: if $q^{\prime }=q$ then

9: ${𝐂}_s^{\prime }\leftarrow {𝐂}_s$.

10: else

11: Generate ${𝒳}_s^{\prime }$ with $q^{\prime }$.

12: Run full $K$-means++ at the server with ${𝒳}_s^{\prime }$ to obtain ${𝐂}_s^{\prime }$.

13: end if

14: return Client centroid sets ${𝐂}^{(l)\prime }$, server data ${𝒳}_s^{\prime },q^{\prime }$ and centroids ${𝐂}_s^{\prime }$.

6实验结果

为了凭经验描述我们新提出的 FC 方法的数据删除效率和性能之间的权衡，我们将其与合成数据集和真实数据集上的基线方法进行了比较。 由于篇幅限制，更深入的实验和讨论委托给附录M。

数据集和基线。 我们在实验中使用由高斯混合模型 (Gaussian) 生成的一个合成数据集和六个真实数据集（Celltype、Covtype、FEMNIST、Postures、TMI、TCGA）。 我们对数据集进行预处理，使数据分布是非独立同分布的。 跨不同的客户。 图3中的符号$K^{\prime }$表示客户端之间（真实）聚类的最大数量，而$K$表示全局数据集中真实聚类的数量。 数据统计和预处理过程的详细描述参见附录M。由于目前没有专为取消联邦集群而设计的现成算法，因此我们采用 Ginart 等人 (2019) 中的 DC-Kmeans (DC-KM) 来应用于我们的问题设置，并使用完全再训练作为基线比较方法。 为了评估完整数据集上的 FC 性能（数据删除之前），我们还使用 Dennis 等人 (2021) 的 K-FED 算法作为基线方法。 在所有图中，我们的 Alg。 1 称为 MUFC。 请注意，在 FL 中，客户端通常是并行训练的，因此估计的时间复杂度等于客户端的最长处理时间与服务器的处理时间之和。

聚类性能。 Tab 的第一行显示了所有方法在完整数据集上的聚类性能。 1. 损失率定义为${\varphi }_f(𝒳;{𝐂}_s)/{\varphi }_c^{*}(𝒳)$，这是用于评估所获得的聚类质量的度量。 对于七个数据集，MUFC 在 TMI 和 Celltype 上提供了最佳性能，这些数据集的不同簇中的数据点数量高度不平衡。 这可以通过指出MUFC和K-FED/DC-KM之间的一个重要区别来解释：客户端发送的量化质心可能具有非单位权重，而MUFC本质上是执行加权$K$-means++在服务器上。 相比之下，K-FED 和 DC-KM 都为客户端的质心分配相同的单位权重。 请注意，根据局部聚类为客户端的质心分配权重不仅可以对方案进行简单分析，而且还可以提高经验性能，特别是对于聚类分布高度不平衡的数据集。 对于除 Gaussian 之外的所有其他数据集，与 K-FED/DC-KM 相比，MUFC 获得了有竞争力的聚类性能。 DC-KM 在高斯数据上优于 MUFC 的主要原因是在这种情况下所有簇的大小相同。 另请注意，DC-KM 为每个客户端运行完整的 $K$-means++ 集群，而 MUFC 仅执行初始化。 虽然在客户端运行完整的$K$-means++聚类可以提高某些数据集上的经验性能，但它也大大增加了训练过程中的计算复杂度和取消学习过程中的重新训练概率，如图3。 尽管如此，我们还在附录 M 中的 MUFC 客户端上运行完整 $K$-means++ 聚类时，将 MUFC 与 K-FED/DC-KM 的性能进行了比较。

我们还研究了$K^{\prime }$和$\gamma$对聚类性能的影响。 图3(a)显示，当时，MUFC可以获得较低的损失率，表明数据是非独立同分布的。 分布在各个客户端。 图3(b)表明，由于我们使用均匀采样，$\gamma$的选择似乎对高斯数据集的聚类性能没有很大影响在 Alg 的第 6 步中。 1 生成服务器数据集。 同时，图3(c)表明$\gamma$可以对现实数据集的聚类性能产生显着影响，这与我们在定理4.1。 两个图中的红色垂直线表示默认选择 $\gamma =1/\sqrt{n}$，其中 $n$ 代表跨客户端的总数据点数量。

忘却表现。 由于K-FED不支持数据去除，计算复杂度较高，其经验聚类性能比DC-KM差（见表1）。 1)，我们只比较MUFC和DC-KM的遗忘性能。 为简单起见，我们考虑在每一轮取消学习时从均匀随机选择的客户端 $l$ 中删除一个数据点。 Tab 的第二行。 1记录加速比w.r.t。 一轮 MUFC 遗忘的完整再训练（Alg. 4)，当删除的点不在客户端$l$选择的质心集中时。图3(e)显示了TMI数据集上对抗性去除的累积去除时间，通过去除每轮对目标函数当前值贡献最大的数据点来模拟，图3(f)-(l)显示了随机去除的不同数据集上的累积去除时间。 结果表明，与所有其他基线方法相比，MUFC 保持了较高的遗忘效率，并且与七个数据集上随机删除的完全再训练相比，提供了 $84$x 的平均加速比。 我们还在图3(d)中报告了遗忘过程中MUFC损失率的变化。 每次删除后损失率几乎保持不变，这表明我们的忘却方法不会显着降低聚类性能。 类似的结论也适用于其他测试数据集，如附录M所示。

表格1： 不同 FC 算法的聚类性能与集中式 $K$-means++ 聚类相比。

		TMI	Celltype	Gaussian	TCGA	Postures	FEMNIST	Covtype
Loss ratio	MUFC	$1.24\pm 0.10$	$1.14\pm 0.03$	$1.25\pm 0.02$	$1.18\pm 0.05$	$1.10\pm 0.01$	$1.20\pm 0.00$	$1.03\pm 0.02$
	K-FED	$1.84\pm 0.07$	$1.72\pm 0.24$	$1.25\pm 0.01$	$1.56\pm 0.11$	$1.13\pm 0.01$	$1.21\pm 0.00$	$1.60\pm 0.01$
	DC-KM	$1.54\pm 0.13$	$1.46\pm 0.01$	$1.02\pm 0.00$	$1.15\pm 0.02$	$1.03\pm 0.00$	$1.18\pm 0.00$	$1.03\pm 0.02$
Speed-up of MUFC (if no retraining is performed)		$151$x	$1535$x	$2074$x	$483$x	$613$x	$53$x	$267$x

图3： 阴影区域代表不同轨迹结果的标准偏差。 (a) 数据异构性对MUFC聚类性能的影响：$K^{\prime }$表示客户端数据覆盖的（全局）聚类的最大数量，而$K^{\prime }=10$表示数据点是 i.i.d. 分布在各个客户端。 (b)(c)量化步长$\gamma$对MUFC聚类性能的影响。 红色垂直线表示默认选择 $\gamma =1/\sqrt{n}$，其中 $n$ 是跨客户端的数据点总数。 (d) 每轮遗忘后损失率的变化。 (e) 对抗性移除的累积移除时间。 (f)-(l) 随机移除的累积移除时间。

道德声明

我们模拟中使用的七个数据集都是公开的。 其中TCGA和TMI包含潜在敏感的生物数据，登录数据库后下载。 我们在处理这些匿名数据时遵守所有规定，并且只会发布数据处理管道以及在 TCGA 和 TMI 不受限制的数据。 不包含敏感信息的数据集可以直接从其开源存储库下载。

再现性声明

我们的实现可在 https://github.com/thupchnsky/mufc 获取。 源代码中包含详细说明。

致谢

这项工作由 NSF 拨款 1816913 和 1956384 资助。 作者感谢 Eli Chien 的有益讨论。

附录A相关作品

联合集群。 FC 的想法是使用驻留在不同边缘设备上的数据执行集群。 它与聚类 FL (Sattler 等人, 2020) 密切相关，其目标是基于数据集的聚类结构同时学习多个全局模型，并根据聚类分配进行个性化佛罗里达州客户数据（Mansour 等人，2020）。 FC 和分布式集群之间的一个区别（Guha 等人，2003；Ailon 等人，2009） 是不同客户端之间数据异构性的假设。 最近的工作（Ghosh 等人，2020；Dennis 等人，2021；Chung 等人，2022）利用客户数据的非独立同分布性质来提高一些学习者的表现。 另一个区别涉及数据隐私。 以前的大多数方法都围绕将精确的 (Dennis 等人, 2021) 或量化的客户端（本地）质心 (Ginart 等人, 2019) 发送到服务器的想法，这可能不被认为是私有的，因为它泄露了所有客户端的数据统计或集群信息。 为了避免发送精确的质心，Li 等人（2022）建议将数据点和质心之间的距离发送到服务器，而不向任何相关方透露数据点的成员资格。 请注意，目前 FC 问题的计算或信息理论保密/隐私还没有正式的定义，因此很难比较解决 FL 不同方面的方法。 我们的方法引入了一种易于忘记的聚类过程和新的隐私机制，该机制直观上很有吸引力，因为它涉及将客户端的模糊点计数传递给服务器。

稀疏安全聚合。 稀疏安全聚合旨在针对局部模型高维但稀疏的情况，以通信有效的方式安全地聚合局部模型。 稀疏安全聚合的现有工作（Beguier等人，2020；Ergun等人，2021）要么具有模型维度上线性的通信复杂性，要​​么只能生成聚合模型的近似值基于某些稀疏化程序（Han等人，2020）。 相比之下，我们的 SCMA 方案可以安全地恢复输入稀疏模型的精确总和，通信复杂度在模型维度上为对数。

私人集合联盟。 与稀疏安全聚合相比，私有集联合（Kissner & Song，2005；Frikken，2007；Seo 等人，2012）是一个相关但不同的问题。 它需要多方相互通信才能安全地计算其集合的并集。 在 SCMA 中，我们聚合多重集，其中包括私有集并集问题中未考虑的每个元素的频率。 另外，我们的方案仅包括从客户端到服务器的一轮通信，而私有集联合问题中没有服务器，但需要多轮客户端到客户端通信。

机器忘却。 对于集中机器遗忘问题，之前的工作中提出了两种类型的遗忘要求：精确遗忘和近似遗忘。 为了实现精确的遗忘，未学习的模型需要与完全重新训练的模型具有相同的性能。 为了实现这一目标，Cao & Yang (2015)引入了分布式学习器，Bourtoule 等人 (2021) 提出了基于分片的方法，Ginart 等人 (2019) 使用量化来消除聚类问题中删除数据的影响，Chen 等人 (2021) 将基于分片的方法应用于图神经网络。 对于近似遗忘，未学习模型和完全再训练模型之间的行为“差异”应该受到适当限制，类似于差异隐私背景下的做法。 沿着后一个方向，Guo 等人 (2020) 引入了线性模型的逆牛顿更新，Sekhari 等人 (2021) 研究了近似未学习模型的泛化性能，Fu 等人 (2022) 提出了基于采样的贝叶斯推理的 MCMC 去学习算法，Golatkar 等人 (2020a; b) 设计了基于 Fisher 的深度神经网络模型更新机制信息与神经切线核，而 Chien 等人 (2022; 2023); Pan等人(2023)将分析扩展到图神经网络。 最近的一些工作也研究了 FL 设置中的数据删除：Liu 等人 (2021) 提出在再训练期间使用更少的迭代进行联合取消学习，Wu 等人 (2022) t1>将知识蒸馏引入到遗忘过程中，以消除要求删除的数据点的影响，而Wang等人（2022）考虑通过检查每个数据点的内部影响来删除特定类别中的所有数据卷积神经网络中的通道。 这些联合取消学习方法（大部分）是经验性的，并且没有对删除后的模型性能和/或取消学习效率提供理论保证。 相比之下，我们提出的 FC 框架不仅能够在实践中实现高效的数据删除，而且还为未学习模型的性能和未学习过程的预期时间复杂度提供了理论保证。

附录B$K$-表示++初始化

即使对于 $K=2$,$K$ 均值问题也是 NP 困难的，并且当点位于二维欧几里德空间中时 (Mahajan 等人, 2012)。 解决问题的启发式算法，包括 Lloyd 方法（Lloyd，1982）和 Hartigan 方法（Hartigan & Wong，1979），不能保证获得全局最优解，除非进一步对点和簇结构进行假设（Lee等人，2017）。 尽管获得 $K$ 均值问题的精确最优解很困难，但有许多方法可以获得最优质心的质量近似值。 例如，Vassilvitskii & Arthur (2006)中引入了随机初始化算法($K$-means++），初始化后的期望目标值为$(\log K)$ - 逼近最佳目标 ($𝔼(\varphi )\le (8\ln K+16){\varphi }^{*}$)。 $K$-means++ 初始化工作如下：最初，质心集 $𝐂$ 被假定为空。 然后，从第一个质心的$X$中随机均匀采样一个点，并将其添加到$𝐂$中。 对于接下来的 $K-1$ 轮，来自 $X$ 的点 $x$ 以概率 $d^2(x,𝐂)/{\varphi }_c(𝒳;𝐂)$ 采样作为新质心，并添加到 $𝐂$。 这里，$d(x,𝐂)$表示$x$与迄今为止选择的$𝐂$中的质心之间的最小${\mathrm{\ell }}_2$距离。 初始化步骤之后，我们到达用于运行 Lloyd 算法的 $𝐂$ 中的 $K$ 初始质心。

附录C算法复杂度分析1

客户端集群的计算复杂性。 客户端集群涉及运行$K$-means++初始化过程，其复杂性$O(nKd)$。

服务器端集群的计算复杂性。 服务器端集群涉及运行 $K$-means++ 初始化过程，然后是具有 $T$ 次迭代的 Lloyd 算法，其复杂度为 $O(K^{2}LTd)$。

SCMA 在客户端的计算复杂度。 客户端 $l$ 上 $S_i^{(l)}$ 的计算最多需要对 ${𝔽}_p,$ $i\in [2KL]$ 进行 $O(K\log i)$ 次乘法。 总计算复杂度等于$O(K^{2}L\log (KL))$乘法和加法运算与${𝔽}_p$。

服务器端 SCMA 的计算复杂度。 服务器端的计算复杂度主要取决于 Berlekamp-Massey 解码算法 （Berlekamp，1968；Massey，1969） 的复杂度，该算法将多项式 $g(x)$ 分解为 ${𝔽}_p$ (Kedlaya & Umans, 2011)，并用已知的$j$、$q_j\ne 0$求解线性方程$S_i={\sum }_{l\in [L]}{S}_i^{(l)}={\sum }_{j:q_j\ne 0}{q}_j\cdot j^{i-1}$。 ${𝔽}_p$ 上 Berlekamp-Massey 解码的复杂度为 $O(K^2{L}^2)$。 使用 Kedlaya & Umans (2011) 中的算法对 ${𝔽}_p$ 进行多项式 $g(x)$ 因式分解的复杂度是 $O({(KL)}^{1.5}\log p+KL{\log }^{2}p)$ 次运算，而不是 ${𝔽}_p$。 求解 $S_i={\sum }_{l\in [L]}{S}_i^{(l)}$ 的复杂性等于查找 Vandermonde 矩阵的逆矩阵，它需要对 ${𝔽}_p$ 进行 $O(K^2{L}^2)$ 运算（Eisinberg & Fedele, 2006 ）。 因此，服务器端的总计算复杂度是$\max \{O(K^2{L}^2),O({(KL)}^{1.5}\log p+KL{\log }^{2}p)\}$操作超过${𝔽}_p$。

SCMA在客户端的通信复杂性。 由于每个$S_i^{(l)}$都可以用$\lceil \log p\rceil$位来表示，因此每个客户端$l$发送的信息${\{S_i^{(l)}\}}_{i\in [2KL]}$可以用$2KL\lceil \log p\rceil \le \max \{2KL\log n,2KLd\log B\}+1$ 请注意，最多有长度为 $B^d$ 的 ${\sum }_{k\in [KL]}\left(\genfrac{}{}{0pt}{}{B^d}{k}\right)\left(\genfrac{}{}{0pt}{}{n}{k-1}\right)$ $q$ 元向量。 因此，从客户端到服务器 $l$ 的通信 $q^{(l)}$ 的成本至少为 $\log \left({\sum }_{k\in [KL]}\left(\genfrac{}{}{0pt}{}{B^d}{k}\right)\left(\genfrac{}{}{0pt}{}{n}{k-1}\right)\right)=\max \{O(KL\log n),O(KLd\log B)\}$ 位，这意味着我们的方案是顺序最优的。 沟通成本。 请注意，遵循该领域的标准实践，我们没有考虑安全模型聚合中噪声生成的复杂性，因为它可以离线完成并且独立于里德-所罗门编码过程。

附录D定理证明4.1

证明。

我们首先考虑不执行量化的情况（算法5)。 引理 D.1 中提供了此设置中联合目标值的性能保证。

Lemma D.1.

假设跨客户端的整个数据集用$𝒳$表示，算法5返回的服务器质心集是${𝐂}_s$。 然后我们有

证明。

让 ${𝐂}^{*}$ 表示最小化整个数据集 $X\in {ℝ}^{n\times d}$ 的目标 (1) 的最佳质心集，让 $C^{*}\in {ℝ}^{n\times d}$ 为记录${𝐂}^{*}$中与每个数据点最接近的质心的矩阵，${𝐂}_s$是Alg返回的质心集。 1，以及 $C_s\in {ℝ}^{n\times d}$ 矩阵，该矩阵根据定义 3.1 中定义的全局聚类，在 ${𝐂}_s$ 中记录了每个数据点的相应中心点。 由于我们对每个客户端数据集执行 $K$-means++ 初始化，因此对于客户端 $l$ 它保持

$𝔼\left({\Vert X^{(l)}-C^{(l)}\Vert }_F^2\right)$ $\le (8\ln K+16){\Vert X^{(l)}-C_{*}^{(l)}\Vert }_F^2,\forall l\in [L]$

$\le (8\ln K+16){\Vert X^{(l)}-C^{*,(l)}\Vert }_F^2$ (3)

其中 $C^{(l)}\in {ℝ}^{n^{(l)}\times d}$ 记录了 ${𝐂}^{(l)}$ 中与 ${𝒳}^{(l)}$ 中每个数据点 $x_i$ 最近的中心点，$C_{*}^{(l)}$ 是可以最小化客户 $l$ 的局部 $K$ 均值目标的最优解，$C^{*,(l)}$ 表示 $C^{*}$ 中与客户 $l$ 相对应的行。对所有客户求和 (D) 得出

$𝔼\left({\displaystyle \sum _{l=1}^L}{\Vert X^{(l)}-C^{(l)}\Vert }_F^2\right)\le (8\ln K+16){\displaystyle \sum _{l=1}^L}{\Vert X^{(l)}-C^{*,(l)}\Vert }_F^2.$ (4)

在服务器端，客户端质心被重新组织成矩阵$X_s\in {ℝ}^{n\times d}$。 客户端质心的权重转换为 $X_s$ 中行的重复。 由于我们在服务器上执行完整的 $K$-means++ 集群，因此可以得出以下结论

$𝔼\left({\Vert X_s-C_s\Vert }_F^2\right)$ $=𝔼\left({\displaystyle \sum _{l=1}^L}{\Vert C^{(l)}-C_s^{(l)}\Vert }_F^2\right)$

$\stackrel{(a)}{\le }(8\ln K+16){\displaystyle \sum _{l=1}^L}𝔼\left({\Vert C^{(l)}-C_{s,*}^{(l)}\Vert }_F^2\right)$

$\le (8\ln K+16){\displaystyle \sum _{l=1}^L}𝔼\left({\Vert C^{(l)}-C^{*,(l)}\Vert }_F^2\right),$ (5)

其中 $C_{s,*}\in {ℝ}^{n\times d}$ 是最小化服务器上​​的 $K$ 意味着目标的最佳解决方案。 值得指出的是，$C_{s,*}$与$C^{*}$不同，它们是针对不同优化目标的最优解。 请注意，我们仍然保留 $(a)$ 的 RHS 期望。 随机性来自于 $C^{(l)}$ 是通过 $K$-means++ 初始化获得的，这是一个概率过程。

组合 (4) 和 (D) 结果为

$𝔼\left({\varphi }_f(𝒳;{𝐂}_s)\right)$ $=𝔼\left({\displaystyle \sum _{l=1}^L}{\Vert X^{(l)}-C_s^{(l)}\Vert }_F^2\right)$

$\le 2\cdot 𝔼\left[{\displaystyle \sum _{l=1}^L}\left({\Vert X^{(l)}-C^{(l)}\Vert }_F^2+{\Vert C^{(l)}-C_s^{(l)}\Vert }_F^2\right)\right]$

$\le (16\ln K+32){\displaystyle \sum _{l=1}^L}\left[{\Vert X^{(l)}-C^{*,(l)}\Vert }_F^2+𝔼\left({\Vert C^{(l)}-C^{*,(l)}\Vert }_F^2\right)\right].$ (6)

对于$𝔼\left({\Vert C^{(l)}-C^{*,(l)}\Vert }_F^2\right)$，我们有

$𝔼\left({\Vert C^{(l)}-C^{*,(l)}\Vert }_F^2\right)$ $\le 2\cdot 𝔼\left({\Vert C^{(l)}-X^{(l)}\Vert }_F^2+{\Vert X^{(l)}-C^{*,(l)}\Vert }_F^2\right)$

$=2\cdot {\Vert X^{(l)}-C^{*,(l)}\Vert }_F^2+2\cdot 𝔼\left({\Vert C^{(l)}-X^{(l)}\Vert }_F^2\right).$ (7)

将 (D) 替换为 (D) 显示 ，从而完成证明。

如果我们只关心整个数据集中非离群点的性能，我们可以将项 $𝔼\left({\sum }_{l=1}^L{\Vert C^{(l)}-C^{*,(l)}\Vert }_F^2\right)$ 的上限设置为

$$𝔼\left(\sum _{l=1}^L{\Vert C^{(l)}-C^{*,(l)}\Vert }_F^2\right)\le {ϵ}_2{\varphi }_c^{*}(𝒳).$$ (8)

在这里，我们使用了这样一个事实：$C^{(l)}$ 行都是由 $K$-means++ 初始化过程采样的真实数据点。 对于每个数据点$x_i$，它保存${\Vert x_i-c_i^{*}\Vert }^2|{𝒞}_i^{*}|\le {ϵ}_2{\varphi }_c^{*}({𝒞}_i^{*})$，其中$x_i\in {𝒞}_i^{*}$。 在这种情况下，我们到达 ，其中 ${𝒳}_t$ 对应于所有非离群点。 ∎

Remark。

在 Guha 等人 (2003) 的定理 4 中，作者表明，对于分布式 $K$ 中值问题，如果我们使用 $O\mathit{}\mathrm{(}b\mathrm{)}$ 逼近算法（即，$\varphi \mathrm{\le }O\mathit{}\mathrm{(}b\mathrm{)}\mathrm{\cdot }{\varphi }^{\mathrm{*}}$)用于分布式计算机上子数据集的$K$中值问题，并使用$O\mathit{}\mathrm{(}c\mathrm{)}$-近似算法来解决$K$ -集中式机器上的中值问题，整体分布式算法有效地实现了集中式$K$中值问题最优解的$O\mathit{}\mathrm{(}b\mathit{}c\mathrm{)}$-近似。 这与我们的观察一致，即 Alg。 5 可以为集中式 $K$-means 问题的最优解提供预期的 $O\mathit{}\mathrm{(}{\log }^{\mathrm{2}}\mathit{}K\mathrm{)}$-近似值，因为 $K$-means++初始化在客户端和服务器端实现了 $O\mathit{}\mathrm{(}\log \mathit{}K\mathrm{)}$ 近似。

我们还指出，在 Dennis 等人 (2021) 中，作者假设客户端 $l$ 上全局最优聚类的准确聚类数量已知且等于 $K^{\mathrm{(}l\mathrm{)}}$，并提出$K$-FED算法，该算法在$K^{\mathrm{\prime }}\mathrm{=}{\max }_{l\mathrm{\in }\mathrm{[}L\mathrm{]}}\mathit{}{K}^{\mathrm{(}l\mathrm{)}}\mathrm{\le }\sqrt{K}$时表现良好。 $K^{\mathrm{\prime }}$ 和 $K$ 之间的差异表示不同客户端之间的数据异构性。 只要对证明稍作修改，当事先知道每个客户机的 $K^{\mathrm{(}l\mathrm{)}}$ 时，我们也可以得到 ，并在客户机 $l$ 上执行 $K^{\mathrm{(}l\mathrm{)}}$-means++ 而不是 Alg 中的 $K$-means++ 。 1. 对于每个客户端保护整个集群数据的极端设置（w.r.t.） 全局最优聚类($L\mathrm{=}K\mathrm{,}{K}^{\mathrm{\prime }}\mathrm{=}\mathrm{1}$))，Alg的性能保证。 1 变为 ，这与通过从该簇中均匀随机采样的数据点为每个最佳簇播种相同。 从Vassilvitskii & Arthur (2006)的引理3.1我们看到，我们确实可以有$𝔼\mathit{}\mathrm{\left(}{\varphi }_f\mathit{}\mathrm{(}𝒳\mathrm{;}{𝐂}_s\mathrm{)}\mathrm{\right)}\mathrm{=}\mathrm{2}\mathit{}{\varphi }_c^{\mathrm{*}}\mathit{}\mathrm{(}𝒳\mathrm{)}$，其中近似因子不依赖于$K$。这表明不同客户端之间的数据异构性可以使整个 FC 框架受益。

接下来我们给出定理4.1的证明。 遵循与引理 D.1 证明中使用的相同想法，我们得出

$𝔼\left({\varphi }_f(𝒳;{𝐂}_s)\right)$ $\le 3\cdot 𝔼\left[{\displaystyle \sum _{l=1}^L}\left({\Vert X^{(l)}-C^{(l)}\Vert }_F^2+{\Vert C^{(l)}-{\widehat{C}}^{(l)}\Vert }_F^2+{\Vert {\widehat{C}}^{(l)}-C_s^{(l)}\Vert }_F^2\right)\right],$ (9)

其中 ${\widehat{C}}^{(l)}$ 是 $C^{(l)}$ 的量化版本。 第一项可以以与引理 D.1 中相同的方式设置上限。 对于第二项，如果我们选择量化仓的中心作为重建点，则通过量化一个点引入的失真受到 $\frac{\sqrt{d}\gamma }{2}$ 的限制。 所以，

$$𝔼\left(\sum _{l=1}^L{\Vert C^{(l)}-{\widehat{C}}^{(l)}\Vert }_F^2\right)\le n{\left(\frac{\sqrt{d}\gamma }{2}\right)}^2=\frac{nd{\gamma }^2}{4}.$$ (10)

第三项可以限制为

$𝔼\left({\displaystyle \sum _{l=1}^L}{\Vert {\widehat{C}}^{(l)}-C_s^{(l)}\Vert }_F^2\right)\le (8\ln K+16){\displaystyle \sum _{l=1}^L}𝔼\left({\Vert {\widehat{C}}^{(l)}-C^{*,(l)}\Vert }_F^2\right)$

$𝔼\left({\Vert {\widehat{C}}^{(l)}-C^{*,(l)}\Vert }_F^2\right)\le 3\cdot 𝔼\left({\Vert {\widehat{C}}^{(l)}-C^{(l)}\Vert }_F^2+{\Vert C^{(l)}-X^{(l)}\Vert }_F^2+{\Vert X^{(l)}-C^{*,(l)}\Vert }_F^2\right).$ (11)

将 (10) 和 (D) 替换为 (9) 会导致

这就完成了证明。 与引理 D.1 类似，我们可以将其用于非离群点 ${𝒳}_t$、。 ∎

附录E引理证明5.1

证明。

假设$𝒳$中的数据点数为$n$,${𝒳}_R$的大小为$R$，初始质心设置为$𝒳$是$𝐂$。 我们用归纳法证明${𝐂}^{\prime }$是由Alg返回的。 3 在概率上相当于在 ${𝒳}^{\prime }=𝒳\backslash {𝒳}_R$ 上重新运行 $K$-means++ 初始化。

归纳的基本情况相当于研究 $c_1$ 的删除过程，即 $K$-means++ 选择的第一个点。 有两种可能的情况：$c_1\in {𝒳}_R$ 和 $c_1\notin {𝒳}_R$。 在第一种情况下，我们将重新运行 ${𝒳}^{\prime }$ 上的初始化过程，这相当于重新训练模型。 在第二种情况下，由于我们知道$c_1\notin {𝒳}_R$，因此从$𝒳$中选择$c_1$作为第一个质心的概率等于条件概率

${\displaystyle \frac{1}{n-R}}$ $=\mathbb{P}(\text{choose}{c}_1\text{from}𝒳\text{as the first centroid}|c_1\notin {𝒳}_R)$

$=\mathbb{P}(\text{choose}{c}_1\text{from}{𝒳}^{\prime }\text{as the first centroid}).$

接下来假设$K>1$,$i=({\arg \min }_j{c}_j\in {𝒳}_R)-1$。 Alg 返回的质心 ${𝐂}_{i-1}^{\prime }=\{c_1^{\prime }=c_1,\mathrm{\dots },c_{i-1}^{\prime }=c_{i-1}\}$。 3 可以被视为在概率上等同于通过在前 $i-1$ 轮中重新运行 ${𝒳}^{\prime }$ 上的初始化过程而获得的模型。 然后我们有

$\mathbb{P}(\text{choose}{c}_i\text{from}𝒳\text{as}i\text{-th centroid}|c_i\notin {𝒳}_R)$ $={\displaystyle \frac{\mathbb{P}(\text{choose}{c}_i\text{from}𝒳\text{as}i\text{-th centroid}\cap c_i\notin {𝒳}_R)}{\mathbb{P}(c_i\notin {𝒳}_R)}}$

$\stackrel{(a)}{=}{\displaystyle \frac{\mathbb{P}(\text{choose}{c}_i\text{from}𝒳\text{as}i\text{-th centroid})}{\mathbb{P}(c_i\notin {𝒳}_R)}}$

$={\displaystyle \frac{d^2(c_i,{𝐂}_{i-1}^{\prime })/{\varphi }_c(𝒳;{𝐂}_{i-1}^{\prime })}{1-{\sum }_{x\in {𝒳}_R}{d}^2(x,{𝐂}_{i-1}^{\prime })/{\varphi }_c(𝒳;{𝐂}_{i-1}^{\prime })}}$

$={\displaystyle \frac{d^2(c_i,{𝐂}_{i-1}^{\prime })/{\varphi }_c(𝒳;{𝐂}_{i-1}^{\prime })}{{\varphi }_c({𝒳}^{\prime };{𝐂}_{i-1}^{\prime })/{\varphi }_c(𝒳;{𝐂}_{i-1}^{\prime })}}$

$={\displaystyle \frac{d^2(c_i,{𝐂}_{i-1}^{\prime })}{{\varphi }_c({𝒳}^{\prime };{𝐂}_{i-1}^{\prime })}}$

$=\mathbb{P}(\text{choose}{c}_i\text{from}{𝒳}^{\prime }\text{as}i\text{-th centroid}),$

其中$(a)$根据$i$的定义成立，表明第$i$质心不在${𝒳}_R$中。 因此，Alg 返回的质心 $c_i^{\prime }=c_i$。 3 可以看作是在第 $i$ 轮中对 ${𝒳}^{\prime }$ 重新运行初始化过程而获得的。 再次基于 $i$ 的定义，很明显，对于 $j>i$,$c_j^{\prime }$ 是 $K$-means++ 过程选择的质心超过${𝒳}^{\prime }$。 这证明了我们的说法，${𝐂}^{\prime }$ 由 Alg 返回。 3 的概率相当于在 ${𝒳}^{\prime }$ 上重新运行 $K$-means++ 初始化所获得的结果。

Vassilvitskii & Arthur (2006) 的定理 1.1 证明

$$𝔼({\varphi }_c({𝒳}^{\prime };{𝐂}^{\prime }))\le 8(\ln K+2){\varphi }_c^{*}({𝒳}^{\prime }),$$ (12)

这就完成了证明。 ∎

附录F定理证明5.4

证明。

我们首先基于Alg分析重新运行$K$-means++初始化的概率。 3. 假设5.2和5.3可用于导出$x_i\in 𝐂$概率的表达式（其中$x_i$是需要的点被遗忘），这也等于重新训练的概率。

Lemma F.1.

假设$𝒳$中的数据点数量为$n$，并且数据集包含至少一个异常值的概率上限为$O\mathit{}\mathrm{\left(}\mathrm{1}\mathrm{/}n\mathrm{\right)}$。 令$𝐂$为在$𝒳$上运行$K$-means++获得的质心集。 对于大小为 $R$ 的任意移除集 ${𝒳}_R\mathrm{\subseteq }𝒳$，我们有

for random removals:

for adversarial removals:

证明。

由于根据定义，异常值可以与所有真实聚类点任意远，因此在初始化期间，它们可能会以非常高的概率被采样为质心。 为了简化分析，我们假设异常值如果存在于数据集中，则以概率 $1$ 采样为质心，这意味着我们始终需要在以下情况下重新运行 $K$-means++ 初始化：在进行任何删除之前，异常值存在于完整数据集中。

对于随机删除，要求取消学习的点 $x_i$ 是从 $𝒳$ 中均匀随机抽取的，显然 $\mathbb{P}(x_i\in 𝐂)=\frac{K}{n}$，因为 $𝐂$ 包含 $𝒳$ 中的 $K$ 个不同数据点。

对于对抗性删除，我们需要分析选择 $x_i$ 作为第 $(k+1)$ 个质心的概率，假设第一个 $k$ 质心已经确定并且 $x_i\notin {𝐂}_k=\{c_1,\mathrm{\dots },c_k\}$。 为简单起见，我们首先假设 $𝒳$ 中没有异常值。 然后我们有

$$\mathbb{P}(\text{choose}{x}_i\text{from}𝒳\text{as the}(k+1)\text{-th centroid}|{𝐂}_k)=\frac{d^2(x_i,{𝐂}_k)}{{\sum }_{y\ne x_i}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)}$$ (13)

对于分母 ${\sum }_{y\ne x_i}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)$，以下三个观察结果成立

${\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)$ $\ge {\varphi }_c^{*}(𝒳)\ge {\varphi }_c^{*}({𝒞}_i^{*}),x_i\in {𝒞}_i^{*}$

${\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)$ $\ge {\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}^{*})$

${\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)$ $\ge {\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}_k).$

所以，

${\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)$ $\ge {\displaystyle \frac{{\varphi }_c^{*}({𝒞}_i^{*})}{5}}+{\displaystyle \frac{2}{5}}\left({\displaystyle \sum _{y\ne x_i}}{d}^2(y,{𝐂}^{*})+d^2(y,{𝐂}_k)\right)$

$\stackrel{(a)}{\ge }{\displaystyle \frac{1}{5}}\left({\varphi }_c^{*}({𝒞}_i^{*})+{\displaystyle \sum _{y\ne x_i}}{\Vert c_y-c_y^{*}\Vert }^2\right),$ (14)

其中 $c_y,c_y^{*}$ 分别是 ${𝐂}_k$ 和 ${𝐂}^{*}$ 中距 $y$ 最近的质心。 这里，$(a)$是${\Vert a-b\Vert }^2={\Vert a-c+c-b\Vert }^2\le 2({\Vert a-c\Vert }^2+{\Vert b-c\Vert }^2)$这一事实的结果。 由于根据我们的假设，$x_i$ 不是 ${𝒞}_i^{*}$ 的异常值，因此我们有

$${\varphi }_c^{*}({𝒞}_i^{*})\ge \frac{|{𝒞}_i^{*}|}{{ϵ}_2}{\Vert x_i-c_i^{*}\Vert }^2\ge \frac{n}{K{ϵ}_1{ϵ}_2}{\Vert x_i-c_i^{*}\Vert }^2.$$

最后，

${\varphi }_c^{*}({𝒞}_i^{*})+{\displaystyle \sum _{y\ne x_i}}{\Vert c_y-c_y^{*}\Vert }^2$ $\ge {\displaystyle \frac{|{𝒞}_i^{*}|}{{ϵ}_2}}{\Vert x_i-c_i^{*}\Vert }^2+{\displaystyle \sum _{y\in {𝒞}_i^{*}}}{\Vert c_y-c_y^{*}\Vert }^2$

$={\displaystyle \frac{|{𝒞}_i^{*}|}{{ϵ}_2}}{\Vert x_i-c_i^{*}\Vert }^2+{\displaystyle \sum _{y\in {𝒞}_i^{*}}}{\Vert c_y-c_i^{*}\Vert }^2.$ (15)

对于$\forall y\in {𝒞}_i^{*}$，它保存${\Vert x_i-c_i^{*}\Vert }^2+{\Vert c_y-c_i^{*}\Vert }^2\ge \frac{1}{2}{\Vert x_i-c_y\Vert }^2\ge \frac{1}{2}{d}^2(x_i,{𝐂}_k)$。 因此，(F) 的下界可以为

$$\frac{|{𝒞}_i^{*}|}{{ϵ}_2}{\Vert x_i-c_i^{*}\Vert }^2+\sum _{y\in {𝒞}_i^{*}}{\Vert c_y-c_i^{*}\Vert }^2\ge \frac{|{𝒞}_i^{*}|}{2{ϵ}_2}{d}^2(x_i,{𝐂}_k)\ge \frac{n}{2K{ϵ}_1{ϵ}_2}{d}^2(x_i,{𝐂}_k).$$ (16)

结合 (16) 和 (F) 我们得到

$$\sum _{y\ne x_i}{d}^2(y,{𝐂}_k)+d^2(x_i,{𝐂}_k)\ge \frac{n}{10K{ϵ}_1{ϵ}_2}{d}^2(x_i,{𝐂}_k).$$

在 (13) 中使用此表达式会导致

$$\mathbb{P}(\text{choose}{x}_i\text{from}𝒳\text{as the}(k+1)\text{-th centroid}|{𝐂}_k)\le \frac{10K{ϵ}_1{ϵ}_2}{n},$$ (17)

这适用于$\forall k\in [K]$。 因此，概率$\mathbb{P}(x_i\in 𝐂)$可以计算为

$\mathbb{P}(x_i\in 𝐂)$ $={\displaystyle \sum _{k=0}^{K-1}}\mathbb{P}(\text{choose}{x}_i\text{from}𝒳\text{as the}(k+1)\text{-th centroid}|{𝐂}_k)\mathbb{P}({𝐂}_k)$

$\le {\displaystyle \sum _{k=0}^{K-1}}\mathbb{P}(\text{choose}{x}_i\text{from}𝒳\text{as the}(k+1)\text{-th centroid}|{𝐂}_k)$

(18)

这里，我们假设${𝐂}_0=\mathrm{\varnothing }$。

对于数据集中存在异常值的情况，我们有

$\mathbb{P}(x_i\in 𝐂)$ $=\mathbb{P}(x_i\in 𝐂|x_i\text{is outlier})\mathbb{P}(x_i\text{is outlier})+\mathbb{P}(x_i\in 𝐂|x_i\text{is not outlier})\mathbb{P}(x_i\text{is not outlier})$

这就完成了对抗性移除场景的证明。 最后，通过并集，我们可以得到大小为 $R$ 的移除集 ${𝒳}_R$，

random removals:

adversarial removals:

而且，概率自然满足

$$\mathbb{P}({𝒳}_R\cap 𝐂\ne \mathrm{\varnothing })\le 1.$$

∎

接下来我们给出定理5.4的证明。 随机移除的预期移除时间上限为

$𝔼(\text{Removal time})$ $=𝔼(\text{Removal time}|\text{new initialization needed})\mathbb{P}(\text{new initialization needed})+$

$𝔼(\text{Removal time}|\text{new initialization not needed})\mathbb{P}(\text{new initialization not needed})$

$\le O(nKd+RK)\cdot O\left({\displaystyle \frac{RK}{n}}\right)+O(RK)\cdot 1$

遵循类似的论点，我们还可以证明对抗性移除的预期移除时间可以以 $O(R{K}^3{ϵ}_1{ϵ}_{2}d)$ 为上限。 根据我们的算法 3，两种类型的删除请求的遗忘复杂度也始终以再训练复杂度 $O(nKd)$ 为上限，这完成了证明。 ∎

附录G算法3与量化$K$-means之间的比较

在Ginart等人(2019)中，提出了量化$K$-means来解决集中式环境中类似的机器失学习问题。 然而，这种方法与 Alg 有很大不同。 3. 首先，量化 $K$-means 背后的直觉是，质心是通过取平均值来计算的，当删除后簇中剩余足够的项时，少量点的影响可以忽略不计。 因此，如果我们在每次劳埃德迭代后量化所有质心，那么当我们从数据集中删除少量点时，量化质心将不会以很高的概率发生变化。 与此同时，Alg 背后的直觉。 3如引理F.1中所述。 其次，量化 $K$-means 的预期移除时间复杂度等于 $O\left(R^2{K}^3{T}^2{d}^{2.5}/ϵ\right)$，该复杂度很高，因为需要检查每次迭代移除后所有量化质心是否保持不变，其中 $T$表示收敛前Lloyd迭代的最大次数，$ϵ$是一些内在参数。 相比之下，阿尔格. 即使对于对抗性删除，3也只需要$O(R{K}^3{ϵ}_1{ϵ}_{2}d)$。 另请注意，所描述的量化 $K$ 均值算法不提供删除时间复杂度的性能保证，除非它是随机初始化的。

附录 H量化

对于均匀量化，我们设置 $\widehat{y}=\gamma \cdot a(y)$，其中 $a(y)={\arg \min }_{j\in \mathbb{Z}}|y-\gamma j|,y\in ℝ$. 参数$\gamma >0$确定每个维度中量化仓的数量。 假设所有客户端数据都位于以原点为中心的单位超立方体中，并且如果需要，则执行预处理以满足此要求。 那么每个维度的量化仓数量等于$B={\gamma }^{-1}$，而$d$维度的量化仓总数为$B^d={\gamma }^{-d}$。

在第 4 节中，我们提到可以通过选择量化仓中心作为代表点，并赋予其等于 $q_j$ 的权重来生成 $q_j$ 点。 然后，在$7$行中，我们可以在服务器端使用加权$K$-means++算法来进一步降低计算复杂度，因为服务器端的有效问题大小从$n$到$KL$。 然而，在实践中我们发现，当服务器的计算能力不是 FL 系统的瓶颈时，在量化仓内均匀随机生成数据点通常可以提高聚类性能。 因此，这是我们后续数值模拟的默认方法。

附录一简化联合$K$ - 表示集群

当未执行第 3 节中所述的隐私标准时，如在 Dennis 等人 (2021) 的框架中所做的那样，可以跳过第 3-6 行藻类。 1并将客户端$l$获得的质心集${𝐂}^{(l)}$以及簇大小$(|{𝒞}_1^{(l)}|,\mathrm{\dots },|{𝒞}_K^{(l)}|)$直接发送到服务器。 然后，可以在服务器端对聚合质心集运行加权$K$-means++算法，得到${𝐂}_s$。 Alg 中显示了该简化情况的伪代码。 5. 它遵循与 Guha 等人 (2003) 的分而治之方案类似的想法； Ailon 等人 (2009)，为分布式集群而开发。

算法5 简化联合 $K$ - 表示集群

1: input: Dataset $𝒳$ distributed on $L$ clients (${𝒳}^{(1)},\mathrm{\dots },{𝒳}^{(L)}$).

2: Run $K$-means++ initialization on each client $l$ in parallel, obtain the initial centroid sets ${𝐂}^{(l)}$, and record the corresponding cluster sizes $(|{𝒞}_1^{(l)}|,\mathrm{\dots },|{𝒞}_K^{(l)}|),\forall l\in [L]$.

3: Send $(c_1^{(l)},\mathrm{\dots },c_K^{(l)})$ along with the corresponding cluster sizes $(|{𝒞}_1^{(l)}|,\mathrm{\dots },|{𝒞}_K^{(l)}|)$ to the server, $\forall l\in [L]$.

4: Concatenate $(c_1^{(l)},\mathrm{\dots },c_K^{(l)})$ as rows of $X_s$ and set $(|{𝒞}_1^{(l)}|,\mathrm{\dots },|{𝒞}_K^{(l)}|)$ as the weights for the corresponding rows, $\forall l\in [L]$.

5: Run full weighted $K$-means++ clustering at server with $X_s$ to obtain the centroid set at server ${𝐂}_s$.

6: return Each client retains their own centroid set ${𝐂}^{(l)}$ while the server retains $X_s$ and ${𝐂}_s$.

在 Alg 的第 5 行中。 5，加权$K$-means++会在初始化过程中计算采样概率以及在劳埃德迭代期间计算集群平均值时为数据点分配权重。 由于我们在这里考虑的权重始终是正整数，因此加权数据点也可以被视为数据集中存在相同的数据点，其重数等于权重。

附录 J 给定 ${\{S_i\}}_{i\in [2KL]}$ 的向量 $q$ 的唯一性

证明 Alg 生成的消息。 2可以被唯一解码，我们证明存在唯一的$q$，它在服务器上产生聚合值${\{S_i\}}_{i\in [2KL]}$。 证明是通过反证法。 假设存在两个不同的向量$q$和$q^{\prime }$，它们产生相同的${\{S_i\}}_{i\in [2KL]}$。 在这种情况下，我们有以下一组线性方程${\sum }_{j:q_j\ne 0}{q}_j\cdot j^{i-1}-{\sum }_{j:q_j^{\prime }\ne 0}{q}_j^{\prime }\cdot j^{i-1}=0,$$i\in [2KL]$。 假设 $\{q_j:q_j\ne 0\}$ 和 $\{q_j^{\prime }:q_j^{\prime }\ne 0\}$ 最多表示 $2KL$ 个未知数和 $j^{i-1}$ 个系数，线性方程可以使用范德蒙方阵来描述系数，其中 的列由 $q$ 中非零条目的索引生成。 这导致了矛盾，因为具有不同列生成器的范德蒙方阵是可逆的，如下所示。 因此，对于不同的$q$，聚合值$\{S_i\}$必须不同。 类似地，对于不同的向量$q^{(l)}$、$i\in [2KL]$、$l\in [L]$选择，总和${\sum }_{j:q_j^{(l)}\ne 0}{q}_j^{(l)}\cdot j^{i-1}$是不同的。

如果两个向量 $q$ 和 $q^{\prime }$ 产生相同的 ${\{S_i\}}_{i\in [2KL]}$，则所有 $i\in [2KL]$ 都产生 ${\sum }_{j:q_j\ne 0}{q}_j\cdot j^{i-1}-{\sum }_{j:q_j^{\prime }\ne 0}{q}_j^{\prime }\cdot j^{i-1}=0,$。 令 $\{i_1,\mathrm{\dots },i_u\}=(\{j:q_j\ne 0\}\cup \{j:q_j^{\prime }=0\})$ 为整数集，使得 $q_{i_m}$ 和 $q_{i_m}^{\prime }$ 中至少有一个对于 $m\in [u]$ 来说不为零。 请注意$u\le 2KL$。 将这个方程重写为

(26)

从$u\le 2KL$开始，我们取(26)中的第一个$u$方程并将它们重写为

$Bv=\mathrm{𝟎},$

在哪里

是范德蒙方阵并且

$v=\left[\begin{array}{c}{q}_{i_1}-q_{i_1}^{\prime }\\ \mathrm{⋮}\\ q_{i_u}-q_{i_u}^{\prime }\end{array}\right]$

自 $q\ne q^{\prime }$ 以来是一个非零向量。 众所周知，范德蒙方阵 $B$ 的行列式由 给出，在我们的例子中它是非零的，因为所有 $i_1,\mathrm{\dots },i_u$ 都是不同的。 因此，$B$是可逆的，并且不允许有非零解，这与方程$Bv=\mathrm{𝟎}$相矛盾。

附录 K 服务器端 SCMA 的确定性低复杂度算法

在我们在 Alg 中描述的 SCMA 方案中。 1，服务器的目标是重建向量$q$，给定$i\in [2KL]$的值$S_i={\sum }_{j:q_j\ne 0}{q}_j\cdot j^{i-1}\text{mod}p$。 为此，我们首先使用Berlekamp-Massey算法来计算多项式$g(x)={\prod }_{j:q_j\ne 0}(1-j\cdot x)$。 然后，我们使用 Kedlaya & Umans (2011) 中描述的算法在有限域 ${𝔽}_p$ 上分解 $g(x)$。 4.3 节中提到的复杂度 $O({(KL)}^{1.5}\log p+KL{\log }^{2}p)$ 对应于平均复杂度（找到一种确定性算法，该算法在有限域上分解多项式，其最坏情况复杂度为 $poly(\log p)$是一个开放性问题）。 SCMA方案的附录C中提到的复杂度$\max \{O(K^2{L}^2),O({(KL)}^{1.5}\log p+KL{\log }^{2}p)\}$表示平均复杂度。

接下来我们表明，SCMA 方案在服务器端的确定性解码算法下也具有较小的最坏情况复杂度。 为此，我们替换 Alg 中的整数 $p$。 2 具有较大的数字 $p^{\prime }\ge \max \{KL{B}^{2dKL},n\}+1$，使得 $p^{\prime }$ 大于最大可能的 $S_i$，并且在应用模数时不会溢出$p^{\prime }$ 对 $S_i$ 进行操作。 已知（伯特兰公设）任何整数 $n>3$ 和 $2n-2$ 之间都存在一个素数，因此必定存在一个下界为 $\max \{KL{B}^{2dKL},n\}+1$ 的素数> 和下限 $2(\max \{KL{B}^{2dKL},n\}+1)$ 的两倍。 然而，由于搜索这种大小的素数在计算上可能很困难，因此我们删除了 $p^{\prime }$ 是素数的要求。 相应地，${𝔽}_{p^{\prime }}$不一定是有限域。 然后，客户端$l$、$l\in [L],$将发送$S_i^{(l)}=({\sum }_{j:q_j^{(l)}\ne 0}{q}_j^{(l)}\cdot j^{i-1}+z_i^{(l)})\text{mod}{p}^{\prime }$到服务器$i\in [2KL]$，而不是发送$S_i^{(l)}=({\sum }_{j:q_j^{(l)}\ne 0}{q}_j^{(l)}\cdot j^{i-1}+z_i^{(l)})\text{mod}p$，其中随机密钥 $z_i^{(l)}$ 独立且均匀地分布在 $\{0,\mathrm{\dots },p^{\prime }-1\}$ 上并对服务器隐藏。 服务器获取到$S_i$、$i\in [2KL]$后，由于计算$S_{i}mod{p}^{\prime }$时不会发生溢出，因此可以继续对实数域进行运算。 我们注意到，虽然 $p^{\prime }$ 是指数级的大数据，但 $S_i^{(l)}$ 和 $S_i$ 、 $l\in [L]$ 和 $i\in [2KL]$ 的计算仍然是可控的，并且是通过使用 $O(KL)$ 浮点数计算和存储 $S_i^{(l)}$ 和 $S_i$ 来实现的，而不是使用单个浮点数计算和存储 $S_i^{(l)}$ 。 请注意，$j^i$ 可以使用 $O(i)$ 浮点数计算，其复杂度几乎与 $i$ 成线性关系（即对于某个常数 $c$，$O(i{\log }^{c}i)$）。

我们现在在服务器上提出一种低复杂度的安全聚合算法。 重建$S_i$后，我们有$S_i={\sum }_{j:q_j\ne 0}{q}_j\cdot j^{i-1}$。 服务器切换到真实领域的计算。 首先，它使用Berlekamp-Massey算法求多项式$g(x)={\prod }_{j:q_j\ne 0}(1-j\cdot x)$（该算法最初是为有限域上的BCH码解码而提出的，但它适用于任意域）。 令 $m$ 为 $g(x)$ 的次数。 然后$h(x)=x^{m}g(1/x)={\prod }_{j:q_j\ne 0}(x-j)$。 目标是在实数域上对 $h(x)$ 进行因式分解，其中已知根是 $[B^d]$ 中的整数，并且每个根的重数为 1。

如果$h(x)$的次数是奇数，则和$h(B^d)>0$。 然后我们可以使用二分搜索来找到 $h(x)$ 的根，这需要对 $h(x)$ 进行 $O(\log B^d)$ 多项式计算，从而进行 $O(MK\log B^d)$ 乘法和大小最多为 $\log p^{\prime }$ 的整数的加法运算。 找到一个根$j$后，我们可以将$h(x)$除以$x-j$并开始下一次寻根迭代。

如果$h(x)$的次数是偶数，那么$h^{\prime }(x)$的次数是奇数，并且$h^{\prime }(x)$的根不同并且局限于$[B^d]$。 我们使用二分搜索来查找 $h^{\prime }(x)$ 的根 $j^{\prime }$。 如果，那么我们对$[0,j^{\prime }]=\{0,1,\mathrm{\dots },j^{\prime }\}$使用二分搜索来找到$h(x)$的根，并在$h(x)$ 如果$h(j^{\prime })>0$，则$h^{\prime }(j^{\prime }-1)>0$和。 我们使用二分搜索在$[j^{\prime }-1]$中找到$h^{\prime }(x)$的另一个根。 请注意，对于满足 $h(j_1^{\prime })>0$ 和 $h(j_2^{\prime })>0$ 的 $h^{\prime }(x)$ 的每两个根 $j_1^{\prime }$ 和 $j_2^{\prime }$ ()，我们总能在 $[j_1^{\prime }+1,j_2^{\prime }-1]$ 中找到 $h^{\prime }(x)$ 的另一个根 $j_3^{\prime }$ 。 我们不断迭代搜索每两个这样的根$j_1^{\prime },j_2^{\prime }$，直到找到$h^{\prime }(x)$的根$r_1,\mathrm{\dots },r_{2R+1}$列表，使得为奇数$[2R+1]$ 中的 $i$ 和 $h(r_i)>0$ 甚至 $i\in [2R+1]$。 然后我们可以对集合$[0,r_1],[r_1,r_2],\mathrm{\dots },[r_{2R},r_{2R+1}],[r_{2R+1},B^d]$进行二分搜索，找到$h(x)$的$2R+2$根。 请注意，在迭代期间，我们需要 $2R+1$ 二分搜索迭代来查找 $h^{\prime }(x)$ 的根 $r_1,\mathrm{\dots },r_{2R+1}$ 和 $2R+2$ 二分搜索迭代来查找 $2R+2$ 是 $h(x)$ 的根。

因此，总计算复杂度最多为 $O(MK\log B^d)$ 次多项式求值，次数最多为 $O(MK)$ 且最多为 $O(MK)$ 次多项式除法，这最多需要 $O({(MK)}^2\log B^d)$ 大小最多为 $\log p^{\prime }$ 的整数的乘法和加法。 对于某些常量 ，这会导致总体复杂度为 $O({(MK)}^3{d}^2{\log }^c(MK)\log B),$。

附录L 分配矩阵$C$和$C_s$之间的差异

解释这两个分配矩阵之间差异的一个示例如下。 假设集中式和 FC 设置的全局数据集和质心集相同，即

$$X=\left[\begin{array}{c}{X}^{(1)}\\ \mathrm{\cdots }\\ X^{(L)}\end{array}\right],𝐂={𝐂}_s=\{c_1,\mathrm{\dots },c_K\}.$$

假设对于 $x_1$（即 $X$ 的第一行），我们有

那么，$C$的第一行等于$c_1$。 但是，如果$x_1$驻留在客户端$l$的内存上并且属于本地集群${𝒞}_i^{(l)}$，并且记录的本地质心$c_i^{(l)}$满足

那么$C_s$的第一行是$c_2$，即使是。 这里 $C_s$ 是客户端 $l$ 上矩阵 $C_s^{(l)}$ 的行串联。此示例显示赋值矩阵 $C$ 和 $C_s$ 不同，这也意味着 ${\varphi }_f$ 和 ${\varphi }_c$ 不同。

附录 M实验设置和其他结果

M.1数据集

在下文中，我们描述了数值实验中使用的数据集。 请注意，我们对所有数据集进行了预处理，使得数据矩阵中每个元素的绝对值小于$1$。 每个数据集都有一个表示最佳簇数量的内在参数$K$，这些参数在集中式$K$-means++算法中用于计算最佳目标值的近似值。 我们在后续推导中使用${\varphi }_c^{*}(X)$来表示$K$-means++算法返回的目标值。 除了$K$之外，我们还为每个客户端数据设置一个附加参数$K^{\prime }\sim \sqrt{K}$，以便客户端级别的真实集群数量不大于$K^{\prime }$。 这个非 i.i.d. Dennis 等人 (2021) 中讨论了跨客户端的数据分发。 对于小型数据集（例如 TCGA、TMI），我们将客户端数量 $L$ 视为 $10$，并为所有其他数据集设置 $L=100$。

Celltype [$n=12009,d=10,K=4$] (Han 等人, 2018; Gardner 等人, 2014b) 包含属于四种细胞类型混合物的单细胞 RNA 序列：成纤维细胞、小胶质细胞、内皮细胞和间充质干细胞。 从小鼠细胞图谱中检索的数据由 $12009$ 数据点组成，每个样本具有 $10$ 特征维度，使用 Primary 从原始维度 $23,433$ 减少成分分析（PCA）。 四个簇的大小 是$6506,2328,2201,974$。

姿势 [$n=74975,d=15,K=5$] (Gardner 等人, 2014b; a) 包括通过动作捕捉系统和$12$不同的用户执行五种手势——握拳、用一根手指指向、用两根手指指向、停止（手平放）和抓住（手指卷曲）。 为了建立旋转和平移不变的局部坐标系，利用了手套背面的刚性未标记图案。 数据集中共有$74975$个样本，数据维度为$15$。 给定簇的大小为$19772,17340,15141,12225,10497$。

Covtype [$n=15120,d=52,K=7$] （Blackard & Dean，1999） 包含从美国林务局 (USFS) 获得的七种森林覆盖类型的数字空间数据，以及美国地质调查局 (USGS)。 有 $52$ 制图变量，包括坡度、高程和坡向。 数据集有 $15120$ 个样本。 七个簇的大小为$3742,3105,2873,2307,1482,886,725$。

高斯 [$n=30000,d=10,K=10$]包含十个簇，每个簇都是根据$10$变量高斯分布生成的，该分布均匀地集中在单位超立方体中随机选择的位置。 从每个簇中提取 $3000$ 个样本，总共 $30000$ 个样本。 每个高斯簇都是球形的，方差为 $0.5$。

FEMNIST [$n=36725,d=784,K=62$] (Caldas 等人, 2018) 是一个流行的 FL 基准数据集，包含数字 (0-9) 和字母的图像来自超过 $3500$ 个用户的英文字母（大写和小写）。 它的数据集本质上是从扩展 MNIST 存储库（Cohen 等人，2017） 构建的，根据数字/字符的作者对其进行分区。 我们提取与$100$个不同客户端相对应的数据，每个客户端至少贡献了$350$个数据点。 每个图像都有尺寸$784$。 最大簇的大小为$1234$，最小簇的大小为$282$。

TCGA [$n=1904,d=57,K=4$] 甲基化由癌症基因组图谱 (TCGA) 中 $1904$ 样本的甲基化微阵列数据组成 (Hutter & Zenklusen, 2018) 对应四种不同的癌症类型：低级别胶质瘤（LGG）、肺腺癌（LUAD）、肺鳞状细胞癌（LUSC）和胃腺癌（STAD）。 The observed features correspond to a subset of $\beta$ values, representing the coverage of the methylated sites, at $57$ locations on the promoters of $11$ different genes (ATM, BRCA1, CASP8, CDH1, IGF2, KRAS, MGMT, MLH1, PTEN, SFRP5 and TP53). 选择该基因子集是因为其与癌发生的相关性。 四个簇的大小为$735,503,390,276$。

TMI [$n=1126,d=984,K=4$] 包含来自人类肠道微生物组的样本。 我们从 NIH 人类肠道微生物组（Peterson 等人，2009）中检索了$1126$人类肠道微生物组样本。 每个数据点的维度为$983$，捕获样本中已识别细菌种类或属的频率（浓度）。 该数据集可以根据性别和年龄大致分为四类。 四个簇的大小为$934,125,46,21$。

M.2基线设置。

我们使用 K-FED 和 DC-KM 的公开实现作为我们的基准方法。 对于DC-KM，我们将计算树的高度设置为$2$，并观察叶子代表客户端。 由于K-FED原本不支持数据去除，计算复杂度较高，其聚类性能无法与DC-KM相比（见表1）。 1)，因此我们仅比较 MUFC 与 DC-KM 的忘却性能。 在训练期间，所有方法的集群参数 $K$ 在客户端和服务器中设置为相同，无论数据如何在客户端之间分布。 除 FEMNIST 之外的所有数据集上的实验均重复 $5$ 次以获得均值和标准差，并且由于训练复杂度较高，FEMNIST 上的实验重复 $3$ 次。 请注意，我们使用了与 Ginart 等人 (2019) 中相同数量的重复实验。

M.3 为 MUFC 启用完整客户端训练

请注意，K-FED 和 DC-KM 都允许客户端执行完整的 $K$-means++ 集群，以提高服务器上的集群性能。 因此，为 MUFC 启用完整的客户端训练以及比较完整数据集上的集群性能是合理的。 尽管在这种情况下，我们需要根据每个删除请求重新训练受影响的客户端和 MUFC 服务器，从而导致与 DC-KM 类似的遗忘复杂性，但 MUFC 的集群性能始终优于其他两种基线方法（参见选项卡） 。 2)。 这是因为我们利用了有关客户端质心的聚合权重的信息。

表2： 不同 FC 算法的聚类性能与集中式 $K$-means++ 聚类相比。

		TMI	Celltype	Gaussian	TCGA	Postures	FEMNIST	Covtype
Loss ratio	MUFC	$\mathbf{1.05}\pm \mathbf{0.01}$	$\mathbf{1.03}\pm \mathbf{0.00}$	$\mathbf{1.02}\pm \mathbf{0.00}$	$\mathbf{1.02}\pm \mathbf{0.01}$	$\mathbf{1.02}\pm \mathbf{0.00}$	$\mathbf{1.12}\pm \mathbf{0.00}$	$\mathbf{1.02}\pm \mathbf{0.00}$
	K-FED	$1.84\pm 0.07$	$1.72\pm 0.24$	$1.25\pm 0.01$	$1.56\pm 0.11$	$1.13\pm 0.01$	$1.21\pm 0.00$	$1.60\pm 0.01$
	DC-KM	$1.54\pm 0.13$	$1.46\pm 0.01$	$\mathbf{1.02}\pm \mathbf{0.00}$	$1.15\pm 0.02$	$1.03\pm 0.00$	$1.18\pm 0.00$	$1.03\pm 0.02$

M.4损失率和遗忘效率

在图4中，我们绘制了每次删除请求后损失率变化的结果以及当删除请求是对抗性时的累积删除时间。 结论与6节的结果一致。

图4： 阴影区域代表所有子图不同轨迹结果的标准偏差。 (a)-(d) 每轮遗忘过程后损失率${\varphi }_f(𝒳;{𝐂}_s)/{\varphi }_c^{*}(X)$的变化。 (e)-(h) 对抗性移除的累积移除时间。

M.5批量移除

在图5中，我们绘制了与在一个删除请求（批量删除）中删除多个点有关的结果。 由于在这种情况下，受影响的客户端更有可能为每个请求重新运行 $K$-means++ 初始化，因此预计我们算法的性能（即累积删除时间）将在以下情况下表现得更类似于重新训练：与图 3 中我们仅在一个删除请求中删除一个点的情况相比，我们在一个删除请求中删除了更多点。

图5： 阴影区域代表所有子图不同轨迹结果的标准偏差。 (a)、(c) 在一批删除请求中删除 $10$ 点。 (b)、(d) 在一批删除请求中删除 $30$ 点。