异构制胜：一次性联合集群

摘要

在这项工作中，我们探讨了无监督联合学习 (FL) 的独特挑战和机遇。 我们开发并分析了一种一次性联合聚类方案，k-FED，基于广泛使用的劳埃德$k$-均值聚类方法。 与许多监督问题相反，我们表明联邦网络中的统计异质性问题实际上可以有利于我们的分析。 我们在中心分离假设下分析k-FED，并将其与集中式对应设备的最著名要求进行比较。 我们的分析表明，在每个设备的集群数量 $(k^{\prime })$ 小于网络上的集群总数 $k$、$(k^{\prime }\le \sqrt{k})$ 的异构机制中，我们可以利用异质性来发挥我们的优势——显着削弱 k-FED 的簇分离要求。 从实用的角度来看，k-FED还具有许多理想的特性：它只需要一轮通信，可以异步运行，并且可以处理部分参与或节点/网络故障。 我们通过常见 FL 基准测试的实验来激发我们的分析，并通过个性化 FL 和设备采样中的用例强调一次性聚类的实用性。

1简介

联邦学习 (FL) 旨在在手机或可穿戴设备等大型异构设备网络上执行机器学习（McMahan 等人，2017）。 虽然此类环境中的监督学习问题受到了极大关注，但无监督联邦学习问题相对尚未得到探索（Kairouz 等人，2019）。 在这项工作中，我们证明无监督学习为 FL 提供了独特的机会，特别是对于驻留在联邦网络中的数据进行聚类的任务。

聚类是许多学习任务中至关重要的第一步。 就联邦学习而言，聚类已在客户选择（Cho等人，2020）、个性化（Gho等人，2020）和探索性数据分析中找到了应用。 虽然许多工作探索了分布式集群技术（第 2 节），但大多数工作没有考虑联邦学习的独特挑战，例如统计异质性、系统异质性和严格的通信约束（李等人, 2020a). 这些挑战可能会使分析变得复杂，降低效率，并导致落后者和设备故障等实际问题。 在这项工作中，我们研究了数据在网络上分布不同（即异构）并且设备可以突然加入和离开网络的环境中的通信高效分布式集群。 对于此类设置，我们基于经典的 Lloyd 启发式 （Lloyd，1982） 开发并分析了一次性聚类方案 k-FED > 用于聚类。

我们提出的方法k-FED只需要与中央服务器进行一轮通信。 每个由 $z$ 索引的设备解决本地 $k^{(z)}$ 均值问题，然后通过大小为 $O(d{k}^{(z)})$ 的消息与其本地集群均值进行通信。 正如我们在第 3 节中所示，这允许设备故障，只需要网络中有足够的可用设备，以便数据中存在 $k$ 目标集群。 此外，可以通过中央服务器上的简单重新计算来对以前不可用的设备中的点进行聚类。

除了k-FED的实际好处之外，我们的工作在严格证明联邦学习存在统计异质性可能带来的问题设置方面是独一无二的。 特别是在监督学习中，许多工作都强调了统计异质性的有害影响，观察到异质性会导致联邦优化方法收敛性差（McMahan等人，2017；Li等人，2020b），导致不公平的模型（Mohri等人，2019），或需要新颖的个性化形式（Smith等人，2017；Mansour等人，2020）。 与这些工作相反，我们表明，对于本文考虑的异质性的具体概念（定义3.2中提供并由聚类的应用激发），异质性实际上可以为我们的方法带来可衡量的好处。

更具体地说，与聚类中的许多工作类似(Kumar & Kannan (2010)；Awasthi & Sheffet (2012) 以及其中的参考文献），我们分析 k-FED 在中心分离假设下；也就是说，我们假设聚类的平均值是很好分离的。 我们还考虑了异质性的具体概念：给定一个具有 $k$ 集群的目标集群，我们希望从数据中恢复，我们假设每个设备仅包含来自这些目标的 $k^{\prime }\le \sqrt{k}$ 的数据集群。 例如，对于由 $k$ 良好分离的高斯分布的混合生成的聚类数据，我们假设每个设备都包含来自 $k^{\prime }\le \sqrt{k}$ 分量高斯分布的数据。 在这种制度下，我们表明我们的分离要求与集中式对应机构的要求类似。 此外，集中式设置要求所有集群中心对都满足 $\mathrm{\Omega }(\sqrt{k})$ 中心分离要求，而联合式方法可以处理大部分集群中心对只满足较弱的 $\mathrm{\Omega }(k^{\frac{1}{4}})$ 分离要求的情况。 这是我们知道的第一个结果，它分析了联邦集群背景下异构性的好处。

贡献。 我们提出并分析了一种用于联邦集群的一次性通信方案。 我们提出的方法 k-FED 解决了联邦环境中常见的实际问题，例如高通信成本、落后者和设备故障。 理论上，我们表明 k-FED 的表现与集中式集群类似，其中每个设备仅具有来自最多 $\sqrt{k}$ 个集群的数据，这些集群具有相似的 $\mathrm{\Omega }(\sqrt{k})$中心分离要求。 此外，与集中式设置相反，我们表明，异构网络中的大量簇对只需要 $\mathrm{\Omega }(k^{\frac{1}{4}})$ 较弱的分离假设，因此与集中式设置相比，可以在此设置中解决更广泛的问题。集中式集群。 我们通过常见 FL 基准的实验展示了我们的方法，并探索了 k-FED 在个性化联合学习和设备采样问题中的适用性。 我们的工作强调，异构性可以为联邦学习中的一部分问题带来明显的好处。

2 背景及相关工作

集中式集群。 聚类是最广泛使用的无监督学习任务之一，并且在集中式和分布式设置中都得到了广泛的研究。 尽管存在多种聚类方法，但劳埃德启发式（Lloyd，1982）仍然很受欢迎，部分原因在于其简单性。 在劳埃德的方法中，我们从一组初始的 $k$ 中心开始。 然后，我们将每个点分配给它最近的中心，并将这些中心重新分配为分配给它的所有点的平均值，继续这个过程直到终止。 虽然很容易证明该方法终止，但众所周知，该过程可能需要超多项式时间才能收敛（Arthur & Vassivitskii，2006）。 然而，在适当的假设和仔细选择初始中心的情况下，可以证明它可以在多项式时间内收敛（Arthur & Vassilvitskii, 2006; Ostrovsky 等人, 2013; Kumar & Kannan, 2010; Awasthi & Sheffet, 2012） 。

我们提出的方法k-FED（第3.2节）是这些经典技术的简单、通信高效的分布式变体。 k-FED 运行 Lloyd 方法的变体，用于 $k$ - 表示在每个设备上进行本地集群，然后执行一轮通信以聚合和分配集群。 我们的工作建立在对 Kumar & Kannan (2010) 开发的 Lloyd 算法变体的分析基础上，后来在 Awasthi & Sheffet (2012) 中针对数据聚类问题进行了改进来自混合分布和其他相关结果（例如，McSherry，2001；Ostrovsky 等人，2013）。 这些工作开发了一个确定性框架，不对数据进行生成假设。 我们的分析遵循这个框架，不对数据做出任何生成假设。

并行和分布式集群。 许多工作探索了集中式集群技术的并行或分布式实现（Dhillon & Modha, 2002; Tasoulis & Vrahatis, 2004; Datta 等人, 2005; Bahmani 等人, 2012; Xu 等人, 1999） 。 与本文探讨的一次性通信方案不同，这些方法通常是 Lloyd 启发式或 DBSCAN （Ester 等人，1996） 等方法的直接并行实现，并且需要多轮通信。 另一项工作考虑了仅需要一轮或两轮通信的通信高效的分布式集群变体（例如，Kargupta 等人，2001；Januzaj 等人，2004；Feldman 等人，2012；Balcan 等人，2013 ; Bateni 等人, 2014; Bachem 等人, 2018). 这些工作大多是经验性的，因为对分布式方案的近似质量没有可证明的保证； Balcan 等人的作品 (2013)； Bateni 等人 (2014); Bachem 等人 (2018) 的不同之处在于为集群提供了通信高效的分布式核心集方法，以及可证明的近似保证。 然而，这些工作并没有探索联邦环境或异构性的潜在好处。

联合集群。 有几项工作探索了监督 FL 背景下的聚类，作为更好地建模非 IID 数据的方法（Smith 等人，2017；Ghosh 等人，2019、2020；Sattler 等人，2020）。 这些工作与我们自己的工作不同，具体是在设备方面进行聚类，专注于下游监督学习任务，并使用迭代（Smith等人，2017；Ghosh等人，2020；Sattler等人，2020） 或集中式(Ghosh 等人, 2019) 聚类方案。 虽然不是我们工作的主要重点，但在第 4 节中，我们通过展示 k-FED 如何展示一次性聚类的适用性用作提供个性化联邦学习的简单预处理步骤，相对于 Ghosh 等人 (2020) 中提出的最近的集群 FL 迭代方法，实现类似或更好的性能。

最近，Wang & Chang (2020) 出于无监督学习的目的，探索了一种基于分布式矩阵分解的聚类方法。 然而，虽然作者考虑了统计异质性对其收敛保证的影响，但重点并不是一次性聚类或在分析中显示异质性的明显好处。

3 k-FED：基础知识和主要结果

