跨筒仓联邦学习的能量有效和时间敏感任务分配机制

沙特国王大学学报跨筒仓联邦学习卢建峰a，潘邦奇a，于娟a，刘文超b，姜文超b，韩建民a，叶志伟ca浙江师范大学数学与计算机科学学院，浙江金华321004b广东工业大学计算机学院，广州510006c湖北工业大学计算机学院，湖北武汉430068阿提奇莱因福奥文章历史记录：2022年12月4日收到2023年2月15日修订2023年3月7日接受2023年3月14日网上发售保留字：跨筒仓联邦学习任务分配多目标优化激励机制博弈论A B S T R A C T联邦学习（FL）是一种新型的分布式学习框架，其中具有模型的客户端可以协同训练高质量的全局模型，同时保持其本地数据的隐私。数据集的异构性使得跨竖井场景中每个客户端的全局聚合和本地培训需求不一致。虽然许多努力致力于提高跨筒仓FL的效率，跨筒仓FL的任务分配设计仍然是一个悬而未决的问题。为了优化跨竖井FL的能量消耗和训练时间，我们提出了一种新的能量有效和时间敏感的任务分配（ETTA）机制。具体而言，我们将客户从能量效率最大化的角度出发，分析了基于边际成本收益均衡的最优解的条件，并针对需要轻量级机制的跨竖井FL场景设计了一种近似算法在训练时间最小化方面，我们将此目标建模为极小极大问题，并给出了具有Pareto最优性的解析解。为了保证任务分配达到激励相容，我们进一步设计了一个效用转移选择函数来激励自私客户之间的诚实合作。最后，我们对ETTA的性能进行了大量的实验，以证明它的性能优于最先进的技术，并能在不诚实的环境中保持稳定版权所有©2023作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着物联网技术的高速发展，许多客户端的设备一直在不断地产生大量数据，这对机器学习模型具有极好的价值（Mohammadi et al.，2018年）。然而，传统的机器学习面临着隐私泄露的风险，因为它们通常从分布式设备收集隐私数据，并使用中央服务器训练它们的模型。为了有效地利用客户*通讯作者。电 子 邮 件 地 址 ： lujianfeng@zjnu.edu.cn （ J. Lu ） ， panbangq@zjnu.edu.cn （ B.潘 ） ， yujuan@zjnu.edu.cn （ J. Yu ） ， jiangwenchao@gdut.edu.cn （ W. Jiang ） ，hanjm@zjnu.cn（J. Han），hgcsyzw@hbut.edu.cn（Z.Ye）。沙特国王大学负责同行审查Google提出了联邦学习（FL）作为分布式机器学习的新范式，它在训练模型时保护客户的隐私，而不共享任何行数据（McMahan et al.，2017年）。通过FL技术，可以在多领域应用中对传感数据进行协同模型训练，例如金融风险评估和医疗数据分析（Li et al.，2020年a）。根据客户的特点，FL可以分为两种类型：跨设备FL和跨筒仓FL（Kairouz等人，2021年）。如图1（a）所示，在跨设备FL中，中央服务器是模型所有者，其使用具有本地数据的客户端来参与全局聚合。作为对模型不感兴趣的设备，客户需要补偿以支付本地培训费用。而在跨竖井FL中，如图1（b）所示，客户端是模型所有者，其启动FL过程以提高模型的准确性，因此中央服务器仅用于全局聚合，而不再使用客户端。尽管跨设备FL受到了极大的关注，但跨筒仓FL具有广阔的应用前景。例如，具有不同数据集的医院进行成像https://doi.org/10.1016/j.jksuci.2023.03.0031319-1578/©2023作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comJ. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报64图1.一、（a）跨设备FL和（b）跨筒仓FL的系统框架通过跨筒仓FL训练模型进行诊断（Huang等人， 2021），银行和保险公司通过跨筒仓FL合作进行金融数据分析（Long等人，2020年）等，尽管在实践中广泛需要，任务分配设计的交叉-由于客户之间复杂的交互结构和难以量化的边际效应，筒仓FL仍然是一个悬而未决的问题。一方面，模型的训练会产生成本（Luo et al.，2021年）。由于计算能力的异质性，客户端的训练能耗也不同。为此，我们必须为模型训练找到一个任务分配，以最大化所有客户端的总效用（即，另一方面，客户也希望在特定的截止日期内完成模型训练（Tang和Wong，2021）。因此，任务分配应该通过将任务分配给适当的客户端来缩短模型训练时间。尽管有必要为跨发射井FL设计任务分配，但它提出了许多挑战。首先，客户之间存在复杂的社会效用和训练时间可以被视为多目标优化问题（Huang等人，#20022;，解决问题需要时间。因为当一个客户改变其培训计划时，其他客户的模型性能和预期培训时间也会相应改变第二，使社会效用最大化的任务分配不一定满足每个客户上述两个优化问题构成了一个多目标优化问题，它需要帕累托最优性（Censor，1977）。第三，任务分配面临着客户作弊的挑战 与跨设备FL相比，跨竖井FL的任务分配取决于模型的估值和每个客户端的本地训练成本，这是他们的私人信息（Lu等人，2022年）。一个自私的客户端可能会通过报告错误的信息来为自己的利益分配任务。例如，一个客户表示，她的培训成本是巨大的，因此有效的任务分配然而，训练好的模型是一种公共产品，这个客户可以直接获得公共模型带来的收益，而无需付费。这种行为被称为搭便车，这将损害客户参与模型培训的积极性和社会效用。目前，针对模型训练的任务分配设计主要是重点关注跨器械FL（Pilla，2021; Chen等人，2021; Lim等人，2021年）。然而，中央服务器只能在跨设备FL中基于其评估来建立最满意的训练计划，而跨竖井FL不能部署这些工作。因为每个参与者对模型的评价不同，而且其本地培训的成本在跨筒仓FL中也不同（Tang和Wong，2021），没有这样的时间表，最大限度地为每个人的效用。例如，一些客户对模型的评价很高，因此他们希望中央服务器调用尽可能多的数据（增加客户参与）以优化模型性能（Lu等人，2022年a）。而另一些客户端的训练成本很高，他们希望中心服务器减少模型训练，以节省他们的训练成本。同时，现有的工作只考虑了跨竖井FL中客户端本地训练时间的优化（Huang例如，2022b），并且全局模型的训练时间需要通过任务分配设计进一步优化。另一方面，由于数据量的取值范围属于整数，任务分配问题的最优解 比 较 复 杂 （ Sabir ， 2022 ） ， 需 要 近 似 算 法 来 节 省 求 解 时 间（Guerrero Sánchez et al.， 2020年）。 为此，本文集中讨论了跨学科的任务分配问题。Silo FL，它有无数的工业应用。本文设计了一种能量有效、时间敏感的任务分配机制（ETTA），以优化跨竖井FL中客户端的效用和训练时间为提高能源效益，科学，ETTA通过以下原则最大化社会效用：边际均衡为了减少计算开销，ETTA对目标函数执行LP松弛，并使用均值来近似Pareto最优。最后，基于Groves机制的效用转移我们的主要贡献概述如下：我们将客户的需求在跨筒仓FL中建模为多目标优化。就我们而言，这是优化模型训练效率的第一项工作（模型准确度与训练成本）和模型训练时间。该模型允许中央服务器通过权重系数来平衡能量效率和训练时间。我们开发了ETTA机制来优化任务分配，该机制基于边际递减模型精度实现了最佳社会工作负载。在给定各目标权重因子的情况下，通过调整各客户的工作量，使训练时间和社会效用达到帕累托最优。我们设计了一个效用传递函数来稳定地实现任务分配。据我们所知，本文是第一个工作，考虑真实性的跨筒仓FL机制●●●J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报658Xsnn2NnnXsnn2Nn8n2N设计该函数调整客户效用的计算方法，使自私的客户不能通过欺骗中心服务器来获得额外的利益。所提出的效用传递函数确保了客户之间的诚实合作。我们广泛地评估了ETTA在真实世界和合成数据集上的性能 并以平均算法和贪婪算法为基准，与所提出的机制进行比较。实验结果表明，ETTA优于其他基线的社会效用，培训时间，和激励兼容性。本文的其余部分组织如下：我们首先在第2节讨论相关工作。然后我们介绍了系统模型，并在第三节中形式化的任务分配。在第四节中，我们分别分析了两个目标函数，并设计了相应的算法。在第五节中，我们设计了一个任务分配的效用传递函数。性能评价和结果分析见第6节。最后在第7节中得出结论。2. 相关工作在本节中，我们介绍了FL中效率优化的相关工作及其对跨筒仓FL的适用程度2.1. FL的能效许多现有的工作致力于优化模型所有者的培训效率。对于模型性能，Wang et al. （2021）提出了一种基于图卷积网络的算法，该算法优化FL中的设备采样策略以最小化训练准确性损失。为了节省计算能耗，Luo等人（2021）构建了一种基于低成本采样的算法，以选择控制变量，从而在确保模型收敛的同时最小化训练成本。为了节省通信能耗，Yang等人（2020）提出了一种迭代算法，以最小化FL系统在无线通信网络上的通信和计算能耗。对于训练时间，Lu等人（2022 b）使用方差缩减方法来校正客户端异质性的影响，以使模型更快收敛并减少训练时间。然而，由于跨竖井场景中模型的所有者是多个客户，单一目标的优化只能满足部分客户的需求，因此上述工作并不能直接提高跨竖井FL的效率。2.2. FL培训时间一些研究对FL的训练时间进行了优化，但仍有改进的 Tran等人（2019 a）设计客户端选择方案，以提高FL收敛速度。但在跨筒仓FL中，由于所有客户都在进行培训，因此无法选择客户模型的参与者和受益者为了解决这个公共2.3. FL机制的策略证明由于客户是自私和理性的，FL机制的防策略性一些机制是从中央服务器的角度设计的。Zhan等人（2020）研究了FL激励机制，以模拟客户为模型培训做出贡献。Zhang et al.（2021 b）提出了一种基于声誉和反向拍卖的FL激励机制，以在有限的预算下选择和奖励客户。有些是从社会效用的角度设计的。Le et al.（2021）建立了一个原始-对偶拍卖机制，以最大化FL的社会福利。（2020）提出了一种众包框架，以促进FL中模型传输期间的通信效率。但这些机制仅适用于跨设备场景，因为在跨竖井FL中，客户端2.4. 交叉筒仓FL一些研究关注跨筒仓外语，但缺乏对任务分配的分析一方面，一些工作旨在提高跨竖井FL的模型训练效率。例如，Majeedet al.（2020）提出了一种基于水平流的联邦模型，用于使用时间相关特征进行流量分类。Marfoq等人（2020）定义了基于最大加线性系统的交叉竖井FL的拓扑设计问题，以找到系统的拓扑吞吐量数。然而，这些工作没有考虑客户端另一方面，也有一些著作专门针对跨仓物流设计了激励机制。Tang and Wong（2021）从公共产品的角度提出了跨仓物流的激励机制Zhang等人（ 2022年）3. 系统模型3.1. 系统设置我们考虑由中央服务器和一组N ^f1;···; Ng客户端组成的跨竖井FL系统。每个客户端拥有一个本地数据集Dn，并且需要选择一个子 集 SnDn 进 行 本 地 训 练 。 让 s n 表 示 所 选 子 集 Sn 的 数 据 大 小 ， 即sn¼jSnj;n2N。客户端希望找到全局模型的理想权重x，使数据集上的损失函数最小化（Li等人，2020年b）：Lx1XsnLnx;1其中Lnx是数据集Sn上的局部损失函数。为了获得理想的权重x，中央服务器和客户端在训练轮中执行交叉竖井FL。 在每个训练轮r中，训练者更新本地模型权重Xr;n2N，并将Xr发送到中央服务器。 中央服务器聚合本地模型以更新全局模式（McMahan等人，2017年），即，xr¼1Xsnxr：102mm商品困境，Tang和Wong（2021）提出了一种在给定期限内完成模型训练但对于优化问题，这个截止日期是优先的。训练时间过长会导致资源使用不当，训练时间过短为了改善这一缺陷，Huanget al.（2022 b）考虑模型性能和局部训练时间对问题进行建模。然而，单个客户端的局部训练时间缩短全局模型的训练时间需要从任务分配的角度考虑。n2N一方面，上述过程导致不同的客户端计算和通信成本。另一方面，客户可能会从训练模型中获得不同的收入。因此，一些客户可能需要额外的补偿;否则，合作将是不可持续的.3.1.1. 准确性和训练时间根据Li等人（2014）的研究，预期的准确性损失会降低全球模型有一个上限●J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报66.pkkk1Ppn282 ¼ð···ÞnX¼ð···ÞNNf·· ·· ·gfgCsmaxn2Nnn-n个nn-n个nnnnnNn2Nfn然而，Eq.（11）取决于客户O1 = s R 1 =R，其中s是用于局部训练的数据的总大小，即，ksk1¼n2Nsn. 我们使用A_s_n来表示全局模型的准确性训练上述原则要求数据大小分配满足最小温度（℃）;10 ℃其中n<$$>n1;···;nN<$属于笛卡尔积N<$Pn2NNn，As113集合N n1/20;jDnj]\Z;8n2N。;1其中，s1=1;···;sn= 1，R是模型训练轮数。根据等式（9）Eq.（10）、我们需要解决一个多-目标优化，以满足所有客户的需求，8>maxUsmaxxXVnsmax;每轮的持续时间可以表示为Tang和Wong：minCsminmaxnsnlnkto：. slkS2Ns2Nn2Nfnn其中ln表示处理训练所需的CPU周期信息，如准确性收入系数un和CPU free-频率;频率我们将个人简档rn;rn2H;8n2N定 义 为在客户端n的一个数据单元上，fn是容量（CPU频率）k是一轮训练中局部更新的次数，t n是客户端n在每轮训练中用于传递模型权重xr的时间。请注意，训练时间取决于最耗时的客户端，因为中央服务器只有在接收到所有客户端的本地模型权重时才能聚合全局模型。因此，合理分配训练数据可以加速模型收敛，减少训练时间：T<$CR<$A max. RsnlnkRtn：153.1.2. 客户成本在局部模型训练中，第n个客户端可以公式化为中央服务器认为客户端N需要的信息其中H是rn的可能取值范围。私营对应于第n个客户端报告的个人简档的信息被定义为H;nN，hh1;;hN是全球信息。在中央服务器优化Eq. （11）、自私的客户需要选择自己的个人资料上报给中央服务器，但他们的目的是个人效用最大化。该机制需要设计一个效用传递函数来调节客户我们将客户之间的这种策略性互动建模为一个非合作博弈，如下所示。定义1. 个人资料提交游戏（PPSG）。● 参与者：所有客户端n2N。cmp12● 策略：客户n选择个人简介rn2H;n2NCnðs nÞ ¼2 fnlnf ns n；ð 6Þ其中fn是第n个客户端的计算芯片架构系数（Tran等人，2019 b; Kang等人， 2019年）。在模型更新传输中，客户端可以具有变化的传输容量和信道（Sun等人， 2020年）。从这个意义上说，模型权值的传递会给客户端带来异构由于客户端模型权重的大小不依赖于s，我们表示第n个并将其提交给中央服务器。● 目的：每个客户端旨在到最大其效用Unrn;r-n;n2N作为等式（十四）、然后，可以定义PPSG的纳什均衡（NE）。定义2. PPSG的NE是个人简介rNE¼。rNE;·· ·;rNE=8n2N，n在每次迭代中，作为常数Ccmu。因此，第n个客户端总费用计算如下：1NUr;r6U. rNE;rβ;8r-rCns nR.CcmpsnCcmu：7在NE处，给定其他用户的个人简档r-n;n2N，因此，客户端n不能通过偏离rNE来增加其效用。到此外，客户n用价值函数评估其自身的价值Vnsun1-A s-Cnsn;8n2N：8其中，un是客户n的模型准确性收入系数，衡量模型对第n个客户的重要性（Tang和Wong，2021）。由方程式（8）、较低的培训成本和较低的模型准确性损失意味着较高的估值，这是客户所偏好的3.2. 问题公式化由于模型训练成本与数据大小正相关，因此中央服务器应该为本地训练安排一系列合适的数据大小分配，以最大化社会效用，即，联系我们中文（简体）n2N同时，客户也希望尽可能缩短培训时间。根据等式（5）、当训练轮数R给定时，每轮训练时间越短，总训练时间越快n为了达到网络效率和社会效用最大化，我们设计了具有数据大小选择和效用转移功能的ETTA，以便于客户定义3.用于跨筒仓FL的ETTA机制被表示为二元组的ETTA/ETTA，即，数据大小选择函数W和效用传递函数f。● w：H！N是从全局型向量h的笛卡尔积到训练样本量ksk1的映射，它只能求解方程的最优解。（11）通过已知信息。第n个客户端的局部训练样本大小为中文（简体）● /：H！R 从报告的信息向量 r1; ;rn 映 射到转移效用向量/1; ;/n，客户端n的效用函数重写为UnrVnwnr/nr：14n2N;204J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报67ð·Þ ð·Þ¼ð···ÞPX2½]Xð ޼𷷷 þ···Þ.Σð·Þð Þ82rNE1/4 hn;8hn2H;8n2N。1nnn2n nCCdj-1<$2<$;如果歼-1歼2歼 6ksk16Dj-12;dj-1<$N<$;如果Dj-1型中程弹道导弹6ksk16Dj-1N：<>。...n我们的目标是设计ETTA中的w 和/以满足以下性质：效率：模型训练数据大小分配ss1;;sn具有方程的帕累托最优性。（十一）、激励相容性：在激励机制的作用下，如果有一组NE或NE/4。rNE;···;rNE，其中预算平衡：所有客户的效用转移总和零，即，n2N/n≥0（见表1）。如图2所示，中心服务器接收每个客户端上报的隐私信息，计算最优任务分配，并发送给每个客户端;同时，中心服务器设置的转移效用满足激励兼容性和预算平衡。在上述性质的约束下，Eq. （11）可以改写为min>s2NFksk1;kkCs- 1-kUs;拉瓦托图二.任务分配机制的系统框架。>s：t：s.w.r.;8h2HN;b[001 pdf 1st-31files]/n=10;8r2HN;i2NUnrn;h- n6U nhn;h-n;8n2N：拉克什ðdÞð15Þ由中央服务器设置的训练数据大小的量是s1;···;sNn，现在任意选择一个客户端n并添加一个数据由方程式（15）中，社会效用和训练时间由目标函数（15a）中的权重系数k0;1加权，等式（15 a）（15）C和Eq. （15d）分别代表预算平衡和激励相容的约束。4. 多目标优化在本节中，我们分别分析了社会效用最大化和训练时间最小化，并给出了ETTA的一些帕累托最优解。在这些分析中，我们放松了约束，包括激励相容和预算平衡。4.1. 社会效用分析跨仓FL过程减少了模型的精度损失，增加了客户端的能耗因此，我们需要从两个方面来分析社会效用：模型精度的收益和训练成本。根据等式（3）随着模型训练数据量的增加，模型的精度损失减小假设单位在当地的模特培训，以及她为社会带来的模特准确性收入的变化，中文（简体）un½As0-As];16n2N其中s 0s1;;s n 1个;s N.注意，在Eq. （3），s在形式的总和，因此对于任何客户端n2N，他们的边际收益增加一个本地训练数据单位与数据大小s是DUs。接下来，我们考虑由于数据大小的增加而导致的客户培训成本的增加从等式（6）和（7），我们可以看到不同客户端的培训成本在相同规模的本地培训数据下有所不同。我们假设客户端信息的分布中央服务器将从成本最低的客户端分配模型训练的数据大小，以最大化社会效用。对于第n个客户，她本地模型训练的边际成本如下：dCnCcmpsn1-Ccmpsn1fnlf2：17表1符号和函数的总结。符号物理意义N客户端集合Dn客户端的本地数据集n客户的本地培训数据集n训练数据大小R模型培训回合sn;s客户端n本地训练的数据大小及其平均值ln;l客户端n的每个数据单元所需的CPU周期数，以及其平均值当量（17）意味着每个客户端的本地训练边际成本与当前数据大小分配无关，客户端在选择客户端时，该机制具有一定的优先级，我们将其表示为j<$j-1<$1<$;·· ·;j-1<$N<$，其中j<$·<$是集合N的置换，j-1<$·<$是j的逆变换。优先级原则由中央服务器和其他约束条件决定。例如，在仅考虑社会公用事业，中央服务器将更倾向于客户端与低培训成本，这可以被反应作为D. j-1×1×6;· ··;6d. j-1N。考虑到所有客户都需要fn;f客户端n的CPU频率及其平均值tn;t客户端n的传输时间及其平均值k一轮hn中央服务器请求的客户端nrn客户端选择的策略n全球模型精度损失Cn·客户端总成本nVn·客户端n根据客户的边际成本，dCn;nN和中心服务的客户选择原则。我们可以得到模型训练的边际成本，8>dj-11;如果0 6ksk16. Dj-11。;公司简介ð18Þ分别为社会效用和总培训时间·· ····**...8>w·;/·分别为数据大小选择和效用传递函数：>个J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报68. Σ.ΣfnX>：Xð Þ ð Þ.ΣX-su.Σfn-1n-1fnn2pRk21nn nF不，1/4英尺2英寸 sω2<$tn，存在a2RF2n2Nf12016年12月21日星期一no2016年12月21日星期一算法1. 注重效用在此原则下，数据量随着数据量的增加而增加。因此，在步骤10- 14中收入是平等的。算法1的复杂度为O N3.该算法的理论基础来自定理1。算法1的输出解s仅考虑社会效用，对应于等式1的解。（15）当k≥0时。但我们也希望系数k可以自由调整，以适应不同的实际需要。这就促使我们从训练的时候就考虑解决4.2. 训练时间分析根据等式（4）训练涉及的数据量越小，训练时间越短。一个极端的情况是，用于训练的数据大小为零，训练时间也为零。但这种情况违背了FL的初衷，一般来说，一些模型训练任务会给出一个合适的样本量。本节讨论的重点是如何分配给定局部训练的总数据大小，以实现最优化-Eq的。（15a）。从等式根据公式（16）和（18），模型精度的边际收益随着训练数据的大小而减小，而边际训练成本保持不变。 因此，社会效用是最大的。当我看到边际模型收入等于边际在确定总数据大小ksωk1之后，中央服务器需要将本地训练数据大小分配给每个客户端，如sω1;·· ·;sωN以最大限度地减少每轮的时间。最佳数据分配sω需要满足培训成本。8>1n-1ksωn2N=f1g;拉瓦托关于k s k1，即，ksωk1¼sωn：n2N阿贝什ð23Þ@-unAs@ksk11sk-3Xu;120mm以找到任何总数据大小s中的边际收益。由于数据单元对模型精度损失的影响较小，因此我们可以使用等式（20）近似方程。（十六）、当DUs>DC s时，增加一个数据单元的模型性能收益大于其训练成本，增加数据规模可以带来更多的社会效用。相反，当DUsDC ss时，数据的大小需要减少才能增加<证据当jNj2时，记为sω1;sω2作为Eq.的最优解。式（22）中，sosω满足jsωj<$sω1<$sω2。 Ifsω不满足等式（23a）在不失去一般性的情况下，假设l1ksωl2ksω：24<社会效用因此，社会效用最大化当且仅当DUsDCs，即，2f11f22nsωlkolk13Ds121n2Nn2联 系我们 pkn：Þ正整数e使得l2ksω2<$l1ksω1<$e。因此，让因此，证明了这个定理。H^s1;^s2.sω1<$ef1f2;sω2-ef1f2<$，我们有利用定理1，我们可以得到一个Pareto最优解，ax. ^snlnk tl2ksωte25多目标优化问题。算法1给出了最优解，社会效用的最优解，即社会效用的帕累托最优解^sn2f^s1;^s2gfn卢恩1/4英尺2英寸2n-2：Þ因为该解决方案限制了每个客户端的本地训练数据大小。在算法1中，步骤2-注意，边际培训成本由于e>0，方程（25）与sω是方程的最优解相矛盾（二十二）、因此，最佳值sω必须满足等式（23 a）。 假设引理1在jNj <$$>m时成立，则如果jNj<$1也成立，则可以推导出引理1。进行如下操作：表示sω1;sω2;·· ·;sωm1作 为Eq. 的 最 优 解 。 （22 ） ，sosωsatis-¼n2N当量（24）表示max：>个J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报698>sωtltktt.不等式（i）意味着存在正数e1，使得maxnsωnlnktno<$sωtltktt-e1.由于jN=tj¼m和等式（二十三）由预假设s是成立，我们有ln-1ksωn 1/4lnksωn;8n2N=ftg的最优解fn-1-fnmin maxsω2Hn2N=ftgnsωnlnktno;26Þ时间：：jsωj ¼Xsωn：n2N=ftg合并等式（26）和（i），我们有，lmksωtM最大值1/4 ^snlnk：27n让es1;es2;· ··;esm;esm1。sω;sω;·· ·;sωef mf m1布里尔fmk;sω-efm1fm与Eq相似。（28）我们有m1lm给定样本大小，我们可以使用定理2来最小化maxsωnlnkn2NfnþtnΣ1/4ma x. esnlnktne：2018年这个样本量的训练时间。由于更大的样本量意味着更高的潜在时间开销，我们通过比较不同的全局样本量来权衡效用和训练时间。具体来说，当当量（28）与sω是方程的最优解相矛盾（二十二）、类似地，通过设置e0，也可推出不等式（ii）来反驳上述命题<. H引理1描述了等式（22）的最优解的重要性质，从中可以直接求解最定理2. 数据大小分配sω1;sω2;·· ·;sωNEq优化。（22）当且仅当8n2N，确定了全局样本大小，也确定了每个客户端的任务分配给定k，我们只需要优化总样本量，目标函数可以重写为Fksk1;kkC s ω-1-kUsω;33其中sωfnksωk1n.i2Nln因此，在算法2中，如图2所示。 3、利用遍历法寻找总数据量的最优值。在步骤5然而，在真正的联邦学习中，sω nksωk129Þ是每个客户端的本地数据大小的上限，nlXfn：低于激励机制分配给她的数据大小，n证据Lni2Nnism。 因此，步骤7具体来说，我们找到那些本地数据上限低于最优分配的客户端，并在步骤10-11中将其训练数据大小设置为上限。另一方面，本地样本量上限大于分配任务量的客户端选择根据引理1，如果sω是方程1的最优解（22）然后8n2N=f1g，我们有接受分配的样本量。算法2的复杂度是O.N3M循环可以结束，因为最佳数据大小不是ln-1kfn-1sωn-1¼ lnkfn sωn：100大于总数据大小的上限4.3. 任务分配另外，利用8n2N和8i2N=fng，我们可以得到，sωlnfisω31ifnlin替代Eq. （31）对于sωi;8i2N=fng，在等式（32）中，（22），我们得到fnksωk1算法2可以求解任意权重的最优任务分配，但计算复杂度较高。实际上，选择一个理想的训练计划是一个背包问题，是NP完全问题。直接求解这类问题的最优解将面临大量的计算成本（Sabir等人，2021a），因此采用启发式算法是一种合理的方法sωn 1/4升i 2Nfi>n2N=tMm1J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报70Li：1320（Sabir等人，2021 b）。为了降低计算复杂度，算法2，我们可以使用方程的近似条件。（19）计算最佳样本量。当边际培训成本因此，证明了这个定理。每个客户端的h没有太大的不同，由于线性J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报71.202Ef ¼f一个SN312pð·Þ82822n n2¼RðNuÞ3 fl3 F@RX。flf2snn2R21n2Nn22算法3.任务调度的近似算法图三. 算法2的流程图。s n; 8n 2 N在等式中（6），我们可以用期望值Efnf;Ell来估计所有客户端的CPU能耗，并且nXE. 1fnlf2sn1flf2Xsn：34n2Nn2N根据定理2计算数据，以便循环上述过程。通过近似总样本量，我们不再需要像算法2那样遍历M。算法的复杂度因此，3被简化为O。N3与定理1类似，总边际训练成本可以是近似为方程的一阶条件。（34）关于ksk1。推论1. 最大化社会效用的总数据大小可以近似为二、 -2。-4证据类似于等式总的边际训练成本可以近似为等式（20）的一阶条件。（34）关于ksk1，2n2N@ksk11/4Rflf2：336mm根据等式（20）Eq.（36）简化1架K-S-3 PU ¼ Rflf得到Eq. （35）。H推论1简化了计算，减少了服务器对公共信息的需求。用推论1解决数据量的激励机制只需要知道相关客户信息的均值最佳的总数据大小可以使用等式来近似（35）。然后我们可以使用定理2来计算最优数据分配，以获得近似的Pareto最优性。算法3给出了具体的计算方法。 在算法3中，如图3所示。步骤1使用推论1来获得总数据量的最佳值的近似值。在步骤2二、同样，每个客户端的本地数据大小也有上限。因此，步骤4具体来说，我们找到那些本地数据上限低于最优分配的客户端，并在步骤8-12中将其训练数据大小设置为上限接下来，在步骤18-5. 用于任务分配在第4节中，我们已经知道，诸如ln，nN和f n;nN决定了数据的大小分配。因此，客户有足够的动机通过伪造这些私人信息来获得最有利的训练数据大小。 这种误报会使中心服务器失去用于求解最优训练计划的信息，最终损害社会效用。因此，在本节中，我们设计了一个效用传递函数f，以保持客户和ETTA的稳定性。ksk1：350万J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报7282ð·Þnð·Þ8P42¼-无菌过滤器 - -一种Þ-ððÞÞn8882.Σ2n n nnnnnnnnnn-n个n-n个n我爱你Þ.Σ满足激励相容性。H2 Nn n见图4。算法3的流程图。客户端收到中央服务器分配的任务后，进行当地培训，这将产生费用Cn<$R1fnlf2sωCcmu 、8n2N. 客户往往会虚报他们的信息（例如，如果中央服务器没有给出相应的数据，则算法2将报告它们的f n; n N更少，使得算法2分配更少的数据激励帕累托优性取决关于客户信息，虚假的个人资料可以使算法偏离正确的解决方案。为此，中心服务器将支付客户端相应的培训报酬为8n2N，rn当量（37）是对Eq的重写（7）由于所有客户都有不变的通信成本，因此采用通信成本的平均值Ccmu;n2N来计算相应的报酬。在训练之后，中央服务器将聚合本地模型并将全局模型发送到每个客户端。由于中心服务器从全局模型中没有收益，因此奖励客户端可能会导致中心服务器的货币赤字。另一方面，如算法1所讨论的，一些客户端不参与训练，但最终得到全局模型，这是一种搭便车行为。因此，客户需要向中央服务器纳税，在效用传递函数（40）的作用下，客户n;8n2N的效用为：UrVwr/r：41在本节中，我们使用算法3来实现数据大小选择函数w，因为算法3比算法1需要更少的私有信息。结合数据大小选择函数w_（？）·k和效用传递函数f，设计了ETTA。接下来，我们分析ETTA需要满足的特性。在任务分配和转移支付规则的共同作用下，委托人的效用满足激励相容性。定理3.ETTA与w_（？）和/w_（？）满足激励相容性。证据考虑PPSG的一组策略r^h，我们只需要证明它是一个NE，其中8n2NUnhn;h-nVnwh/nhu nn n A w hN1 sC nwnh：Þi2N如果客户n偏离策略hn，并报告个人资料8rn2H，则SRX. 1l2CMU38Unrn;h-nun-unA wrN-1s-PCnwnr;43¼Nn2N 2ff snC：Þ其中r<$r;hi2N2N. 在算法3的步骤1中，ETTA使用1N-n个每个客户端向中央服务器支付的税s是总数的jNj培训成本（即薪酬总额由于客户信息的平均值是公开信息，每个客户将比较其局部最优训练分配与具有Pareto最优的数据大小分配。客户被激励虚报个人资料，以获得更多报酬或减少培训成本，如果有相当大的公共信息到计算的总数据尺寸，所以kwh k1kwrk1.由等式（3），AwhAwr。同样，当在数据总量相同的情况下，正确信息的数据配置社会成本不大于虚假信息的社会成本。将UD表示为Unrn;h-n-Unhn;h-n;rn2H;n2N，由等式（42）和（43），局部最优和Pareto最优之间的插值为了引导人们-用于报告中央服务器UD¼Ur;h-U老实说，我们用这个东西这意味着客户不能通过偏离nsNsXR Si2N39战略h，即，当量（十二）、因此，rNE^h是PPSG的NE，并且ETTA调整客户端n的效用转移;nN.综上所述，该机制的效用传递函数为：/nrnwnw-s;40最后，我们证明了具有效用转移选择函数的ETTA，任务管理器可以维持中央服务器的预算平衡提案1. 所有客户的效用转移之和其中，hn1n;fn;jDnj;8n2N为中心服务器所需的客户也就是说，Pn2N证据/n= 0; 8r 2HN; 8n 2 N。-J. 卢湾，澳-地Pan，J.Yu等人沙特国王大学学报73J 2018年12月28日X“X#Rflfn¼¼¼N.Σ¼ ×82合并等式（39）和（40）式中，我们有8n2N，/nrN-1s-Xriwih;45I因此，在本发明中，X/nr 1/4X“N-1”s-Xrinwinhnn n#–平均分配不考虑异质性，将训练任务均匀地分配给每个客户端（Kim等人，2019年）。为了公平起见，我们考虑两种情况：（i）局部样本量没有上限，（ii）每个客户端n的局部样本量上限为Dn3000;nN.贪婪策略，根据相关目标的优先级选择客户端（Zhang等人，2021a），并且忽略辅助客户端，直到当前客户端的本地样本耗尽。具体来说，当聚焦对培训时间，的优先级p1

下载后可阅读完整内容，剩余1页未读，立即下载