传统的内核k-means算法在训练时需要将所有数据收集到云端。这种方法有两个缺点：消耗大量网络带宽和用户隐私难以保障。为此，我们需要设计一种联邦内核k-means算法。该算法可以让用户仅上传本地的计算结果而非原始数据，同时云端利用这个本地计算结果依然可以构建内核k-means模型。本项研究旨在解决联邦内核k-means算法设计过程中的两项挑战：1)如何分布式求解内核k-means的优化问题；2)如何保障算法的通信效率。针对第一个挑战，我们采用了一种常用的内核k-means问题的近似解法，该解法需要求解在内核k-means问题中使用的内核矩阵的特征值和特征向量。我们将求解特征值和特征向量的问题转化为一个凸的随机复合优化（SCO）问题，并设计了一种分布式随机近端梯度下降（DSPGD）算法来解决SCO问题。针对第二个挑战，我们设计了一种机制来提高DSPGD算法的通信效率。我们从理论上证明了DSPGD按O(1/T)的收敛率收敛到全局最优解，并且分析了联邦内核k-means算法的通信开销以及聚类质量。我们的实验结果表明，与现有算法相比，联邦内核k-means算法能有效减少通信开销。

参与人员：

周晓晨