在本节中，我们首先讨论与 Lloyd 类型方法相关的聚类的一些基本知识和现有结果。 在 3.1 节中，我们提出了 Awasthi & Sheffet (2012) 用于集中式集群的确定性框架，我们在此基础上进行构建。 我们提出我们的方法k-FED并在3.2节中陈述我们的理论结果。 我们在附录A中提供了详细的证明。

3.1 集中式$k$-表示

在标准（集中）$k$-means问题中，我们给出一个矩阵$A\in {ℝ}^{n\times d}$，其中每行$A_i$是${ℝ}^d$中的一个数据点>。 我们还给出了一个固定的正整数$k\le n$，我们的目标是将数据点划分为$k$个不相交的分区，$𝒯=(T_1,\mathrm{\dots },T_k),$，从而最小化$k$-表示成本：

$$\varphi (𝒯)=\sum _{j=1}^k\sum _{i\in T_j}{\parallel A_i-\mu (T_j)\parallel }_2^2.$$ (1)

这里我们使用$\mu (S)$作为运算符来表示$S$索引的点的平均值，即$\mu (S)=\frac{1}{|S|}{\sum }_{i\in S}{A}_i$。 为了简化表示法，当 $T_r$ 明确时，我们将其简化为 ${\mu }_r:=\mu (T_r)$。

算法1 本地 $k^{(z)}$ - 表示 （Awasthi & Sheffet，2012）

1: Input: On device indexed by $z$, the matrix of data points $A^{(z)}$, integer $k^{(z)}$;

2: Project $A^{(z)}$ onto the subspace spanned by the top $k^{(z)}$ singular vectors to get ${\widehat{A}}^{(z)}$. Run any standard $10$-approximation algorithm on the projected data and estimate $k^{(z)}$ centers (${\nu }_1,{\nu }_2,\mathrm{\dots },{\nu }_{k^{(z)}}$).

3: Set

$$S_r\leftarrow \{i:{\parallel {\widehat{A}}_i^{(z)}-{\nu }_r\parallel }_2\le \frac{1}{3}{\parallel {\widehat{A}}_i^{(z)}-{\nu }_s\parallel }_2,\text{for every}s\}$$

and ${\theta }_r^{(z)}\leftarrow \mu (S_r)$

4: Run Lloyd steps until convergence

$$U_r^{(z)}\leftarrow \{i:{\parallel A_i^{(z)}-{\theta }_r^{(z)}\parallel }_2\le {\parallel A_i^{(z)}-{\theta }_s^{(z)}\parallel }_2,\forall s\}$$

and ${\theta }_r^{(z)}\leftarrow \mu (U_r^{(z)})$.

5: Return: Cluster assignments $(U_1^{(z)},U_2^{(z)},\mathrm{\dots },U_{k^{(z)}}^{(z)})$ and their means ${\mathrm{\Theta }}^{(z)}=({\theta }_1^{(z)},\mathrm{\dots },{\theta }_{k^{(z)}})$.

虽然此处所述的 k 均值问题没有为数据点 $A_i$ 指定任何生成模型，但要考虑的一个流行设置是从 $k$ 的混合中采样数据时 - $d$ 维度 ($k\ll d$) 中的分布。 例如，我们可以想象数据点是从 $k$ 高斯分布的混合中采样的。 该生成模型还引入了目标聚类、$𝒯=(T_1,\mathrm{\dots },T_k)$的概念，其中集合$T_i$包含由$i$生成的所有点 - th 分量分布。 许多与分布相关的结果因聚类分布问题而闻名（参见 Kumar & Kannan (2010))。 一般来说，它们可以表述为：如果分布的均值相差 $\text{poly}(k)$ 个标准差，那么我们可以在多项式时间内对数据进行聚类。 Kumar & Kannan (2010) 引入了一个包含许多已知结果的确定性（独立于分布）框架。 这项工作后来被 Awasthi & Sheffet (2012) 简化和改进。 在说明我们使用的符号之后，我们在这里说明该框架的主要结果。 我们强调，在我们的分析中，我们不对数据的生成方式做出任何假设；所有相关数量仅取决于所提供的数据。

符号。 我们现在介绍将在整篇论文中使用的几个定义和符号。 让 $\parallel A\parallel$ 表示矩阵 $A$ 的谱范数，定义为 $\parallel A\parallel ={\max }_{u:{\parallel u\parallel }_2=1}{\parallel Au\parallel }_2$，并让 ${\parallel A_i\parallel }_2$ 表示 ${\mathrm{\ell }}_2$ 向量$A_i$的范数。 为了保持一致性，我们使用 $i$ 和 $j$ 对 $A$ 的各个行进行索引。 此外，当目标聚类$T_1,\mathrm{\dots },T_k$固定时，我们用$r,s$索引聚类，例如，$A_r$是由$T_r$索引的点矩阵>。 为了符号方便，我们让 $c(A_i)$ 表示数据点 $A_i$ 的簇索引，例如 $A_i\in T_{c(A_i)}$。 对于某些点集 $M$ 和另一个点 $x$，让 $d_M(x)$ 表示 $x$ 到集合 $M$，定义为$d_M(x)={\min }_{y\in M}{\parallel x-y\parallel }_2$。 最后，令 $C$ 为 $n\times d$ 矩阵，每行为 $C_i={\mu }_{c(A_i)}$。 对于具有 $n_r=|T_r|$ 的簇 $T_r$，我们定义

$${\tilde{\mathrm{\Delta }}}_r:=\sqrt{k}\frac{\parallel A-C\parallel }{\sqrt{n_r}}.$$ (2)

这里的量$\parallel A-C\parallel /\sqrt{n_r}$可以被认为是标准差的确定性类似物；它测量沿任意方向的最大平均方差。 因此，我们将使用 $({\tilde{\mathrm{\Delta }}}_r+{\tilde{\mathrm{\Delta }}}_s)$，而不是根据标准差来推理两个簇 $T_r$ 和 $T_s$ 之间的分离。 特别是，如果对于足够大的常数$c$，我们说两个簇$T_r$和$T_s$是很好地分离，它们的均值满足:

${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge c({\tilde{\mathrm{\Delta }}}_r+{\tilde{\mathrm{\Delta }}}_s).$ (3)

同样，我们可以将其解释为如果两个簇的均值相差 $c$-标准差，则它们可以很好地分离。 使用 (3) 中的中心分离假设，Awasthi & Sheffet (2012) 表明，对于满足分离假设的目标聚类 $T_1,T_2,\mathrm{\dots },T_k$，变体当应用于集中式聚类问题时，算法 1 中提出的劳埃德算法可以正确地对除一小部分数据点之外的所有数据点进行聚类。 我们在引理1中正式陈述了他们的结果，但在此之前我们定义了一个邻近条件，它将用于精确地表征错误分类的点。

Definition 3.1。

对于某些$i\in T_s$，如果对于每个$r\ne s$,$A_i$在直线上的投影，则称点$A_i$满足邻近条件连接${\mu }_r$和${\mu }_s$，记为${\overline{A}}_i$满足

$${\parallel {\overline{A}}_i-{\mu }_r\parallel }_2-{\parallel {\overline{A}}_i-{\mu }_s\parallel }_2\ge \left(\frac{1}{\sqrt{n_r}}+\frac{1}{\sqrt{n_s}}\right)\parallel A-C\parallel .$$

因此，如果 $i\in T_s$ 的点 $A_i$ 在连接 ${\mu }_r$ 和 ${\mu }_s$ 的直线上的投影更接近 ${\mu }_s$由$\parallel A-C\parallel (\frac{1}{\sqrt{n_r}}+\frac{1}{\sqrt{n_s}})$。 我们将不满足邻近条件的点称为“坏点”。 现在，我们在以下引理中陈述 Awasthi & Sheffet (2012) 的主要结果。

Lemma 1 （Awasthi-Sheffet，2011）。

令 $𝒯=(T_1,\mathrm{\dots },T_k)$ 为目标聚类。 假设每对簇 $T_r$ 和 $T_s$ 都很好地分开。 然后，在算法 1 的步骤 2 之后，对于每个 $r$，它都保持 ${\parallel \mu (S_r)-{\mu }_r\parallel }_2\le \frac{25}{c}\frac{1}{\sqrt{n_r}}\parallel A-C\parallel$。 此外，如果坏点的数量为 $ϵn$，则 (a) 聚类 $\{U_1,U_2,\mathrm{\dots },U_k\}$ 错误分类不超过 $(ϵ+O(1)c^{-4})n$ 个点，并且 (b) . 最后，如果 $ϵ=0$ 则所有点都被正确分配。

当我们说错误分类时，我们指的是关于 $𝒯$ 以及标签的排列。 引理 1 告诉我们聚类均值 $\mu (S_r)$ 距离目标聚类均值 ${\mu }_r$ 不是很远。 请注意，此声明中没有与分布相关的术语；所有相关量均根据数据矩阵$A$和$𝒯$定义。

3.2 k-FED：方法和主要结果

现在，我们将注意力转向联合网络中的数据集群。 在我们的设置中，我们假设网络中的所有设备都可以与中央服务器通信。 我们的聚类方法k-FED（在算法2中描述）可以被认为是分两个阶段工作的。 在第一阶段，每个设备解决局部聚类子问题并计算该子问题的聚类均值。 在第二阶段，中央服务器累积并聚合结果以计算最终的聚类。

符号。 令 $A$ 为网络中所有数据点的 $n\times d$ 数据矩阵。 我们用 $z\in [Z]$ 对各个设备进行索引，因此，我们用 $A^{(z)}\in {ℝ}^{n^{(z)}\times d}$ 表示任何特定设备的数据矩阵，其中 $n^{(z)}$ 是设备上数据点的数量。设备。 让$n_{\min }={\min }_z{n}^{(z)}$。 请注意，$A^{(z)}$ 是$A$ 行的某些子集。 令$𝒯=(T_1,\mathrm{\dots },T_k)$为所有数据的聚类，称为目标聚类。 对于固定的 $𝒯$，让 ${𝒯}^{(z)}=(T_1^{(z)},T_2^{(z)},\mathrm{\dots },T_k^{(z)})$ 是驻留在设备 $z$ 上的目标集群的子集。 请注意，某些 $T_r^{(z)}$ 可能为空。 令 $k^{(z)}$ 为设备 $z$ 上非空子集的数量，并令 $k^{\prime }={\max }_z{k}^{(z)}$ 。 我们的异质性概念是根据 $k^{\prime }$ 的值正式定义的，如下所述。

Definition 3.2 (聚类的异质性)。

在集群的背景下，如果$k^{\prime }\le \sqrt{k}$，我们就说具有足够数据的联邦网络是异构的。 $k^{\prime }$和$\sqrt{k}$之间的比率越低，网络中存在的异质性就越大。

直观地，异质性的定义表明，与来自 $k$ 总簇的数据在网络上以 IID 方式分区相比，数据以非 IID 方式分区，这样只有数据每个设备上都存在少量集群（最多 $k^{\prime }$)。 在具有大量集群的异构联合网络中，这种非 IID 分区是合理的，因为每个设备上的数据分布可能不同，并且不可能在网络上主动重新分布数据。 例如，考虑根据应用程序上的交互数据来识别移动电话用户的兴趣。 这里的交互数据是由用户在其特定设备上生成的，并且将反映个人的品味。 虽然整个网络上的“品味”（集群）总数可能相当大，但典型的用户只会对其中的一小部分感兴趣。 考虑到这个定义，我们接下来描述我们的一次性聚类方法，k-FED，并在异构机制中对其进行分析。

