联邦学习遇见多目标优化

Zeou Hu, Kiarash Shaloudegi, Guojun Zhang, and Yaoliang Yu Zeou Hu and Yaoliang Yu are with the Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1. E-mail: {zeou.hu,yaoliang.yu}@uwaterloo.ca; Kiarash Shaloudegi is with Amazon Advertising. Work was done while at Huawei Noah Ark’s Lab, Montreal, QC, H3N 1X9. E-mail: kiarashs@amazon.com; Guojun Zhang is with Huawei Noah Ark’s Lab, Montreal, QC, H3N 1X9. E-mail: guojun.zhang@huawei.com
摘要

联邦学习已成为一种有前途的大规模分布式方式,可以在大量边缘设备上训练联合深度模型,同时将私人用户数据严格保留在设备上。 在这项工作中,出于确保用户之间的公平性和针对恶意对手的稳健性的动机,我们将联邦学习制定为多目标优化,并提出了一种新算法FedMGDA+,保证收敛到帕累托平稳解。 FedMGDA+ 易于实现,需要调整的超参数较少,并且不会牺牲任何参与用户的性能。 我们建立了 FedMGDA+ 的收敛特性,并指出其与现有方法的联系。 对各种数据集的大量实验证实,FedMGDA+ 与最先进的技术相比具有优势。

关键词关键词帕累托优化、分布式算法、联邦学习、边缘计算、机器学习、神经网络。

1简介

深度学习在许多领域应用中取得了令人印象深刻的成功,这主要归功于算法和架构设计的创新,同样重要的是人们可以通过 GPU、计算机集群以及专用软件和硬件来利用巨大的计算能力。 智能手机、平板电脑、路由器、车载设备、家庭传感器等边缘设备因其无处不在和中等计算能力,为深度学习带来了新的机遇和挑战。 一方面,边缘设备可以直接访问用户可能不愿意共享(例如数据中心)的隐私敏感数据,并且它们比前代设备更强大,能够进行大量的设备上计算。 另一方面,边缘设备在容量、功耗、数据、可用性、通信、内存方面大多是异构的,这给机器学习模型的传统内部训练带来了新的挑战。 因此,最近出现了一种新的范式,称为联邦学习 (FL) (McMahan 等人,, 2017),旨在收获边缘设备的前景。 在边缘设备上开发新的FL算法和系统从此成为机器学习领域的热门研究课题。

从诞生之初,FL就与传统的分布式优化有着密切的联系。 然而,FL 的出现源于解决移动时代新闻挑战的迫切需要,因为现有的分布式优化算法并不是为本身而设计的。 我们提到了与我们的工作最相关的FL的以下特征,并参考了优秀的调查(Li 等人,, 2019; Yang 等人,, 2019; Kairouz 等人, ,2019) 以及其中有关 FL 中更多挑战和应用的参考文献。

  • 非独立同分布:每个用户的数据可能与其他用户的数据明显不同,这违反了统计学习中的标准独立同分布假设,并且给用精确的数学术语制定目标带来了很大的困难(Mohri 等人,,2019) 用户数据的分布往往严重不平衡。

  • 沟通有限: Communication between each user and a central server is constrained by network bandwidth, device status, user participation incentive, etc., demanding a thoughtful balance between computation (on each user device) and communication.

  • 隐私:保护用户(数据)隐私在FL中至关重要。 因此无法共享用户数据(甚至无法共享给云仲裁者),这为解决前两个挑战增加了另一层难度。

  • 公平性:正如最近的工作中所强调的那样(例如,Mohri等人,2019;Li等人,2020b),确保用户之间的公平性成为 FL 的另一个重要目标,因为它在很大程度上决定了用户参与的意愿,并确保了一定程度的针对恶意用户操纵的鲁棒性。

  • 鲁棒性: FL算法最终会在野外部署,因此容易受到恶意攻击。 事实上,最近构建了对抗性攻击(例如Bagdasaryan 等人,2020;Sun 等人,2019;Bhagoji 等人,2019)来揭示 的漏洞FL系统可防止用户侧的恶意操纵。

在这项工作中,受上述最后两个挑战(公平性和鲁棒性)的启发,我们提出了一种新算法FedMGDA+,以补充和改进现有的FL系统。 FedMGDA+ 基于多目标优化,并保证收敛到 Pareto 平稳解。 FedMGDA+ 易于实现,需要调整的超参数较少,最重要的是不会牺牲任何参与用户的性能 我们在包括准确性、公平性和稳健性在内的各种指标下展示了 FedMGDA+ 的卓越性能。

我们的贡献总结如下:

  • 在§3中,基于最近平均值,我们对现有的FL实践提供了一种新颖的、统一的和具有启发性的解释。

  • 在§4中,我们总结了多目标优化的一些背景,并指出了它与现有FL算法的联系。 我们相信,这种新的视角将在未来使两个领域之间的交流更加富有成效。

  • 在§5中,我们提出FedMGDA+,它补充了现有的FL系统,同时将稳健性和公平性明确纳入其算法设计中。 我们证明 FedMGDA+ 在温和的假设下收敛到 Pareto 平稳解。

  • 在§6中,我们进行了广泛的实验,以在各种理想指标下验证 FedMGDA+ 的竞争力,并说明我们的算法和替代算法各自的优缺点。

我们在§2中讨论了更多相关工作,并在§7中总结了一些未来的方向。

为了促进可重复性,我们已在以下位置发布了代码:https://github.com/watml/Fed-MGDA

2相关工作

在本节中,我们将简要回顾一些与我们直接相关的近期工作,并将我们的贡献放在背景中。 首先,McMahan 等人 (2017) 提出了第一个 FL 算法,称为“联合平均”(又名,FedAvg),该算法是一种分几轮进行的同步更新方案。 在每一轮中,中央服务器将当前的全局模型发送给用户子集,然后每个用户使用其各自的本地数据来更新接收到的模型。 服务器收到用户更新后的本地模型后,进行聚合(例如简单平均)以更新全局模型。 有关不同平均方案的更多讨论,请参阅 Li 等人, (2020) Li 等人,2020a 扩展了 FedAvg 以更好地处理非独立同分布的问题。 通过向局部损失函数添加“近端正则化器”并最小化每个用户的莫罗包络函数来分布数据。 正如第 §3 中所指出的,所得算法 FedProxYu (2013) 中近端平均算法的随机版本,并减少当正则化减弱时,变为 FedAvg

由于其灵活的更新方案、部分用户参与以及客户数据的非独立同分布Li等人,2020a,分析FedAvg一直是一项具有挑战性的任务。 针对独立同分布和非独立同分布数据的强凸和平滑问题的 FedAvg 的首次理论分析出现在 Stich, (2019)Li 等人, (2020 ),分别研究了不同采样和平均方案对FedAvg收敛速度的影响,得出这样的结论:当数据集不平衡和非独立同分布。 Huo等人, (2020)中,FedAvg针对非凸问题进行了分析,其中FedAvg被制定为基于随机梯度的算法具有偏置梯度,并且证明了FedAvg随着步长衰减到驻点的收敛性。 此外,Huo等人,(2020)提出了FedMom,一种基于Nesterov动量的服务器端加速,并再次证明了其收敛于驻点。 最近,Reddi 等人 (2020) 提出并分析了几种流行的自适应优化器的联合版本(例如 ADAM)。 他们通过将FL更新方案解耦为服务器优化器客户端优化器来概括FedAvg的框架。 有趣的是,和我们一样,Reddi 等人, (2020) 也观察到了客户端和服务器上学习率衰减的重要性。

最近,Pathak 和 Wainwright(2020) 的一项有趣工作从理论上证明了 FedAvgFedProx(如果存在)不需要达到固定点是原始优化问题的驻点,即使在凸设置和确定性更新中也是如此。 为了解决这个问题,他们建议 FedSplit 来恢复正确的不动点。 不过,如果 FedSplit 仍然可以在异步和随机用户更新下收敛到正确的固定点,它仍然保持开放状态,这两种方法在实践中都被广泛采用并在这里进行了研究。

确保用户之间的公平性已成为 FL 的一个重要目标,因为它在很大程度上决定了用户参与训练过程的意愿。 Mohri 等人,(2019) 认为现有的 FL 算法可能会导致偏向不同用户的联合模型。 为了解决这个问题,Mohri 等人,(2019)提出了不可知联邦学习(AFL)来提高用户之间的公平性。 AFL将目标分布视为用户分布的加权组合,并针对最坏情况实现优化集中模型,从而产生鞍点优化问题,并通过快速随机优化算法解决。 另一方面,基于无线网络中公平的资源分配,Li等人,2020b提出了q-fair联邦学习(q-FFL)以实现更统一的测试精度跨用户。 Li等人,2020b进一步提出q-FedAvg作为解决q-FFL的通信高效算法。 然而,AFLq-FedAvg 都没有明确鼓励用户参与,并且它们遭受对抗性攻击,而我们的算法 FedMGDA+ 的设计是公平的在参与者之间并且对加法和乘法攻击具有鲁棒性。

