Federated Learning with Fair Worker Selection: A Multi-Round Submodular Maximization Approach
Federated Learning with Fair Worker Selection: A Multi-Round Submodular Maximization Approach
复制标题
DOI：
10.1109/mass52906.2021.00033
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Fengjiao Li;Jia Liu;Bo Ji
中科院分区：
文献类型：
--
作者：
Fengjiao Li;Jia Liu;Bo Ji
本文研究了联邦学习系统中的公平工人选择问题，其中公平作为一种激励机制，鼓励更多的工人加入联邦。考虑到全局模型的训练精度作为所选工人的效用，而所选工人是典型的单调次模函数，我们将工人选择问题表述为一个新的具有基数约束和公平性约束的多轮单调次模最大化问题。目标是最大化多轮的时间平均效用，同时还要满足一个额外的公平性要求，即每个工人必须在一定的时间内被选中。虽然带有基数约束的传统次模最大化已经是一个众所周知的NP-Hard问题，但多轮设置中的公平性约束增加了额外的难度。为了解决这一新的挑战，我们提出了三种算法：公平连续贪婪（FairCGl和FairCG2）和公平离散贪婪（FairDG），它们在可行的情况下都满足公平性要求。此外，我们证明了在FairCGl和FairCG2下实现的时间平均效用的非平凡下界。此外，FairDG将公平放在了更高的优先级，确保了更强的短期公平保证，这种保证在每一轮都是有效的。最后，我们进行了大量的仿真来验证所提出算法在时间平均效用和公平满意度方面的有效性。
In this paper, we study the problem of fair worker selection in Federated Learning systems, where fairness serves as an incentive mechanism that encourages more workers to participate in the federation. Considering the achieved training accuracy of the global model as the utility of the selected workers, which is typically a monotone submodular function, we formulate the worker selection problem as a new multi-round monotone submodular maximization problem with cardinality and fairness constraints. The objective is to maximize the time-average utility over multiple rounds subject to an additional fairness requirement that each worker must be selected for a certain fraction of time. While the traditional submodular maximization with a cardinality constraint is already a well-known NP-Hard problem, the fairness constraint in the multi-round setting adds an extra layer of difficulty. To address this novel challenge, we propose three algorithms: Fair Continuous Greedy (FairCGl and FairCG2) and Fair Discrete Greedy (FairDG), all of which satisfy the fairness requirement whenever feasible. Moreover, we prove nontrivial lower bounds on the achieved time-average utility under FairCGl and FairCG2. In addition, by giving a higher priority to fairness, FairDG ensures a stronger short-term fairness guarantee, which holds in every round. Finally, we perform extensive simulations to verify the effectiveness of the proposed algorithms in terms of the time-average utility and fairness satisfaction.