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

章振宇，谭国平，周思源*

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

章振宇1，谭国平1，2，周思源1，2*

（1.河海大学 计算机与信息学院，南京 211100； 2.江苏智能交通及智能驾驶研究院，南京 210019）（*通信作者电子邮箱siyuan.zhou@hhu.edu.cn）

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

联邦学习；无线信道；量化编码；压缩感知；通信开销

0 引言

联邦学习（Federated Learning， FL）［1］是一种分布式机器学习方法，能够使用户协作训练一个共享模型，同时不需要将所有数据集中起来，只需要整合用户端训练出的模型。在联邦学习应用场景下，用户端多针对手机等小型设备，所以无线网络下的联邦学习即无线联邦学习很有研究的必要。然而，对无线联邦学习提出的一个关键挑战是通信开销。一方面，在无线联邦学习中，参与的用户端设备（如手机和平板电脑）通常只能分配少量的通信资源给联邦学习；另一方面，部署在边缘设备上的高级机器学习应用程序，如Gboard，越来越多地使用复杂的深度神经网络（Deep Neural Network， DNN），其中每个用户端上传的训练更新由大量的梯度向量组成，使通信成了严重的瓶颈。因此，最小化无线联邦学习的通信开销变得至关重要［2-3］。

为了降低通信开销，主要有两种方法：一是基于模型压缩，二是减少传输的更新的客户端总数［4-6］。在基于模型压缩的方法中，主流方法又分为量化、随机稀疏化以及联邦蒸馏方法［7］。

量化方法一般分为概率量化和梯度量化：前者是本地更新模型向量化后，对其权重量化；后者是将梯度量化成低精度值以降低通信带宽，应用更为广泛。文献［8］中提出了一种基于深度学习的自适应三进制量化（Federated Trained Ternary Quantization， FTTQ）算法和一个三值联邦平均（Ternary Federated Averaging， T-FedAvg）协议来减少联邦学习系统的上下行通信开销，该算法通过一个自学习量化因子来优化客户端上的量化网络。文献［9］中以非线性的方式划分空间，提出了一种基于Cosine函数的非线性量化方案。此外，文献［10］中将能量最小化问题描述为混合整数非线性规划问题，融合无线传输和权重量化，以最小化全局模型的损失函数为目标，提出了不同5G移动设备的带宽分配和灵活权重量化的压缩策略。

在随机稀疏化方法中，文献［11］中提出了具有动态批处理大小的柔性Top-局部随机梯度下降算法，实现了灵活压缩。文献［12］中提出了稀疏二元压缩的方法，文献［13］中则在此基础上基于非独立同分布、不平衡和小规模批的本地数据，提出了一种新型稀疏三元压缩（Sparse Ternary Compression， STC）框架，在数据集分布非独立同分布场景下性能较好。

还有其他的一些不常见的方法，比如文献［3］中提出了结构化更新和草图更新，结构化更新限制局部更新的模型结构，草图更新通过随机稀疏化、随机旋转和概率量化压缩模型，降低了上行通信数据。文献［14］中把草图更新用于下行数据压缩，并且提出了联邦随即失活，使用户在全局模型的子集上进行训练，不但减小了上行数据量，而且降低了用户端的计算量。

然而，文献［12］与文献［13］中所提出的稀疏二元压缩和稀疏三元压缩方法均没有考虑到无线网络的不可靠性，这就使得其中利用哥伦布编码进行相对位置传输的部分变得过于理想化，因为一旦引入无线网络的不可靠性，利用哥伦布编码进行相对位置的传输时，如果有一个出错，就会导致后面所有信息全部出错；但是这两种方法都已经对模型数据进行了稀疏化处理，那么在此基础上利用1‑bit压缩感知对数据进行进一步的压缩成为可能。文献［15］中提出了一种用于大规模多输入多输出系统上联邦学习的压缩感知方法，降低了联邦学习的算法复杂度。文献［16］在Top-稀疏化的基础上引入了1‑bit压缩感知，并分析了收敛性；但是文献［16］中的1‑bit压缩感知方法在联邦学习的训练效果上表现并不好。

本文旨在通过减少每个客户端更新传输的总位数来降低通信开销，而且不至于像文献［16］中一样损失联邦学习的训练效果，因此提出了一种降低联邦学习用户端到服务器通信成本的新策略，通过在上行链路中首先对本地模型参数数据进行稀疏三元压缩，再利用1‑bit压缩感知对已经稀疏后的模型参数进一步压缩，从而降低上行通信开销；此外，通过设置动态阈值的方法，使用1-bit压缩感知的方法可以进一步降低通信开销。

1 系统模型

联邦学习是一种分布式机器学习方法，旨在保护用户端的数据隐私，这就导致了它和集中式学习是完全不同的学习过程。

1.1 无线联邦学习模型

图1 执行联邦学习的蜂窝网络架构示例