FedAvg 依赖于本地模型的坐标平均来更新全局模型。 根据Wang等人,2020b,在基于神经网络(NN)的模型中,由于神经网络参数的排列不变性,这种坐标平均可能会导致次优结果。 为了解决这个问题,Yurochkin等人,(2019)提出了概率联邦神经匹配(PFNM),它仅适用于全连接的前馈网络。 最近的工作(Wang等人,2020b,)提出了联合匹配平均(FedMA)作为PFNM的分层扩展以适应CNN和 LSTM。 然而,PFNMFedMA中的贝叶斯非参数机制可能容易受到模型中毒攻击(Bagdasaryan 等人,, 2020; Bhagoji 等人,, 2019 ; Wang 等人, 2020a, ),而Sun 等人, (2019) 中讨论了一些简单的防御,例如规范阈值和差分隐私。 我们注意到这些想法与 FedMGDA+ 是互补的,我们计划在未来的工作中研究它们可能的集成。

最后,我们注意到人们对标准化 FL 中的基准、协议和评估非常感兴趣,例如参见 (Caldas 等人,, 2018; He 等人,, 2020). 我们花费了大量精力来遵守建议的规则,通过报告通用数据集、开源我们的代码并包括所有实验细节。

3问题设置

我们回顾了 McMahan 等人 (2017) 的联邦学习 (FL) 框架,并指出了一个看似统一了不同实现的简单解释。 我们考虑 FLm 用户(边缘设备),其中 i 用户对最小化函数 fi:d,i=1,,m 感兴趣,在共享模型参数 𝐰d 上定义。 通常,每个用户函数fi还取决于相应用户的本地(私有)数据𝒟i FL 的主要目标是集体有效优化个人目标{fi},同时应对诸如在简介(§1):用户数据的非独立同分布、有限通信、用户隐私、公平性、鲁棒性等

McMahan 等人, (2017)提出FedAvg来优化单个用户函数的算术平均值:

min𝐰d𝖠𝐟,𝝀0(𝐰),where𝖠𝐟,𝝀0(𝐰):=i=1mλifi(𝐰). (1)

权重λi需要事先指定 典型的选择包括每个用户的数据集大小、每个用户的“重要性”,或者简单地统一,λi1/m FedAvg 的工作原理如下:在每一轮中,选择一个(随机)用户子集,每个用户执行 k 次局部(完整或小批量)梯度下降:

for all i in parallel,𝐰i𝐰iηfi(𝐰i), (2)

然后在服务器端对权重进行平均:

𝐰iλi𝐰i, (3)

最终在下一轮广播给用户。 本地纪元 k 的数量是一个关键因素。 设置k=1相当于通过通常的梯度下降算法求解(1),同时设置k=(并假设每个局部函数收敛fi) 相当于(重复)对 fi 的各个最小值进行平均。 现在,我们对 FedAvg 进行了新的解释,从而深入了解它通过中间 k优化的内容。

我们的解释基于最近平均值(Bauschke等人,2008) 回想一下,莫罗包络线和凸函数的近端映射111对于非凸函数,一旦我们解决近端映射的多值性,类似的结果就会成立,参见Yu等人,(2015) 函数f分别定义为:

𝖬fη(𝐰) =min𝐱12η𝐱𝐰22+f(𝐱), (4)
𝖯fη(𝐰) =argmin𝐱12η𝐱𝐰22+f(𝐱). (5)

给定一组凸函数𝐟=(f1,,fm)和总和为1的正权重𝝀=(λ1,,λm),我们将近端平均值定义为唯一函数𝖠𝐟,𝝀η 这样 𝖯𝖠𝐟,𝝀ηη=iλi𝖯fiη. 换句话说,邻近平均值的邻近图是邻近图的平均值。 更具体地说,Bauschke 等人,(2008) 给出了以下明确但复杂的近端平均值公式:

𝖠𝐟,𝝀η(𝐰) =min𝐰1,,𝐰mi=1mλi[fi(𝐰i)+12η𝐰i22]12η𝐰22, (6)
s.t.i=1mλi𝐰i=𝐰. (7)

从上面的公式我们很容易得出

𝖠𝐟,𝝀0(𝐰) :=limη0+𝖠𝐟,𝝀η(𝐰)=iλifi(𝐰),
𝖠𝐟,𝝀(𝐰) :=limη𝖠𝐟,𝝀η(𝐰)=miniλi𝐰i=𝐰iλifi(𝐰i).

有趣的是,我们现在可以在两种极端设置下将 FedAvg 解释为最小化近端平均值:

  • 具有 k=1 局部步长的 FedAvg 与使用 η=0 最小化近端平均值 𝖠𝐟,𝝀0(𝐰) 完全相同。 这从 FedAvg 的目标 (1) 中可以清楚地看出(正如我们的符号已经表明的那样)。

  • 具有 k= 局部步骤的 FedAvg 与使用 η= 最小化近端平均值 𝖠𝐟,𝝀(𝐰) 完全相同。 的确,

    {min𝐰𝖠𝐟,𝝀(𝐰)}=min𝐰1,,𝐰miλifi(𝐰i), (8)

    其中右侧解耦,因此最优时的 𝐰ifi 的最小值(回想一下 𝝀0)。

因此,我们可以将带有中间 kFedAvg 解释为带有中间 η 的最小化 𝖠𝐟,𝝀η 更有趣的是,如果我们应用 PA-PG 算法 余,(2013,算法。 222) 为了最小化𝖠𝐟,𝝀η,我们得到简单的更新规则

𝐰iλi𝖯fiη(𝐰), (9)

其中近端图是在用户端并行计算的。 我们注意到,最近的 FedProx 算法 (Li 等人, 2020a, ) 本质上是 (9) 的随机版本。 至关重要的是,我们不需要评估复杂的公式 (6),因为更新 (9) 仅需要其近端图,根据定义,它是各个近端图的平均值地图(由每个用户单独计算)。 此外,近端平均值 𝖠𝐟,𝝀η 和算术平均值 𝖠𝐟,𝝀0 之间的差异可以使用每个函数 fi 的 Lipschitz 常数均匀地限制> (余,2013) 因此,对于小步长η,FedAvg(对于任何有限的k)和FedProx都最小化一些近似值 形式的算术平均值 (1)。

如何设置FedAvg中的权重𝝀一直是一个重大挑战。 FL中,数据以高度非独立同分布和不平衡的方式分布,因此不清楚(1)中选择的某些算术平均值是否真的满足人们的实际意图。 (1) 中算术平均值的第二个问题是其众所周知的针对恶意操作的非鲁棒性,这一点已在最近的对抗性攻击中被利用(Bhagoji 等人,, 2019). 相反,Agnostic FL (AFL (Mohri 等人,, 2019)) 旨在优化最坏情况的损失:

min𝐰max𝝀Λ𝖠𝐟,𝝀0(𝐰), (10)

其中集合 Λ 可能比任何特定的 𝝀 更好地覆盖现实,并为所有用户提供一些最低限度的保证(从而实现温和的公平)。 另一方面,(10) 中最坏情况的损失对于对抗性攻击可能更加不稳健。 例如,为某些损失fi添加正常数可以使其主导整个优化过程。 最近的工作 q-FedAvg (Li 等人, 2020b, ) 提出了 FedAvg 之间的 q 范数插值(本质上是1 规范)和 AFL(本质上是 规范)。 通过调整q,q-FedAvg可以实现比FedAvgAFL更好的折衷。

4 多目标最小化 (MoM)

多目标最小化 (MoM) 是指需要同时最小化多个标量目标函数(可能彼此不兼容)的设置。 它也称为向量优化 (Jahn,, 2009),因为目标函数可以组合成单个向量值函数。 用数学术语来说,MoM 可以写成

min𝐰d𝐟(𝐰):=(f1(𝐰),f2(𝐰),,fm(𝐰)), (11)

其中最小值是根据 partial 排序定义的:

𝐟(𝐰)𝐟(𝐳)i=1,,m,fi(𝐰)fi(𝐳). (12)

(我们提醒一下,当将诸如 + 之类的代数运算应用于具有另一个向量 或标量 的向量时,始终按分量执行。) 与单目标优化不同,多目标优化可能会

𝐟(𝐰)𝐟(𝐳) and 𝐟(𝐳)𝐟(𝐰), (13)

在这种情况下,我们说 𝐰𝐳 不具有可比性。

