In this paper, a novel clustered FL framework that enables distributed edge
devices with non-IID data to independently form several clusters in a
distributed manner and implement FL training within each cluster is proposed.
In particular, our designed clustered FL algorithm must overcome two challenges
associated with FL training. First, the server has limited FL training
information (i.e., the parameter server can only obtain the FL model
information of each device) and limited computational power for finding the
differences among a large amount of devices. Second, each device does not have
the data information of other devices for device clustering and can only use
global FL model parameters received from the server and its data information to
determine its cluster identity, which will increase the difficulty of device
clustering. To overcome these two challenges, we propose a joint gradient and
loss based distributed clustering method in which each device determines its
cluster identity considering the gradient similarity and training loss. The
proposed clustering method not only considers how a local FL model of one
device contributes to each cluster but also the direction of gradient descent
thus improving clustering speed. By delegating clustering decisions to edge
devices, each device can fully leverage its private data information to
determine its own cluster identity, thereby reducing clustering overhead and
improving overall clustering performance. Simulation results demonstrate that
our proposed clustered FL algorithm can reduce clustering iterations by up to
99% compared to the existing baseline.

本研究提出了一种新颖的集群型联邦学习框架，使得具有非独立同分布数据的分布式边缘设备能够自主地以分布式方式形成若干个集群，并在每个集群内实现联邦学习训练。通过引入联邦学习和损失协同的分布式聚类方法，本研究克服了联邦学习中的两个挑战，并证明所提出的集群型联邦学习算法与现有基准相比，可以将聚类迭代次数减少多达 99%。

基于联合梯度和损失的聚类联邦学习设计

A Joint Gradient and Loss Based Clustered Federated Learning Design

We study the classic $k$-means/median clustering, which are fundamental
problems in unsupervised learning, in the setting where data are partitioned
across multiple sites, and where we are allowed to discard a small portion of
the data by labeling them as outliers. We propose a simple approach based on
constructing small summary for the original dataset. The proposed method is
time and communication efficient, has good approximation guarantees, and can
identify the global outliers effectively. To the best of our knowledge, this is
the first practical algorithm with theoretical guarantees for distributed
clustering with outliers. Our experiments on both real and synthetic data have
demonstrated the clear superiority of our algorithm against all the baseline
algorithms in almost all metrics.

本文提出了一种基于简要构建的数据摘要的分布式无监督学习算法，对异常点的全局识别有很好的近似保证，并在真实和人工数据上超过了所有基线算法。

分布式聚类与异常检测的实用算法

A Practical Algorithm for Distributed Clustering and Outlier Detection

This paper provides new algorithms for distributed clustering for two popular
center-based objectives, k-median and k-means. These algorithms have provable
guarantees and improve communication complexity over existing approaches.
Following a classic approach in clustering by \cite{har2004coresets}, we reduce
the problem of finding a clustering with low cost to the problem of finding a
coreset of small size. We provide a distributed method for constructing a
global coreset which improves over the previous methods by reducing the
communication complexity, and which works over general communication
topologies. Experimental results on large scale data sets show that this
approach outperforms other coreset-based distributed clustering algorithms.

本文提出一种新的分布式 k-median 和 k-means 聚类算法，通过 coresets 的方法，构建全局 coreset，降低了通信复杂度，实验结果表明该算法优于其他 coreset-based 分布式聚类算法。