1.2 传输模型

对于下行链路，基站使用广播的方式将全局联邦学习模型进行下发。下行传输速率为：

根据已给出的上行传输速率和下行传输速率，可得上行和下行传输时延：

1.3 能耗模型

用户的能耗由训练耗能和传输耗能两部分组成。能耗公式［17］如下：

由于基站可以连续供电，因此不考虑基站的能耗。

1.4 最优上行链路信道分配

文献［18］中系统研究了无线网络对联邦学习的影响，将联邦学习在无线网络中的影响表述成了一个优化问题，并且得到了最优的上行链路信道分配方案。

其中：

一个完整的联邦学习过程如下：

算法1 无线网络下的联邦学习。

1）判断是否收敛，未收敛则重复下述过程；

2）利用匈牙利算法确定最优信道分配策略；

4）用户利用本地数据训练出本地模型，并根据基站分配的信道上传；

5）基站整合接收到的正确的本地模型更新全局模型。

输出 完成训练后的全局模型。

2 稀疏三元压缩与基于1‑bit压缩感知

本章首先介绍了对模型进行稀疏化的方法，通过稀疏三元压缩将模型数据变成了稀疏化数据；接着利用压缩感知可以以低观测数恢复稀疏化数据的特性，引入1‑bit压缩感知对模型数据进行压缩；最后，通过在稀疏化过程中设置动态阈值，引入了有动态阈值的1‑bit压缩感知方法，可以在原先的1‑bit压缩感知方法的基础上进一步降低通信开销。

2.1 稀疏三元压缩

稀疏三元压缩方法的具体流程如图2所示。

其中。

与文献［16］中的方法不同，本文的稀疏化过程舍弃了对更新幅值的保留，只保留更新的趋势。这与文献［13］中的稀疏方法类似，不过因为无线网络的影响，文献［13］中利用相对位置进行哥伦布编码的方法，一旦中途出现数据包错误，就会导致后续所有信息均无法恢复，且重发机制会增大通信频率与时延，所以本文舍弃了利用相对位置进行哥伦布编码的方法，直接上传绝对位置，以降低无线网络不可靠性的影响。

2.2 1‑bit压缩感知的引入

本节利用1‑bit压缩感知方法［21］对已经进行稀疏三元压缩的模型参数数据作进一步压缩，具体流程如图3所示。

图3 引入1‑bit压缩感知的流程

算法2 二进制迭代硬阈值（BIHT）。

2.3 动态阈值的1‑bit压缩感知

算法3 设定动态稀疏化阈值。

这里的动态阈值仅从两个数据之间进行选择，根据实际情况可以很容易扩展到更多数据的情况。

图4 稀疏度对信号恢复准确率的影响

2.4 性能分析

一个完整的动态阈值1‑bit压缩感知联邦学习算法如下：

算法4 动态阈值的1‑bit 压缩感知联邦学习算法。

3 实验与结果分析

表1 系统参数

本文使用Python以及手写数据集，训练过程使用梯度下降法，对联邦学习算法和用户对数据处理的过程进行了仿真。在此仿真中，每个用户利用本地拥有的MNIST数据集［24］训练一个简单的单层前馈神经网络。损失函数是交叉熵损失［25］。

3.1 稀疏三元压缩

本节使用在2.1节中提到的流程对用户需要上传的模型参数进行稀疏三元压缩，通过设定不同的稀疏化阈值，观察稀疏三元压缩对整体的无线联邦学习的影响。

图5 稀疏化阈值对稀疏三元压缩识别准确性的影响

3.2 引入1‑bit压缩感知

3.1节的稀疏三元压缩过程可以看作是本节中1‑bit压缩感知无损重构的结果，本节引入真实的1‑bit压缩感知，使用在2.2节中提到的流程，对用户需要上传的模型参数进行稀疏三元压缩后进一步进行1‑bit压缩感知。

3.3 设置动态阈值的1‑bit压缩感知

本节研究了设置动态阈值的1‑bit压缩感知对训练速度和效果的影响。从图5可以看到，虽然稀疏化阈值设置为5%的过程效果并不如设置为10%的过程，但是两者在收敛速率和最终效果上的差别很小，这就使得通过设置动态稀疏化阈值来进一步压缩数据的方法变成了可能。图7对比了动态阈值的1‑bit压缩感知方法、固定阈值的1‑bit压缩感知方法以及文献［16］中的1‑bit压缩感知方法。

图6 观测数对识别准确率的影响