如果 的目标值 𝐟(𝐰) 是一个最小元素(相对于 (12) 中的部分排序),我们称 𝐰 为 (11) 的帕累托最优解,或者等价于任何 𝐰𝐟(𝐰)𝐟(𝐰) 意味着 𝐟(𝐰)=𝐟(𝐰) 换句话说,在不损害其他目标的情况下,不可能改进𝐟(𝐰)中的任何组件目标。 类似地,如果不存在任何𝐰使得𝐟(𝐰)<𝐟(𝐰),即,我们将𝐰称为帕累托最优解,不可能改进𝐟(𝐰)中的所有组件目标。 显然,任何帕累托最优解也是弱帕累托最优解,但反之则可能不成立。

我们指出MoM中的最优解通常是一个集合(一般是无限基数)(Mukai,1980),并且在没有额外的主观偏好信息的情况下,所有Pareto最佳解决方案被认为同样好(因为它们彼此之间没有可比性)。 这与单一目标案例根本上不同。

从现在开始,为了简单起见,我们假设所有目标函数都是连续可微的,但不一定是凸的(以适应深度模型)。 在这种情况下找到(弱)帕累托最优解非常具有挑战性(在单一目标情况下已经如此)。 相反,我们将面对帕累托平稳解,即满足直观的一阶必要条件的解:

Definition 1 (帕累托平稳性,Mukai,1980)

我们称𝐰帕累托平稳当且仅当一些梯度的凸组合{fi(𝐰)}消失,即存在一些𝛌0使得iλi=1iλifi(𝐰)=𝟎

Lemma 1 (向井,1980)

任何帕累托最优解都是帕累托平稳的。 相反,如果所有函数都是凸函数,则任何帕累托平稳解都是弱帕累托最优。

不用说,对于单一目标情况(m=1),上述结果简化为熟悉的结果。

存在许多用于寻找帕累托平稳解的算法。 我们简要回顾了与我们相关的三个流行的内容,并建议读者参阅优秀的专着(Miettinen,1998)以了解更多详细信息。

加权方法。 𝝀Δ (单纯形)并考虑以下单一加权目标:

min𝐰i=1mλifi(𝐰). (14)

这本质上是 FedAvg 所采用的方法,任何 (14) 的(全局)最小化器都是弱帕累托最优(事实上,如果所有权重 λi 定义 1 可以清楚地看出,加权标量问题 (14) 的任何平稳解都是帕累托平稳原始 MoM (11) 的解决方案。 请注意,标量化权重𝝀一旦选择,就始终是固定的。 不同的 𝝀 会导致不同的 Pareto 平稳解。

ϵ-约束。 ϵm1ι{1,,m} 并考虑以下约束标量问题:

min𝐰 fι(𝐰) (15)
s.t. fi(𝐰)ϵi,iι. (16)

假设约束条件可满足,则 (15) 的任何(全局)最小化器同样是弱帕累托最优。 ϵ-约束方法通过通常的拉格朗日重构与上面的加权方法密切相关。 不过,两者都需要提前固定 m1 尺寸参数(𝝀 ϵ)。

切比雪夫方法。 𝐬m 并考虑极小极大问题(其中 Δ 是单纯形约束):

min𝐰max𝝀Δ𝝀(𝐟(𝐰)𝐬). (17)

同样,任何(全局)最小化器都是弱帕累托最优。 这里 𝐬 是一个固定向量,理想情况下是 𝐟 的下限。 这本质上是 AFL (Mohri 等人,, 2019)𝐬=𝟎 采取的方法。

5 FL 作为多目标最小化

介绍了FLMoM,并观察了两者之间的一些联系,在FL中处理每个用户函数fi是非常自然的 作为 MoM 中的一个单独目标,并旨在同时优化它们,如 (11) 中所示。 这将是我们下面遵循的主要方法,据我们所知,以前尚未正式探讨过这种方法(尽管我们在上一节中看到了明显的联系,也许是回顾性的)。 特别是,我们将MoM中的多重梯度下降算法(Mukai,1980)扩展到FL,与现有的建立连接FL 算法,并证明我们的扩展算法 FedMGDA+ 的收敛特性。 非常重要的是,帕累托最优性和平稳性的概念立即增强了用户之间的公平性,因为我们不鼓励通过牺牲其他用户来改善某些用户。

为了进一步激励我们的发展,让我们与AFL (Mohri 等人,, 2019)中的目标进行比较:

min𝐰max𝝀Δ𝝀𝐟(𝐰)min𝐰maxi=1,,mfi(𝐰), (18)

其中 Δ 表示单纯形222准确地说,AFL𝝀限制为ΛΔ的子集。 我们简单地设置 Λ=Δ 来简化讨论。. 通过优化FedAvg最差损失而不是平均损失,AFL为所有用户提供了一些保证,从而实现了一些公平的形式。 但请注意,AFL 的目标 (18) 对于对抗性攻击并不稳健。 事实上,如果恶意用户人为地“夸大”其损失fi(例如,甚至通过添加/乘以一个常数),它可以完全控制和误导AFL 仅专注于优化其性能。 同样的问题也适用于 q-FedAvg (Li 等人, 2020b, ),尽管如果 q 很小,效果就不那么引人注目。

AFL 的目标 (18) 与 MoM 中的切比雪夫方法非常相似(参见部分 4),这启发我们提出以下迭代算法来求解(11):

𝐰~t+1=argmin𝐰max𝝀Δ𝝀(𝐟(𝐰)𝐟(𝐰~t)), (19)

我们使用上一次迭代中的函数值自适应“居中”用户函数。 当函数fi光滑时,我们应用二次界得到:

𝐰t+1=argmin𝐰max𝝀Δ𝝀J𝐟(𝐰t)(𝐰𝐰t)+12η𝐰𝐰t2, (20)

其中 J𝐟=[f1,,fm]d×m 是雅可比矩阵,η>0 是步长。 至关重要的是,请注意 𝐟(𝐰t) 不会出现在上述边界 (20) 中,因为我们在 (19) 中减去了它。 由于 (20) 在 𝐰 中是凸的,在 𝝀 中是凹的,我们可以将 min 与 max 交换并获得对偶:

max𝝀Δ min𝐰𝝀J𝐟(𝐰t)(𝐰𝐰t)+12η𝐰𝐰t2. (21)

通过将其导数设置为 𝟎 来求解 𝐰,我们得到:

𝐰t+1=𝐰tη𝐝t,𝐝t=J𝐟(𝐰t)𝝀t, (22)
where𝝀t=argmin𝝀ΔJ𝐟(𝐰t)𝝀2. (23)

请注意,𝐝t 正是雅可比行列式 J𝐟 中列(,梯度)的凸包中的最小范数元素,并找到 𝝀t 相当于求解一个简单的二次规划。 (22) 中产生的迭代算法称为多重梯度下降算法 (MGDA),它已在 Mukai (1980) 中(重新)发现; Fliege 和 Svaiter,(2000); Désidéri,(2012),最近在 Sener 和 Koltun,(2018)中应用于多任务学习; Lin 等人,(2019) 以及在 Albuquerque 等人,(2019) 训练 GAN。 我们在这里的简洁推导揭示了关于 MGDA 的一些新见解,特别是它与 AFL 的联系。

为了使 MGDA 适应联邦学习环境,我们提出了以下扩展。

平衡用户平均性能和公平性。 我们观察到 (22) 中的 MGDA 更新类似于 FedAvg,其关键区别在于 MGDA 自动 调整双权重变量 𝝀 在每个步骤中,而 FedAvg 根据有关用户功能的先验信息(或在缺乏此类信息时简单统一)预设 𝝀 )。 重要的是,在 MGDA 中找到的方向 𝐝t所有参与目标的共同下降方向:

𝐟(𝐰t+1) 𝐟(𝐰t)+J𝐟(𝐰t)(𝐰t+1𝐰t)+12η𝐰t+1𝐰t2
𝐟(𝐰t), (24)

其中第一个不等式源自 𝐟 上熟悉的平滑度假设,而第二个不等式则简单地源自将 𝐰=𝐰t 插入 (20) 并注意到 𝐰t+1 根据定义只能进一步减少 (20)。 很明显,当且仅当 𝐝t=J𝐟(𝐰t)𝝀t=𝟎𝐰t 是帕累托平稳时(参见部分 4)。 换句话说,MGDA 绝不会牺牲任何参与目标来换取比其他目标更大的改进,而具有固定权重 𝝀FedAvg 可能会尝试这样做。 另一方面,具有固定权重𝝀FedAvg可以在权重𝝀下实现更高的平均性能 很自然地在平均性能和公平性之间引入以下权衡:

update (22) with 𝝀t=argmin𝝀Δ,𝝀𝝀0ϵJ𝐟(𝐰t)𝝀2. (25)

显然,设置ϵ=0会恢复FedAvg,并具有先验权重𝝀0,而设置ϵ=1会恢复MGDA,其中权重变量𝝀在没有任何限制的情况下进行调整,以实现最大的公平性。 在实践中,通过中间的ϵ(0,1),我们可以在两个(有时)相互冲突的目标之间取得理想的平衡。 此外,即使使用无信息权重𝝀0=𝟏/m,使用中间ϵ也允许我们将每个用户函数对共同方向𝐝t的贡献设定上限,从而实现一些针对恶意操纵的鲁棒性形式。