方法说明。

与集中情况类似（第 3.1 节），令 $C^{(z)}$ 为局部聚类均值的 $n^{(z)}\times d$ 矩阵，即 ${𝒯}^{(z)}$ 。 考虑某个设备上集群$T_r$的非空susbset$T_r^{(z)}$，并让$n_r^{(z)}=|T_r^{(z)}|$。 我们假设有一个常数$m_0>1$，这样对于所有$r$来说$n_r^{(z)}\ge \frac{1}{m_0}{n}_r$。我们将使用这个数量来确保各个设备有“足够”的积分。 让，

${\mathrm{\Delta }}_r=k^{\prime }{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r}}},\text{and}\lambda =\sqrt{k^{\prime }}\left({\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_{\min }}}}\right).$ (4)

在k-FED（算法-2）的第一步中，每个（可用）设备$z\in [Z]$在本地运行算法-1并求解本地聚类本地数据集 $A^{(z)}$ 和参数 $k^{(z)}$ 存在问题。 我们假设 $k^{(z)}$ 是已知的。 此阶段输出设备集群中心${\mathrm{\Theta }}^{(z)}=({\theta }_1^{(z)},\mathrm{\dots },{\theta }_{k^{(z)}}^{(z)})$和每个设备$z$的集群分配$U_1^{(z)},\mathrm{\dots },U_{k^{(z)}}^{(z)}$。 在此阶段，请注意，即使每个设备都已将自己的点分类为簇，但我们还没有跨设备的点的聚类。 中央服务器尝试通过聚合设备集群中心并将它们分成 $k$ 集 ${\tau }_1,\mathrm{\dots },{\tau }_k$ 来创建此集群。 这些集合引起网络上数据的聚类，如下定义：

Definition 3.3 (k-FED诱导聚类）。

令${\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_k$为算法2返回的设备中心的聚类。 定义，

$$T_r^{\prime }=\{i:A_i^{(z)}\in U_s^{(z)}\text{and}{\theta }_s^{(z)}\in {\tau }_r,z\in [Z],s\in [k^{(z)}]\}.$$

然后，${𝒯}^{\prime }=(T_1^{\prime },\mathrm{\dots },T_k^{\prime })$形成整个数据的不相交分区，称为k-FED诱导聚类。

算法2 k-FED

1: On each device $z\in [Z]$, run Algorithm-1 with local data $A^{(z)}$ and $k^{(z)}$ and obtain device cluster centers ${\mathrm{\Theta }}^{(z)}=({\theta }_1^{(z)},\mathrm{\dots },{\theta }_{k^{(z)}}^{(z)})$ at the central node.

2: Pick any $z\in [Z]$ and let $M\leftarrow {\mathrm{\Theta }}^{(z)}$.

3: repeat

4: Let $\overline{\theta }\leftarrow {\arg \max }_{z\in [Z],i\in [k]}{d}_M({\theta }_i^z)$. That is, the farthest ${\theta }_i^{(z)}$ from the set $M$.

5: $M\leftarrow M\cup \{\overline{\theta }\}$.

6: until there are $k$ points in $M$, i.e. $\left|M\right|=k$

7: Run one round of Lloyd’s heuristic to cluster points ${\theta }_i^{(z)}$, $z\in [Z],i\in [k]$ into $k$ sets/clusters, $({\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_k)$. Use points in $M$ as initial centers.

8: Return: the clustering $({\tau }_1,{\tau }_2,\mathrm{\dots },{\tau }_k)$ of the device cluster centers and the corresponding k-FED induced clustering (Definition 3.3).

为了将 k-FED 诱导的聚类 ${𝒯}^{\prime }$ 的质量与我们的目标聚类 $𝒯$ 的质量进行比较，我们需要两种不同的分离假设。 我们将它们称为active和inactive分离，并通过以下两个定义来介绍它们。

Definition 3.4 （活动/非活动簇对）。

如果存在至少一个设备同时包含来自 $T_r$ 和 $T_s$ 的数据点，则一对簇 $(T_r,T_s)$ 被称为活动对。 如果没有设备同时具有来自集群 $T_r$ 和 $T_s$ 的数据点，我们将集群对 $(T_r,T_s)$ 称为非活动对。

Definition 3.5。

对于一些足够大的常数$c$，我们说两个簇$T_r$和$T_s$满足主动分离要求，如果${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge 2c\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s)$。类似地，如果${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge 10\sqrt{m_0}({\lambda }_r+{\lambda }_s)$，我们就说它们满足非活动分离要求。

直观上，这些概念反映了对两种不同类型的簇对（活动簇对和非活动簇对）进行聚类的难度。 如果没有设备同时拥有来自 $T_r$ 和 $T_s$ （即非活动对）的数据，则各个设备必须解决的聚类子问题会更容易，因为它们从不涉及来自这两个设备的数据这些集群同时进行。 因此，非活动簇对的分离要求弱于活动簇对的分离要求。 现在我们陈述我们的主要定理，它描述了k-FED的性能。 我们在附录A中提供了详细的证明。

Theorem 3.1 （主定理）.

令 $𝒯=(T_1,T_2,\mathrm{\dots },T_k)$ 为联合网络上数据的固定目标聚类。 让 $m_0>1$ 使得 $|T_r^{(z)}|\ge \frac{1}{m_0}|T_r|$ 对于所有 $r,s$ 和所有 $z\in [Z]$ 而言。 假设每个主动簇对$T_r$和$T_s$满足主动分离要求，即

$${\parallel \mu (T_r)-\mu (T_s)\parallel }_2\ge c\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s).$$

此外，假设对于每个非活动簇对$T_r,T_s$，

$${\parallel \mu (T_r)-\mu (T_s)\parallel }_2\ge 10\sqrt{m_0}\lambda .$$

然后，在 k-FED 终止时，除了 $O(\frac{1}{c^2})n$ 点之外的所有点都被正确分类。 此外，如果对于每个设备$z$，数据点$A^{(z)}$满足其局部问题的邻近条件（定义3.1)，则所有点都被正确分类。

和之前一样，通过分类，我们的意思是 k-FED 和 $𝒯$ 产生的聚类 ${𝒯}^{\prime }$ 与除 $O(\frac{1}{c^2})n$ 点，直到 $𝒯$ 标签的排列。 请注意，当$k^{\prime }\approx k$时，我们的主动分离要求比集中式集群$(\mathrm{\Omega }(k)$与$\mathrm{\Omega }(\sqrt{k}))$中的要求更严格。 此外，正如人们所预料的那样，随着每个设备上每个集群的点数减少，本地集群变得更加困难。 我们对 $\sqrt{m_0}$ 的不利依赖凸显了这一点。

然而，与每个设备通常具有数据的随机子集的通用分布式学习框架相比，驻留在联邦网络中的设备上的数据通常是本地生成的，因此设备之间的数据分区是不相同分布的。 具体地，在实践中，驻留在设备上的目标集群的子集的数量可能远小于集群的总数。 因此，正如定义 3.2 中所述，我们研究 $k^{\prime }\le \sqrt{k}$ 的情况。 观察到，在这种设置中，我们的主动分离要求减少为集中式 $k$ 均值问题（带有额外的 $\sqrt{m_0}$ 惩罚），而我们的非主动分离要求减弱为 $k^{1/4}$. 我们在推论 1.1 中正式声明了这一点。

Corollary 1.1。

假设$k^{\prime }\le \sqrt{k}$，一个主动簇对$(T_r,T_s)$满足主动分离要求，如果

${\parallel {\mu }_r-{\mu }_s\parallel }_2$ $\ge c\sqrt{m_{0}k}\left({\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r}}}+{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_s}}}\right)$