因为压缩模型参数数据是以加大联邦学习训练次数为代价的，所以仍需考虑联邦学习算法训练到相同水平时的总计通信开销。图8中对比了引入动态阈值的1‑bit压缩感知方法、固定阈值的1‑bit压缩感知方法、文献［16］中的1‑bit压缩感知方法、稀疏三元压缩方法以及标准联邦学习的识别准确性如何随着用户上传数据总大小的变化而变化。从图8中可以看到，当联邦学习训练到相同的水平时，对比用户采用不同方法所上传的数据量，引入动态阈值的1‑bit压缩感知方法优于固定阈值的1‑bit压缩感知方法，两种引入压缩感知的方法均优于稀疏三元压缩方法，且均比文献［16］中的方法训练效果好。相比不采用该方法的标准联邦学习算法，引入动态阈值的1‑bit压缩感知方法的无线联邦学习过程将用户上传数据总大小降低至原有算法的2/11。

当用户使用固定功率进行信号发射时，在相同信道条件下，其上行链路的传输速率可看作一定值。由于所需要传输的模型压缩了，所以用户的传输时延大幅降低了，这也导致用户的传输能耗随之降低。图9中比较了引入动态阈值的1‑bit压缩感知算法与采用标准联邦学习算法之间用户的传输能耗关系。可以看到，当联邦学习训练到相同的水平时，引入动态阈值的1‑bit压缩感知算法的无线联邦学习算法将上行传输能耗降低至不采用该算法的标准联邦学习算法的1/10。

图9 识别准确性与用户传输能耗的关系

4 结语

本文在无线联邦学习背景下，提出了新型的降低用户在上行链路发送数据大小的方法。该方法是在稀疏三元压缩的基础上进一步加入动态阈值的1‑bit压缩感知，在联邦学习的每一轮训练中，用户所需要传输的模型参数数据量降低至不采用该方法的标准联邦学习过程的1/25。在联邦学习训练到相同水平时，采用本文方法的无线联邦学习算法的总通信开销降低至不采用该方法的标准联邦学习算法的2/11，将上行传输能耗降低至不采用该方法的标准联邦学习算法的1/10。但是本文方法的联邦学习收敛速率仍然较慢，后续将研究如何提升该方法在无线联邦学习中的收敛速率。

[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］.https：//arxiv.org/pdf/1610.02527.pdf.

[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］.https：//arxiv.org/pdf/1610.05492.pdf.

[4] RIBERO M， VIKALO H. Communication-efficient federated learning via optimal client sampling［EB/OL］. （2020-10-14）［2021-06-08］.https：//arxiv.org/pdf/2007.15197.pdf.

[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.

[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.

[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］.https：//arxiv.org/pdf/1811.11479.pdf.

[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.

[9] HE Y， ZENK M， FRITZ M. CosSGD： nonlinear quantization for communication-efficient federated learning［EB/OL］. （2020-12-15）［2021-06-20］.https：//arxiv.org/pdf/2012.08241.pdf.

[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］.https：//arxiv.org/pdf/2012.11070.pdf.

[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.

[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.

[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.

[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］.https：//arxiv.org/pdf/1812.07210.pdf.

[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.

[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］.https：//arxiv.org/pdf/2103.16055.pdf.

[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.

[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.

[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.

[20] KUHN H W. The Hungarian method for the assignment problem［J］. Naval Research Logistics Quarterly， 1955， 2（1/2）： 83-97.

[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.

[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.

[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.

[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.

[25] HENNIG C， KUTLUKAYA M. Some thoughts about the design of loss functions［J］. REVSTAT — Statistical Journal， 2007， 5（1）： 19-39.

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

ZHANG Zhenyu1， TAN Guoping1，2， ZHOU Siyuan1，2*

（1，，211100，；2，210019，）

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.

Federated Learning (FL); wireless channel; quantization coding; compressive sensing; communication overhead

This work is partially supported by National Natural Science Foundation of China （61701168， 61832005）， China Postdoctoral Science Foundation （2019M651546）， Major Science and Technology Project of Transportation Department of Jiangsu Province （2019Z07）.

ZHANG Zhenyu， born in 1998， M. S. candidate. His research interests include wireless network， federated learning.

TAN Guoping， born in 1975， Ph. D.， professor. His research interests include wireless distributed machine learning， mobile edge computing， internet of vehicles.

ZHOU Siyuan， born in 1985， Ph. D.， professor. His research interests include wireless network， beyond 5G communication， internet of things.

TP181

A

1001-9081（2022）06-1675-08

10.11772/j.issn.1001-9081.2021061374

2021⁃08⁃02；

2021⁃09⁃02；录用日期：2021⁃09⁃08。

国家自然科学基金资助项目（61701168，61832005）；中国博士后科研基金资助项目（2019M651546）；江苏省交通运输厅重大科技项目（2019Z07）。

章振宇（1998—），男，江苏南京人，硕士研究生，CCF会员，主要研究方向：无线网络、联邦学习；谭国平（1975—），男，湖南澧县人，教授，博士生导师，博士，CCF会员，主要研究方向：无线分布式机器学习、移动边缘计算、车联网；周思源（1985—），男，江苏南京人，教授，博士，CCF会员，主要研究方向：无线网络、Beyond 5G通信、物联网。