通过规范化增强抵御恶意用户的鲁棒性。 现有工作(例如,Bhagoji 等人,, 2019; Xie 等人,, 2019) 已经证明,FedAvg 中的平均梯度可以是即使是单个恶意用户也很容易操纵。 虽然最近研究了更稳健的聚合策略(例如,参见 Blanchard 等人,, 2017; Yin 等人,, 2018; Diakonikolas 等人,, 2019),但它们不一定能保持FedMGDA+(例如找到共同的下降方向并收敛到帕累托平稳解)。 相反,我们建议基于以下考虑将每个用户的梯度简单地归一化为单位长度: (a) 归一化(子)梯度对于非平滑和随机优化专家来说很常见(Anstreicher 和 Wolsey,2009 ),有时可以简化步长调整。 (b) 用归一化梯度求解(22)中的权重𝝀t仍然保证公平性,,结果方向𝐝t对于所有参与目标都是递减的(通过与 (5) 之后的评论完全相似的推理)。 (c) 归一化恢复了针对任何恶意用户的乘法“通货膨胀”的鲁棒性,这与 MGDA 针对加性“通货膨胀”的内置鲁棒性相结合(参见方程 19),提供针对对抗性攻击的合理稳健性保证。

平衡通信和设备上计算。 由于§3中提到的各种原因,用户设备和中央服务器之间的通信在FL中受到严重限制。 另一方面,现代边缘设备能够执行合理数量的设备内计算。 因此,我们允许每个用户设备在将其更新𝐠=𝐰0𝐰(即初始𝐰0和最终𝐰之间的差异)传达给中央服务器。 然后服务器调用(扩展的)MGDA执行全局更新,该更新将广播到下一轮用户设备。 我们注意到,许多现有的FL系统已经采用了类似的策略(例如,McMahan 等人,2017;Li 等人,2020b,;Li 等人,2020a,)

二次采样可减轻非独立同分布并提高吞吐量。 由于FL中的边缘设备数量巨大,期望大多数设备参与每一轮甚至大多数轮次是不现实的。 因此,FL 中的当前做法是选择用户设备的(不同)子集来参与每一轮(McMahan 等人,, 2017) 此外,对用户设备进行随机二次采样还可以帮助对抗用户特定数据的非独立同分布(例如,McMahan 等人,, 2017;Li 等人,, 2020) 在这里,我们指出基于 MGDA 的算法的一个重要优势:它的更新是沿着共同的下降方向(参见 (5)),这意味着任何参与的目标用户只能减少。 我们相信 MGDA 的这一独特属性为用户参与FL提供了强大的动力。 据我们所知,现有的FL算法不提供类似的算法激励。 最后但并非最不重要的一点是,子采样还解决了 MGDA 中的简并问题:当参与用户的数量超过维度 d 时,雅可比行列式 J𝐟 具有完整的行秩(22)在单次迭代中实现帕累托平稳并停止进展。 子采样消除了这种不良影响,并允许不断优化不同的用户子集。

通过上述扩展,我们在算法1中总结了我们的扩展算法FedMGDA+,并证明了以下收敛保证(具体的陈述和证明见附录A):

Theorem 1a.

令每个用户函数fiL-Lipschitz平滑且M-Lipschitz连续,并选择步长ηt使得tηt=tσtηt<,其中 σt2:=𝐄𝐝t𝐝^t2

𝐝t :=J𝐟(𝐰t)𝝀t,𝝀t=argmin𝝀ΔJ𝐟(𝐰t)𝝀, (26)
𝐝^t :=J^𝐟(𝐰t)𝝀^t,𝝀^t=argmin𝝀ΔJ^𝐟(𝐰t)𝝀. (27)

然后,对于 k=r=1 我们有:

mint=0,,T𝐄J𝐟(𝐰t)𝝀t20. (28)

这里 k 是本地更新的数量,r 是每个本地更新中的小批量的数量。 收敛速度取决于随机共同下降方向 d^t 的“方差”项 σt 减小的速度(如果有的话),而这又取决于我们对用户进行二次采样或用户的异质性如何。

对于确定性梯度更新,即使有更多的局部更新,我们也可以证明收敛性(k>1):

Theorem 1b

令每个用户函数fiL-Lipschitz平滑且M-Lipschitz连续。 对于任意数量的局部更新k,如果全局步长ηt0tηt=、局部学习率ηtl0εt:=𝛌t𝛌^t0,那么我们有:

mint=0,,TJ𝐟(𝐰t)𝝀t20. (29)

该定理的精确表述及其证明请参见附录A 我们注意到,限制偏差 εt 的一种自然方法是应用 FedMGDAϵ 约束版本。 例如,如果 𝝀𝝀0ϵtϵt 是有界的,则 εt2mϵt 也是有界的。 因此,当 ϵt0εt0 而且,当k=1时,我们不需要局部学习率ηtl衰减来收敛;此外,如果εt0(例如在FedAvg中),那么我们的收敛保证减少到通常的梯度下降,这是预期的,因为我们知道FedAvgk=1,r=1 与集中梯度下降相同。 最后,我们注意到,当k>1时,局部学习率ηtl必须消失才能获得收敛。 Reddi 等人, (2020) 中也指出了局部学习率衰减的重要性。

当函数fi是凸函数时,我们可以得到更好的结果:

Theorem 2.

假设每个用户函数 fi 是凸函数并且 M-Lipschitz 连续。 假设每轮 FedMGDA+ 都包含一个强凸用户函数,其权重远离 0。 然后,通过选择 ηt=2c(t+2)k=r=1,我们有

𝐄𝐰t𝐰t24M2c2(t+3), (30)

𝐰t𝐰t0 几乎可以肯定,其中 𝐰t𝐰t 最接近的 Pareto 平稳解,c 是某个常数。

附录A中可以找到稍微更强的结果,我们还允许一些用户函数是非凸的。 如果梯度归一化远离 0,则相同的结果成立(否则我们已经接近帕累托平稳性)。 对于r,k>1,使用与§3中类似的参数,我们期望FedMGDA+优化一些代理问题(例如近端平均值),我们将彻底的理论分析留给未来的工作。

我们注意到,即使仅限于确定性情况,MGDA 的收敛速度也是最近在 Fliege 等人,(2019) 中得出的。 随机情况(我们在这里考虑)更具挑战性,我们的定理为 FedMGDA+ 提供了第一个收敛保证。 我们希望强调,FedMGDA+ 不仅仅是 FL 从业者的替代算法;它可以用作后处理步骤来增强现有的 FL 系统或与现有的 FL 算法(例如 FedProx q-FedAvg)。 这对于非凸用户函数特别有吸引力,因为 MGDA 能够收敛到所有 Pareto 驻点,而诸如 FedAvg 之类的方法即使在我们枚举权重时也不一定享有此属性𝝀0 (米耶蒂宁,1998) 此外,还可以找到多个甚至枚举所有帕累托最优解(帕累托前沿)。 例如,我们可以使用不同的随机种子或初始化多次运行FedMGDA+ 正如 Lin 等人 (2019) 所示,我们还可以在 (22) 中加入额外的线性约束来编码一个人的偏好并鼓励更多样化的解决方案。 不过,在维度较高(用户数量较多时)和通信受限的情况下,这些技术的效果会大打折扣。 实际上,服务器可以动态调整(22)中的线性约束,以将算法引导至更理想的帕累托平稳解。

最后,我们提到寻找共同的下降方向(算法1的第6行)是一个标准的二次方程仅在服务器端解决的编程(QP)问题。 对于中等数量的(采样)用户,使用通用 QP 求解器就足够了,而对于大量用户,我们也可以使用条件梯度算法 (Sener 和 Koltun,2018 年) 等方法高效求解 λ,每一步的复杂度与模型维度和参与用户数量成正比。 在下面的实验中,我们使用了通用 QP 解析器,并且我们观察到这种开销可以忽略不计,因此 FedAvgFedMGDA 的总体运行时间几乎相同。

1 for t=1,2, do
2 choose a subset It of pm clients/users
3 for iIt do
4 𝐠i ClientUpdate(i,𝐰t)
𝐠¯i:=𝐠i/𝐠i
// normalize
5
6
7 𝝀argmin𝝀Δ,𝝀𝝀0ϵiλi𝐠¯i2
𝐝tiλi𝐠¯i
// common direction
8
9 choose (global) step size ηt
10 𝐰t+1𝐰tηt𝐝t
11
12
13 Function ClientUpdate(i,𝐰):
14 𝐰0𝐰
15 repeat k epochs
// split local data into r batches
16
17 𝒟i𝒟i,1𝒟i,r
18 for j{1,,r} do
19 𝐰𝐰ηfi(𝐰;𝒟i,j)
20
21
22 return 𝐠:=𝐰0𝐰 to server
Algorithm 1 FedMGDA+