$=c\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s).$

类似地，如果满足非活动簇对 $(T_r,T_s)$ 则满足非活动分离要求

$${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge 10\sqrt{m_0}{k}^{\frac{1}{4}}\left(\frac{\parallel A-C\parallel }{\sqrt{n_r}}+\frac{\parallel A-C\parallel }{\sqrt{n_s}}\right).$$

因此，在的设置中，k-FED仅在一轮通信中恢复目标分区。 此外，非活动簇对只需要满足我们的 $\mathrm{\Omega }(k^{\frac{1}{4}})$ 分离要求，而不是所有簇对在引理 1 的集中设置中需要满足的 $\mathrm{\Omega }(\sqrt{k})$ 分离要求> 持有。 这凸显了在联合网络上运行 k-FED 的情况下存在异构性的好处。

k-FED 的实际好处。

最后，我们强调 k-FED 方法的几个实际好处：

• 一次性： k-FED 每个设备只需要一轮通信：一条传出消息发送本地聚类结果，一条传入消息接收集群身份信息的消息。

• 无全网同步： Lloyd 启发式和变体的经典并行实现（例如，Dhillon & Modha，2002），需要网络范围的同步/初始化步骤。 与这些方法不同，k-FED中的每个设备独立工作，不需要初始化/同步步骤。

• 新设备/设备故障： 假设我们已经在当前网络上进行了聚类，对于任何进入网络的新设备，无论是由于先前的故障还是作为新的参与者，都可以在不涉及网络中任何其他设备的情况下计算聚类信息。 正如我们在定理 3.2（下面）中所示，只需将新设备 $z$ 中的任何新本地集群中心 ${\theta }_i^{(z)}$ 分配给最近的设备集群均值$M$ 足够了。 中央服务器只需维护$k$集群意味着$\mu ({\tau }_1),\mathrm{\dots },\mu ({\tau }_k)$即可执行此更新。

Theorem 3.2.

k-FED的步骤2-8以$O(Z{k}^{\prime }\cdot k^2)$成对距离计算结束。 此外，在计算出步骤 6 中的集合 $M$ 后，可在 $O(k^{\prime }\cdot k)$ 距离计算中正确分配来自未知设备 $z$ 的新本地群集中心 ${\mathrm{\Theta }}^{(z)}$。

正如我们在第 4 节中所示，k-FED 的这些属性使其成为用作廉价启发式<的理想候选者。 /t4> 用于联邦网络中的聚类，无论是用于数据探索还是作为另一种算法的预处理步骤的一部分，即使在未正式满足分离要求的设置中也是如此。

4应用与实验

我们现在提出k-FED的实验评估。 我们首先将理论专门针对特殊情况，其中数据是从第 4.1 节中的 $k$ 高斯混合中提取的，以验证我们关于合成数据的理论。 在第 4.2 节中，我们在真实数据集上评估 k-FED - 提供实验证据，强调异质性的好处和 k-FED 的通信效率。 我们进一步介绍了k-FED在客户选择和个性化方面的两种应用。 每个实验的数据集详细信息可以在相应部分找到。 k-FED 的实现和实验设置详细信息可以在以下位置找到：http://github.com/metastableB/kfed/。

4.1 分离高斯混合体

我们首先将定理专门用于分离由 $k$ 高斯 $F_1,F_2,\mathrm{\dots },F_k$ 混合生成的数据的情况。 令 ${\mu }_r=\mu (F_r)$ 为混合物成分 $F_r$ 的平均值，令 $w_1,w_2,\mathrm{\dots },w_k$ 为混合权重。 最后，令 $w_{\min }={\min }_r{w}_r$ 为最小混合权重。 令 ${\sigma }_{\max }$ 为所有分量分布中沿任意方向的最大方差。 假设此数据驻留在我们的设备上，这样任何单个设备都不会拥有来自多个 组件的数据。 我们陈述以下定理（在附录 A 中证明），该定理指定了此设置满足我们的分离假设所需的条件：

Theorem 4.1.

设数据品脱总数$n=\text{poly}\left(\frac{d}{w_{\min }}\right)$。 则任何活跃簇对$r,s$以高概率满足活跃分离要求：

$${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge \frac{c\sqrt{k{m}_0}{\sigma }_{\max }}{\sqrt{w_{\min }}}\text{polylog}\left(\frac{d}{w_{\min }}\right).$$

此外，如果不活动簇对$r^{\prime },s^{\prime }$满足不活动分离要求，则概率较高

$${\parallel {\mu }_{r^{\prime }}-{\mu }_{s^{\prime }}\parallel }_2\ge \frac{c\sqrt{m_0}{k}^{\frac{1}{4}}{\sigma }_{\max }}{\sqrt{w_{\min }}}\text{polylog}\left(\frac{d}{w_{\min }}\right).$$

最后，通过这种分离，所有点都以很高的概率满足邻近条件。

具体来说，在此设置中 k-FED 以高概率准确地恢复目标聚类。 为了根据经验评估我们的理论，我们实例化了上述设置的简化实例，如下所示：

表1： 对混合高斯分布进行聚类的聚类精度。 在这里，对于所有实例，我们选择 $k^{\prime }=\sqrt{k}$。 我们可以看到，k-FED 产生的一次性聚类与目标聚类高度一致，特别是当 $k$ 相对较小时到$d$。

Parameters	Accuracy
$(d=100,k=16,m_0=5,c=100)$	$100.00\pm 0.00$
$(d=100,k=64,m_0=5,c=100)$	$98.82\pm 0.70$
$(d=300,k=64,m_0=5,c=100)$	$99.27\pm 0.73$
$(d=300,k=100,m_0=5,c=100)$	$98.40\pm 0.80$
$(d=300,k=16,m_0=5,c=100)$	$100.00\pm 0.00$

设置。 再次考虑高斯分量$F_1,\mathrm{\dots },F_k$，并定义整数集$G_i=\{p\mid (i-1)\times \sqrt{k}\le p\le i\times \sqrt{k}\}$。 因此，这些集合$G_i$可用于索引高斯分量$(F_{(i-1)\sqrt{k}},\mathrm{\dots },F_{i\sqrt{k}})$。 对于每个$G_i$，通过从$p\in G_i$的每个组件$F_p$中采样$\text{poly}(dk)$样本来构造一组数据点$D_i$ >。 因此集合$D_i$包含$\sqrt{k}\cdot \text{poly}(dk)$样本$(w_r=\frac{1}{k},\forall r)$。 选择$m_0$，并为每组数据点$D_i$，在$m_0$个设备之间分配数据，以便每个设备准确接收$\frac{1}{m_0}\cdot \text{poly}(dk)$个样本。 现在，我们在此设置上运行 k-FED，并测量 10 次运行的平均聚类质量（如表 1 所示）。 正如人们所期望的那样，k-FED 生成的聚类与目标聚类非常一致。 请注意，通过构造，具有来自同一组 $G_i$ 的数据的所有设备都包含来自同一组高斯分量的数据。 此外，具有来自不同集合$G_i$的数据的设备没有共同的高斯分量。 因此，同一集合$G_i$内的所有簇对都是活动簇对，并且存在$\sqrt{k}\left(\genfrac{}{}{0pt}{}{\sqrt{k}}{2}\right)$这样的簇对。 此外，任何对 $(r,s)$ 使得 $r\in G_i$、$s\in G_j$ $i\ne j$ 形成非活动簇对，并且有 $\left(\genfrac{}{}{0pt}{}{k}{2}\right)-\sqrt{k}\left(\genfrac{}{}{0pt}{}{\sqrt{k}}{2}\right)=O(k^2)$这样的对。 这些仅需要满足较弱的非活性分离要求。

图1： 对混合高斯分布进行聚类时，分离常数 $c$ 对聚类精度的影响。 即使对于相对较小的$c$值，对于由高斯混合生成的数据的情况，k-FED也可以恢复高度准确的聚类，同时降低运行间的方差。

请注意，虽然我们规定 $c\ge 100$ 来保持参数，但图 1 表明即使在 $c$ 小得多的设置中也可以恢复聚类。

4.2真实数据的实证评估

在本节中，我们将实证探讨k-FED以及第3节中的相关分析。 首先，我们验证了我们的理论结果，表明相对于随机 IID 分区数据的聚类，结构化（异构）分区上的聚类可以提高聚类性能。 其次，我们探讨了一次性聚类相对于通信密集型基线的影响。 最后，我们研究了一次性聚类在客户抽样和个性化联邦学习方面的实际应用。

4.2.1 k-FED的性质

异质性的好处（Def. 3.2)。 我们比较了k-FED在设备中两个不同数据分区上的性能：（i）一个具有IID随机分区，以及（ii） ）另一个具有结构化分区。 为了生成本实验的底层结构化分区，我们使用以下启发式方法。 首先，我们将所有数据聚类到 $k$ 簇中，以获得 $k$ 值的范围。对于每个$k$，我们将已有的聚类作为目标聚类$𝒯$，并构造数据矩阵$A$和中心矩阵$C$.最后，对于每对聚类均值${\mu }_r,{\mu }_s$，我​​们计算数量$\frac{\parallel {\mu }_r-{\mu }_s\parallel }{2\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s)}$，即聚类均值的实际分离与所需的主动分离的比率。 我们选择一个 $k$ 值，在该值下，大量簇可以很好地分离（参见附录 B，图 5)。 我们将其称为oracle 集群。 现在，为了生成 (i) 的 IID 分区，我们在 $Z$ 设备之间随机分配此数据。 为了生成 (ii) 的结构化分区，我们将数据划分到 $Z$ 设备中，以便每个设备仅接收来自不超过 $k^{\prime }$ 集群的随机子集的数据。 对于 $k^{\prime }$ 的每个值，我们使用 k-FED 对设备上两种情况的数据进行聚类，并计算 $k$ - 表示成本。 让 ${\varphi }^{\ast }$ 表示 $k$ - 表示原始 oracle 集群的成本。 让 $\varphi (k^{\prime })$ 表示 $k$ - 表示将 $k^{\prime }$ 集群分配给每个设备时的成本。 图2展示了结构化分区($\varphi (k^{\prime })-{\varphi }^{\ast }$)和随机分区($\varphi (k)-{\varphi }^{\ast }$)的成本变化之间的相对成本比率。

