Federated Learning(FL) is a privacy-preserving machine learning paradigm
where a global model is trained in-situ across a large number of distributed
edge devices. These systems are often comprised of millions of user devices and
only a subset of available devices can be used for training in each epoch.
Designing a device selection strategy is challenging, given that devices are
highly heterogeneous in both their system resources and training data. This
heterogeneity makes device selection very crucial for timely model convergence
and sufficient model accuracy. To tackle the FL client heterogeneity problem,
various client selection algorithms have been developed, showing promising
performance improvement in terms of model coverage and accuracy. In this work,
we study the overhead of client selection algorithms in a large scale FL
environment. Then we propose an efficient data distribution summary calculation
algorithm to reduce the overhead in a real-world large scale FL environment.
The evaluation shows that our proposed solution could achieve up to 30x
reduction in data summary time, and up to 360x reduction in clustering time.

在大规模 FL 环境中，本研究旨在研究客户端选择算法的开销，并提出一种高效的数据分布摘要计算算法来减少开销。评估结果显示，我们的解决方案在数据摘要时间上能够实现 30 倍的降低，聚类时间上能够实现 360 倍的降低。

加速联邦学习的高效数据分配估计

Efficient Data Distribution Estimation for Accelerated Federated  Learning

The standard client selection algorithms for Federated Learning (FL) are
often unbiased and involve uniform random sampling of clients. This has been
proven sub-optimal for fast convergence under practical settings characterized
by significant heterogeneity in data distribution and computing and
communication resources across clients. For applications having timing
constraints due to limited communication opportunities, the client selection
strategy is critical to complete model training within the fixed budget of
communication rounds. To address this, we develop a biased client selection
strategy, GreedyFed that identifies and greedily selects the most contributing
clients in each communication round. This method builds on a fast approximation
algorithm for the Shapley Value at the parameter server (PS), making the
computation tractable for real-world applications with many clients. Compared
to various client selection strategies on several real-world datasets,
GreedyFed demonstrates fast and stable convergence with high accuracy under
timing constraints and a higher degree of heterogeneity in data distribution,
systems constraints, and privacy requirements.

发展了一种被称为 GreedyFed 的具有偏见的客户选择策略，它能够在固定的通信轮次内，在数据分布、系统限制和隐私要求的高度异质性条件下，实现快速而稳定的收敛，并获得高准确性。