6实验

6.1 实验设置

表格1: 数据集摘要
Dataset Train Clients Train samples Test clients Test samples Batch size
CIFAR-10 (Krizhevsky,, 2009) 100 50000 100 10000 {10,}
F-MNIST (Xiao et al.,, 2017) 100 60000 100 10000 {10,}
FEMNIST (Caldas et al.,, 2018) 3406 709385 3406 80011 {20,}
Shakespeare (Li et al., 2020a, ) 31 92959 31 23255 {10}
Adult (Dua and Graff,, 2017) 2 32561 2 16281 {10}
表2: CIFAR-10模型
Layer Output Shape # of Trainable Parameters Activation Hyper-parameters
Input (3,32,32) 0
Conv2d (64,28,28) 4864 ReLU kernel size =5; strides=(1,1)
MaxPool2d (64,14,14) 0 pool size=(2,2)
LocalResponseNorm (64,14,14) 0 size=2
Conv2d (64,10,10) 102464 ReLU kernel size =5; strides=(1,1)
LocalResponseNorm (64,10,10) 0 size=2
MaxPool2d (64,5,5) 0 pool size=(2,2)
Flatten 1600 0
Dense 384 614784 ReLU
Dense 192 73920 ReLU
Dense 10 1930 softmax
Total 797962
表3: 时尚 MNIST 模型
Layer Output Shape # of Trainable Parameters Activation Hyper-parameters
Input (1,28,28) 0
Conv2d (10,24,24) 260 ReLU kernel size =5; strides=(1,1)
MaxPool2d (10,12,12) 0 pool size=(2,2)
Conv2d (20,8,8) 5020 ReLU kernel size =5; strides=(1,1)
MaxPool2d (20,4,4) 0 pool size=(2,2)
Dropout2d (20,4,4) 0 p=0.5
Flatten 320 0
Dense 50 16050 ReLU
Dropout 50 0 p=0.5
Dense 10 510 softmax
Total 21840
表 4: 联邦EMNIST模型(Reddi等人,, 2020)
Layer Output Shape # of Trainable Parameters Activation Hyper-parameters
Input (1,28,28) 0
Conv2d (32,26,26) 320 kernel size =3; strides=(1,1)
Conv2d (64,24,24) 18496 ReLU kernel size =3; strides=(1,1)
MaxPool2d (64,12,12) 0 pool size=(2,2)
Dropout (64,12,12) 0 p=0.25
Flatten 9216 0
Dense 128 1179776
Dropout 128 0 p=0.5
Dense 62 7998 softmax
Total 1206590
表 5: 我们的实验中使用的超参数。
Name Parameters
AFL γλ{0.01,0.1,0.2,0.5},γw{0.01,0.1}
q-FedAvg q{0.001,0.01,0.1,0.5,1,2,5,10}, L{0.1,1,10}
FedMGDA+ η{0.5,1,1.5,2}, and Decay{0,140,130,120,110,13,12}
FedAvg-n η{0.5,1,1.5,2}, and Decay{0,140,130,120,110,13,12}
FedProx μ{0.001,0.01,0.1,0.5,1,10}
MGDA-Prox μ=0.1, η{0.5,1,1.5,2}, and Decay{0,140,130,120,110,15,13,12}

在本小节中,我们提供实验细节,包括数据集描述、采样方案、模型配置和超参数设置。 我们使用的数据集的快速摘要可以在 Table 1 中找到。 我们在FedMGDA+中有两个参数来控制每轮通信中本地更新的总数:k,本地epoch的数量,以及r=n/b,每个本地时期的更新数量。 这里 n 是每个用户的样本数量(为简单起见,假设相同),而 b 是每个本地更新的小批量大小。 正如 例如McMahan 等人,(2017)(表 2)所观察到的,具有较大的 k 与具有较小的 b(或等效的更大的r),就本地更新总数而言。 此外,具有合适的 bk=1 通常会带来令人满意的性能,而非常大的 k 可能会导致稳定或发散。 因此,在我们的实验中,我们修复k=1,同时改变b以减少超参数的总数。 这对应于每个通信轮中每个用户的本地数据的单次传递。

6.1.1 CIFAR-10 (Krizhevsky,, 2009) 和 Fashion MNIST (Xiao 等人,, 2017) 数据集

为了创建一个非 i.i.d. 数据集,我们遵循与 McMahan 等人,(2017) 中类似的采样过程:首先,我们根据类别对所有数据点进行排序。 然后,它们被分成 500 分片,每个用户被随机分配 5 数据分片。 通过考虑100个用户,该过程保证没有用户从超过5个类接收数据,并且每个用户的数据分布彼此不同。 本地数据集是平衡的——所有用户都有相同数量的训练样本。 本地数据分为训练集、验证集和测试集,百分比分别为 80%、10% 和 10%。 这样,每个用户都有用于训练的 400 数据点、用于测试的 50 数据点和用于验证的 50 数据点。 我们使用的 CNN 模型类似于 McMahan 等人 (2017) 中的模型,具有两个卷积层,后跟三个全连接层。 详细信息包含在 CIFAR-10 的23<中/t5> 代表 Fashin MNIST。 为了使用本地数据更新每个用户的本地模型,我们应用具有本地批量大小 b=10、本地历元 k=1 和本地学习率 η=0.01b=400k=1η=0.1 为了模拟并非所有用户都可以参与每轮通信的事实,我们使用参数 p 来控制参与用户的比例:p=0.1 是默认设置,这意味着只有 10% 的用户参与每轮沟通。

6.1.2 联合 EMNIST 数据集(Caldas 等人,2018)

对于此实验设置,我们使用与 Reddi 等人 (2020) 相同的数据集、模型和超参数。 我们使用 Caldas 等人 (2018) 的联合 EMNIST 数据集。 该数据集由数字图像和英文字符(包括小写和大写)组成,总共 62 个类别。 作者对图像进行分区的方式自然会导致数据集异构且不平衡。 我们使用Table4中描述的模型和以下超参数:局部学习率η=0.1并选择10 每轮沟通客户数(按照建议)。 我们的设置与 (Reddi 等人,, 2020) 中的设置之间的唯一区别是我们对所有算法都使用本地纪元 k=1

6.1.3 莎士比亚数据集(李等人, 2020a, )

对于莎士比亚数据集的实验,我们使用与 q-FedAvg 论文 (Li 等人, 2020b, ) 中相同的模型、数据预处理和采样程序。 该数据集基于莎士比亚全集构建,其中剧中的每个角色代表一个用户。 Li 等人, 2020a 之后,我们对 31 用户进行二次采样,以训练用于下一个字符预测的神经语言模型。 每个字符嵌入在8维空间中,序列长度为80个字符。 我们使用的模型是一个两层 LSTM(隐藏大小 256),后面跟着一个密集层 (McMahan 等人,, 2017; Li 等人, 2020a, ) 所有算法共享的联合超参数包​​括:总通信轮次T=200、本地批量大小b=10、本地历元k=1以及本地优化器SGD,除非另有说明。

6.1.4 成人数据集(Dua 和 Graff,2017 年)

按照AFL (Mohri 等人,, 2019)中的设置,我们根据教育将Adult数据集分为两个不重叠的域属性 - phd 域和非 phd 域。 生成的 FL 设置由两个用户组成,每个用户都拥有来自两个域之一的数据。 此外,数据按照Li等人,2020b中的方式进行预处理,以具有99二进制特征。 我们对主论文中提到的所有 FL 算法都使用逻辑回归模型。 本地数据分为训练集、验证集和测试集,百分比分别为 80%、10% 和 10%。 在每一轮中,两个用户都参与,服务器汇总他们的损失和梯度(或权重)。 所有算法共享的联合超参数包​​括:总通信轮次T=500、本地批量大小b=10、本地历元k=1、本地学习率η=0.01,除非另有说明,本地优化器是没有动量的 SGD。 算法特定的超参数将在下面适当的地方提到。 一个重要的注意事项是 phd 域仅具有 413 个样本,而 non-phd 域具有 32,148 个样本,因此split 非常不平衡,而由于样本量不足,在 phd 域上训练 only 在所有域上的性能较差。

6.1.5 超参数

我们使用各种超参数评估不同算法的性能,总结在5中。 特别是,按照 Anstreicher 和 Wolsey (2009),我们在服务器上尝试了次线性 O(1/t) 和指数衰减 O(βt) 学习率 η ,以及用于客户端更新的固定本地学习率η 最终我们决定每 100 步将 ηt 衰减 β 倍:ηt=β[t100],其中 β=decay100/TT 是通信轮次的总数(例如 decay = 1/10)。 我们注意到,Reddi 等人,(2020) 也发现指数衰减在他们的实验中最有效。 我们使用网格搜索来为所有算法选择合适的局部学习率。

