第17卷第3期 智能系统学报 Vol.17 No.3 2022年5月 CAAI Transactions on Intelligent Systems May 2022 D0:10.11992/tis.202106029 网络出版地址:htps:/ns.cnki.net/kcms/detail/23.1538.TP.20211213.1548.002.html 基于隐式随机梯度下降优化的联邦学习 窦勇敢2,袁晓形 (1.南京信息工程大学自动化学院,江苏南京210044:2.江苏省大数据分析技术重点实验室,江苏南京 210044) 摘要:联邦学习是一种分布式机器学习范式,中央服务器通过协作大量远程设备训练一个最优的全局模 型。目前联邦学习主要存在系统异构性和数据异构性这两个关键挑战。本文主要针对异构性导致的全局模型 收敛慢甚至无法收敛的问题,提出基于隐式随机梯度下降优化的联邦学习算法。与传统联邦学习更新方式不 同,本文利用本地上传的模型参数近似求出平均全局梯度,同时避免求解一阶导数,通过梯度下降来更新全局 模型参数,使全局模型能够在较少的通信轮数下达到更快更稳定的收敛结果。在实验中,模拟了不同等级的异 构环境,本文提出的算法比FedProx和FedAvg均表现出更快更稳定的收敛结果。在相同收敛结果的前提下, 本文的方法在高度异构的合成数据集上比F©dProx通信轮数减少近50%,显著提升了联邦学习的稳定性和鲁 棒性。 关键词:联邦学习;分布式机器学习;中央服务器;全局模型:隐式随机梯度下降:数据异构:系统异构:优化算 法:快速收敛 中图分类号:TP8文献标志码:A文章编号:1673-4785(2022)03-0488-08 中文引用格式:窦勇敢,袁晓彤.基于隐式随机梯度下降优化的联邦学习.智能系统学报,2022,17(3):488-495. 英文引用格式:DOU Yonggan,YUAN Xiaotong.Federated learning with implicit stochastic gradient descent optimization. CAAI transactions on intelligent systems,2022,17(3):488-495. Federated learning with implicit stochastic gradient descent optimization DOU Yonggan",YUAN Xiaotong'2 (1.School of Automation,Nanjing University of Information Science and Technology,Nanjing 210044,China;2.Jiangsu Key Laboratory of Big Data Analysis Technology,Nanjing 210044,China) Abstract:Federated learning is a distributed machine learning paradigm.The central server trains an optimal global model by collaborating with numerous remote devices.Presently,there are two key challenges faced by federated learn- ing:system and statistical heterogeneities.Herein,we mainly focus on the slow convergence of the global model or when it even fails to converge due to system and statistical heterogeneities.We propose a federated learning optimiza- tion algorithm based on implicit stochastic gradient descent optimization,which is different from the traditional method of updating in federated learning.We use the locally uploaded model parameters to approximate the average global gradient and to avoid solving the first-order and update the global model parameter via gradient descent.This is per- formed so that the global model can achieve faster and more stable convergence results with fewer communication rounds.In the experiment,different levels of heterogeneous settings were simulated.The proposed algorithm shows con- siderably faster and more stable convergence behavior than FedAvg and FedProx.In the premise of the same conver- gence results,the experimental results show that the proposed method reduces the number of communication rounds by approximately 50%compared with Fedprox in highly heterogeneous synthetic datasets.This considerably improves the stability and robustness of federated learning. Keywords:federated learning:distributed machine learning;central server;global model;implicit stochastic gradient descent;statistical heterogeneity;systems heterogeneity:optimization algorithm;faster convergence 收稿日期:2021-06-18.网络出版日期:2021-12-14. 近些年来,随着深度学习的兴起,人们看到了 基金项目:国家自然科学基金项目(61876090,61936005):科技创 新2030-“新一代人工智能”重大项目(2018AAA0100400) 人工智能的巨大潜力,同时希望人工智能技术应 通信作者:袁晓彤.E-mail:xtyuanl980@gmail.com 用到更复杂和尖端的领域。而现实状况是数据分
DOI: 10.11992/tis.202106029 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20211213.1548.002.html 基于隐式随机梯度下降优化的联邦学习 窦勇敢1,2,袁晓彤1,2 (1. 南京信息工程大学 自动化学院,江苏 南京 210044; 2. 江苏省大数据分析技术重点实验室,江苏 南京 210044) 摘 要 :联邦学习是一种分布式机器学习范式,中央服务器通过协作大量远程设备训练一个最优的全局模 型。目前联邦学习主要存在系统异构性和数据异构性这两个关键挑战。本文主要针对异构性导致的全局模型 收敛慢甚至无法收敛的问题,提出基于隐式随机梯度下降优化的联邦学习算法。与传统联邦学习更新方式不 同,本文利用本地上传的模型参数近似求出平均全局梯度,同时避免求解一阶导数,通过梯度下降来更新全局 模型参数,使全局模型能够在较少的通信轮数下达到更快更稳定的收敛结果。在实验中,模拟了不同等级的异 构环境,本文提出的算法比 FedProx 和 FedAvg 均表现出更快更稳定的收敛结果。在相同收敛结果的前提下, 本文的方法在高度异构的合成数据集上比 FedProx 通信轮数减少近 50%,显著提升了联邦学习的稳定性和鲁 棒性。 关键词:联邦学习;分布式机器学习;中央服务器;全局模型;隐式随机梯度下降;数据异构;系统异构;优化算 法;快速收敛 中图分类号:TP8 文献标志码:A 文章编号:1673−4785(2022)03−0488−08 中文引用格式:窦勇敢, 袁晓彤. 基于隐式随机梯度下降优化的联邦学习 [J]. 智能系统学报, 2022, 17(3): 488–495. 英文引用格式:DOU Yonggan, YUAN Xiaotong. Federated learning with implicit stochastic gradient descent optimization[J]. CAAI transactions on intelligent systems, 2022, 17(3): 488–495. Federated learning with implicit stochastic gradient descent optimization DOU Yonggan1,2 ,YUAN Xiaotong1,2 (1. School of Automation, Nanjing University of Information Science and Technology, Nanjing 210044, China; 2. Jiangsu Key Laboratory of Big Data Analysis Technology, Nanjing 210044, China) Abstract: Federated learning is a distributed machine learning paradigm. The central server trains an optimal global model by collaborating with numerous remote devices. Presently, there are two key challenges faced by federated learning: system and statistical heterogeneities. Herein, we mainly focus on the slow convergence of the global model or when it even fails to converge due to system and statistical heterogeneities. We propose a federated learning optimization algorithm based on implicit stochastic gradient descent optimization, which is different from the traditional method of updating in federated learning. We use the locally uploaded model parameters to approximate the average global gradient and to avoid solving the first-order and update the global model parameter via gradient descent. This is performed so that the global model can achieve faster and more stable convergence results with fewer communication rounds. In the experiment, different levels of heterogeneous settings were simulated. The proposed algorithm shows considerably faster and more stable convergence behavior than FedAvg and FedProx. In the premise of the same convergence results, the experimental results show that the proposed method reduces the number of communication rounds by approximately 50% compared with Fedprox in highly heterogeneous synthetic datasets. This considerably improves the stability and robustness of federated learning. Keywords: federated learning; distributed machine learning; central server; global model; implicit stochastic gradient descent; statistical heterogeneity; systems heterogeneity; optimization algorithm; faster convergence 近些年来,随着深度学习的兴起,人们看到了 人工智能的巨大潜力,同时希望人工智能技术应 用到更复杂和尖端的领域。而现实状况是数据分 收稿日期:2021−06−18. 网络出版日期:2021−12−14. 基金项目:国家自然科学基金项目(61876090,61936005);科技创 新 2030–“新一代人工智能”重大项目(2018AAA0100400). 通信作者:袁晓彤. E-mail: xtyuan1980@gmail.com. 第 17 卷第 3 期 智 能 系 统 学 报 Vol.17 No.3 2022 年 5 月 CAAI Transactions on Intelligent Systems May 2022
·489· 实勇敢,等:基于隐式随机梯度下降优化的联邦学习 第3期 散在各个用户或行业中,用户数据存在隐私上的 行可变数量的本地工作,缺乏自主调节能力。 敏感性和安全性。如何在保护数据隐私前提下进 在解决联邦学习异构性的问题上,近邻优化 行机器学习模型训练,让人工智能技术发挥出更 的更新方式广泛地用于研究,包括高效通信分布 强大的作用成为一种挑战。 式机器学习16、联邦学习中公平性和鲁棒性的权 为了让这些隐私数据流动起来,同时应对非 衡。近邻优化在原理上与有偏正则化相同,其 独立同分布数据的影响,Google科学家Mcma- 中文献[I8]中考虑有偏正则化的方法对FedAvg han等提出联邦学习(federated learning),通过协 进行重新参数化,提出FedPro,通过有偏正则化 调大量远程分布式设备在保护用户数据隐私的前 约束每个设备学习的本地模型更加接近于全局模 提下训练一个高质量的全局模型。 型,并允许各参与训练的设备在本地执行可变数 目前的联邦学习算法还存在诸多问题。首 量的工作,在异构环境中提供了收敛的保证。由 先,每个设备CPU、GPU、ISP、电池以及网络连接 于FedProx在优化全局模型参数w时和FedAvg方 (3G、4G、5G、WIFI)回等硬件差异导致设备间存 式相同,通过简单平均本地上传的模型参数来更 在很大的系统异构性。传统的联邦学习方法Fe- 新全局模型参数,导致全局模型收敛速度慢,缺 dAvg”在规定时间内将没有训练结束的设备简单 乏直接对全局模型参数的优化。 丢弃,这在现实情况中是不可取的,浪费了大量 受小批量近似更新的元学习机制的启发, 的计算资源。其次,每个设备的数据分布和类型 本文提出了基于隐式随机梯度下降优化的联邦 存在很大的差异),跨设备的数据是非独立同分 学习算法,在本地模型更新阶段通过近邻优化约 布的(non-D),这是数据的异构性。不同的异构 束本地模型更新更加接近于全局模型,在全局 环境中模型的收敛效果差别很大,甚至无法收 模型聚合阶段通过求解近似全局梯度,利用梯度 敛。这些系统级别的异构性给联邦学习带来了极 下降来更新全局模型参数。最终实现全局模型 大的挑战。 能够在较少的通信轮数下达到更快更稳定的收敛 现有针对异构性问题的分布式优化算法中, 结果。 大部分都是针对特定异构环境设定的。例如:文 本文的贡献主要体现在以下3个方面: 献[4-6]提出让所有设备都参与每一轮的训练,虽 1)区别于已有的方法,不在对全局模型参数 然在异构数据环境中的收敛性得到了保证,但是 进行简单平均。在全局模型聚合阶段,通过利用 这在现实的联邦环境山中是不可行的。这不仅增 本地上传的模型参数近似求出平均全局梯度,同 加了服务器的通信负担,而且参与联邦训练的设 时也避免求解一阶导数。 备也应随机抽取。也有方法通过共享本地数据来 2)针对异构性导致的全局模型收敛慢甚至 解决数据异构性的问题-,但这违背了联邦学习 无法收敛的问题,区别于现有的联邦学习算法, 保护用户数据隐私的前提。在联邦设置中,文献[9 本文提出基于隐式随机梯度下降优化的联邦学习 通过在服务器端设计基于动量优化器FEDYOGI 算法,通过隐式随机梯度下降来更新全局模型参 来加快异构数据环境中全局模型收敛速度,这虽 数,能够使全局模型参数实现更加高效的更新, 然提高了模型的收敛速度,但却增加了服务器的 从而可以在有限的计算资源下加快模型的收敛 计算量,在有限的计算资源下不是好的选择。此 速度。 外,也有研究者利用二阶拟牛顿法优化模型,在 3)和现有的工作相比,本文的算法在高度异 相同的异构环境中,与FedAvg相比达到相同精 构的合成数据集上,30轮左右就可以达到Fe- 度下减少了通信轮数,提高了通信效率,但这潜 dAvg的收敛效果,40轮左右可以达到FedProx的 在增加了客户端本地的计算量。 收敛效果。在相同收敛效果的前提下,本文的算 除了数据异构性,每个参与联邦训练的客户 法比FedProx减少了近50%的通信轮数。 端的硬件存在差异,这导致设备间存在很大的系 统异构性。例如:在文献12-15]中,介绍了在 1客户端-服务器的联邦学习更新架构 异构环境中目前最新的联邦学习研究进展,在全 联邦学习更新架构主要有客户端-服务器和 局模型聚合阶段的更新方式同FedAvg一样,在 去中心化对等计算架构。其中最常用的是客户端- 指定的时间窗口内,服务器将未完成训练的设备 服务器的联邦学习更新架构。训练过程主要分为 直接丢弃,不允许上传本轮训练的模型参数。各 两个阶段:本地模型更新阶段和全局模型聚合阶 参与训练的设备不能根据自己硬件性能在本地执 段。具体更新过程如图1所示
散在各个用户或行业中,用户数据存在隐私上的 敏感性和安全性。如何在保护数据隐私前提下进 行机器学习模型训练,让人工智能技术发挥出更 强大的作用成为一种挑战。 为了让这些隐私数据流动起来,同时应对非 独立同分布数据的影响,Google 科学家 Mcmahan 等 [1] 提出联邦学习 (federated learning),通过协 调大量远程分布式设备在保护用户数据隐私的前 提下训练一个高质量的全局模型。 目前的联邦学习算法还存在诸多问题。首 先,每个设备 CPU、GPU、ISP、电池以及网络连接 (3G、4G、5G、WIFI) [2] 等硬件差异导致设备间存 在很大的系统异构性。传统的联邦学习方法 FedAvg[1] 在规定时间内将没有训练结束的设备简单 丢弃,这在现实情况中是不可取的,浪费了大量 的计算资源。其次,每个设备的数据分布和类型 存在很大的差异[3] ,跨设备的数据是非独立同分 布的(non-IID),这是数据的异构性。不同的异构 环境中模型的收敛效果差别很大,甚至无法收 敛。这些系统级别的异构性给联邦学习带来了极 大的挑战。 现有针对异构性问题的分布式优化算法中, 大部分都是针对特定异构环境设定的。例如:文 献 [4-6] 提出让所有设备都参与每一轮的训练,虽 然在异构数据环境中的收敛性得到了保证,但是 这在现实的联邦环境[1] 中是不可行的。这不仅增 加了服务器的通信负担,而且参与联邦训练的设 备也应随机抽取。也有方法通过共享本地数据来 解决数据异构性的问题[7-8] ,但这违背了联邦学习 保护用户数据隐私的前提。在联邦设置中,文献 [9] 通过在服务器端设计基于动量优化器 FEDYOGI 来加快异构数据环境中全局模型收敛速度,这虽 然提高了模型的收敛速度,但却增加了服务器的 计算量,在有限的计算资源下不是好的选择。此 外,也有研究者利用二阶拟牛顿法优化模型[10] ,在 相同的异构环境中,与 FedAvg 相比达到相同精 度下减少了通信轮数,提高了通信效率,但这潜 在增加了客户端本地的计算量。 除了数据异构性,每个参与联邦训练的客户 端的硬件存在差异,这导致设备间存在很大的系 统异构性[11]。例如:在文献 [12-15] 中,介绍了在 异构环境中目前最新的联邦学习研究进展,在全 局模型聚合阶段的更新方式同 FedAvg[1] 一样,在 指定的时间窗口内,服务器将未完成训练的设备 直接丢弃,不允许上传本轮训练的模型参数。各 参与训练的设备不能根据自己硬件性能在本地执 行可变数量的本地工作,缺乏自主调节能力。 w 在解决联邦学习异构性的问题上,近邻优化 的更新方式广泛地用于研究,包括高效通信分布 式机器学习[16] 、联邦学习中公平性和鲁棒性的权 衡 [17]。近邻优化在原理上与有偏正则化相同,其 中文献 [18] 中考虑有偏正则化的方法对 FedAvg 进行重新参数化,提出 FedProx,通过有偏正则化 约束每个设备学习的本地模型更加接近于全局模 型,并允许各参与训练的设备在本地执行可变数 量的工作,在异构环境中提供了收敛的保证。由 于 FedProx 在优化全局模型参数 时和 FedAvg 方 式相同,通过简单平均本地上传的模型参数来更 新全局模型参数,导致全局模型收敛速度慢,缺 乏直接对全局模型参数的优化。 受小批量近似更新的元学习机制[19] 的启发, 本文提出了基于隐式随机梯度下降优化的联邦 学习算法,在本地模型更新阶段通过近邻优化约 束本地模型更新更加接近于全局模型,在全局 模型聚合阶段通过求解近似全局梯度,利用梯度 下降来更新全局模型参数。最终实现全局模型 能够在较少的通信轮数下达到更快更稳定的收敛 结果。 本文的贡献主要体现在以下 3 个方面: 1) 区别于已有的方法,不在对全局模型参数 进行简单平均。在全局模型聚合阶段,通过利用 本地上传的模型参数近似求出平均全局梯度,同 时也避免求解一阶导数。 2) 针对异构性导致的全局模型收敛慢甚至 无法收敛的问题,区别于现有的联邦学习算法, 本文提出基于隐式随机梯度下降优化的联邦学习 算法,通过隐式随机梯度下降来更新全局模型参 数,能够使全局模型参数实现更加高效的更新, 从而可以在有限的计算资源下加快模型的收敛 速度。 3) 和现有的工作相比,本文的算法在高度异 构的合成数据集上,30 轮左右就可以达到 FedAvg 的收敛效果,40 轮左右可以达到 FedProx 的 收敛效果。在相同收敛效果的前提下,本文的算 法比 FedProx 减少了近 50% 的通信轮数。 1 客户端–服务器的联邦学习更新架构 联邦学习更新架构主要有客户端–服务器和 去中心化对等计算架构。其中最常用的是客户端– 服务器的联邦学习更新架构。训练过程主要分为 两个阶段:本地模型更新阶段和全局模型聚合阶 段。具体更新过程如图 1 所示。 ·489· 窦勇敢,等:基于隐式随机梯度下降优化的联邦学习 第 3 期
第17卷 智能系统学报 ·490· 服务器聚合更新 {w】wg】wg】,…,wr 服务器 [w] [w]] [w] [w]] 客户端本地更新 For each selected clientick in parallel do [] [w]]=Enc[[w 0 w=Dec[[p']] 客户端1 客户端2 客户端3 客户端k 图1客户端-服务器联邦学习架构 Fig.1 Federated learning architecture of client and server 1)本地模型更新 离较小。具体的算法流程为: 在本地模型更新阶段,服务器首先随机选取 输入w随机初始化参数,N总设备: K个客户端,然后服务器发送全局模型参数[w 输出最终的全局模型参数w。 给被选客户端,客户端利用本地数据并行执行 1)FOR全局轮数t=0,1,…,T-1; E个epoch的随机梯度下降,然后将更新后的模型 2)Server以概率p随机选取K个设备并指定 参数经过同态加密算法2o加密w】=Encw], 固定学习率; 之后再上传至服务器。 3)Server发送当前全局模型w给所选设备; 2)全局模型聚合 4)每个设备k=1,2,…,K并行计算:F(w)= 服务器聚合来自各个客户端加密后的模型参 数{w,w]】,[w],…,w]》,对模型参数 (f(wxy) 几ke 进行加权平均计算,最后服务器将更新后的全局 5)w!-arg min F.(m)hv 模型参数[]发送给下一轮被选客户端。客户端 6)重复4人5),结束并行计算,每个设备将计 接收全局模型参数并将其解密w=Dec[w],进行 算结果w传至Server; 下一轮模型参数更新。重复上述过程,直至损失 7)Server以固定轮数衰减的学习率n,对 收敛。 (w-w)做梯度下降更新全局模型参数: 2隐式随机梯度下降优化的联邦学 w+1=w- 习算法设计 - 8)Server将更新后的模型参数w+1发送给CIi- 在本节中,主要介绍联邦近邻优化算法和隐 ents: 式随机梯度下降优化算法的关键要素。由于联邦 9)重复28)t次; 学习是通过大量设备与中央服务器协同学习一个最 10)END 优的全局模型,因此我们的最终目标是最小化: 在算法1中,步骤4)~6)为本地模型训练阶 minEminF()+w 段,7)~9)为Server全局模型更新阶段,然后将更 (1) 新后的模型参数发送给下一轮参与训练的设备。 式中:w是设备k在本地迭代过程中所得的近似最 不断重复以上过程,直至模型损失收敛。 优解;w是需要求解全局模型的最优解;F(w)= 2.1联邦近邻优化 En[C(f(w,x),y】,每个设备本地数据x服从不 在本地模型训练阶段,主要在本地模型更新 同的分布D,损失函数是预测值与真实值之间的 时引入带参数的近邻算子约束本地模型更新更加 差。式(1)包含两方面的优化过程:1)在本地模 接近于全局模型,这种本地优化算法被称为Fed- 型训练阶段,每个设备通过全局模型参数w学习 PrOx算法8,每个设备k的本地目标函数被重新定 一个本地近似最优w;2)在全局模型聚合阶段, 义为 服务器通过各设备上传的w利用隐式随机梯度下 minG.ow)=Fa(w)+号-wG (2) 降来调整全局模型参数w,使w与所有w,的平均距
服务器 {[[w1 ]], [[w2 ]], [[w3 ]], …, [[wk ]]} t+1 t+1 t+1 t+1 [[wt ]] [[wt ]] [[wt ]] [[wt ]] [[wt+1 [[w ]] t+1 [[w 3 ]] k t+1]] 2 [[wt+1]] 1 客户端 1 客户端 2 客户端 3 客户端 k … … 客户端本地更新 For each selected client i ϵ k in parallel do for epoch=1, … , E do wt+1 i =wi−ηc t Δ G t i(wi ) Returnwi t+1to server t+1 t+1 [[wi ]]=Enc[[wi ]] t t wi =Dec[[w ]] 服务器聚合更新 图 1 客户端-服务器联邦学习架构 Fig. 1 Federated learning architecture of client and server 1)本地模型更新 K [[w t ]] E [[w t+1 i ]] = Enc[w t+1 i ] 在本地模型更新阶段,服务器首先随机选取 个客户端,然后服务器发送全局模型参数 给被选客户端,客户端利用本地数据并行执行 个 epoch 的随机梯度下降,然后将更新后的模型 参数经过同态加密算法[20] 加密 , 之后再上传至服务器。 2)全局模型聚合 {[[w t+1 1 ]],[[w t+1 2 ]],[[w t+1 3 ]],··· ,[[w t+1 k ]]} [[w t ]] w t i = Dec [[w t ]] 服务器聚合来自各个客户端加密后的模型参 数 ,对模型参数 进行加权平均计算,最后服务器将更新后的全局 模型参数 发送给下一轮被选客户端。客户端 接收全局模型参数并将其解密 ,进行 下一轮模型参数更新。重复上述过程,直至损失 收敛。 2 隐式随机梯度下降优化的联邦学 习算法设计 在本节中,主要介绍联邦近邻优化算法和隐 式随机梯度下降优化算法的关键要素。由于联邦 学习是通过大量设备与中央服务器协同学习一个最 优的全局模型,因此我们的最终目标是最小化: min w Ek [ min wk { Fk (wk)+ λ 2 ∥wk −w∥ 2 2 }] (1) wk k w Fk (wk) := Exk∼Dk [ L(f (wk , xi), yi) ] xk Dk w wk wk w w wk 式中: 是设备 在本地迭代过程中所得的近似最 优解; 是需要求解全局模型的最优解; ,每个设备本地数据 服从不 同的分布 ,损失函数是预测值与真实值之间的 差。式 (1) 包含两方面的优化过程:1)在本地模 型训练阶段,每个设备通过全局模型参数 学习 一个本地近似最优 ;2)在全局模型聚合阶段, 服务器通过各设备上传的 利用隐式随机梯度下 降来调整全局模型参数 ,使 与所有 的平均距 离较小。具体的算法流程为: w 0 输入 随机初始化参数, N 总设备; w 输出 最终的全局模型参数 t+1。 1) FOR 全局轮数 t = 0,1,··· ,T −1 ; pk K ηc 2) Server 以概率 随机选取 个设备并指定 固定学习率 ; w t 3) Server 发送当前全局模型 给所选设备; k = 1,2,··· ,K Fk (wk) = 1 nk ∑ i∈nk L(f (wk , xi), yi) 4) 每个设备 并行计算: ; w t+1 k = argmin wk [ Fk (wk)+ λ 2 ∥wk −w t ∥ 2 2 ] 5) ; w t+1 k 6) 重复 4)~ 5),结束并行计算,每个设备将计 算结果 传至 Server; ηg λ ( w t −w ∗ k ) 7) Serve r 以固定轮数衰减的学习率 对 做梯度下降更新全局模型参数: w t+1 = w t −ηgλ w t− 1 K ∑ k∈S t w t+1 k ; w t+1 8) Server 将更新后的模型参数 发送给 Clients; 9) 重复 2)~8) t 次; 10) END 在算法 1 中,步骤 4)~6) 为本地模型训练阶 段,7)~9) 为 Server 全局模型更新阶段,然后将更 新后的模型参数发送给下一轮参与训练的设备。 不断重复以上过程,直至模型损失收敛。 2.1 联邦近邻优化 k 在本地模型训练阶段,主要在本地模型更新 时引入带参数的近邻算子约束本地模型更新更加 接近于全局模型,这种本地优化算法被称为 FedProx 算法[18] ,每个设备 的本地目标函数被重新定 义为 min wk Gk (wk) = Fk (wk)+ λ 2 wk −w t 2 2 (2) 第 17 卷 智 能 系 统 学 报 ·490·
·491· 实勇敢,等:基于隐式随机梯度下降优化的联邦学习 第3期 式中:A是一个约束本地模型和全局模型差异的 有设备上传的本地模型参数作为更新后的全局模 超参数:w表示在第轮服务器聚合更新之后的全 型参数。因为VG(w)=A(w-w),所以在服务器 局模型参数。 2.2基于隐式随机梯度下降的全局模型更新优化 端只需通过如-只之就可以得到平均全局 本地训练结束后,每个设备将更新后的模型 模型梯度,因此避免了求解一阶导数,然后利用 参数w上传至服务器,服务器通过聚合本地模型 随机梯度下降对全局模型参数进行更新。相比 参数更新全局模型参数。从加快全局模型收敛速 于FedProx,本算法在信息比较冗余的情况下能更 度的目标出发,在服务器全局模型聚合阶段利用 高效地利用有效信息。其次,在迭代的过程 隐式随机梯度下降算法对全局模型参数进一步优 中也会很快收敛到最小值附近,加快模型的收敛 化,使其能够在有限的资源下以更少的通信轮数 速度。 达到更快更稳定的收敛效果。 3实验与结果 由于客户端本地目标函数为minG.(w)= F(w)+)w-w,假设w是目标函数Gw)的最 为了验证本文提出的隐式随机梯度下降优化 优解,且函数F.(w)可微。由一阶最优条件可以 算法的有效性,本文在3个真实数据集和3个合成 得到: 数据集上进行实验,在分类和回归任务上进行评 VF(w)+λ(w-w)=0 (3) 估,并与当前具有代表性的解决异构性问题的方 由链式法则可以得到: 法FedProx阁以及经典的FedAvg算法进行比较。 3.1实验设置 VG:(w)-3w w VF:(wi)+ 在Linux系统下,包括2块GeForce GTX1080 -(8)w- Ti和1块GeForce GTX TITAN X的服务器上进行 (4) 仿真实验,代码使用Tensorflow框架实现,基于 )*F.()- Python.3来实现基于隐式随机梯度下降优化的联 邦学习算法。其中,训练轮数、每轮迭代次数、选 a(w'-wi) 择设备数量、学习率等超参数设置如表1所示。 所以7G(w)=A(w-w),式(4)展现了全局模 型的梯度估计可以通过求解当前任务的近似更新 表1超参数设置 来计算。在第轮,所选设备在本地数据集上利用 Table 1 Setting of Hyperparameters 随机梯度下降更新E轮后,求出近似最优解w。 超参数 Synthetic Snet140 MNIST EMNIST 服务器通过式(4)可以计算出平均的全局梯度: 200 800 200 200 VG(w)= (5) Naum_cpochs 20 20 30 20 Bhatch_size 10 10 10 o 由于精确的本地最优解w很难去估计,本文 Nau clients 0 10 10 10 用次优解w来代替w,因此全局模型参数更新为 ne 0.01 0.6 0.03 0.003 =w-ngA -2 (6) ngi 0.75 1.1 0.75 0.95 式中:S,为K个设备的子集;t为当前训练轮数; 为了保证评估方法与结果的公平性,本文提 1 :=为按固定轮数衰减的学习率;为初始化 出的方法与FedProx、FedAvg使用了相同的本地 学习率,在训练模型初期用较大的学习率对全局 求解器,在模拟系统异构设置时,掉队的设备数 模型进行优化,随着通信轮数的不断增加学习率 量分别设置为0%、50%、90%。生成合成数据集 逐步减小,有效保证了全局模型在训练过程中能 本文使用了和FedProx类似的方法,通过式(7)生 以较快的速度逐步趋于稳定。更新后的w1作为 成本地数据: 下一轮训练的全局模型参数。 y=argmax (softmax(Wx+b)) (7) 从式(3)(6)推导过程很容易看出,本文提出 式中:W∈10×60:x∈60:b∈10。通过式(7)生成 基于隐式随机梯度下降优化的联邦学习算法是直 30个设备的数据集,同样每轮随机抽取10个参 接对全局模型参数进行优化,而不是简单平均所 与训练
λ w t t 式中: 是一个约束本地模型和全局模型差异的 超参数; 表示在第 轮服务器聚合更新之后的全 局模型参数。 2.2 基于隐式随机梯度下降的全局模型更新优化 w t+1 k 本地训练结束后,每个设备将更新后的模型 参数 上传至服务器,服务器通过聚合本地模型 参数更新全局模型参数。从加快全局模型收敛速 度的目标出发,在服务器全局模型聚合阶段利用 隐式随机梯度下降算法对全局模型参数进一步优 化,使其能够在有限的资源下以更少的通信轮数 达到更快更稳定的收敛效果。 min wk Gk (wk) = Fk (wk)+ λ 2 ∥wk −w t ∥ 2 2 w ∗ k Gk (wk) Fk (wk) 由于客户端本地目标函数为 ,假设 是目标函数 的最 优解,且函数 可微。由一阶最优条件可以 得到: ∇F ( w ∗ k ) +λ ( w ∗ k −w t ) = 0 (3) 由链式法则可以得到: ∇Gk ( w t ) = ( ∂w ∗ k ∂wt )⊺ ∇Fk ( w ∗ k ) + λ ( I− ( ∂w ∗ k ∂wt )⊺) ( w t −w ∗ k ) = λ ( w t −w ∗ k ) + ( ∂w ∗ k ∂wt )⊺ ∗ ( ∇Fk ( w ∗ k ) +λ ( w ∗ k −w t )) = λ ( w t −w ∗ k ) (4) ∇Gk (w t ) = λ ( w t −w ∗ k ) t w t+1 k 所以 ,式(4)展现了全局模 型的梯度估计可以通过求解当前任务的近似更新 来计算。在第 轮,所选设备在本地数据集上利用 随机梯度下降更新 E 轮后,求出近似最优解 。 服务器通过式 (4) 可以计算出平均的全局梯度: ∇G ( w t ) = λ w t − 1 K ∑ k∈S t w ∗ k (5) w ∗ k w t+1 k w ∗ k 由于精确的本地最优解 很难去估计,本文 用次优解 来代替 ,因此全局模型参数更新为 w t+1 = w t −ηgλ w t − 1 K ∑ k∈S t w t+1 k (6) S t t ηg = 1 t ηgi ηgi w t+1 式中: 为 K 个设备的子集; 为当前训练轮数; 为按固定轮数衰减的学习率; 为初始化 学习率,在训练模型初期用较大的学习率对全局 模型进行优化,随着通信轮数的不断增加学习率 逐步减小,有效保证了全局模型在训练过程中能 以较快的速度逐步趋于稳定。更新后的 作为 下一轮训练的全局模型参数。 从式 (3)~(6) 推导过程很容易看出,本文提出 基于隐式随机梯度下降优化的联邦学习算法是直 接对全局模型参数进行优化,而不是简单平均所 ∇Gk (w t ) = λ ( w t −w ∗ k ) λ w t − 1 K ∑ k∈S t w ∗ k 有设备上传的本地模型参数作为更新后的全局模 型参数。因为 ,所以在服务器 端只需通过 就可以得到平均全局 模型梯度,因此避免了求解一阶导数,然后利用 随机梯度下降对全局模型参数进行更新。相比 于 FedProx,本算法在信息比较冗余的情况下能更 高效地利用有效信息。其次,在迭代的过程 中也会很快收敛到最小值附近,加快模型的收敛 速度。 3 实验与结果 为了验证本文提出的隐式随机梯度下降优化 算法的有效性,本文在 3 个真实数据集和 3 个合成 数据集上进行实验,在分类和回归任务上进行评 估,并与当前具有代表性的解决异构性问题的方 法 FedProx[18] 以及经典的 FedAvg[1] 算法进行比较。 3.1 实验设置 在 Linux 系统下,包括 2 块 GeForce GTX 1 080 Ti 和 1 块 GeForce GTX TITAN X 的服务器上进行 仿真实验,代码使用 Tensorflow 框架实现,基于 Python3 来实现基于隐式随机梯度下降优化的联 邦学习算法。其中,训练轮数、每轮迭代次数、选 择设备数量、学习率等超参数设置如表 1 所示。 表 1 超参数设置 Table 1 Setting of Hyperparameters 超参数 Synthetic Snet140 MNIST EMNIST Nnum_rounds 200 800 200 200 Nnum_epochs 20 20 20 20 Bbatch_size 10 10 10 10 Nnum_clients 10 10 10 10 ηc 0.01 0.6 0.03 0.003 ηgi 0.75 1.1 0.75 0.95 为了保证评估方法与结果的公平性,本文提 出的方法与 FedProx、FedAvg 使用了相同的本地 求解器,在模拟系统异构设置时,掉队的设备数 量分别设置为 0%、50%、90%。生成合成数据集 本文使用了和 FedProx 类似的方法,通过式(7)生 成本地数据: y = argmax(softmax(W x+b)) (7) 式中: W ∈ 10×60;x ∈ 60;b ∈ 10。通过式(7)生成 30 个设备的数据集,同样每轮随机抽取 10 个参 与训练。 ·491· 窦勇敢,等:基于隐式随机梯度下降优化的联邦学习 第 3 期
第17卷 智能系统学报 ·492· 3.23个真实数据集和模型 表2设备数据集分布 Sent1402l是一个Twitter带有表情的文本信 Table 2 Datasets distribution on devices 息情感分类数据集,该任务使用的是一个两层 数据集 设备/台 总样本/个 平均样本/个 LSTM,包含256个隐藏层单元,每个Twitter帐户 Sent140 772 40783 53 对应一个设备。该模型以25个字符序列作为输 MNIST 1000 69035 69 EMNIST 200 18345 92 入,通过两个LSTM层和一个全连接层,每个训 练样本输出一个字符。 3.3 合成数据集实验结果分析 MNIST22是一个0~9手写体数字识别数据 首先在第1个实验中,为了验证本文的算法 集,在这个任务上利用逻辑回归的方法研究手写 在异构数据集上有更快的收敛速度,本文在3组 数字图像分类问题。为了生成非独立同分布数 合成数据集上进行实验,分别是Synthetic_0_0 据,本文将数据随机分布在1000个设备中,每个 Synthetic_0.5_0.5、Synthetic_1l,从左到右数据异 设备只有2种数字。模型的输人是28x28维的图 构性逐渐增强,异构性越强,对模型收敛影响越 像,输出是0~9这10个数字的标签。 大。本文通过损失的减小速度和梯度方差2的 EMNIST2)是MNIST数据集的扩展,包含 变化来衡量模型的收敛速度,结果如图2所示。 09数字和26个英文字母的大小写,构成了更大 为了证明本文方法的公平性和有效性,约束项 难度的62类手写字符图像分类任务,但在实验中 统一设置成相同的值。由图2训练损失和梯度 只随机抽取10个小写字母,每个设备分配5个 方差可以看出,本文的方法在第30轮左右达到 类,在这个任务上利用逻辑回归的方法研究图像 了FedAvg的收敛效果,在第40轮左右达到了 分类问题。模型的输人是28×28维的图像,输出 FedProx的收敛效果,并且40轮以后还在继续收 是aj这10个类的标签。 敛。梯度方差(variance of local gradient,.VLG)越 对于以上所有数据集,客户端的本地数据分配 小表示越稳定,收敛性越好。VLG可表示为 遵循幂律分布。本文在本地分配80%为训练集 VLG= 20%为测试集。各设备数据集组成如表2所示。 G)-v. (8) 60 40 .Ours 40 -Ours 75 50 0 50100150 200 0 50100150200 0 50100.150200 训练轮数 训练轮数 训练轮数 (a)Synthetic_0_0损失曲线 (b)Synthetic0.50.5损失曲线 (c)Synthetic_.L_I损失曲线 8 1.2 2.5 FedAvg FedProx Ours 1.00 1.0 1.5 0.6 1.0 F一ousV .50 0.30 0.4 0.5 50 100150 200 50100150 200 50 100150200 训练轮数 训练轮数 训练轮数 (d)Synthetic00梯度方差曲线(e)Synthetic0.50.5梯度方差曲线 ()Synthetic_L_1梯度方差曲线 图2合成数据集实验结果分析 Fig.2 Analysis of experimental results of synthetic datasets 实验中,通过使所有设备执行相同的工作量 表3合成数据集上平均测试精度 来模拟不存在系统异构性的情况,随着数据异构 Table 3 Average test accuracy on synthetic datasets 性增强,全局模型收敛结果最终会趋于某个区 数据集 FedAvg FedProx 本文 间,因此本文取最后一半通信轮数的平均测试精 Synthetic 00 79.6 83.6 85.0 度作为模型好坏的评判标准,在合成数据集上平 Synthetic 0.5 0.5 79.3 81.7 84.5 均测试精度如表3所示,可以看出本文提出的算 Synthetic 1 I 69.7 75.6 76.3 法平均测试精度普遍高于FedProx和FedAvg
3.2 3 个真实数据集和模型 Sent140[21] 是一个 Twitter 带有表情的文本信 息情感分类数据集,该任务使用的是一个两层 LSTM,包含 256 个隐藏层单元,每个 Twitter 帐户 对应一个设备。该模型以 25 个字符序列作为输 入,通过两个 LSTM 层和一个全连接层,每个训 练样本输出一个字符。 × MNIST[22] 是一个 0~9 手写体数字识别数据 集,在这个任务上利用逻辑回归的方法研究手写 数字图像分类问题。为了生成非独立同分布数 据,本文将数据随机分布在 1 000 个设备中,每个 设备只有 2 种数字。模型的输入是 28 28 维的图 像,输出是 0~9 这 10 个数字的标签。 × EMNIST[23] 是 MNIST 数据集的扩展,包含 0~9 数字和 26 个英文字母的大小写,构成了更大 难度的 62 类手写字符图像分类任务,但在实验中 只随机抽取 10 个小写字母,每个设备分配 5 个 类,在这个任务上利用逻辑回归的方法研究图像 分类问题。模型的输入是 28 28 维的图像,输出 是 a~j 这 10 个类的标签。 对于以上所有数据集,客户端的本地数据分配 遵循幂律分布[24]。本文在本地分配 80% 为训练集, 20% 为测试集。各设备数据集组成如表 2 所示。 表 2 设备数据集分布 Table 2 Datasets distribution on devices 数据集 设备/台 总样本/个 平均样本/个 Sent140 772 40783 53 MNIST 1 000 69035 69 EMNIST 200 18345 92 3.3 合成数据集实验结果分析 λ 首先在第 1 个实验中,为了验证本文的算法 在异构数据集上有更快的收敛速度,本文在 3 组 合成数据集上进行实验,分别是 Synthetic_0_0、 Synthetic_0.5_0.5、Synthetic_1_1,从左到右数据异 构性逐渐增强,异构性越强,对模型收敛影响越 大。本文通过损失的减小速度和梯度方差[25] 的 变化来衡量模型的收敛速度,结果如图 2 所示。 为了证明本文方法的公平性和有效性,约束项 统一设置成相同的值。由图 2 训练损失和梯度 方差可以看出,本文的方法在第 30 轮左右达到 了 FedAvg 的收敛效果,在第 40 轮左右达到了 FedProx 的收敛效果,并且 40 轮以后还在继续收 敛。梯度方差(variance of local gradient, VLG)越 小表示越稳定,收敛性越好。VLG 可表示为 VLG = 1 K ∑K k=1 ∇G ( w t ) − ∇Gk ( w t+1 k ) 2 (8) 60 40 20 0 训练损失 75 100 117 50 25 12 训练损失 64 60 40 20 0 训练损失 (a) Synthetic_0_0 损失曲线 (b) Synthetic_0.5_0.5 损失曲线 (c) Synthetic_1_1 损失曲线 (d) Synthetic_0_0 梯度方差曲线 (e) Synthetic_0.5_0.5 梯度方差曲线 (f) Synthetic_1_1 梯度方差曲线 FedAvg FedProx Ours 50 100 150 200 训练轮数 50 100 150 200 训练轮数 0 50 100 150 200 训练轮数 0 50 100 150 200 训练轮数 FedAvg FedProx Ours FedAvg FedProx FedAvg FedProx FedAvg FedProx Ours Ours Ours 梯度方差 1.50 1.59 1.00 0.50 0.30 梯度方差 1.2 0.8 1.0 0.6 0.4 梯度方差 2.5 2.0 1.5 1.0 0.5 0 50 100 150 200 训练轮数 0 50 100 150 200 训练轮数 FedAvg FedProx Ours 图 2 合成数据集实验结果分析 Fig. 2 Analysis of experimental results of synthetic datasets 实验中,通过使所有设备执行相同的工作量 来模拟不存在系统异构性的情况,随着数据异构 性增强,全局模型收敛结果最终会趋于某个区 间,因此本文取最后一半通信轮数的平均测试精 度作为模型好坏的评判标准,在合成数据集上平 均测试精度如表 3 所示,可以看出本文提出的算 法平均测试精度普遍高于 FedProx 和 FedAvg。 表 3 合成数据集上平均测试精度 Table 3 Average test accuracy on synthetic datasets % 数据集 FedAvg FedProx 本文 Synthetic_0_0 79.6 83.6 85.0 Synthetic_0.5_0.5 79.3 81.7 84.5 Synthetic_1_1 69.7 75.6 76.3 第 17 卷 智 能 系 统 学 报 ·492·
·493· 窦勇敢,等:基于隐式随机梯度下降优化的联邦学习 第3期 3.4真实数据集实验结果分析 者为0%时,代表所有设备执行相同的工作量 在本实验中,为了验证本文提出的算法在高 (E=20)。在指定的全局时间周期内,当E<20时, 度系统异构性和数据异构性环境下的整体效果, FedAvg会丢掉这些掉队者,本文的算法和Fed 本节在3个联邦学习常用真实数据集和一个合成 PrOx会合并这些掉队者,不同的是本文在全局模 数据集上比较不同算法的稳定性和收敛效果,其 型聚合阶段会有效地使用合并掉队者的模型参 中Synthetic11客户端本地类别设置为5,实现在 数,利用隐式随机梯度下降对全局模型进一步优 数据异构性基础上模拟不同系统异构性的联邦设置。 化。真实数据集上的训练损失如图3所示,从上 本文通过约束设备的本地工作量,使每个设 到下3行图片分别代表0%、50%和90%的掉队 备训练指定的E来模拟系统的异构性,对于不同 者。随着迭代轮数的不断增加,平均损失逐渐趋 的异构设置,随机选择不同的E(E<20)分配给 于稳定,从图3中可以看出本文提出的算法的收 0%、50%和90%当前参与训练的设备。当掉队 敛速度明显优于Fedavg和FedProx。 …FedAvg ---FedProx -Ours 1.5 1.8 15 6 罩4 0.5 20 0.5 0.5 0 50 100 150200 50 100150200 0 100200300 400 0 200400600800 训练轮数 训练轮数 训练轮数 训练轮数 (a)Synthetic11掉队者o% (b)MNIST掉队者0% (c)EMNIST掉队者O% (d)Sent140掉队者0% 1.8 1.5 18 1.5 1.0 1.0 50 25 三 0.5 =03 05 0 50100150200 50100150200 0 100200300400 200400600800 训练轮数 训练轮数 训练轮数 训练轮数 (e)Synthetic1I掉队者50% ()MNIST掉队者50% (g)EMNIST掉队者50% (h)Sent140掉队者50% 1.8 1.5 1.5, 价 130 1.5 100 1.0 M 0.5 0 50100150200 50100150200 100200300400 200400600800 训练轮数 训练轮数 训练轮数 训练轮数 (①Synthetic_I_1掉队者90% G)MNIST掉队者90% (k)EMNIST掉队者90% (0)Sent140掉队者90% 图3真实联邦数据集实验结果分析 Fig.3 Analysis of experimental results of realistic federated datasets 表4给出了在高度异构环境下模型的平均测 4结束语 试精度,从表中可以看出掉队者为90%时,本文 提出的算法的平均测试精度最高,其次是Fed- 本文提出了一种基于隐式随机梯度下降优化 Prox。本文算法在MNIST数据集上比FedProx 的联邦学习算法。全局模型聚合阶段不再是简单 高5%。实验中,在Sentl40数据集上通过设置相 的平均各设备上传的模型参数,而是利用本地上 同超参数进行比较不同算法运行时间,在通信轮 传的模型参数近似求出全局梯度,同时避免求解 数为200的情况下,FedAvg、FedProx和本文所提 一阶导数。利用随机梯度下降对全局模型参数 算法运行时间分别为67min、108min、108min。 进行更新,在信息几余的情况下能更准确地利用 有效信息,随着通信轮数不断增加,全局模型会 表4高度异构环境各算法平均测试精度 Table 4 Average test accuracy of each algorithm in 很快收敛到最小值附近。在3个合成数据集和 highlyheterogeneous environment % 3个真实数据集上的实验结果充分表明:该算法 数据集 FedAvg FedProx 本文算法 能够在不同异构环境中均表现出更快更稳健的收 敛结果,显著提高了联邦学习在实际应用系统中 Synthetic 1 1 72.3 76.1 77.4 的稳定性和鲁棒性。 MNIST 76.7 81.4 86.4 EMNIST 50.4 68.1 68.3 参考文献: Sent140 57.0 69.4 69.5 [1]MCMAHAN B,MOORE E,RAMAGE D,et al.Commu-
3.4 真实数据集实验结果分析 在本实验中,为了验证本文提出的算法在高 度系统异构性和数据异构性环境下的整体效果, 本节在 3 个联邦学习常用真实数据集和一个合成 数据集上比较不同算法的稳定性和收敛效果,其 中 Synthetic_1_1 客户端本地类别设置为 5,实现在 数据异构性基础上模拟不同系统异构性的联邦设置。 本文通过约束设备的本地工作量,使每个设 备训练指定的E来模拟系统的异构性,对于不同 的异构设置,随机选择不同的 E(E<20) 分配给 0%、50% 和 90% 当前参与训练的设备。当掉队 者为 0% 时,代表所有设备执行相同的工作量 (E=20)。在指定的全局时间周期内,当 E<20 时, FedAvg 会丢掉这些掉队者,本文的算法和 FedProx 会合并这些掉队者,不同的是本文在全局模 型聚合阶段会有效地使用合并掉队者的模型参 数,利用隐式随机梯度下降对全局模型进一步优 化。真实数据集上的训练损失如图 3 所示,从上 到下 3 行图片分别代表 0%、50% 和 90% 的掉队 者。随着迭代轮数的不断增加,平均损失逐渐趋 于稳定,从图 3 中可以看出本文提出的算法的收 敛速度明显优于 Fedavg 和 FedProx。 1.5 1.8 1.0 0.5 训练损失 1.5 1.8 1.0 0.5 训练损失 1.5 1.8 1.0 0.5 训练损失 1.0 1.5 0.5 0.3 训练损失 1.0 1.5 0.5 0.3 训练损失 1.0 1.5 0.5 0.3 训练损失 1.0 1.5 0.5 0.4 训练损失 100 130 50 0 训练损失 50 75 83 25 60 72 40 20 训练损失 训练损失 1.5 1.8 1.0 训练损失 0.5 1.5 1.8 1.0 训练损失 0.5 训练轮数 训练轮数 训练轮数 0 100 200 300 400 0 100 200 300 400 100 200 300 400 0 200 400 600 800 0 200 400 600 800 0 200 400 600 800 0 50 100 150 200 0 50 100 150 200 0 50 100 150 200 训练轮数 训练轮数 训练轮数 训练轮数 训练轮数 训练轮数 训练轮数 训练轮数 训练轮数 0 50 100 150 200 0 50 100 150 200 0 50 100 150 200 FedAvg FedProx Ours (a) Synthetic_1_1 掉队者0% (b) MNIST 掉队者0% (c) EMNIST 掉队者0% (d) Sent140 掉队者0% (e) Synthetic_1_1 掉队者50% (f) MNIST 掉队者50% (g) EMNIST 掉队者50% (h) Sent140 掉队者50% (i) Synthetic_1_1 掉队者90% (j) MNIST 掉队者90% (k) EMNIST 掉队者90% (l) Sent140 掉队者90% 图 3 真实联邦数据集实验结果分析 Fig. 3 Analysis of experimental results of realistic federated datasets 表 4 给出了在高度异构环境下模型的平均测 试精度,从表中可以看出掉队者为 90% 时,本文 提出的算法的平均测试精度最高,其次是 FedProx。本文算法在 MNIST 数据集上比 FedProx 高 5%。实验中,在 Sent140 数据集上通过设置相 同超参数进行比较不同算法运行时间,在通信轮 数为 200 的情况下,FedAvg、FedProx 和本文所提 算法运行时间分别为 67 min、108 min、108 min。 表 4 高度异构环境各算法平均测试精度 Table 4 Average test accuracy of each algorithm in highlyheterogeneous environment % 数据集 FedAvg FedProx 本文算法 Synthetic_1_1 72.3 76.1 77.4 MNIST 76.7 81.4 86.4 EMNIST 50.4 68.1 68.3 Sent140 57.0 69.4 69.5 4 结束语 本文提出了一种基于隐式随机梯度下降优化 的联邦学习算法。全局模型聚合阶段不再是简单 的平均各设备上传的模型参数,而是利用本地上 传的模型参数近似求出全局梯度,同时避免求解 一阶导数。 利用随机梯度下降对全局模型参数 进行更新,在信息冗余的情况下能更准确地利用 有效信息,随着通信轮数不断增加,全局模型会 很快收敛到最小值附近。在 3 个合成数据集和 3 个真实数据集上的实验结果充分表明:该算法 能够在不同异构环境中均表现出更快更稳健的收 敛结果,显著提高了联邦学习在实际应用系统中 的稳定性和鲁棒性。 参考文献: [1] MCMAHAN B, MOORE E, RAMAGE D, et al. Commu- ·493· 窦勇敢,等:基于隐式随机梯度下降优化的联邦学习 第 3 期
第17卷 智能系统学报 ·494· nication-efficient learning of deep networks from decent- 2021,32(2):394-410 ralized data[C]//Proceedings of the 20th International [13]MALINOVSKIY G,KOVALEV D,GASANOV E,et Conference on Artificial Intelligence and Statistics.Fort al.From local SGD to local fixed-point methods for fed Lauderdale,USA,2017:1273-1282. erated learning[C]/Proceedings of the 37th Internation- [2]WANG Hongyi,YUROCHKIN M,SUN Yuekai,et al. al Conference on Machine Learning.New York,USA, Federated learning with matched averaging [EB/OL]. 2020:6692-6701. (2020-02-25)[2021-03-09 Ihttps:/arxiv:2002.06440, [14]HANZELY F.RICHTARIK P.Federated learning of a 2020. mixture of global and local models [EB/OLl.(2020- [3]KOPPARAPU K,LIN E,ZHAO J.FedCD:Improving 02-10)[2021-03-09]https:/∥arXiv:2002.05516,2020. performance in non-IID federated learning [EB/OL]. [15]ROTHCHILD D.PANDA A.ULLAH E,et al.FetchS- (2020-07-27)[2021-03-09]https:/∥arxiv:2006.09637 GD:Communication-efficient federated learning with 2020. sketching[C]//Proceedings of the 37th International Con- [4]YU Hao,YANG Sen,ZHU Shenghuo.Parallel restarted ference on Machine Learning.New York,USA,2020: SGD with faster convergence and less communication: 8253-8265. Demystifying why model averaging works for deep learn- [16]WANG Jialei,WANG Weiran,SREBRO N.Memory ing[C]//Proceedings of the Thirty-Third AAAl Confer- and communication efficient distributed stochastic op- ence on Artificial Intelligence.Palo Alto,USA,2019: timization with minibatch-prox[Cl//Proceedings of the 5693-5700. 2017 Conference on Learning Theory.New York,USA, [5]WANG Shigiang,TUOR T,SALONIDIS T,et al.Adapt- 2017:1882-1919. ive federated learning in resource constrained edge com- [17]LI Tian,HU Shengyuan,BEIRAMI A,et al.Federated puting systems[J].IEEE journal on selected areas in com- multi-task learning for competing constraints[EB/OL]. munications,2019,37(6):1205-1221. [2021-03-09]https://openreview.net/forum?id=1ZN5 [6]YU Hao,JIN Rong,YANG Sen.On the linear speedup y4yx6T1. analysis of communication efficient momentum SGD for [18]LI Tian,SAHU A,ZAHEER M,et al.Federated optim- distributed non-convex optimization[C]//Proceedings of ization in heterogeneous networks[J.Proceeding of ma- the 36th International Conference on Machine Learning. chine learning and systems,2020,2:429-450. Long Beach,USA,2019:7184-7193. [19]ZHOU Pan,YUAN Xiaotong,XU Huan,et al.Efficient [7]JEONG E,OH S,KIM H,et al.Communication-efficient meta learning via minibatch proximal update[EB/OL]. on-device machine learning:federated distillation and (2019-12-08)[2021-03-09]https:/openreview.net/ augmentation under Non-IID private data [EB/OL]. forum?id=B1gSHVrx8S. (2018-11-28)[2021-03-09]https:∥arxiv:1811.11479, [20]PHONG L T,AONO Y,HAYASHI T,et al.Privacy- 2018. preserving deep learning via additively homomorphic [8]HUANG Li,YIN Yifeng,FU Zeng,et al.LoAdaBoost: encryption[].IEEE transactions on information forensics loss-based AdaBoost federated machine learning with re- and security,2018,13(S):1333-1345. duced computational complexity on IID and non-IID in- [21]GO A,BHAYANI R,HUANG Lei.Twitter sentiment tensive care data[J].PLoS one,2020,15(4):e0230706. classification using distant supervision[J].CS224N [9]REDDI S.CHARLES Z,ZAHEER M,et al.Adaptive project report,Stanford,2009,1(12):2009. federated optimization [EB/OL].(2021-09-08) [22]LECUN Y,BOTTOU L,BENGIO Y,et al.Gradient- [2021-10-09]htps:/∥arXiv::2003.00295,2021 based learning applied to document recognition[J].Pro- [10]YANG Kai,FAN Tao,CHEN Tianjian,et al.A quasi- ceedings of the IEEE,1998,86(11):2278-2324 newton method based vertical federated learning frame- [23]COHEN G,AFSHAR S,TAPSON J,et al.EMNIST:ex- work for logistic regression[EB/OL].(2019-12-04) tending MNIST to handwritten letters[C]//2017 Interna- [2021-09-08]htps:∥arXiv:1912.00513,2019. tional Joint Conference on Neural Networks (IJCNN). [11]DHAKAL S.PRAKASH S.YONA Y,et al.Coded fed- Anchorage,USA,2017:2921-2926. erated learning[C]//2019 IEEE Globecom Workshops [24]Tung KK.Topics in Mathematical Modeling[M].Prin- (GC Wkshps).Waikoloa,USA,2019:1-6. ceton University Press,2007. [12]WANG Cong,YANG Yuanyuan,ZHOU Pengzhan.To- [25]BALLES,LUKAS,PHILIPP HENNING.Dissecting wards efficient scheduling of federated mobile devices adam:the sign,magnitude and variance of stochastic under computational and statistical heterogeneity[J]. gradients[C]//International Conference on Machine IEEE transactions on parallel and distributed systems, Learning.PMLR,2018:404-413
nication-efficient learning of deep networks from decentralized data[C]//Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Fort Lauderdale, USA, 2017: 1273−1282. WANG Hongyi, YUROCHKIN M, SUN Yuekai, et al. Federated learning with matched averaging [EB/OL]. (2020−02−25)[2021−03−09]https://arxiv: 2002.06440, 2020. [2] KOPPARAPU K, LIN E, ZHAO J. FedCD: Improving performance in non-IID federated learning [EB/OL]. (2020−07−27) [2021−03−09]https:// arxiv: 2006.09637, 2020. [3] YU Hao, YANG Sen, ZHU Shenghuo. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning[C]//Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. Palo Alto, USA, 2019: 5693-5700. [4] WANG Shiqiang, TUOR T, SALONIDIS T, et al. Adaptive federated learning in resource constrained edge computing systems[J]. IEEE journal on selected areas in communications, 2019, 37(6): 1205–1221. [5] YU Hao, JIN Rong, YANG Sen. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization[C]//Proceedings of the 36th International Conference on Machine Learning. Long Beach, USA, 2019: 7184−7193. [6] JEONG E, OH S, KIM H, et al. Communication-efficient on-device machine learning: federated distillation and augmentation under Non-IID private data [EB/OL]. (2018−11−28)[2021−03−09]https:// arxiv: 1811.11479, 2018. [7] HUANG Li, YIN Yifeng, FU Zeng, et al. LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data[J]. PLoS one, 2020, 15(4): e0230706. [8] REDDI S, CHARLES Z, ZAHEER M, et al. Adaptive federated optimization [EB/OL]. (2021−09−08) [2021−10−09]https:// arXiv: 2003.00295, 2021. [9] YANG Kai, FAN Tao, CHEN Tianjian, et al. A quasinewton method based vertical federated learning framework for logistic regression[EB/OL]. (2019−12−04) [2021−09−08]https:// arXiv: 1912.00513, 2019. [10] DHAKAL S, PRAKASH S, YONA Y, et al. Coded federated learning[C]//2019 IEEE Globecom Workshops (GC Wkshps). Waikoloa, USA, 2019: 1−6. [11] WANG Cong, YANG Yuanyuan, ZHOU Pengzhan. Towards efficient scheduling of federated mobile devices under computational and statistical heterogeneity[J]. IEEE transactions on parallel and distributed systems, [12] 2021, 32(2): 394–410. MALINOVSKIY G, KOVALEV D, GASANOV E, et al. From local SGD to local fixed-point methods for federated learning[C]//Proceedings of the 37th International Conference on Machine Learning. New York, USA, 2020: 6692−6701. [13] HANZELY F, RICHTÁRIK P. Federated learning of a mixture of global and local models [EB/OL]. (2020− 02−10)[2021−03−09]https:// arXiv: 2002.05516, 2020. [14] ROTHCHILD D, PANDA A, ULLAH E, et al. FetchSGD: Communication-efficient federated learning with sketching[C]//Proceedings of the 37th International Conference on Machine Learning. New York, USA, 2020: 8253−8265. [15] WANG Jialei, WANG Weiran, SREBRO N. Memory and communication efficient distributed stochastic optimization with minibatch-prox[C]//Proceedings of the 2017 Conference on Learning Theory. New York, USA, 2017: 1882−1919. [16] LI Tian, HU Shengyuan, BEIRAMI A, et al. Federated multi-task learning for competing constraints[EB/OL]. [2021−03−09]https://openreview.net/forum?id=1ZN5 y4yx6T1. [17] LI Tian, SAHU A, ZAHEER M, et al. Federated optimization in heterogeneous networks[J]. Proceeding of machine learning and systems, 2020, 2: 429–450. [18] ZHOU Pan, YUAN Xiaotong, XU Huan, et al. Efficient meta learning via minibatch proximal update[EB/OL]. (2019−12−08)[2021−03−09]https://openreview.net/ forum?id=B1gSHVrx8S. [19] PHONG L T, AONO Y, HAYASHI T, et al. Privacypreserving deep learning via additively homomorphic encryption[J]. IEEE transactions on information forensics and security, 2018, 13(5): 1333–1345. [20] GO A, BHAYANI R, HUANG Lei. Twitter sentiment classification using distant supervision[J]. CS224N project report, Stanford, 2009, 1(12): 2009. [21] LECUN Y, BOTTOU L, BENGIO Y, et al. Gradientbased learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278–2324. [22] COHEN G, AFSHAR S, TAPSON J, et al. EMNIST: extending MNIST to handwritten letters[C]//2017 International Joint Conference on Neural Networks (IJCNN). Anchorage, USA, 2017: 2921−2926. [23] Tung K K. Topics in Mathematical Modeling[M]. Princeton University Press, 2007. [24] BALLES, LUKAS, PHILIPP HENNING. Dissecting adam: the sign, magnitude and variance of stochastic gradients[C]//International Conference on Machine Learning. PMLR, 2018: 404−413. [25] 第 17 卷 智 能 系 统 学 报 ·494·
·495· 窦勇敢,等:基于隐式随机梯度下降优化的联邦学习 第3期 作者简介: 袁晓彤,教授,博士生导师,中国 计算机学会计算机视觉专委会委员 实勇敢,硕士研究生,主要研究方 中国自动化学会模式识别与机器智 向为联邦学习、语义分割。 能专委会委员,IEEE会员,主要研究 方向为机器学习和计算机视觉。入选 江苏省双创人才。发表学术论文80 余篇。 关于提名2022年度中国人工智能学会会士候选人的通知 根据《中国人工智能学会会士评定工作办法》的规定,2022年度中国人工智能学会会士候选人提名工 作即日启动。现将本会会士候选人提名要求及安排通知如下: 一、会士候选人资格 会士候选人必须同时满足以下条件: (一)在人工智能领域的科学研究与技术开发方面做出国内外瞩目的突出成就及创新贡献。 (二)所做出的科研成果在人工智能相关产业起了引领作用,或发表在高水平期刊或会议上的论文在国 内外产生了广泛的学术影响。 (三)具有五年以上(对学会有突出贡献者不限)高级会员会龄,并一直关心支持学会工作,为学会建设 做出了突出贡献。 二、会士候选人的提名 (一)会士评选采用提名制,会士候选人须由被提名人之外的其他人提名产生。每位会士候选人须得到 三名提名人的提名。 (二)学会会士是有效提名人,每位提名人每年作为提名人提名会士候选人不得超过两人。 (三)会士提名人必须填写《中国人工智能学会会士候选人提名表》(见附件)。 三、会士评定程序 会士评定工作委员会对会士被提名人的资格与提名程序进行审核,若符合要求,则提名成立,被提名人 确定为正式候选人,并将材料提交会士评定专家委员会依据《中国人工智能学会会士评定工作办法》评定 遴选。会士评选结果将在学会网站上公示五个工作日;若无异议,正式当选为中国人工智能学会会士。 四、材料报送 请提名人填写《中国人工智能学会会士候选人提名表》并签字,于2022年5月31日前发送至会士评定 工作委员会办公室,邮箱:zhb@caai.cn。 提名工作期间有问题请咨询会士评定工作委员会办公室。 联系人:贾晓丽 电话:010-82686686 邮箱:zhb@caai.cn 中国人工智能学会 2022年5月5日
作者简介: 窦勇敢,硕士研究生,主要研究方 向为联邦学习、语义分割。 袁晓彤,教授,博士生导师,中国 计算机学会计算机视觉专委会委员, 中国自动化学会模式识别与机器智 能专委会委员,IEEE 会员,主要研究 方向为机器学习和计算机视觉。入选 江苏省双创人才。发表学术论文 80 余篇。 关于提名 2022 年度中国人工智能学会会士候选人的通知 根据《中国人工智能学会会士评定工作办法》的规定,2022 年度中国人工智能学会会士候选人提名工 作即日启动。现将本会会士候选人提名要求及安排通知如下: 一、会士候选人资格 会士候选人必须同时满足以下条件: (一)在人工智能领域的科学研究与技术开发方面做出国内外瞩目的突出成就及创新贡献。 (二)所做出的科研成果在人工智能相关产业起了引领作用,或发表在高水平期刊或会议上的论文在国 内外产生了广泛的学术影响。 (三)具有五年以上(对学会有突出贡献者不限)高级会员会龄,并一直关心支持学会工作,为学会建设 做出了突出贡献。 二、会士候选人的提名 (一)会士评选采用提名制,会士候选人须由被提名人之外的其他人提名产生。每位会士候选人须得到 三名提名人的提名。 (二)学会会士是有效提名人,每位提名人每年作为提名人提名会士候选人不得超过两人。 (三)会士提名人必须填写《中国人工智能学会会士候选人提名表》(见附件)。 三、会士评定程序 会士评定工作委员会对会士被提名人的资格与提名程序进行审核,若符合要求,则提名成立,被提名人 确定为正式候选人,并将材料提交会士评定专家委员会依据《中国人工智能学会会士评定工作办法》评定 遴选。会士评选结果将在学会网站上公示五个工作日;若无异议,正式当选为中国人工智能学会会士。 四、材料报送 请提名人填写《中国人工智能学会会士候选人提名表》并签字,于 2022 年 5 月 31 日前发送至会士评定 工作委员会办公室,邮箱:zhb@caai.cn。 提名工作期间有问题请咨询会士评定工作委员会办公室。 联系人:贾晓丽 电 话:010-82686686 邮 箱:zhb@caai.cn 中国人工智能学会 2022 年 5 月 5 日 ·495· 窦勇敢,等:基于隐式随机梯度下降优化的联邦学习 第 3 期