我们在 FEMNIST 和 Shakespeare 数据集（Caldas 等人，2018）（详细信息参见附录B)上进行了此实验。 从图2中绘制的结果可以看出，与在IID随机分区上实现的成本相比，基于结构化分割的聚类实现的成本更接近于oracle分区的成本。 我们注意到，即使经过如此仔细的构造，实际数据集中实现的分离也比所需的要小得多（附录B)。 即便如此，我们的实验表明，异构性可以使基于共同基准的联合集群受益。

图2： 与随机分区（$\varphi (k)$）相比，结构化分区（$\varphi (k^{\prime })$）下的 $k$ 均值成本更接近于 Oracle 聚类（${\varphi }^{\ast }$）的成本。 随着异构性的增加($k^{\prime }$ 减少），结构化分区的好处变得更加显着，其中 $\varphi (k^{\prime })-{\varphi }^{\ast }\ll \varphi (k)-{\varphi }^{\ast }$。

沟通效率。 该方法的一个优点是它只需要一轮通信。 鉴于此，我们很自然地想知道 k-FED 的性能与其他通信密集型集群基线相比如何。 特别是，在分布式设置中解决 $k$-means 的常见方法是简单地并行化每个步骤的集群分配和集群均值计算。 在这里，我们表明，对于具有多个 $k^{\prime }$ 值的数据集的不同分区，我们的一次性方法 $k$-FED 能够产生类似的聚类输出（就 $k$-意味着成本；越低越好）作为简单的分布式$k$-意味着，需要多轮通信。 在这里，我们使用与之前实验相同的预言机集群来构建我们的设备数据。

图3： $k$-FED（仅使用一轮通信）能够提供与朴素分布式 $k$ 类似的聚类质量。

4.2.2 $k$-Fed的应用

个性化的佛罗里达州。 与将单一全局模型拟合到所有设备上的数据相比，联合学习个性化（独立但相关）模型可以提高有效样本量，同时适应联邦网络中的异质性（例如，Smith 等人，2017；Mansour 等）人，2020）。

Ghosh 等人 (2020) 最近提出了一种通过联邦网络学习模型的算法，当聚类信息不可用时，设备将被划分为集群。 考虑每个设备集群想要解决的监督学习问题，并假设集群 $k$ 的数量已知。 他们的方法，即迭代联合聚类算法 (IFCA)，在第一步中初始化 $k$ 模型 $(m_1,\mathrm{\dots },m_k)$，每个聚类都有一个模型。 在每轮开始时，所有 $k$ 模型都会发送到设备。 每个设备都会选择能够最小化其本地可用数据的损失函数的模型。 该设备现在可以配置为计算并传输该模型的损失函数的梯度，或者可以在本地执行一些模型更新并将更新的模型发送到中央服务器。 作为本轮的最后一步，对于每个模型 $m_i$ $i\in [k]$，将识别选择该模型的所有设备。 所有这些设备都分配有集群 ID $i$。 然后，使用集群 $i$ 中的设备发送的信息，通过模型平均或梯度平均来更新模型 $m_i$。

表2： 使用三种方法测试旋转 MNIST 的准确性。 基于k-FED输出的聚类信息训练个性化模型，达到了与IFCA相同的性能，而没有IFCA在$k^{\prime }=1$时的高计算和通信开销>。 对于$k^{\prime }=2$，与IFCA相比，k-FED的性能下降要少得多。

	Global	IFCA	$k$-FED
100 devices ($k^{\prime }=1$)	95.0	98.0	98.0
200 devices ($k^{\prime }=1$)	94.5	97.2	97.8
100 devices ($k^{\prime }=2$)	95.3	95.6	97.1
200 devices ($k^{\prime }=2$)	94.5	95.1	96.4

我们在学习集群个性化模型的问题上实例化了 IFCA。 如(Ghosh 等人, 2020) 所示，我们使用 MNIST 数据集进行此实验。 我们通过 $0,90,180$ 和 $270$ 度旋转构建 $k=4$ 集群并将它们分布在设备之间。 请注意，在 IFCA 的设置中，每个设备仅包含来自单个集群的数据（因为我们是集群设备而不是单个数据点）。 因此，我们设置 $k^{\prime }=1$ 并将 IFCA 与简单的基于 k-FED 的方法进行比较：我们首先执行一次性聚类以获得初始聚类，然后我们使用 FedAvg (McMahan 等人, 2017) 来学习每个集群的一个模型。 作为基线，我们还学习一个全局模型并将其包括在内以进行比较。 从表2($k^{\prime }=1$)的测试精度可以看出，k-FED与IFCA具有竞争力。 此外，k-FED还有一个额外的优点，即一旦分配了簇标识，我们只需要传输一个模型而不是$k$模型通过 IFCA 传输。

由于 k-FED 对数据进行聚类，因此 k-FED + FedAvg 方法也可以处理有数据的情况来自同一设备上的多个集群。 表2 ($k^{\prime }=\sqrt{k}=2$) 显示了此类分区的测试精度。 在这里，我们观察到 IFCA 的性能与 k-FED 相比有所下降。

客户选择。 最后，我们证明$k$-FED产生的聚类信息对于客户端选择应用（Cho等人，2020）是有用的先验。 在实践中，跨设备联合优化算法需要容忍部分设备参与（Kairouz等人，2019）。 直观地说，与随机采样设备相比，在每轮通信中合并来自“代表性”设备的信息可能会加速联合网络上学习任务的收敛。 随机抽样时，可以选择相似且可能冗余的客户。 最近的设备选择方法提出在随机选择的设备子集中额外选择训练损失较大的设备（Cho等人，2020）以帮助提高收敛速度。 我们将 $k$-FED 与此方法结合起来，进一步过滤掉来自同一集群的设备。 请注意，$k$-FED 不会给基线算法增加显着的额外开销，因为它只需要在训练之前运行一次性聚类。 结果如图4所示。 我们发现，利用 $k$-FED 学习到的底层结构可以促进这些现实联合基准的收敛。

图4： $k$-FED 提供的附加聚类信息可以帮助实现比最近的客户端选择技术 pow-d （Cho 等人，2020）更快的收敛。

与 Cho 等人 (2020) 类似，我们还观察到，对于图 4 中的实验，使用有利于客户端选择策略来减少所有设备上的测试性能差异与随机选择相比，客户信息更丰富（可能代表性不足）。 例如，在 FEMNIST 上，当使用 k-fed 结合 pow-d 而不是随机选择时，最终测试精度的方差降低了 35%。 这在我们希望为联邦学习强加公平概念的场景中可能很有用（Mohri等人，2019；Li等人，2020c）。

5结论

在这项工作中，我们通过严格分析异构性对 Lloyd 分布式集群算法的简单一次性变体的影响，提供了一个示例，说明联邦网络中的异构性如何有益。 我们提出的方法 k-FED 解决了联邦环境中常见的实际问题，例如高通信成本、落后者和设备故障。 我们相信，异质性的其他具体概念——加上仔细的分析——可能会为联邦学习中的许多其他问题带来好处，这是未来工作的一个有趣的方向。

6致谢

这项工作得到了国家科学基金会拨款 IIS1838017、Google 学院奖、Facebook 学院奖和 CONIX 研究中心的部分支持。 本材料中表达的任何意见、发现、结论或建议均为作者的观点，并不一定反映国家科学基金会或任何其他资助机构。

附录A证明

A.1 证明定理3.1（主定理）

在我们继续证明定理3.1之前，我们首先建立一些基本知识结果。 令 $𝒯=(T_1,\mathrm{\dots },T_k)$ 为我们的目标聚类，让 $T_r^{(z)}$ 为设备 $z$ 上聚类 $T_r$ 的点的子集。 对于设备 $z$ 上的任何点 $A_i^{(z)}$，让 $c(A_i^{(z)})$ 表示它所属集群的索引。 那是，

$$A_i^{(z)}\in T_{c(A_i^{(z)})}^{(z)}\subseteq T_{c(A_i^{(z)})}.$$

还记得矩阵 $C$ 的定义，即均值矩阵。 这里 $C$ 的第 $i$ 行包含包含数据点 $A_i$ 的簇的平均值，即 $C_i=\mu (T_{c(A_i)})$。 我们的第一个引理限制了“本地”簇的意思 $\mu (T_r^{(z)})$ 可以偏离 $\mu (T_r)$ 多远。

Lemma 2 (Kumar & Kannan (2010) 中的引理 5.2）。

令 $T_r^{(z)}$ 为设备 $z$ 上 $T_r$ 的子集。 让 $\mu (T_r^{(z)})$ 表示 $T_r^{(z)}$ 索引的点的平均值。 然后，

${\parallel \mu (T_r^{(z)})-\mu (T_r)\parallel }_2\le {\displaystyle \frac{\parallel A-C\parallel }{\sqrt{|T_r^{(z)}|}}}.$

证明。

令 $A^{(z)}$ 为设备 $z$ 上 $A$ 的子矩阵，并令 ${\tilde{C}}^{(z)}$ 为均值矩阵的相应子矩阵$C$。令 $u$ 为 $T_r^{(z)}$ 中点的指示向量。 观察到，

${\parallel |T_r^{(z)}|(\mu (T_r^{(z)})-{\mu }_r)\parallel }_2$ $={\parallel (A^{(z)}-{\tilde{C}}^{(z)})\cdot u\parallel }_2$

$\le \parallel A^{(z)}-{\tilde{C}}^{(z)}\parallel {\parallel u\parallel }_2$

$\le \parallel A-C\parallel \sqrt{\left|T_r^{(z)}\right|}.$

在这里，对于最后一个不等式，我们注意到 $(A^{(z)}-{\tilde{C}}^{(z)})$ 包含 $(A-C)$ 行的子集，因此包含 $\parallel A^{(z)}-{\tilde{C}}^{(z)}\parallel \le \parallel A-C\parallel$。 ∎

现在考虑每个设备$z$上的本地集群问题。 该设备有一个数据矩阵$A^{(z)}$，其行是$A$的子集。 令 $T_1^{(z)},T_2^{(z)},\mathrm{\dots },T_k^{(z)}$ 为该设备上 $T_1,T_2,\mathrm{\dots },T_k$ 的子集，其中不超过 $k^{\prime }$ 为非空。 构造一个与 $A^{(z)}$ 具有相同维度的矩阵 $C^{(z)}$，其中对于 $A^{(z)}$ 的每一行，$C^{(z)}$ 的相应行包含平均值该点所属的本地簇的名称。 即，$C^{(z)}$ 的第 $i$ 行包含 $\mu (T_{c(A_i^{(z)})}^{(z)})$。 使用下一个引理，我们用 $(A-C)$ 来限制矩阵 $(A^{(z)}-C^{(z)})$ 的算子范数。

Lemma 3.

令 $T_1^{(z)},T_2^{(z)},\mathrm{\dots }{T}_k^{(z)}$ 为驻留在设备上的目标集群的子集，其中 $k^{\prime }$ 不为空。 令$A^{(z)}$为对应的$n^{(z)}\times d$数据矩阵。 设$C^{(z)}$为相应的均值矩阵；即每一行$C_i^{(z)}=\mu (T_{c(A_i^z)}^z)$。 然后，

$$\parallel A^{(z)}-C^{(z)}\parallel \le 2\sqrt{k^{\prime }}\parallel A-C\parallel .$$

证明。

令 ${\tilde{C}}^{(z)}$ 为 $n^{(z)}\times d$ 矩阵，其中 ${\tilde{C}}_i^{(z)}=\mu (T_{c(A_i^{(z)})})$。 首先，考虑沿顶部奇异方向的单位向量 $u$ 并观察：

${\parallel {\tilde{C}}^{(z)}-C^{(z)}\parallel }^2$ $={\displaystyle \sum _{r=1}^k}|T_r^{(z)}|{\left(\left(\mu (T_r^{(z)})-\mu (T_r)\right)\cdot u\right)}^2$

$\le {\displaystyle \sum _{r=1}^k}|T_r^{(z)}|{\parallel \mu (T_r^{(z)})-\mu (T_r)\parallel }_2^2$

${\le }_{(a)}{k}^{\prime }{\parallel A-C\parallel }^2.$

这里对于不等式$(a)$，我们调用引理2。 另外，注意到 $\parallel A^{(z)}-{\tilde{C}}^{(z)}\parallel \le \parallel A-C\parallel$，我们得到，

$\parallel A^{(z)}-C^{(z)}\parallel$ $\le \parallel A^{(z)}-{\tilde{C}}^{(z)}\parallel +\parallel {\tilde{C}}^{(z)}-C^{(z)}\parallel$

$\le (1+\sqrt{k^{\prime }})\parallel A-C\parallel \le 2\sqrt{k^{\prime }}\parallel A-C\parallel .$

∎

我们分四个部分证明定理3.1：

1. 在第一步中，我们证明满足主动分离条件足以满足引理1（引理4)所需的Awasthi-Sheffet分离条件。

2. 接下来，我们使用定理 4 来证明 k-FED (Algorithm-1) 的第一步将找到与设备 $z$ 上的真正中心 $\mu (T_r^{(z)})$ 接近的局部中心 ${\theta }_r^{(z)}$。 我们在引理 5 中陈述并证明了这一点。

3. 在下一步中，我们展示了在k-FED的步骤2-6中挑选$k$初始中心的过程恰好挑选了一个本地聚类中心${\theta }_r^{(z)}$ 对于每个集群 $r$。也就是说，我们选择与每个目标簇相对应的 $k$ 本地中心。 （引理 6)