Refer to caption
Refer to caption
Refer to caption
Refer to caption
Refer to caption
图1: CIFAR-10 上 FedAvgFedMGDA 之间的插值。 x - 轴是通信轮数。 从左到右:(a) 和 (b) 非独立同分布/独立同分布设置中的平均用户准确度。 (c) 和 (d) 在非独立同分布/独立同分布设置中均匀平均训练损失。 结果是使用不同随机种子运行 5 次的平均值。
Refer to caption
Refer to caption
Refer to caption
图2: ()在成人数据集上测试 SOTA 算法的准确性,并在博士领域的损失中添加对抗性偏差;并与仅在博士领域的训练基线进行比较。 AFLq-FedAvg 的偏差尺度不同,因为 AFL 使用平均损失,而 q-FedAvg 使用(非平均)总损失。 ()在存在恶意用户的情况下,在 CIFAR-10 上测试不同算法的准确性,该恶意用户用恒定因子缩放其损失函数。 所有算法均在 Adult 上运行 500 轮,在 CIFAR-10 上运行 1500 轮。 报告的结果是使用不同随机种子运行 5 的平均值。 详细的超参数设置请参见部分B.2

我们在几个公共数据集上评估我们的算法 FedMGDA+:CIFAR-10 (Krizhevsky,, 2009)、F-MNIST (Xiao 等人,, 2017)、联邦 EMNIST (Caldas 等人,, 2018)、莎士比亚 (Li 等人, 2020a, ) 和成人 (Dua 和 Graff,, 2017) ,并与现有的 FL 系统进行比较,包括 FedAvg (McMahan 等人,, 2017)FedProx (李等人, 2020a, )0>, q-FedAvg1> (李等人, 2020b, )2>, 以及 澳大利亚足球联盟333AFL实验AFL实验 在原始工作 (Mohri 等人,, 2019) 和后来与之比较的工作中(例如 (Li 等人, 2020b, ))在数据集上报告了非常客户很少(23),可能是由于适用性原因。 我们在工作中遵循了这一惯例。 (毛利等人,2019) 此外,根据§5中的讨论,人们可以设想现有算法的几种潜在扩展,以提高其性能。 因此,我们还与以下扩展进行比较:FedAvg-n,它是带有梯度归一化的FedAvg,以及MGDA-Prox,它是 FedMGDA+ 在每个用户的损失函数中添加了近端正则化器。444也可以将梯度归一化的思想应用到q-FedAvg上;然而,我们从实验中观察到,生成的算法不稳定,特别是对于较大的 q 值。 我们区分 FedMGDA+FedMGDA,后者是 MGDA 到 FL 的普通扩展。

我们指出FL算法应部署在具有中等计算能力的智能设备上。 因此,我们选择进行实验的模型是中等规模的(参见234 了解详情),与 FedAvgq-FedAvgAFL 中的复杂度相似。 由于篇幅限制,我们仅在主论文中报告一些有代表性的结果,并将全套实验推迟到附录B

6.2实验结果

在本小节中,我们将报告有关我们提出的算法 FedMGDA+ 的实验结果,并将其与各种性能指标(包括准确性、鲁棒性和公平性)下的最先进 (SOTA) 替代方案进行比较。 我们提醒一下,准确度指标正是 FedAvg 在训练期间旨在优化的目标,因此它在该指标上比其他替代算法(例如 FedMGDA+)具有一些优势AFLq-FedAvg 都旨在为用户带来一定的公平性,也许偶尔会造成一些准确性损失,但希望损失很小。

6.2.1 恢复FedAvg

正如§5中提到的,我们可以通过调整方程中的ϵ约束来控制用户平均性能和公平性之间的平衡25 设置 ϵ=0 恢复 FedAvg,设置 ϵ=1 恢复 FedMGDA 为了凭经验验证这一点,我们使用不同的 ϵ 运行 (25),并在 1 中报告 CIFAR-10 的结果 对于数据的独立同分布和非独立同分布(F-MNIST 上的结果,请参阅部分 B.1)。 这些结果证实,将 ϵ0 更改为 1 会产生 FedAvgFedMGDA 之间的插值,正如预期的那样。 由于 FedAvg 本质上优化了(均匀)平均训练损失,因此它自然在此指标下表现最好( 1 (c) 和 (d))。 尽管如此,值得注意的是,在非独立同分布设置中,一些中间ϵ值实际上比FedAvg带来更好的用户准确性( 1 (a))。

Refer to caption
Refer to caption
Refer to caption
图3: CIFAR-10 上的用户测试精度分布:()算法运行 2000 通信轮次和 b=10 超参数为μ=0.01代表FedProxη=1.5decay=1/10代表FedMGDA+FedAvgη=1.0decay=1/10代表MGDA-Proxq=0.5L=1.0代表q-FedAvg ()算法运行 3000 通信轮次和 b=400 超参数为: μ=0.5 代表 FedProxη=1.0decay=1/40 用于 FedMGDA+MGDA-ProxFedAvgq=0.1L=0.1 用于 q-FedAvg 报告的统计数据是使用不同随机种子运行 4 的平均值。
Refer to caption
Refer to caption
图4: CIFAR-10 数据集上的训练损失与通信回合相比,改进用户的百分比。 显示了两个代表性案例:()本地批量大小b=10,以及()本地批量大小b=400 结果是使用不同随机种子运行 4 的平均值。

6.2.2稳健性

我们之前在§5中讨论过,梯度归一化和 MGDA 的内置稳健性允许 FedMGDA+ 在实际 FL 部署中对抗某些对抗性攻击。 我们现在根据经验评估 FedMGDA+ 针对这些攻击的稳健性。 我们在单个恶意用户存在的情况下运行各种 FL 算法,该用户旨在通过夸大其损失来操纵系统。 我们考虑一种对抗性设置,其中攻击者参与每一轮通信,并通过 (i) 添加偏差,或 (ii) 将其乘以缩放因子(称为偏差)来夸大其损失函数,并且分别进行​​缩放攻击。 在第一个实验中,我们通过向代表性不足的用户(即 PhD 域)添加恒定偏差来模拟对 Adult 数据集的偏差攻击,因为更自然地预期攻击者由小型用户组成用户数量。 在此设置中,我们可以获得的最差性能仅限于仅使用 PhD 数据 训练模型。 偏置攻击下的结果如图2(左)所示;另请参阅部分B.2了解更多结果。 我们观察到,在没有攻击的情况下,AFLq-FedAvg 的表现略好于 FedMGDA+;然而,它们的性能在受到攻击时会恶化到接近最坏情况的水平。 相比之下,FedMGDA+ 不会受到任何偏见攻击的影响,这从经验上支持了我们在第 §5 中的主张。 请注意,我们在此比较中没有包含 FedAvg,因为从其定义可以清楚地看出,FedAvgFedMGDA+ 一样,不受偏差的影响攻击。 2(右)显示了使用和不使用对抗性缩放的不同算法在 CIFAR-10 上的结果。 如前所述,具有梯度归一化的 q-FedAvg 非常不稳定,特别是在缩放攻击下,因此我们在这里没有包含其结果。 2(右)可以立即看出(i)缩放攻击会影响所有不采用梯度归一化的算法; (ii) q-FedAvg 在此攻击中受影响最大; (iii) 令人惊讶的是,与无扩展攻击下的结果相比,FedMGDA+ 以及在较小程度上 MGDA-Prox 实际上收敛到稍微更好的 Pareto 解决方案。 上述结果凭经验验证了 FedMGDA+ 在最常见的偏差扩展攻击下的鲁棒性。

6.2.3 公平性

最后,我们在 CIFAR-10 上使用不同的公平概念,将 FedMGDA+ 与现有的 FL 算法进行比较。 对于第一个实验,我们采用与(Li等人, 2020b, )相同的公平性度量,并通过计算用户测试误差的方差来衡量公平性。 我们使用不同的超参数运行每个算法,并在结果中选择平均准确度最好的算法,如 3 ;完整的结果表可以在部分B.3中找到。 从该图中,我们观察到 (i) FedMGDA+ 实现了最佳平均精度,而其标准差与 q-FedAvg 相当; (ii) FedMGDA+ 显着优于 FedMGDA,这清楚地证明了我们在 算法 1 中提出的修改方案 香草 MGDA; (iii) 在平均准确度和标准差方面,FedMGDA+ 优于 FedAvg-n,后者使用与 FedMGDA+ 相同的标准化步骤。 这些观察结果证实了 FedMGDA+ 在促进公平方面的有效性。 我们在 Federated EMNIST 数据集上进行了相同的实验,观察到了类似的结果,可以在 Table 6 B.4

