Efficient wireless federated learning algorithm based on 1‑bit compressive sensing

doi:10.11772/j.issn.1001-9081.2021061374

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (6): 1675-1682.DOI: 10.11772/j.issn.1001-9081.2021061374

• National Open Distributed and Parallel Computing Conference 2021 (DPCS 2021） • Previous Articles

Efficient wireless federated learning algorithm based on 1‑bit compressive sensing

Zhenyu ZHANG¹, Guoping TAN¹^,², Siyuan ZHOU¹^,²()

^1.College of Computer and Information，Hohai University，Nanjing Jiangsu 211100，China
^2.Jiangsu Intelligent Transportation and Intelligent Driving Research Institute，Nanjing Jiangsu 210019，China

Received:2021-08-02 Revised:2021-09-02 Accepted:2021-09-08 Online:2022-01-10 Published:2022-06-10
Contact: Siyuan ZHOU
About author:ZHANG Zhenyu，born in 1998，M. S. candidate. His researchinterests include wireless network，federated learning
TAN Guoping，born in 1975，Ph. D.，professor. His researchinterests include wireless distributed machine learning，mobile edge computing，internet of vehicles.
Supported by:
National Natural Science Foundation of China(61701168);China Postdoctoral Science Foundation(2019M651546);Major Science and Technology Project of Transportation Department of Jiangsu Province(2019Z07)

基于1‑bit压缩感知的高效无线联邦学习算法

章振宇¹, 谭国平¹^,², 周思源¹^,²()

^1.河海大学计算机与信息学院，南京 211100
^2.江苏智能交通及智能驾驶研究院，南京 210019

通讯作者: 周思源
作者简介:章振宇（1998—），男，江苏南京人，硕士研究生，CCF会员，主要研究方向：无线网络、联邦学习
谭国平（1975—），男，湖南澧县人，教授，博士生导师，博士，CCF会员，主要研究方向：无线分布式机器学习、移动边缘计算、车联网
基金资助:
国家自然科学基金资助项目(61701168);中国博士后科研基金资助项目(2019M651546);江苏省交通运输厅重大科技项目(2019Z07)

Abstract

Abstract:

In the wireless Federated Learning （FL） architecture， the model parameter data need to be continuously exchanged between the client and the server to update the model， thus causing a large communication overhead and power consumption on the client. At present， there are many methods to reduce communication overhead by data quantization and data sparseness. In order to further reduce the communication overhead， a wireless FL algorithm based on 1?bit compressive sensing was proposed. In the uplink of wireless FL architecture， the data update parameters of its local model， including update amplitude and trend， were firstly recorded on the client. Then， sparsification was performed to the amplitude and trend information， and the threshold required for updating was determined. Finally， 1?bit compressive sensing was performed on the update trend information， thereby compressing the uplink data. On this basis， the data size was further compressed by setting dynamic threshold. Experimental results on MNIST datasets show that the 1?bit compressive sensing process with the introduction of dynamic threshold can achieve the same results as the lossless transmission process， and reduce the amount of model parameter data to be transmitted by the client during the uplink communication of FL applications to 1/25 of the normal FL process without this method； and can reduce the total user upload data size to 2/11 of the original size and reduce the transmission energy consumption to 1/10 of the original size when the global model is trained to the same level.

Key words: Federated Learning (FL), wireless channel, quantization coding, compressive sensing, communication overhead

摘要：

在无线联邦学习（FL）的架构中，用户端与服务器端之间需要持续交换模型参数数据来实现模型的更新，因此会对用户端造成较大的通信开销和功率消耗。目前已经有多种通过数据量化以及数据稀疏化来降低通信开销的方法。为了进一步降低通信开销，提出了一种基于1?bit压缩感知的无线FL算法。在无线FL架构的上行链路中，这种算法首先在用户端记录其本地模型数据的更新参数，包括更新幅值和趋势；接着对幅值和趋势信息进行稀疏化，并确定更新所需的阈值；最后对更新趋势信息进行1?bit压缩感知，从而压缩上行数据。在此基础上，通过设置动态阈值的方法进一步压缩数据大小。在MNIST数据集上的实验结果表明：引入动态阈值的1?bit压缩感知过程能够获得与无损传输过程相同的效果，在FL应用的上行通信过程中能将用户端需要传输的模型参数数据量降低至不采用该方法的标准FL过程的1/25；而在全局模型训练到相同水平时，能将用户上传数据总大小降低至原来的2/11，将传输能耗降低至原来的1/10。

关键词: 联邦学习, 无线信道, 量化编码, 压缩感知, 通信开销

CLC Number:

TP181

Zhenyu ZHANG, Guoping TAN, Siyuan ZHOU. Efficient wireless federated learning algorithm based on 1‑bit compressive sensing[J]. Journal of Computer Applications, 2022, 42(6): 1675-1682.

章振宇, 谭国平, 周思源. 基于1‑bit压缩感知的高效无线联邦学习算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1675-1682.

Figures/Tables 10

Fig. 1 Example of a cellular network architecture executing federated learning

Fig. 2 Flowchart of sparse ternary compression

Fig. 3 Flowchart of introducing 1?bit compressive sensing

Fig. 4 Influence of sparsity on signal recovering accuracy

Tab. 1 System parameters

参数	取值	参数	取值
$P B$	1 W	$γ E$	0.006 5 J
$P m a x$	0.01 W	$γ T$	500 ms
$P i$	0.01 W	$m$	0.023 dB
$N 0$	-174 dBm/Hz	$ϑ$	10⁹
$B D$	20 MHz	$ς$	10^-27
$B U$	1 MHz	$ω i$	40
$σ i$	1	$K i$	［6，5，4，2，1］

Tab. 1 System parameters

参数	取值	参数	取值
$P B$	1 W	$γ E$	0.006 5 J
$P m a x$	0.01 W	$γ T$	500 ms
$P i$	0.01 W	$m$	0.023 dB
$N 0$	-174 dBm/Hz	$ϑ$	10⁹
$B D$	20 MHz	$ς$	10^-27
$B U$	1 MHz	$ω i$	40
$σ i$	1	$K i$	［6，5，4，2，1］

Fig. 5 Influence of sparsification threshold on identification accuracy of sparse ternary compression

Fig. 6 Influence of number of measurements on identification accuracy

Fig. 7 Influence of dynamic sparsification threshold on identification accuracy

Fig. 8 Relationship between identification accuracy and number of bits uploaded

Fig. 9 Relationship between identification accuracy and user transmission energy consumption

References 25

1	KONEČNÝ J， MCMAHAN H B， RAMAGE D， et al. Federated optimization： distributed machine learning for on-device intelligence［EB/OL］. （2016-10-08）［2021-06-12］..
2	MCMAHAN B， MOORE E， RAMAGE D， et al. Communication-efficient learning of deep networks from decentralized data［C］// Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2017：1273-1282.
3	KONEČNÝ J， McMAHAN H B， YU F X， et al. Federated learning： strategies for improving communication efficiency［EB/OL］. （2017-10-30）［2021-06-17］..
4	RIBERO M， VIKALO H. Communication-efficient federated learning via optimal client sampling［EB/OL］. （2020-10-14）［2021-06-08］.. 10.48550/arXiv.2007.15197
5	CHEN Y， SUN X Y， JIN Y C. Communication-efficient federated deep learning with layerwise asynchronous model update and temporally weighted aggregation［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 31（10）： 4229-4238. 10.1109/tnnls.2019.2953131
6	WANG L P， WANG W， LI B. CMFL： mitigating communication overhead for federated learning［C］// Proceedings of the IEEE 39th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2019： 954-964. 10.1109/icdcs.2019.00099
7	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-06-16］.. 10.1109/mis.2020.3028613
8	XU J J， DU W L， JIN Y C， et al. Ternary compression for communication-efficient federated learning［J］. IEEE Transactions on Neural Networks and Learning Systems， 2022， 33（3）： 1162-1176. 10.1109/tnnls.2020.3041185
9	HE Y， ZENK M， FRITZ M. CosSGD： nonlinear quantization for communication-efficient federated learning［EB/OL］. （2020-12-15）［2021-06-20］.. 10.48550/arXiv.2012.08241
10	CHEN R， LI L， XUE K P， et al. To talk or to work： energy efficient federated learning over mobile devices via the weight quantization and 5G transmission co-design［EB/OL］. （2020-12-21）［2021-06-20］.. 10.48550/arXiv.2012.11070
11	LI L， SHI D， HOU R H， et al. To talk or to work： flexible communication compression for energy efficient federated learning over heterogeneous mobile edge devices［C］// Proceedings of the 2021 IEEE Conference on Computer Communications. Piscataway： IEEE， 2021： 1-10. 10.1109/infocom42981.2021.9488839
12	SATTLER F， WIEDEMANN S， MÜLLER K R， et al. Sparse binary compression： towards distributed deep learning with minimal communication［C］// Proceedings of the 2019 International Joint Conference on Neural Networks. Piscataway： IEEE， 2019： 1-8. 10.1109/ijcnn.2019.8852172
13	SATTLER F， WIEDEMANN S， MÜLLER K R， et al. Robust and communication-efficient federated learning from non-IID data［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 31（9）： 3400-3413. 10.1109/tnnls.2019.2944481
14	CALDAS S， KONEČNÝ J， McMAHAN H B， et al. Expanding the reach of federated learning by reducing client resource requirements［EB/OL］. （2019-01-08）［2021-06-23］.. 10.48550/arXiv.1812.07210
15	JEON Y S， AMIRI M M， LI J， et al. A compressive sensing approach for federated learning over massive MIMO communication systems［J］. IEEE Transactions on Wireless Communications， 2021， 20（3）： 1990-2004. 10.1109/twc.2020.3038407
16	FAN X， WANG Y， HUO Y， et al. 1‑bit compressive sensing for efficient federated learning over the air［EB/OL］. （2021-03-30）［2021-06-22］.. 10.1109/iccworkshops50388.2021.9473872
17	PAN Y J， PAN C H， YANG Z H， et al. Resource allocation for D2D communications underlaying a NOMA-based cellular network［J］. IEEE Wireless Communications Letters， 2018， 7（1）： 130-133. 10.1109/lwc.2017.2759114
18	CHEN M Z， YANG Z H， SAAD W， et al. A joint learning and communications framework for federated learning over wireless networks［J］. IEEE Transactions on Wireless Communications， 2021， 20（1）： 269-283. 10.1109/twc.2020.3024629
19	XI Y， BURR A， WEI J B， et al. A general upper bound to evaluate packet error rate over quasi-static fading channels［J］. IEEE Transactions on Wireless Communications， 2011， 10（5）： 1373-1377. 10.1109/twc.2011.012411.100787
20	KUHN H W. The Hungarian method for the assignment problem［J］. Naval Research Logistics Quarterly， 1955， 2（1/2）： 83-97. 10.1002/nav.3800020109
21	BOUFOUNOS P T， BARANIUK R G. 1‑bit compressive sensing［C］// Proceedings of the 42nd Annual Conference on Information Sciences and Systems. Piscataway： IEEE， 2008： 16-21. 10.1109/ciss.2008.4558487
22	JACQUES L， LASKA J N， BOUFOUNOS P T， et al. Robust 1‑bit compressive sensing via binary stable embeddings of sparse vectors［J］. IEEE Transactions on Information Theory， 2013， 59（4）： 2082-2102. 10.1109/tit.2012.2234823
23	KOEP N， MATHAR R. Binary iterative hard thresholding for frequency-sparse signal recovery［C］// Proceedings of the 21th International ITG Workshop on Smart Antennas. Berlin： VDE VERLAG， 2017： 1-7. 10.1109/ssp.2018.8450728
24	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. 10.1109/5.726791
25	HENNIG C， KUTLUKAYA M. Some thoughts about the design of loss functions［J］. REVSTAT — Statistical Journal， 2007， 5（1）： 19-39.

[1]	Xinyuan QIU, Zecong YE, Xiaolong CUI, Zhiqiang GAO. Survey of communication overhead of federated learning [J]. Journal of Computer Applications, 2022, 42(2): 333-342.
[2]	SHEN Ziyi, WANG Weiya, JIANG Donghua, RONG Xianwei. Visual image encryption algorithm based on Hopfield chaotic neural network and compressive sensing [J]. Journal of Computer Applications, 2021, 41(10): 2893-2899.
[3]	ZHANG Yitian, YU Jiong, LU Liang, LI Ziyang. Task scheduling strategy based on data stream classification in Heron [J]. Journal of Computer Applications, 2019, 39(4): 1106-1116.
[4]	SONG Zihui, LI Zhuo, CHEN Xin. Mobile crowdsensing task distribution mechanism based on compressed sensing [J]. Journal of Computer Applications, 2019, 39(1): 15-21.
[5]	JIN Feng, TANG Hong, ZHANG Jinyan, YIN Lixin. Pilot optimization and channel estimation in massive multiple-input multiple-output systems based on compressive sensing [J]. Journal of Computer Applications, 2018, 38(5): 1447-1452.
[6]	LI Zhou, CUI Chen. Observation matrix optimization algorithm in compressive sensing based on singular value decomposition [J]. Journal of Computer Applications, 2018, 38(2): 568-572.
[7]	ZHANG Tao, KANG Yuan, REN Shuai, LIU Yunong. Information hiding algorithm based on compression sensing and GHM multiwavelet transform [J]. Journal of Computer Applications, 2017, 37(9): 2581-2584.
[8]	YANG Xuefeng, CHENG Yaoyu, WANG Gao. Super-resolution algorithm for remote sensing images based on compressive sensing in wavelet domain [J]. Journal of Computer Applications, 2017, 37(5): 1430-1433.
[9]	SONG Yang, HUANG Zhiqing, ZHANG Yanxin, LI Mengjia. Dynamic sampling method for wireless sensor network based on compressive sensing [J]. Journal of Computer Applications, 2017, 37(1): 183-187.
[10]	WANG Qiang, ZHANG Peilin, WANG Huaiguang, YANG Wangcan, CHEN Yanlong. Survey on construction of measurement matrices in compressive sensing [J]. Journal of Computer Applications, 2017, 37(1): 188-196.
[11]	TIAN Zengshan, DAI Haipeng. WiFi fingerprint database updating based on surface fitting [J]. Journal of Computer Applications, 2016, 36(5): 1192-1195.
[12]	LIU Jinlong, XIONG Chengyi, GAO Zhirong, ZHOU Cheng, WANG Shuxian. Image compressive sensing reconstruction via total variation and adaptive low-rank regularization [J]. Journal of Computer Applications, 2016, 36(1): 233-237.
[13]	WANG Yuxin, CAO Shijie, GUO He, CHEN Zheng, CHEN Xin. Communication aware multiple directed acyclic graph scheduling considering cost and fairness [J]. Journal of Computer Applications, 2015, 35(11): 3017-3020.
[14]	XIE Bin, CHEN Bo, LE Honghao. Improved linear minimum mean square error channel estimation algorithm based on orthogonal frequency division multiplexing [J]. Journal of Computer Applications, 2015, 35(11): 3265-3269.
[15]	QIN Feng SUN Fengrong SONG Shangling ZHANG Xinping LI Xincai. Iterative image reconstruction for differential phase contrast CT based on compressive sensing [J]. Journal of Computer Applications, 2013, 33(06): 1732-1736.

Efficient wireless federated learning algorithm based on 1‑bit compressive sensing

基于1‑bit压缩感知的高效无线联邦学习算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 25

Related Articles 15

Recommended Articles

Metrics