4. 最后，我们认为通过这种初始化，产生的局部聚类中心 $({\tau }_1,\mathrm{\dots },{\tau }_k)$ 的聚类具有这样的属性，即对应于同一聚类（例如 $T_r$)的所有局部聚类中心将是在同一组中（例如 ${\tau }_r$)。 而且，任何$T_s$、$s\ne r$对应的本地聚类中心都不在${\tau }_r$中。 正如我们稍后讨论的，这足以使 $({\tau }_1,\mathrm{\dots },{\tau }_k)$ 产生的诱导聚类与我们的目标聚类 $𝒯=(T_1,T_2,\mathrm{\dots })$ 一致，直到局部聚类阶段发生的标签排列和错误分类。

Lemma 4.

令 $(T_r,T_s)$ 为簇对，使得 ${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge 2c\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s).$ 令 $T_r^z\subseteq T_r$ 和 $T_s^z\subseteq T_s$ 为设备 $z$ 上的大子集。 然后，

${\parallel {\mu }_r^{(z)}-{\mu }_s^{(z)}\parallel }_2\ge c\sqrt{k^{\prime }}\left({\displaystyle \frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^{(z)}}}}+{\displaystyle \frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_s^{(z)}}}}\right).$

证明。

（引理4)使用三角不等式，我们有

${\parallel {\mu }_r^{(z)}-{\mu }_s^{(z)}\parallel }_2$ $\ge {\parallel {\mu }_r-{\mu }_s\parallel }_2-{\parallel {\mu }_r^{(z)}-{\mu }_r\parallel }_2-{\parallel {\mu }_s-{\mu }_s^{(z)}\parallel }_2$

$\ge 2c\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s)-{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^{(z)}}}}-{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_s^{(z)}}}}$ (5)

使用主动分离假设。 现在，扩展项可以将左侧写为

${\parallel {\mu }_r^{(z)}-{\mu }_s^{(z)}\parallel }_2$ $\ge 2c\sqrt{m_0}\left(k^{\prime }{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r}}}+k^{\prime }{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_s}}}\right)-{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^{(z)}}}}-{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_s^{(z)}}}}$

$\ge \underset{(i)}{\underbrace{\left(2\sqrt{{\displaystyle \frac{m_0{n}_r^{(z)}}{n_r}}}-{\displaystyle \frac{1}{c{k}^{\prime }}}\right)c{k}^{\prime }{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^{(z)}}}}}}+\underset{(ii)}{\underbrace{\left(2\sqrt{{\displaystyle \frac{m_0{n}_s^{(z)}}{n_s}}}-{\displaystyle \frac{1}{c{k}^{\prime }}}\right)c{k}^{\prime }{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_s^{(z)}}}}}}.$

我们首先只考虑术语$(i)$。 根据引理3,$\parallel A-C\parallel \ge \frac{1}{2\sqrt{k^{\prime }}}\parallel A^{(z)}-C^{(z)}\parallel$。 使用这个我们可以将 $(i)$ 绑定为

$$\left(2\sqrt{\frac{m_0{n}_r^{(z)}}{n_r}}-\frac{1}{c{k}^{\prime }}\right)c{k}^{\prime }\frac{\parallel A-C\parallel }{\sqrt{n_r^{(z)}}}\ge \left(2\sqrt{\frac{m_0{n}_r^{(z)}}{n_r}}-\frac{1}{c{k}^{\prime }}\right)c\sqrt{k^{\prime }}\frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^{(z)}}}.$$

现在回想一下，对于大型集群子集 $n_r^{(z)}\ge \frac{1}{m_0}{n}_r$ 以及 $2\sqrt{\frac{m_0{n}_r^{(z)}}{n_r}}-\frac{1}{c{k}^{\prime }}\ge 2-\frac{1}{c{k}^{\prime }}\ge 1$。 这意味着我们可以将术语 $(i)$ 绑定为，