在接下来的实验中,我们将展示 FedMGDA+ 不仅能产生公平的最终解决方案,而且还能在整个训练过程中保持公平性,即在每一轮中,它都不会为了提高整体性能而牺牲任何 参与用户的性能。 据我们所知,“训练期间的公平性”以前从未被研究过,尽管它具有很大的实际意义——它鼓励用户参与。 为了检验这种公平性,我们在 CIFAR-10 上进行了多项实验,并测量了每轮沟通中改善的参与者的百分比。 具体来说,我们测量所有参与用户每轮前后的训练损失,并报告改进或保持不变的百分比。555t 时刻改进用户的百分比定义为 iIt𝕀{fi(𝐰t+1)fi(𝐰t)}/|It|,,其中 Itt时刻选择的用户,𝕀{A}是事件A的指示函数。 4显示了两个代表性案例的训练损失在每轮沟通中改善的参与用户的百分比;请参阅部分B.5了解不同超参数的完整结果。

我们可以看到,FedMGDA+ 在用户改进百分比方面始终优于其他算法,这意味着通过使用 FedMGDA+,每次参与后性能变差的用户会减少。 此外,我们从4(左)注意到,在本地批量大小b=10的情况下,改进用户的百分比小于100%,这可以解释如下:对于小批量(即b<|𝒟|,其中𝒟表示本地数据集),接收到的更新来自用户的不是给定全局模型的用户损失的真实梯度(即𝐠ifi(𝐰));它们是真实梯度的噪声估计。 因此,MGDA 计算的共同下降方向存在噪声,并且可能并不总是适用于所有参与用户。 为了消除这种噪声的影响,我们设置了 b=|𝒟|,它允许我们从用户那里恢复真实的梯度。 结果如 4(右)所示,它证实了当步长衰减(过冲较少)时,改进用户的百分比正如预期的那样,FedMGDA+ 训练期间达到 100%。

表 6: 测试联邦 EMNIST 上用户的全批次准确率、每轮 10 个用户、本地学习率 η=0.1、总通信轮次 1500 报告的统计数据是使用不同随机种子运行 4 的平均值。
Algorithm Average (%) Std. (%)
FedMGDA 85.73±0.05 14.79±0.12
FedMGDA+ 87.60±0.20 13.68±0.19
MGDA-Prox 87.59±0.19 13.75±0.18
FedAvg 84.97±0.44 15.25±0.36
FedAvg-n 87.57±0.09 13.74±0.11
FedProx 84.97±0.45 15.26±0.35
q-FedAvg 84.97±0.44 15.25±0.37

7结论

我们提出了一种用于联邦学习的新颖算法FedMGDA+ FedMGDA+ 基于多目标优化,旨在收敛到 Pareto 平稳解。 FedMGDA+ 易于实现,需要调整的超参数较少,并且可以很好地补充现有的 FL 系统。 最重要的是,FedMGDA+ 能够抵御加法和乘法对抗性操作,并确保所有参与用户之间的公平性。 我们为FedMGDA+建立了基础知识收敛保证,指出了其与最新FL算法的联系,并进行了大量的实验来验证其有效性。 未来,我们计划正式量化多个本地更新引起的权衡,并为 FedMGDA+ 建立一些隐私保证。

致谢

用于准备本研究的资源部分由安大略省、加拿大政府通过 CIFAR 以及赞助 Vector Institute 的公司提供。 我们衷心感谢 NSERC、加拿大 CIFAR 人工智能主席计划和滑铁卢-华为联合创新实验室的资助支持。 我们感谢 NVIDIA Corporation(数据科学资助)捐赠了两个 Titan V GPU,它们在一定程度上支持了本工作的计算。

参考

附录A证明

Theorem 1a (完整版).

假设每个用户函数 fiL-Lipschitz 平滑(即 2fiL𝐈)和 M-Lipschitz 连续。 然后,对于步长 ηt(0,12L] 我们有

mint=0,,T𝐄[J𝐟(𝐰t)𝝀t]2[𝐟(𝐰0)𝐄𝐟(𝐰T+1)+t=0Tηt(Mσt+Lηtσt2)]t=0Tηt, (31)

其中 σt2:=𝐄J𝐟(𝐰t)𝛌tJ^𝐟(𝐰t)𝛌^t2 是随机共同方向的方差。 此外,如果某个用户函数 fi 从下面有界,并且可以选择 ηt 以便 tηt=,tηtσt<,则 (31) 收敛到 0。

证明。

𝝃t:=J𝐟(𝐰t)𝝀tJ^𝐟(𝐰t)𝝀^t,其中J^𝐟(𝐰t):=[^f1(𝐰t),,^fm(𝐰t)]是每个用户的随机梯度的串联,并且

𝝀t=argmin𝝀ΔJ𝐟(𝐰t)𝝀,𝝀^t=argmin𝝀^ΔJ^𝐟(𝐰t)𝝀^, (32)

对于后者,如果第 i 个用户没有参与第 t 轮,我们也会限制 λ^i=0。然后,应用二次界和更新规则(我们提醒向量和标量之间的比较应该理解为分量方式):

𝐟(𝐰t+1) 𝐟(𝐰t)ηtJ𝐟(𝐰t)J^𝐟(𝐰t)𝝀^t+Lηt22J^𝐟(𝐰t)𝝀^t2 (33)
𝐟(𝐰t)ηtJ𝐟(𝐰t)J𝐟(𝐰t)𝝀t+Lηt2J𝐟(𝐰t)𝝀t2+ηtJ𝐟(𝐰t)𝝃t+Lηt2𝝃t2 (34)
𝐟(𝐰t)ηt(1Lηt)J𝐟(𝐰t)𝝀t2+ηtM𝝃t+Lηt2𝝃t2, (35)

其中我们使用 Lipschitz 连续性 fi(𝐰)M𝝀t 的一阶最优性条件,以便

𝝀Δ,𝝀,J𝐟(𝐰t)J𝐟(𝐰t)𝝀t𝝀t,J𝐟(𝐰t)J𝐟(𝐰t)𝝀t. (36)

ηt12L,取期望并重新排列我们得到

mint=0,,T𝐄[J𝐟(𝐰t)𝝀t]2[𝐟(𝐰0)𝐄𝐟(𝐰T+1)+t=0Tηt(Mσt+Lηtσt2)]t=0Tηt, (37)

其中σt2:=𝐄𝝃t2

Theorem 1b (完整版).

假设每个用户函数 fiL-Lipschitz 平滑(即 2fiL𝐈)和 M-Lipschitz 连续。 然后,对于任意数量的局部更新k,具有全局学习率ηt(0,12L]、确定性梯度更新和局部学习率ηtl,我们有

mint=0,,TJ𝐟(𝐰t)𝝀t2[𝐟(𝐰0)𝐟(𝐰T+1)+M2ηtt=0T((εtm+ηtl(k1))+Lηt(εtm+ηtl(k1))2)]t=0Tηt, (38)

其中 εt:=𝛌t𝛌~t 是精确权重和近似权重之间的偏差。 此外,如果某个用户函数 fi 从下方有界,则 (38) 中的左侧只要 εt0ηtl0ηt0tηt=

证明。

𝝀t=argmin𝝀ΔJ𝐟(𝐰t)𝝀,𝝀~t=argmin𝝀ΔJ~𝐟(𝐰t)𝝀, (39)

δt:=J𝐟(𝐰t)𝝀tJ~𝐟(𝐰t)𝝀~t,其中 J~𝐟(𝐰t):=[~f1(𝐰t),,~fm(𝐰t)] 是每个用户累积更新 ~fi(𝐰t) 的串联。 形式上,~fi(𝐰t):=𝐰t𝐰tk 表示用户 i 的初始 𝐰tk 本地更新后的最终 𝐰tk 之间的差值。 (请注意,为了简单起见,我们在这里滥用了符号 𝐰t𝐰tk,因为它们不区分用户 i 这不是一个大问题,因为上下文很清楚。)

𝐰t1:=𝐰tfi(𝐰t)𝐰tj+1:=𝐰tjηtlfi(𝐰tj),j=1,,k1 为局部优化步骤。

然后,

~fi(𝐰t) =𝐰t𝐰tk (40)
=(𝐰t𝐰t1)+(𝐰t1𝐰t2)++(𝐰tk1𝐰tk) (41)
=fi(𝐰t)+ηtlfi(𝐰t1)++ηtlfi(𝐰tk1), (42)

因此,~fi(𝐰t) 和渐变 fi(𝐰t) 之间的差异受以下限制:

~fi(𝐰t)fi(𝐰t) =ηtlj=1k1fi(𝐰tj) (44)
ηtlj=1k1fi(𝐰tj) (45)
ηtl(k1)M, (46)

因此,

δt =J𝐟(𝐰t)𝝀tJ~𝐟(𝐰t)𝝀~t (47)
J𝐟(𝐰t)𝝀tJ𝐟(𝐰t)𝝀~t+J𝐟(𝐰t)𝝀~tJ~𝐟(𝐰t)𝝀~t (48)
εtmM+ηtl(k1)M, (49)

