Research on Hierarchical Federated Learning Incentive Mechanism Based on Master-Slave Game
-
摘要: 为了优化分层联邦学习(FL)全局模型的训练时延,针对实际场景中终端设备存在自私性的问题,该文提出一种基于博弈论的激励机制。在激励预算有限的条件下,得到了终端设备和边缘服务器之间的均衡解和最小的边缘模型训练时延。考虑终端设备数量不同,设计了基于主从博弈的可变激励训练加速算法,使得一次全局模型训练时延达到最小。仿真结果显示,所提出的算法能够有效降低终端设备自私性带来的影响,提高分层联邦学习全局模型的训练速度。Abstract: In order to optimize the training delay of the hierarchical Federated Learning (FL) global model, focusing on the selfishness of the terminal devices in the actual scene, an incentive mechanism based on game theory is proposed. Under the condition of limited incentive budget, the equilibrium solution between terminal devices and edge servers and the minimum edge model training delay are obtained. Considering the different number of terminal devices, a variable incentive training acceleration algorithm based on Stackelberg game is designed to minimize the training delay of a global model. Simulation results demonstrate that the proposed algorithm can effectively reduce the impact of terminal devices selfishness and improve the training speed of hierarchical federated learning global model.
-
Key words:
- Hierarchical Federated Learning (FL) /
- Game theory /
- Incentive mechanism
-
1. 引言
随着各种智能设备的不断普及,依赖数据和计算能力的机器学习技术得到了迅速发展。为了解决机器学习模型训练面临的数据安全问题,2017年谷歌提出了一种新的分布式机器学习方法——联邦学习(Federated Learning, FL)[1]。在联邦学习的架构中,设备用户的原始数据不会上传至数据中心,而是留在设备本地进行模型训练,设备只上传训练出的模型参数[2]。联邦学习将机器学习与在中心服务器中获取、存储和训练数据分离开来,实现了用户数据隐私保护[3]。
自从谷歌提出联邦学习这个概念后,联邦学习就成为机器学习领域的一个研究热点。McMahan等人[4]提出了一个基于模型平均的联邦学习实用模型,并进行了广泛的实证评估,这篇文章提出的联邦平均算法(Federated Average algorithm, FedAvg)成为一个经典的联邦学习算法。在此基础上,研究者针对FedAvg算法优化,进行了一系列研究。Li等人[5]在FedAvg的基础上引入了一个修正项,提出了FedProx (FedAvg with the Proximal term)算法,它允许在设备之间局部地执行可变量的工作,并且依赖这个修正项来确保方法的稳定性,解决了联邦学习固有的系统异质性和统计异质性问题。Mills等人[6]采用分布式Adam优化技术和模型压缩技术,提出了一种改进的FedAvg算法CE-FedAvg(Communication-Efficient FedAvg),该算法可以减少达到目标精度所需的通信轮次和每一轮需要加载的数据量,解决了联邦学习在物联网边缘计算的高效通信问题。Li等人[7]则从算法的公平性角度出发,提出了q-Fair FL算法,它重新权衡了FedAvg算法中的目标函数,在损失函数中分配更高的权重给损失较高的设备,从而使训练精度分布更加均匀。为了进一步优化联邦学习的性能,有研究者对传统联邦学习框架进行了改进。Liu等人[8]将基于边缘和基于云的联邦学习结合起来,提出了分层联邦学习架构,该分层联邦学习架构与基于云的联邦学习架构相比,模型训练时间和终端设备的能耗都得到了降低。Abad等人[9]通过分簇法研究了在蜂窝网中的分层联邦问题,优化了分层联邦学习的全局通信时延。
然而不管是针对传统联邦学习框架还是分层联邦学习框架,目前已有的研究大多集中在优化联邦学习算法以提高模型训练性能上,用于激励终端设备参加模型训练的激励机制在很大程度上却被忽视了。大多数流行的分布式训练算法都是使用小批量随机梯度下降[10],这在实际训练中,需要等待每一个同步批次中最慢的设备,导致随机优化的完全同步往往很慢,即受到“掉队效应”[11]的影响,这在异构网络中更为明显。同时,目前的大多数研究都做出了一个乐观的假设,即所有的终端设备在受到邀请时,都将无条件地参与联邦学习。这在现实世界中是不实际的,因为在联邦模型训练过程中,终端设备在计算和通信方面承受着相当大的开销[12],如果没有精心设计的激励机制,具有自私性的终端设备将不会拿出足够的资源甚至不愿意加入到联邦学习任务中来,这将导致十分严重的“掉队效应”,使得模型的训练时间大大增加,影响联邦学习的使用。
针对上述问题,本文在分层联邦学习框架下,考虑实际场景中每个边缘服务器下连接的终端设备数量不同,首先对模型训练过程进行了建模分析,得出一次全局模型训练的时间消耗和资源消耗。然后在终端设备和边缘服务器之间设计了两层主从博弈(即Stackelberg博弈[13]),通过调整分配给每个边缘服务器的激励预算值,提出了基于主从博弈的可变激励训练加速算法。该算法能够刺激终端设备更加积极地参与到联邦学习的任务中来,有效地减小“掉队效应”的影响,从而最小化全局模型训练时间。
2. 系统模型
如图1所示在分层FL架构中,假设有一个云服务器
C ,边缘服务器集合为N={i:i=1,2,⋯,N} ,边缘服务器i 下连接的终端设备集合为Mi={m:m=1,2,⋯,M} ,每个终端设备集合大小不相同。考虑完全同步的FL,完成一次全局训练过程如下:终端设备端。终端设备
m 基于本地的数据集来进行本地模型训练,假设所有的终端设备的本地数据集大小相同,为了达到相同的本地模型精度θ∈(0,1) ,终端设备m 需要进行迭代的次数可以表示为[14]L(θ)=μlog2(1θ) (1) 其中,
μ 是一个取决于数据集大小和机器学习任务的参数。fi:m 表示边缘服务器i 下的终端设备m 进行本地计算时的CPU频率,Cm 表示完成1次本地迭代计算任务需要的总的CPU转圈数。那么完成L(θ) 次本地迭代,边缘服务器i 下的终端设备m 所消耗的能量和时间可以分别表示为ecmpi:m=L(θ)kCm(fi:m)2 (2) tcmpi:m=L(θ)Cmfi:m (3) 其中,
k 是一个取决于芯片结构的系数。为了使终端设备投入更多的计算资源以减小本地训练模型所花的时间,边缘服务器端会引入激励机制,即边缘服务器i 向其下面的终端设备提供奖励,qi:m 表示边缘服务器i 对其服务范围内的终端设备m 提供的CPU频率单价,那么终端设备m 迭代一次获得的收入为qi:mfi:m 。本地模型精度达到θ 之后,终端设备向对应的边缘服务器上传训练得到的参数。假设每个边缘服务器能够分配给终端设备的信道总带宽均为B ,边缘服务器将其均分给下面的每一个终端设备,那么传输率可以表示为rm→i=Bmlog2(1+hmumN0) (4) 其中,
N0 为噪声功率,um 为传输功率,hm 为信道增益。终端设备m 完成一次参数传输至边缘服务器i 所需要的时间为tcomm→i=dmrm→i (5) 其中,
dm 表示终端设备m 传输的参数量,所需要的能量为ecomm→i=tcomm→ium (6) 边缘服务器端。边缘服务器
i 在收到终端设备传来的参数后,会进行聚合然后再分发下去。以上的过程会迭代多次,直到所有的边缘服务器达到一个相同边缘服务器模型精度ε 。为了达到所需精度,对于一个凸的机器学习任务,边缘服务器需要迭代的次数可以表示为[14]I(ε,θ)=δ(log2(1ε))1−θ (7) 其中,
δ 是取决于学习任务的参数。由于边缘服务器通常拥有强大的计算能力和稳定的能量供给,所以边缘服务器端的模型参数聚合和分发所产生的时间与能量消耗在本文中没有考虑。对于终端设备来说,接收分发下来的参数所消耗的时间和能量相比于它上传参数要小得多,在这里本文也不予考虑。因此,边缘服务器i 完成I(ε,θ) 次迭代,所需要的时间为Ti=I(ε,θ)[maxm∈Mi(tcmpi:m)+tcomm→i] (8) 终端设备
m 消耗的总能量为Ei:m=I(ε,θ)(ecmpi:m+ecomm→i) (9) 边缘服务器会向云服务器上传满足精度要求的边缘服务器模型参数,假设边缘服务器的传输率都为
ri ,上传的参数量为di ,那么上传1次参数,边缘服务器的时间和能量消耗分别为tcomi→C=diri (10) ecomi→C=uitcomi→C (11) 其中,
ui 表示边缘服务器的传输功率。云服务器端:在接收到边缘服务器端传来的模型参数后,云服务器端进行参数聚合并更新模型,这样就完成了一次全局迭代。相较于其他环节,这个聚合时间非常短,本文也不考虑。那么,一次全局迭代,所需要的总时间为
T=maxi∈NTi+tcomi→C (12) 云服务器负责分配激励预算给每个边缘服务器,总预算为
V 。边缘服务器i 所分配到的激励预算为Wi 。定义边缘服务器i 对于一次全局迭代的时间贡献度为1Ti ,时间贡献度越大,表示边缘服务器i 迭代到所要求的精度的时间越短。云服务器会基于每个边缘服务器的时间贡献度来给予边缘服务器奖励,云服务器端总的奖励为Rc ,边缘服务器i 从云服务器端获得的奖励定义为Rc1Ti 。3. 基于主从博弈的激励机制
3.1 博弈问题定义
本文考虑信息对称场景,即每个终端设备会在训练开始前向其所连接的边缘服务器报告自己能够提供的最大算力、本地数据集大小等先验信息。在终端设备层和边缘服务器层之间引入主从博弈(即Stackelberg博弈)。将终端设备作为跟随者(follower),边缘服务器作为领导者(leader)。边缘服务器
i 决定给每个终端设备m 的CPU频率单价qi:m=qi:1,qi:2,⋯,qi:m 。根据报价,每个边缘服务器服务范围内的各个终端设备向其报告自己用于参与训练的CPU频率fi:m=fi:1,fi:2,⋯,fi:m ,然后边缘服务器再调整单价qi:m 。边缘服务器i 下的终端设备m 的效用函数可以表示为Ui:m=I(ε,θ)L(θ)qi:mfi:m−ηEi:m (13) 其中,第1项为终端设备
m 完成一次全局迭代获得的激励奖励,第2项为总的计算和传输能耗。系数η 用于匹配效用函数前后两项的数量级。边缘服务器i 的效用函数可以表示为Ui=Rc1Ti−∑m∈Miqi:mfi:m−ηecomi→C (14) 其中,第1项为边缘服务器
i 从云服务器获得的奖励,第2项为边缘服务器i 向下面的终端设备支出的激励总和,第3项为边缘服务器i 上传参数的传输能耗。博弈框架如图2所示。首先明确引入激励机制的目的是减小完成一次全局迭代的时间。云服务器作为激励预算分配者(Allocator),负责为每个边缘服务器分配用于激励的预算
Wi ,然后每个边缘服务器和其服务范围内的终端设备形成1个博弈簇,进行Stackelberg博弈。在1个博弈簇内,每个终端设备m∈Mi 根据边缘服务器i 的激励报价,决定自己投入训练任务的CPU频率,从而最大化自己的效用函数。故会产生m 个下层子博弈问题。边缘服务器i 根据其服务范围内的所有终端设备的CPU频率投入情况,再重新调整自己给出的激励报价,最大化自己的效用函数。故产生一个上层子博弈问题。一个博弈簇内上下两层子博弈反复进行,直到达到纳什均衡点。下层子博弈问题定义为
max fi:mUi:m=I(ε,θ)L(θ)qi:mfi:m−ηEi:m s.t. fmini:m≤fi:m≤fmaxi:m} (15) 上层子博弈问题定义为
max qi:mUi=Rc1Ti−∑m∈Miqi:mfi:m−ηecomi→C s.t. ∑m∈Miqi:mfi:m≤Wi∑i∈NWi≤V} (16) 3.2 博弈均衡解分析
3.2.1 下层子博弈求解
为了找到下层子博弈的均衡解,首先对
Ui:m 求1阶导数,可以得到∂Ui:m∂fi:m=I(ε,θ)L(θ)qi:m−2ηI(ε,θ)L(θ)kCmfi:m (17) 因为
∂2Ui:m∂f2i:m=−2ηI(ε,θ)L(θ)kCm<0 (18) 所以
Ui:m 是严格凹的,保证了纳什均衡解存在且唯一。可得均衡解为f∗i:m(qi:m)=max{qi:m2ηkCm,fmaxi:m} (19) 3.2.2 上层子博弈求解
边缘服务器
i 的效用函数式(14)由3部分组成,(1)Rc1Ti ,(2)−∑m∈Miqi:mfi:m ,(3)−ηecomi→C 。由前面系统模型的描述中可知,−ηecomi→C 可视为一个常量,所以下面分析(1)和(2)的凹凸情况。分析(1),令
h=Rc1Ti 并代入f∗i:m 可得表达式h(qi:m)=Rc1I(ε,θ)[maxm∈Mi(2ηkC2mL(θ)/qi:m)+tcomm→i] (20) h(qi:m) 的黑塞矩阵定义为A=(∂2h∂q2i:1⋯∂2h∂qi:1∂qi:m⋮⋱⋮∂2h∂qi:m∂qi:1⋯∂2h∂q2i:m) (21) 由于
∂2h∂q2i:m=−4ηkRcL(θ)I(ε,θ)2C2mtcomm→i(2ηkL(θ)I(ε,θ)C2m+I(ε,θ)tcomm→iqi:m)3 (22) ∂2h∂qi:m∂qi:n=0 (m≠n) (23) 所以
h(qi:m) 的黑塞矩阵可进一步表示为A=(−4ηkRcL(θ)I(ε,θ)2C2mtcom1→i(2ηkL(θ)I(ε,θ)C2m+I(ε,θ)tcom1→iqi:1)3…0⋮⋱⋮0⋯−4ηkRcL(θ)I(ε,θ)2C2mtcomm→i(2ηkL(θ)I(ε,θ)C2m+I(ε,θ)tcomm→iqi:m)3) (24) 矩阵
A 的所有特征值均小于等于0,矩阵A 负定,所以h(qi:m) 为凹函数。分析(2),令
g=−∑m∈Miqi:mfi:m ,代入f∗i:m 可得表达式g(qi:m)=−∑m∈Mi12ηkCmqi:m2 (25) g(qi:m) 对qi:m 求2阶导可得∂2g∂q2i:m=−1ηkCm<0 (26) 所以
g(qi:m) 为严格凹的。根据以上分析可知,边缘服务器i 的效用函数Ui 为一个凹函数。下面求解上层子博弈。式(16)等效于
min qi:mUi=−Rc1Ti+∑m∈Miqi:mf∗i:m+ηecomi→C s.t. y1=∑m∈Miqi:mf∗i:m−Wi≤0y2=∑i∈NWi−V≤0} (27) 上述问题变成一个凸问题,可以用拉格朗日乘数法来解。其拉格朗日函数可以表示为
L(qi:m,λ1,λ2)=−Rc1Ti+λ1(∑m∈Miqi:mf∗i:m−Wi)+λ2(∑i∈NWi−V ) (28) 通过KKT条件,可以推导出充分必要条件
∂L∂qi:m=−2ηkRcL(θ)I(ε,θ)C2m(2ηkL(θ)I(ε,θ)C2m+I(ε,θ)tcomm→iqi:m)2+λ11ηkCmqi:m=0 (29) λ1y1=λ1(∑m∈Miqi:mf∗i:m−Wi)=λ1(∑m∈Mi12ηkCmq2i:m−Wi)=0 (30) λ1≥0 (31) 由条件式(31)可得
λ1=2η2k2RcL(θ)I(ε,θ)C3mqi:m(2ηkL(θ)I(ε,θ)C2m+I(ε,θ)tcomm→iqi:m)2>0 (32) 所以
∑m∈Mi12ηkCmq2i:m−Wi=0 (33) 表明解是存在的。当边缘服务器
i 给每一个终端设备m 的qi:m 相同时,可解得qi:m=√2ηkCmmWi (34) 这个特殊解的实际意义在于如果
qi:m 不相同,那么时间会由算得最慢的那个终端设备决定,从而使得边缘服务器i 的效用函数降低。只有当边缘服务器i 将激励预算Wi 全部使用,且分配下去的qi:m 相等时,边缘服务器i 以及终端设备m 这一簇的时间消耗Ti 才能达到最小,从而使得边缘服务器i 的效用函数达到最大值。3.3 博弈执行过程
初始化阶段,云服务器将总预算
V 均分给每个边缘服务器,此时W1=W2=⋯=Wi=Vi 。步骤1 边缘服务器
i 刚开始随意分配激励单价qi:m ,终端设备m 会提供相应的算力,使得自己的效用函数Ui:m 达到最大。此时边缘服务器i 会发现它完成I(ε,θ) 次迭代的时间是受限于计算最慢的那个终端设备,故它会重新分配qi:m ,激励最慢的终端设备增加算力,从而减小Ti ,增加自己的效用函数Ui 。最终边缘服务器i 会根据终端设备的个数,均分Wi ,此时的qi:m 即为前面求出的特殊解式(34)。步骤2 当每个边缘服务器和它连接的终端设备达到均衡点后,边缘服务器
i 得到了Ti 和最终的效用函数Ui 。此时每个边缘服务器i 会将最终的Ti 上报给云服务器。为了使得一次全局迭代的总时间达到最小,云服务器会根据每个边缘服务器的Ti 大小值调整激励预算分配比例。步骤3 得到重新分配的激励预算后,每个边缘服务器再重复步骤1,然后云服务器重复步骤2,直到每个边缘服务器的
Ti 值最终相等。整个系统达到稳定的状态,且完成一次全局迭代的时间达到最短。根据上述过程,本文提出了全局模型训练的加速算法,如算法1所示。
算法1 基于主从博弈的可变激励训练加速算法 输入:N={i:i=1,2,⋯,N},Mi={m:m=1,2,⋯,M},计算任务Task,数据集D, W1=W2=⋯=Wi=Vi。 输出:激励预算分配的均衡点Wi={Wi,i∈N},Qi:m={qi:m,m∈Mi} ,终端设备m提供的算力均衡解F*i:m={f∗i:m,m∈Mi}。 (1) repeat (2) for i in N do
(3) 边缘服务器i分配激励单价{qi:m,m∈Mi},激励单价需满足条件∑m∈Miqi:mfi:m≤Wi。终端设备m会提供相应的算力
{f∗i:m=max{qi:m2ηkCm,fmaxi:m},m∈Mi},使得自己的效用Ui:m达到最大。(4) if tcmpi:m≠tcmpi:n(m≠n) then (5) 边缘服务器i重新分配qi:m,使得自己的效用函数Ui达到最大,同时得到时间Ti。 (6) end for (7) if Ti<Tj(i≠j) then (8) 云服务器重新分配V(减小Wi,增大Wj)。 (9) Until Ti=Tj(i≠j) 4. 仿真结果与分析
本文用MNIST数据集[15]来评估所提出的激励机制的性能。随机分配相同数量的10个种类的训练数据给每个终端设备,用随机梯度下降来训练本地模型,学习率为0.1。其他一些参数为:完成1次本地迭代计算任务需要的总的CPU转圈数
Cm=5000 ,边缘服务器i 下的终端设备m 进行本地计算时的CPU频率fi:m∈[1,109] Hz,信道总带宽B=106 Hz,噪声功率N0=10−8 W,传输功率um=200 mW,终端设备m 传输的参数量dm=2500 bit,终端设备m 进行迭代的次数L(θ)=2 ,边缘服务器需要迭代的次数I(ε,θ)=5 ,芯片结构的系数k=2×10−28 ,系数η=1018 。(1) 边缘服务器与终端设备的博弈迭代过程。为了评估这个过程,本文对一个博弈簇进行仿真实验,在激励预算足够的情况下,探究边缘服务器给出的激励单价对终端设备效用以及边缘服务器自身效用的影响,同时验证引入激励机制能够刺激终端设备投入更多的计算资源,减少本地计算时间。
图3显示的是边缘服务器给出的CPU激励单价对单个终端设备效用值的影响。可见,单个终端设备的效用值随着激励单价的增加逐渐上升并最终达到最大值稳定下来。这是因为随着激励单价
q 的增加,终端设备得到的奖励越来越多,导致其效用不断增加。当激励单价增加到某个值,如图中的q=20 时,终端设备会将所有的计算资源都投入到本地模型训练任务中,此时它获得的奖励值达到最大,故效用值也达到最大。而如果q 继续增加,由于该终端设备之前就已投入了全部的CPU频率资源,所以边缘服务器为了节省激励成本,实际上并不会继续增加真正给到该终端设备的激励单价,故该终端设备的效用值保持最大值不变。图3虽然是显示的单个终端设备效用与激励单价的关系,但是该博弈簇中的所有终端设备都遵循这个关系,当每个终端设备效用值达到最大时,下层子博弈达到均衡点。
图4显示的一个边缘服务器给出的激励单价对其效用值的影响。可以看到,边缘服务器的效用值随着激励单价的增加而增加,最后达到最大值并稳定下来。这是因为增加激励单价
q ,能够刺激终端设备提供更多的算力到模型训练任务中来,从而减小时间Ti ,增大了该边缘服务器对于一次全局迭代的时间贡献度。虽然增加激励单价会导致边缘服务器的激励支出增加,但是它能够从云服务器端获得更多的奖励,故其效用值最终增加。当激励单价增加到某个值,比如图中的q=20 时,终端设备将全部算力投入计算,时间Ti 达到最小,该边缘服务器效用值达到最大。同样地,之后激励单价如果继续增加,边缘服务器为了节约激励成本,实际上并不会给予已经完全激励了的终端设备更高的激励单价,故终端设备的效用值保持最大值不变。当一个博弈簇中的边缘服务器的效用达到最大时,上层子博弈达到均衡点。当上下两层子博弈同时达到均衡点时,该博弈簇内的Stackelberg博弈达到纳什均衡点。
图5显示的是单个终端设备的本地计算时间与边缘服务器给出的激励单价的关系。可以看到,终端设备的本地计算时间随着激励单价
q 的增加逐渐减少,因为终端设备提供了更多的本地计算资源。当激励单价q 增大到某个值,比如图中的q=20 时,该终端设备贡献出全部的算力,本地计算时间达到最小。此后q 继续增加,由于没有多余的计算资源,本地计算时间不会再继续减小,故保持最小值不变。以上的仿真实验虽然是对一个博弈簇,在激励预算分配足够的情况下进行的实验,但是所有的博弈簇中的博弈迭代过程都遵循上述分析的结果。并且在激励预算不够的情况下,边缘服务器最终会根据其服务范围内的终端设备个数,均分激励预算,即满足前文解出的特殊解
qi:m=√2ηkCmmWi ,从而博弈达到纳什均衡点,最小化本地计算时间Ti 。(2) 云服务器激励预算分配达到平衡点的过程。假设边缘服务器数量为2,边缘服务器1下连接的终端设备数量为1 000个,边缘服务器2下连接的数量为1 200个,云服务器能够分配的总激励预算
V=40000 。刚开始时分配情况为W1=W2=V/2=20000 ,然后云服务器会调整分配情况,一部分分给W1 ,剩余部分全部分给W2 ,即W2=V−W1 。从图6可以看到,刚开始均分时,由于边缘服务器1连接的终端设备数量更少,故
T1 <T2 ,全局训练时间取决于较大者。然后云服务器开始减小W1 ,同时等量增大W2 。T1 随着W1 的减小而增大,因为边缘服务器1连接的终端设备得到的激励在减小,用于计算的CPU频率降低,本地计算时间增加,导致最终T1 增大。W1 减小,相应地W2 在增加,边缘服务器2获得更多的激励预算,故T2 逐渐减小。当云服务器分配W1=8700 ,W2=31300 时,T1=T2 ,如图6中的两条曲线的交点处所示,此时全局训练时间达到最小,激励预算分配达到均衡点。(3)将本文提出的基于主从博弈的可变激励训练加速算法与没有设计激励机制的算法[8]进行比较。边缘服务器个数设置为2个,每个边缘服务器下连接不同数量的终端设备。两个边缘服务器连接的终端设备总数分别设置为800个、1 000个、1 200个。
在没有设计激励机制的算法中,为了反映真实情况下终端设备的自私性,本文假设会有一定比例的终端设备不会完全贡献自己的资源甚至不愿意参与到联邦学习中。
从图7可以看到,在没有激励机制的情况下,全局模型的训练时延随着终端设备数的增加而减小,这是因为虽然设备存在自私性,但是随着设备的基数增加,总的算力资源是增加的。而在本文提出的激励机制算法中,由于激励预算是一定的,所以随着设备数量的增加,每个设备能够分到的激励量在减小,所以总的算力在减小,导致总时间增加。但是,在不同终端设备总数的情况下,与没有激励机制的算法相比,本文提出的带有激励机制的算法均能够有效地刺激终端设备积极参与到训练中来,提供更多的资源到训练过程中,从而有效降低了全局模型训练的总时延。
5. 结束语
本文面向分层联邦学习框架,针对联邦学习中终端设备存在自私性而影响全局模型训练时间的问题,设计了基于主从博弈的激励机制。该机制通过对分层联邦学习模型训练过程进行建模,利用可变激励训练加速算法,不断调整分配给边缘服务器的激励预算,使得边缘服务器和终端设备达到纳什均衡点的同时,最小化1次全局模型训练时间。仿真结果表明,本文所提算法能够有效地降低终端设备自私性带来的影响,优化分层联邦学习全局模型的训练时延。
-
算法1 基于主从博弈的可变激励训练加速算法 输入:N={i:i=1,2,⋯,N},Mi={m:m=1,2,⋯,M},计算任务Task,数据集D, W1=W2=⋯=Wi=Vi。 输出:激励预算分配的均衡点Wi={Wi,i∈N},Qi:m={qi:m,m∈Mi} ,终端设备m提供的算力均衡解F*i:m={f∗i:m,m∈Mi}。 (1) repeat (2) for i in N do
(3) 边缘服务器i分配激励单价{qi:m,m∈Mi},激励单价需满足条件∑m∈Miqi:mfi:m≤Wi。终端设备m会提供相应的算力
{f∗i:m=max{qi:m2ηkCm,fmaxi:m},m∈Mi},使得自己的效用Ui:m达到最大。(4) if tcmpi:m≠tcmpi:n(m≠n) then (5) 边缘服务器i重新分配qi:m,使得自己的效用函数Ui达到最大,同时得到时间Ti。 (6) end for (7) if Ti<Tj(i≠j) then (8) 云服务器重新分配V(减小Wi,增大Wj)。 (9) Until Ti=Tj(i≠j) -
[1] MCMAHAN B and RAMAGE D. Federated learning: Collaborative machine learning without centralized training data[EB/OL]. https://starrymind.tistory.com/180, 2017. [2] NIKNAM S, DHILLON H S, and REED J H. Federated learning for wireless communications: Motivation, opportunities, and challenges[J]. IEEE Communications Magazine, 2020, 58(6): 46–51. doi: 10.1109/MCOM.001.1900461 [3] LIU Yi, PENG Jialiang, KANG Jiawen, et al. A secure federated learning framework for 5G networks[J]. IEEE Wireless Communications, 2020, 27(4): 24–31. doi: 10.1109/MWC.01.1900525 [4] McMAHAN B, MOORE E, RAMAGE D, et al. Communication-efficient learning of deep networks from decentralized data[C]. The 20th International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, USA, 2017: 1273–1282. [5] LI Tian, SAHU A K, ZAHEER M, et al. Federated optimization in heterogeneous networks[C]. Machine Learning and Systems 2020, Austin, USA, 2020, 2: 429–450. [6] MILLS J, HU Jia, and MIN Geyong. Communication-efficient federated learning for wireless edge intelligence in IoT[J]. IEEE Internet of Things Journal, 2020, 7(7): 5986–5994. doi: 10.1109/JIOT.2019.2956615 [7] LI Tian, SANJABI M, BEIRAMI A, et al. Fair resource allocation in federated learning[C]. The 8th International Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2019: 1–27. [8] LIU Lumin, ZHANG Jun, SONG S H, et al. Client-edge-cloud hierarchical federated learning[C]. 2020 IEEE International Conference on Communications (ICC), Dublin, Ireland, 2020: 1–6. [9] ABAD M S H, OZFATURA E, GUNDUZ D, et al. Hierarchical federated learning ACROSS heterogeneous cellular networks[C]. 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Barcelona, Spain, 2020: 8866–8870. [10] SUN Haifeng, LI Shiqi, YU F R, et al. Toward communication-efficient federated learning in the internet of things with edge computing[J]. IEEE Internet of Things Journal, 2020, 7(11): 11053–11067. doi: 10.1109/JIOT.2020.2994596 [11] SHI Yuanming, YANG Kai, JIANG Tao, et al. Communication-efficient edge AI: Algorithms and systems[J]. IEEE Communications Surveys & Tutorials, 2020, 22(4): 2167–2191. doi: 10.1109/COMST.2020.3007787 [12] LUO Siqi, CHEN Xu, WU Qiong, et al. HFEL: Joint edge association and resource allocation for cost-efficient hierarchical federated edge learning[J]. IEEE Transactions on Wireless Communications, 2020, 19(10): 6535–6548. doi: 10.1109/TWC.2020.3003744 [13] KHAN L U, RAJ PANDEY S, TRAN N H, et al. Federated learning for edge networks: Resource optimization and incentive mechanism[J]. IEEE Communications Magazine, 2020, 58(10): 88–93. doi: 10.1109/MCOM.001.1900649 [14] TRAN N H, BAO Wei, ZOMAYA A, et al. Federated learning over wireless networks: Optimization model design and analysis[C]. IEEE INFOCOM 2019-IEEE Conference on Computer Communications, Paris, France, 2019: 1387–1395. [15] LECUN Y, BOTTOU L, BENGIO Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278–2324. doi: 10.1109/5.726791 期刊类型引用(3)
1. 王志良,何刚,俞文心,许康,文军,刘畅. 边缘场景下动态联邦学习优化方法. 计算机技术与发展. 2024(02): 98-104 . 百度学术
2. 宋彪,薛涛,刘俊华. 基于学习博弈和契约论的分层联邦学习隐私保护激励机制. 计算机系统应用. 2024(07): 26-38 . 百度学术
3. 康海燕,冀珊珊. 面向无线边缘网络的分层Stackelberg博弈群体激励方法. 电子学报. 2024(07): 2382-2392 . 百度学术
其他类型引用(4)
-