$$\left(2\sqrt{\frac{m_0{n}_r^{(z)}}{n_r}}-\frac{1}{c{k}^{\prime }}\right)c{k}^{\prime }\frac{\parallel A-C\parallel }{\sqrt{n_r^{(z)}}}\ge c\sqrt{k^{\prime }}\frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^{(z)}}}.$$

我们也得到了项 $(ii)$ 的对称表达式。 在等式 5 中使用它，我们得到所需的结果：

${\parallel {\mu }_r^{(z)}-{\mu }_s^{(z)}\parallel }_2\ge c\sqrt{k^{\prime }}\left({\displaystyle \frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^{(z)}}}}+{\displaystyle \frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_s^{(z)}}}}\right).$

∎

由于算法 1 在每个设备上本地运行，因此它不受非活动分离条件的影响，因为根据定义，每个设备上都存在仅活动集群对的子集。 这意味着算法1成功解决了局部聚类问题。 特别是在包含来自某个集群 $T_r$ 的数据的设备 $z$ 上，${\theta }_r^z$ 距离 $\mu (T_r^{(z)})$ 不太远。 显示此结果是我们的第二步，我们在下面的引理 5 中正式声明这一点。

Lemma 5.

令 $(T_1^{(z)},\mathrm{\dots },T_k^{(z)})$ 为 $(T_1,\mathrm{\dots },T_k)$ 在某些设备 $z$ 上的子集，其中不超过 $k^{\prime }$ 为非空。 此外，假设所有非空子集都很大，即$|T_r^{(z)}|\ge \frac{1}{m_0}\left|T_r\right|$。 最后，假设$z$上的所有活动簇对都满足活动分离要求。 然后，在算法 1 终止时，对于每个非空 $T_r^{(z)}$，我们有

$${\parallel {\theta }_r^{(z)}-\mu (T_r^{(z)})\parallel }_2\le \frac{25}{c}\frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^z}}\le \frac{50\sqrt{k^{\prime }}}{c}\frac{\parallel A-C\parallel }{\sqrt{n_r^z}},$$

和，

$${\parallel {\theta }_r^{(z)}-\mu (T_r)\parallel }_2\le 2\sqrt{m_0{k}^{\prime }}\frac{\parallel A-C\parallel }{\sqrt{n_r}}\le 2\sqrt{m_0}\lambda .$$

证明。

首先注意数据矩阵$A^{(z)}$和中心矩阵$C^{(z)}$的局部聚类问题满足引理1的要求。 由此可见，

$${\parallel {\theta }_r^{(z)}-\mu (T_r^{(z)})\parallel }_2\le \frac{25}{c}\frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^z}}.$$

现在应用引理3给我们第一个陈述。

为了证明第二个命题，我们从三角不等式开始：

${\parallel {\theta }_r^{(z)}-\mu (T_r)\parallel }_2$ $\le {\parallel {\theta }_r^{(z)}-\mu (T_r^{(z)})\parallel }_2+{\parallel \mu (T_r^{(z)})-\mu (T_r)\parallel }_2$

$\le {\displaystyle \frac{25}{c}}{\displaystyle \frac{\parallel A^{(z)}-C^{(z)}\parallel }{\sqrt{n_r^z}}}+{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^z}}}.$

对于最后一个不等式，我们使用引理 2。 现在应用引理 3 并取 $c\ge 100$，我们得到

${\parallel {\theta }_r^{(z)}-\mu (T_r)\parallel }_2$ $\le {\displaystyle \frac{50\sqrt{k^{\prime }}}{c}}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^z}}}+{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^z}}}$

$\le \left({\displaystyle \frac{50}{c}}+{\displaystyle \frac{1}{\sqrt{k^{\prime }}}}\right)\sqrt{k^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^z}}}$

$\le 2\sqrt{k^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r^z}}}\le 2\sqrt{m_0{k}^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r}}}$

$\le 2\sqrt{m_0}\lambda .$

∎

这意味着对于固定的$r$，中央服务器从设备$z\in [Z]$接收到的所有${\theta }_r^{(z)}$都“接近”$\mu (T_r)$。

下一步是证明在步骤 2-6 中选择的 $k$ 初始中心 k-FED 中，每个目标都有一个对应的集群$T_i$。 稍后我们将证明，这足以让算法的最后一步将本地聚类中心正确分配给正确的分区。

Lemma 6.

让 $𝒯=(T_1,\mathrm{\dots },T_k)$ 成为我们的目标聚类。 假设所有活动簇对和非活动簇对满足其分离要求。 进一步设$n_{\min }\ge \frac{4}{c^2{k}^{\prime }}{n}_{\max }$。 然后，在 k-FED 第 6 步结束时，对于每个目标簇 $T_r$，都存在一个 ${\theta }_s^{(z)}\in M$，使得 ${\theta }_s^{(z)}=\mu (T_s^{(z)})$对于一些$z\in [Z]$。

在我们继续证明这个引理之前，我们声明并证明本地聚类中心 ${\theta }_r^{(z)}$ 与 $s\ne r$ 的某个聚类平均值 $\mu (T_s)$ 的接近程度的下界：

Lemma 7。

让${\theta }_r^{(z)}:=\mu (T_r^{(z)})$。 对于任何 $s\ne r$、$z^{\prime }\in [Z]$，

$${\parallel {\theta }_r^{(z)}-{\theta }_s^{(z^{\prime })}\parallel }_2\ge 6\sqrt{m_0}\lambda .$$

证明。

首先，根据三角不等式注意到，

$${\parallel {\theta }_r^{(z)}-{\theta }_s^{(z^{\prime })}\parallel }_2\ge {\parallel {\mu }_r-{\mu }_s\parallel }_2-{\parallel {\mu }_r-{\theta }_r^{(z)}\parallel }_2-{\parallel {\mu }_s-{\theta }_s^{(z^{\prime })}\parallel }_2.$$

使用引理 5 和我们的非活动分离假设，我们将右侧进一步限制为，

${\parallel {\mu }_r-{\mu }_s\parallel }_2-{\parallel {\mu }_r-{\theta }_r^{(z)}\parallel }_2-{\parallel {\mu }_s-{\theta }_s^{(z^{\prime })}\parallel }_2$ $\ge 10\sqrt{m_0{k}^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_{\min }}}}-4\sqrt{m_0{k}^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r}}}$

$\ge 6\sqrt{m_0{k}^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_{\min }}}}\ge 6\sqrt{m_0}\lambda ,$

如预期的。 ∎

证明。

（引理6)令$M_t$表示k-FED的步骤2-6中的集合$M$ t4>，在选取第一个 $t$ 点之后 $(1\le t\le k)$。 让我们将迭代$t$中选择的点k-FED表示为${\theta }_t$。 那是，

$${\theta }_t\leftarrow \underset{z\in [Z],i\in [k]}{\arg \max }{d}_{M_{t-1}}({\theta }_i^{(z)}).$$

我们将证明集合 $M_t$ 在每次迭代 $t$ 时包含与 $t$ 个不同目标簇相对应的 $t$ 个点。这个不变量在 $t=1$ 处是微不足道的。 假设该语句首先在某个 处变为 false。 让点 ${\theta }_{t^{\prime }}$ 对应于集群 $T_r$ 的局部集群平均值。 那么必须存在一些 ，使得 ${\theta }_{t^{\prime \prime }}$ 也对应于 $T_r$ 的本地集群平均值。 此外，必须存在某个簇$s\ne r$，使得${\theta }_s^{(z)}\notin M_{t^{\prime }}$对于任何$z\in [Z]$。

现在根据 $d_{M_{t-1}}({\theta }_{t^{\prime }})$ 的定义，我们有

$d_{M_{t-1}}({\theta }_{t^{\prime }})$ $=\underset{\theta \in M_{t-1}}{\min }{\parallel {\theta }_{t^{\prime }}-\theta \parallel }_2$

$\le {\parallel {\theta }_{t^{\prime }}-{\theta }_{t^{\prime \prime }}\parallel }_2$

${\le }_{(a)}{\parallel {\theta }_{t^{\prime }}-\mu (T_r)\parallel }_2+{\parallel \mu (T_r)-{\theta }_{t^{\prime \prime }}\parallel }_2$

${\le }_{(b)}4\sqrt{m_0{k}^{\prime }}{\displaystyle \frac{\parallel A-C\parallel }{\sqrt{n_r}}}\le 4\sqrt{m_0}\lambda .$ (6)

这里不等式 (a) 由三角不等式得出，(b) 由引理 5 得出。

现在考虑任何 $z$ 的 ${\theta }_s^{(z)}$。 由于$M_t$中不包含来自$T_s$的其他本地聚类中心，根据引理7，我们得出结论，对于每个$\theta \in M_{t-1}$，

${\parallel {\theta }_s^{(z)}-\theta \parallel }_2\ge 6\sqrt{m_0}\lambda .$

但这意味着$d_{M_{t-1}}({\theta }_{t^{\prime }})\le 4\sqrt{m_0}\lambda \le 6\sqrt{m_0}\lambda \le d_{M_{t-1}}({\theta }_s^{(z)})$导致了基于${\theta }_{t^{\prime }}$的定义的矛盾。 这完成了我们的论证。 ∎