最后一步来自第一项的矩阵范数不等式和第二项的三角不等式。 请注意,δtεt0ηtl0 时消失。

然后,应用二次上限,我们有

𝐟(𝐰t+1) 𝐟(𝐰t)ηtJ𝐟(𝐰t)J~𝐟(𝐰t)𝝀~t+Lηt22J~𝐟(𝐰t)𝝀~t2 (50)
=𝐟(𝐰t)ηtJ𝐟(𝐰t)J𝐟(𝐰t)𝝀t+Lηt2J𝐟(𝐰t)𝝀t2+ηtJ𝐟(𝐰t)δt+Lηt2δt2 (51)
𝐟(𝐰t)ηt(1Lηt)J𝐟(𝐰t)𝝀t2+ηtMδt+Lηt2δt2, (52)

ηt12L,伸缩并重新排列我们得到

mint=0,,TJ𝐟(𝐰t)𝝀t2[𝐟(𝐰0)𝐟(𝐰T+1)+t=0Tηt(Mδt+Lηtδt2)]t=0Tηt, (53)

δt 替换为 (49),我们得到 (38)。

最后,如果 εt0ηtl0,则 δt0 以及 (38) 中的右侧 0T 时,在这种情况下,左侧 mint=0,,TJ𝐟(𝐰t)𝝀t 也会收敛到 0

Theorem 2 (完整版).

假设每个用户函数fiσ-强凸(即2fiσ𝐈)和M-Lipschitz连续。 假设在每一轮 t FedMGDA 包含一些函数 fvt 使得

fvt(𝐰t)fvt(𝐰t)t2𝐰t𝐰t2, (54)

其中 𝐰t𝐰t 到 (11) 帕累托平稳集 W 的投影。 假设𝐄[λvtt+σt|𝐰t]c>0,那么

𝐄[𝐰t+1𝐰t+12]πt(1cη0)𝐄[𝐰0𝐰02]+s=0tπtπsηs2M2, (55)

其中 πt=s=1tηsπ0=1 尤其,

  • 如果tηt=,tηt2<,则𝐄[𝐰t𝐰t2]0𝐰t收敛几乎肯定会达到帕累托平稳集W;

  • 有了选择ηt=2c(t+2)我们有

    𝐄[𝐰t𝐰t2]4M2c2(t+3). (56)
证明。

对于每个用户i,让我们定义函数

f^i(𝐰,I):=Iifi(𝐰), (57)

其中随机变量 I{0,1}m 指示哪个用户参与特定回合。 显然,我们有𝐄f^i(𝐰,I)=fi(𝐰)𝐄Ii 因此,我们的多目标最小化问题等效为:

min𝐰{𝐄f^1(𝐰,I),,𝐄f^m(𝐰,I)}, (58)

因为正缩放不会改变帕累托平稳性。 (如果愿意,我们还可以对随机函数 f^i(𝐰,I) 进行归一化,以使无偏属性 𝐄f^i(𝐰,I)=fi(𝐰) 成立。)

我们现在按照 Mercier 等人,(2018) 进行,并提供稍微更清晰的分析。 让我们表示 𝐰t 𝐰t 到 (58) 的帕累托平稳集 W 的投影,,

𝐰t=argmin𝐰W𝐰t𝐰. (59)

然后,

𝐰t+1𝐰t+12 𝐰t+1𝐰t2 (60)
=𝐰tηt𝐝t𝐰t2 (61)
=𝐰t𝐰t22ηt𝐰t𝐰t,𝐝t+ηt2𝐝t2. (62)

为了限制中间项,我们根据假设得出:

vt,f^vt(𝐰t,It)f^vt(𝐰t,It) t2𝐰t𝐰t2, (63)
i,f^i(𝐰t,It)f^i(𝐰t,It) 0, (64)

其中第二个不等式来自 𝐰t 的定义。 所以,

𝐰t𝐰t,𝐝t =𝐰t𝐰t,i:Ii=1λifi(𝐰t) (65)
i:Ii=1λi(fi(𝐰t)fi(𝐰t))+σt2𝐰t𝐰t2 (66)
=iλi(f^i(𝐰t,It)f^i(𝐰t,It))+σt2𝐰t𝐰t2 (67)
λvtt+σt2𝐰t𝐰t2. (68)

从 (62) 继续并取条件期望:

𝐄[𝐰t+1𝐰t+12|𝐰t] (1ctηt)𝐰t𝐰t2+ηt2M2, (69)

其中ct:=𝐄[λvtt+σt|𝐰t]c>0 取期望,我们得到熟悉的递归:

𝐄[𝐰t+1𝐰t+12] (1cηt)𝐄[𝐰t𝐰t2]+ηt2M2, (70)

从中我们得出

𝐄[𝐰t+1𝐰t+12] πt(1cη0)𝐄[𝐰0𝐰02]+s=0tπtπsηs2M2, (71)

其中 πt=s=1t(1cηs)π0=1 πt0tηt=开始,我们知道

𝐄[𝐰t+1𝐰t+12]0 (72)

如果 tηt=tηt2<

设置ηt=2c(t+2)我们得到πt=2(t+2)(t+1)并通过归纳

s=0tπtπsηs2=4c2(t+2)(t+1)s=0ts+1s+24c2(t+4), (73)

何处

𝐄[𝐰t+1𝐰t+12]4M2c2(t+4). (74)

使用标准的超鞅论证我们还可以证明

𝐰t𝐰t0 almost surely. (75)

该证明在随机优化中众所周知,因此省略(或参见Mercier 等人, (2018, Theorem 5) 了解详细信息)。

附录B完整的实验结果

在本节中,我们提供了主要论文中未提及的其他结果。

B.1 恢复 FedAvg 完整结果:Fashion-MNIST 和 CIFAR-10 的结果

补充15<中显示的结果/t3>和6总结了F-MNIST数据集上的类似结果,而图0>71> 以对数尺度描述了 CIFAR-10 数据集上的训练损失。

Refer to caption
Refer to caption
图5: FedAvgFedMGDA 之间的插值(F-MNIST,iid 设置)。 ()平均用户准确度。 ()训练损失均匀平均。 结果是使用不同随机种子运行 5 次的平均值。
Refer to caption
Refer to caption
图6: FedAvgFedMGDA 之间的插值(F-MNIST,非独立同分布设置)。 ()平均用户准确度。 ()训练损失均匀平均。 结果是使用不同随机种子运行 5 次的平均值。
Refer to caption
Refer to caption
图7: FedAvgFedMGDA (CIFAR-10) 之间的插值。 两张图都以对数尺度绘制了均匀平均的训练损失。 ()非独立同分布设置。 ()iid 设置。 结果是使用不同随机种子运行 5 次的平均值。

B.2 鲁棒性完整结果:对成人数据集的偏见攻击

表 7: 在成人数据集上测试 SOTA 算法的准确性,并将各种规模的对抗性偏差添加到 PhD 的域损失中;并与仅在PhD领域的训练基线进行比较。 AFL 的偏差范围与 q-FedAvg 不同,因为 AFL 使用平均损失,而 q-FedAvg 使用(非平均)总损失。 算法运行 500 轮,报告的结果是使用不同随机种子的 5 次运行的平均值。
Name Bias Uniform PhD Non-PhD
AFL 0 83.26±0.01 77.90±0.00 83.32±0.01
AFL 0.01 83.28±0.03 76.58±0.27 83.36±0.03
AFL 0.1 82.30±0.04 74.59±0.00 82.39±0.04
AFL 1 81.86±0.05 74.25±0.57 81.94±0.05
q-FedAvg, q=5 0 83.26±0.18 76.80±0.61 83.33±0.19
q-FedAvg, q=5 1000 83.34±0.04 76.57±0.44 83.41±0.04
q-FedAvg, q=5 5000 81.19±0.03 74.14±0.41 81.27±0.03
q-FedAvg, q=5 10000 81.07±0.03 73.48±0.78 81.16±0.02
q-FedAvg, q=2 0 83.30±0.09 76.46±0.56 83.38±0.09
q-FedAvg, q=2 1000 83.33±0.04 76.24±0.00 83.41±0.04
q-FedAvg, q=2 5000 83.11±0.03 75.69±0.00 83.20±0.03
q-FedAvg, q=2 10000 82.50±0.07 75.69±0.00 82.58±0.07
q-FedAvg, q=0.1 0 83.44±0.06 76.46±0.56 83.52±0.07
q-FedAvg, q=0.1 1000 83.34±0.03 76.35±0.41 83.42±0.02
q-FedAvg, q=0.1 5000 83.35±0.03 76.57±0.66 83.42±0.03
q-FedAvg, q=0.1 10000 83.36±0.05 76.80±0.49 83.43±0.05
FedMGDA+ Arbitrary