现在我们准备证明我们的主要定理3.1。

证明。

从引理6，我们知道k-FED第6步结束时的集合$M$恰好包含一个每个目标聚类对应的中心。 令本地聚类中心${\tilde{\theta }}_r\in M$对应于聚类$T_r$。 观察对于任何$z\in [Z]$，

${\parallel {\theta }_r^z-{\tilde{\theta }}_r\parallel }_2$ $\le {\parallel {\theta }_r^z-{\mu }_r\parallel }_2+{\parallel {\mu }_r-{\tilde{\theta }}_r\parallel }_2$

$\le 4\sqrt{m_0}\lambda ,$

使用引理 7。 此外，对于任何$s\ne r$，

${\parallel {\theta }_s^z-{\tilde{\theta }}_r\parallel }_2$ $\ge 6\sqrt{m_0}\lambda .$

这意味着，对于每个 $r$ 和 $z\in [Z]$，${\theta }_r^z$ 比任何其他初始中心 ${\tilde{\theta }}_s$、$s\ne r$ 更接近相应的初始中心 ${\tilde{\theta }}_r$。 令${\tau }_r$为分配给$\widetilde{{\theta }_r}$的本地聚类中心的集合。 那么可以看出，${\tau }_r$只包含所有设备$z$的本地聚类中心${\theta }_r^{(z)}$，即${\tau }_r$包含所有设备聚类中心对应目标集群$T_r$。

现在考虑 k-FED 诱导聚类的定义（定义 3.3)，其中我们定义

$$T_r^{\prime }=\{i:A_i^{(z)}\in U_s^{(z)}\text{and}{\theta }_s^{(z)}\in {\tau }_r\}.$$

在这种情况下，我们知道${\tau }_r$中仅包含与簇$T_r$相对应的局部簇中心。 因此我们诱导的簇 $T_r^{\prime }$ 变成，

$$T_r^{\prime }=\{i:A_i^{(z)}\in U_r^{(z)}\}.$$

现在从引理 1 我们知道，在每个设备上，集合 $(U_1^{(z)},\mathrm{\dots },U_{k^{\prime }}^{(z)})$ 和 $(T_1^{(z)},\mathrm{\dots },T_{k^{\prime }}^{(z)})$ 最多仅在 $O(\frac{1}{c^2})n^{(z)}$ 上有所不同。 总结所有设备 $z$ 上的误差，我们发现我们的诱导聚类 $(T_1^{\prime },\mathrm{\dots },T_k^{\prime })$ 和目标聚类 $(T_1,\mathrm{\dots },T_k)$ 仅在 $O(\frac{1}{c^2})n$ 点上有所不同。 最后，如果所有局部点都满足其各自的邻近条件（定义3.1)，则没有点被错误分类。 我们的证明到此结束。 ∎

A.2 k-FED的运行时间和处理新设备

现在我们分析k-FED步骤2-8的运行时间。 由于步骤 1 是在各个设备上运行 Algorithm-1，因此我们在分析中不包括此步骤的运行时间。 请注意，在分离假设到位的情况下，算法 1 将在多项式时间内收敛。 然而，正如在实践中观察到的，类似 Lloyd 的方法通常只需要几次迭代即可终止。

Theorem A.1.

k-FED的步骤2-8需要$O(Z{k}^{\prime }\cdot k^2)$成对距离计算来终止。 此外，在计算出步骤 6 中的集合 $M$ 后，可在 $O(k^{\prime }\cdot k)$ 距离计算中正确分配来自未见设备 $z$ 的新本地群集中心 ${\mathrm{\Theta }}^{(z)}$。

证明。

（定理3.2)第一部分的证明来自于简单的逐步分析。 步骤1可以在$O(1)$中执行。 步骤 2-6 恰好执行 $k$ 次。 在每次迭代$t$、$(1\le t\le k)$时，我们计算所有设备簇中心（其中最多$Z{k}^{\prime }$)到$M_{t-1}$ 因此，在迭代$t$时，这可以通过$Z{k}^{\prime }\cdot t$距离计算来实现。 总结所有 $t$，我们发现步骤 2-6 可以在 $O(Z{k}^{\prime }\cdot k^2)$ 距离计算中运行。 最后，第7步要求我们将所有$Z{k}^{\prime }$设备簇中心分配给$M$中的$k$初始点之一。这可以在$O(Z{k}^{\prime }\cdot k)$距离计算中实现。 因此，成对距离计算的总体复杂度为$O(Z{k}^{\prime }\cdot k^2)$。

该语句的第二部分注意到，对于每个 ${\theta }_r^{(z)}\in {\mathrm{\Theta }}^{(z)}$，集合 $M$ 中最近的点必须是我们选择的初始中心 ${\tilde{\theta }}_r$，如定理3.1的证明。 因此，每个${\theta }_r^{(z)}\in {\mathrm{\Theta }}^{(z)}$都根据需要分配给正确的分区${\tau }_r$。 ∎

A.3 从高斯混合中分离数据

现在我们证明定理4.1。 回想一下，我们正在 $k^{\prime }\le \sqrt{k}$ 的设置中工作。 我们的证明基于引理 6.3、Kumar 和 Kannan (2010) 的结果。

证明。

首先考虑一个活动簇对$r,s$。 根据我们的分离要求，我们有：

${\parallel {\mu }_r-{\mu }_s\parallel }_2$ $\ge {\displaystyle \frac{2c\sqrt{k{m}_0}{\sigma }_{\max }}{\sqrt{w_{\min }}}}\text{polylog}\left({\displaystyle \frac{d}{w_{\min }}}\right)$

$\ge 2c\sqrt{k{m}_0}{\displaystyle \frac{{\sigma }_{\max }\sqrt{n}}{\sqrt{w_{\min }n}}}\text{polylog}\left({\displaystyle \frac{d}{w_{\min }}}\right).$

我们进一步简化右手得到，

$${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge c\sqrt{k{m}_0}{\sigma }_{\max }\sqrt{n}\left(\frac{1}{\sqrt{w_{r}n}}+\frac{1}{\sqrt{w_{s}n}}\right)\text{polylog}\left(\frac{d}{w_{\min }}\right).$$

现在请注意，每个组件 $F_r$ 的点数非常接近 $w_r{n}_r$，概率非常高。 这里$w_r$是分量$r$的混合权重，$n_r$是数据点的数量。 使用这个，我们很可能有

$${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge c\sqrt{k{m}_0}{\sigma }_{\max }\sqrt{n}\left(\frac{1}{\sqrt{n_r}}+\frac{1}{\sqrt{n_s}}\right)\text{polylog}\left(\frac{d}{w_{\min }}\right).$$

进一步地，可以证明$\parallel A-C\parallel$是$O\left({\sigma }_{\max }\sqrt{n}\cdot \text{polylog}\left(\frac{d}{w_{\min }}\right)\right)$的概率很高（参见(Dasgupta等人, 2007))。 因此我们得出结论，很有可能

$${\parallel {\mu }_r-{\mu }_s\parallel }_2\ge c\sqrt{k{m}_0}\left(\frac{\parallel A-C\parallel }{\sqrt{n_r}}+\frac{\parallel A-C\parallel }{\sqrt{n_s}}\right).$$

从而满足主动分离的要求。 非活动分离条件的证明是类似的。 最后，邻近条件源自高斯的浓度特性。 ∎

附录B实验细节

B.1 数据集

对于涉及真实数据的所有实验，我们使用 EMNIST、FEMNIST 和 Shakespeare 数据集。 这些数据集及其相应的模型可在 LEAF 基准测试中获取：https://leaf.cmu.edu/。 对于客户端选择实验，我们通过为每个设备分配 2 个类别来手动划分 FEMNIST 的子集（前 10 个类别）。 总共有 500 台设备。 所有设备上的训练样本数量以及每个设备中每个类别的训练样本数量都遵循幂律。 我们使用莎士比亚的自然划分，其中每个设备对应于威廉·莎士比亚戏剧中的一个说话角色。 我们从整个数据集中随机抽取 109 个用户。 对于个性化实验，遵循Ghosh等人（2020），我们使用基于CNN的模型，该模型具有一个隐藏层和200个隐藏单元，并以$0.01$和$10$ 每台设备上的本地更新。

B.2 根据分离选择$k$

如第 4.2 节所述，为了创建 oracle 聚类，我们会针对 $k$ 的每个候选值，为每个聚类对 $(r,s)$ 计算数量 $c_{rs}=\frac{\parallel {\mu }_r-{\mu }_s\parallel }{2\sqrt{m_0}({\mathrm{\Delta }}_r+{\mathrm{\Delta }}_s)}$。 我们构建了这些$c_{rs}$的分布图。 图 5 提供了 MNIST 数据集的此类绘图示例。 从这里可以看出，对于 $k$ 的所有值，相对间隔都非常小。 因此，即使对于这种预言聚类，聚类平均值之间的实际间隔也很小。 要为 Oracle 集群选择 $k$，我们选择一个固定值 $c_0$（例如 $0.5$)，然后选择 $k$ 的值这导致簇对$(r,s)$的最大分数具有$c_{rs}>c_0$。

图5： $c_{rs}$ 的分布图，针对 MNIST 数据集上 $k$ 的各种值。 可以看出，对于大多数簇对来说，表明它们之间的分离度比较小。