联邦学习综述

今天要跟大家分享的内容是一篇联邦学习领域方面比较全面的综述文章：Advances and Open Problems in Federated Learning。该文章发表于2021年，由来自麻省理工、斯坦福、谷歌等25所国际知名高校(机构)的学者联合所著，共调研了400余篇文献，内容非常丰富。由于篇幅所限，这里聚焦于几个基础方面进行分享，并进行一定的补充。

联邦学习的定义

联邦学习（Federated learning）属于机器学习的一类，文章给出较为广泛的联邦学习的定义如下：

Federated learning is a machine learning setting where multiple entities (clients) collaborate in solving a machine learning problem, under the coordination of a central server or service provider. Each client’s raw data is stored locally and not exchanged or transferred; instead, focused updates intended for immediate aggregation are used to achieve the learning objective.

联邦学习的背景

联邦学习的提出源于在大数据分析的不断发展下人们对保护数据隐私和安全的重视和需求。我们考虑一个标准的统计学习问题阐述联邦学习的背景，假定共有N个观测值，每一个观测为p维，对应一个感兴趣的响应变量Y。希望通过优化一个合适定义的损失函数（e.g. 对数似然函数）来得到参数估计。传统场景下，整个数据集样本量N小，且均存储在同一台电脑上，经典优化算法（例如梯度下降、牛顿法等）能够非常容易施行。然而，在现实场景中，有很多有用的数据分布在大量移动通信设备中。用户期待汇总这些数据信息训练一个全局的模型，获得更好的体验。但是，这些数据通常是非常敏感的，不能直接上传到同一个中心服务器从而使用传统的方法训练模型。因此，如何在满足数据隐私和安全的前提下，设计一个机器学习框架，让用户的数据能够被高效地共同使用，就是一个非常重要的问题。由此，联邦学习应运而生。

联邦学习基本的训练过程

一个基本的联邦学习框架包括一个中心服务器(Server)和多台设备(Clients), 具体训练过程由以下步骤组成：

Step1. 选择联机的Clients：Server从一组满足联机要求的Clients中抽样。例如，只抽取正接入无线网络且处于空闲状态的设备登陆到服务器。

Step2. 广播：每个被选中的Client从Server处下载当前的模型参数和一个训练程序。

Step3. 计算：每个Client利用本机上的数据，执行训练程序进行局部计算。例如利用本机数据和当前参数进行随机梯度下降（SGD），得到梯度估计量。并将计算得到的梯度信息(而非原始数据)发送到Server。

Step4. 聚合更新：Server收集Clients的信息（例如梯度）进行汇总平均，并更新模型参数。

放宽核心假设-去中心化联邦学习

经典的联邦学习框架要求存在一个中心Server，Server连接各Clients，负责与各Clients进行通信和数据传输。这样的结构容易施行，但由于 Server在框架中扮演了过于重要的角色，因此也存在严重缺陷。首先，这不是隐私保护的最佳选择，一旦Server被攻克，攻击者就有机会与每个Client通信。其次，这样的中心化结构极为脆弱，一旦Server停止工作，整个训练任务也随之停止。另外，由于Server必须与大量的Clients进行持续通信，导致中心化结构对网络的带宽有很高的要求。

由此，有部分学者提出了去中心化联邦学习(fully decentralized learning)。表1给出经典联邦学习和去中心化联邦学习的差异比较。去中心化联邦学习的主要特点是：整个框架中不再需要一个中心Server负责模型训练和通信（虽然可能仍然需要Server负责开启训练任务），所有与计算相关的通信都仅仅发生在Clients之间。Clients间形成了一个网络结构用于数据传输。网络结构的每一个节点代表一个Client，每一条边代表Clients之间的通信关系。我们以梯度下降为例，给出去中心化联邦学习的基本实现步骤：

Step 1. 每个Client根据网络结构，收集邻居Client的信息得到聚合后的模型参数。

Step 2. 随后，每个Client基于该参数以及本机数据计算梯度进行梯度下降，并更新局部模型。

目前去中心化学习作为新兴研究方向，还有很多开放性问题（尤其是理论方面）待解决。

表 1 经典联邦学习和去中心化联邦学习的主要差异比较

联邦学习与典型分布式学习的区别

联邦学习属于分布式学习，但正如背景中所介绍的，它有具体适用的场景，与典型的分布式学习有明显的区别。表2全面地总结了典型分布式以及联邦学习间的不同之处。概括而言，与典型的分布式优化问题相比，联邦优化问题有以下几个关键特性：

1. 设备通常由大量的移动设备组成，每一个设备上的数据量相对较小，而设备数相对较多。

2. 设备间的数据通常是非独立同分布、且不平衡的。

3. 设备有通信限制：移动设备可能存在频繁掉线、速度缓慢、费用昂贵等问题。

4. 更注重隐私，不允许原始数据在设备间互相传输。

其中，隐私问题和通信效率被视为是需要优先考虑的问题。联邦学习这些独有的特性，对其理论研究和算法改进都带来巨大的挑战。

表 2 联邦学习v.s. 典型分布式学习

联邦学习优化算法及其理论分析

目前最流行的联邦学习方法，是由McMahan et al, 2017提出的Federated Averaging（也称parallel SGD/local SGD）方法（及其变体）。具体而言，我们知道机器学习中经典的SGD算法为：每次使用一个样本来计算梯度并进行参数更新。扩展到多台机器的版本，即为：每个Client在每次通信中使用一个样本来计算梯度并局部更新参数，将参数传给Server。Server汇总平均后更新模型参数再返回给Clients。这样的效率对于通信受限的联邦学习框架是难以承受的。因此，为了提高通信效率，Federated Averaging考虑每个Client首先在本地多次通过SGD更新模型，再将更新后的模型参数传给Server进行汇总平均。其基本算法见算法1：

算法 1 Federated Averaging (local SGD). 其中为模型参数，为数据，为学习率，为损失函数

由此，Federated Averaging类方法所面临的一个重要理论问题立刻产生：在本地进行多次更新以加速通信的行为，会如何影响整个算法的收敛速度。这也是联邦学习中最广泛、重要的研究内容之一，我们在接下来的部分进行具体介绍。

为研究联邦学习算法的收敛速度，定义为关于参数和单个样本的损失函数，我们的目标是最小化全局损失。与SGD优化算法类似，文章通常假设：损失函数是凸的、H-Lipschitz连续的。即有

另一方面，也常假设随机梯度的方差有界，即

对于算法的收敛速度，考虑error bound去衡量，即定义算法在第T步的收敛误差为

其中。进一步，定义K为每一次通信前的局部更新次数，M为每次通信的设备数，N为设备总数，T为总的通信次数。则Federated averaging等一系列联邦学习算法有两个基准。

1. minibatch SGD, 假设每个Client通信T轮，每个Client不执行K次局部SGD，而是执行一次minibatch SGD，对应数据量为K。则此时整个算法等价于迭代T轮的minibatch SGD，batchsize为KM，由此收敛速度有上界。
2. 单机SGD，假设仅有一个Client参与模型更新，则此时等价于迭代KT轮的SGD，收敛速率上界为。

文章称为最优的统计项(“statistical” term)，而为最优的优化项(“optimization” term）。在联邦学习中，我们关心局部更新次数K如何影响收敛速度，以及在什么条件下联邦学习算法能达到上述最优水平。

现有文献分别在数据独立同分布(iid)以及非独立同分布(non-iid)假定下做了收敛性研究，表3给出了iid情况下各算法收敛速度的对比。从结果中可见，如果成为收敛速度中的主要控制项，那么算法可以渐进达到最优收敛速度，为此要求。而对于非凸问题，文章指出想要渐进达到相同的收敛速度，则需要。

而对于non-iid，情况变得更具挑战，此时每个Client上的局部损失函数和全局损失函数间可能存在较大差异。为保证算法最终的收敛性，通常需要对二者的差异作出限制，现有文献给出的常见假定见表4。基于相应对non-iid的假定以及其他辅助假定（例如损失函数的凸性），表5给出数据非独立同分布下各算法收敛速度的对比结果。可见在non-iid场景下，算法的收敛性速度较慢。实际上文献表明，对于Federated Averaging类方法，局部更新（）可能会减慢收敛速度。目前，验证当时算法收敛速度是降低还是提升，仍然是一个重要的公开问题。

表 3 iid假设下各优化算法的收敛速度比较（在T次迭代之后的error bound上界）。假设有M个设备参与每轮迭代，损失函数是凸的且H-Smooth ，随机梯度方差上界为。

表 4 非独立同分布假设

表 5 non-iid 下各联邦学习的收敛速度（基于不同的假设和变体）

联邦学习的未来展望

文章给出了联邦学习存在的大量开放性问题，包括：

1. Non-iid以及数据不平衡下，更高效的算法与收敛速度分析。
2. 对抗Server/Clients遭受攻击，Clients失去响应等问题的更稳健的算法。
3. 如何在保护隐私的情况下（例如差分隐私方法），同时达到较高的估计效率（尤其在高维情况下）。

软件和数据集

文章提供了实现联邦学习的软件和数据集。数据集符合联邦学习应用场景：数据分散、通常不平衡（不同的Client有不同数量的样本）且分布不相同（每个Client的数据来自不同的分布），可用于进行基准测试。

（1）数据集

1. EMNIST数据集： 原始数据由671,585个数字图像和大小写英文字符（62个类）组成。联邦学习的版本将数据集拆分到3,400个不平衡Clients，每个Clients上的数字/字符为同一人所写，由于每个人都有独特的写作风格，因此数据是非同分布的。

来源：Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre ́ van Schaik. EMNIST: an extension of MNIST to handwritten letters. arXiv preprint arXiv:1702.05373, 2017.

2.Stackoverflow数据集： 该数据集由Stack Overflow的问答组成，并带有时间戳、分数等元数据。训练数据集包含342,477多个用户和135,818,730个例子。其中的时间戳信息有助于模拟传入数据的模式。

下载地址：https://www.kaggle.com/stackoverflow/stackoverflow

3.Shakespeare数据集： 该数据是从The Complete Works of William Shakespeare获得的语言建模数据集。由715个字符组成，其连续行是Client数据集中的示例。训练集样本量为16,068，测试集为2,356。

来源：Sebastian Caldas, Peter Wu, Tian Li, Jakub Konecˇny ́, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. arXiv preprint arXiv:1812.01097, 2018.

（2）开源软件包

1.TensorFlow Federated： TensorFlow框架，专门针对研究用例，提供大规模模拟功能来控制抽样。支持在模拟环境中加载分散数据集，每个Client的ID对应于TensorFlow数据集对象。

来源：The TFF Authors. TensorFlow Federated, 2019. URL：https://www.tensorflow.org/federated.

2.PySyft： PyTorch框架，使用PyTorch中的联邦学习。适用于考虑隐私保护的机器学习，采用差分隐私和多方计算（MPC）将私人数据与模型训练分离。

来源：Theo Ryffel, Andrew Trask, Morten Dahl, Bobby Wagner, Jason Mancuso, Daniel Rueckert, and Jonathan Passerat-Palmbach. A generic framework for privacy preserving deep learning, 2018.

除此以外，文章也提供了其他软件实现以及数据源供研究使用。

参考文献

Bellet, A., Guerraoui, R., Taziki, M., and Tommasi, M. (2018), “Personalized and private peer-to-peer machine learning,” in International Conference on Artificial Intelligence and Statistics, PMLR, pp. 473–481.

Colin, Igor, Aurélien Bellet, Joseph Salmon, and Stéphan Clémençon. "Gossip dual averaging for decentralized optimization of pairwise functions." In International Conference on Machine Learning, pp. 1388-1396. PMLR, 2016.

Lan, Guanghui. "An optimal method for stochastic composite optimization." Mathematical Programming 133, no. 1 (2012): 365-397.

Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., DOliveira, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascn, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konecn, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., zgr, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W., Stich, S. U., Sun, Z., Suresh, A. T., Tramr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F. X., Yu, H., and Zhao, S. (2021), “Advances and Open Problems in Federated Learning,” Foundations and Trends in Machine Learning, 14, 1–210.

Li, Yuzheng, Chuan Chen, Nan Liu, Huawei Huang, Zibin Zheng, and Qiang Yan. "A blockchain-based decentralized federated learning framework with committee consensus," IEEE Network 35, no. 1 (2020): 234-241.

McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017), “Communication-efficient learning of deep networks from decentralized data,” in Artificial Intelligence and Statistics, PMLR, pp. 1273–1282.

Stich, Sebastian U. "Local SGD converges fast and communicates little. (2018)" arXiv preprint arXiv:1805.09767.

Karimireddy, Sai Praneeth, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. (2020), "Scaffold: Stochastic controlled averaging for federated learning," In International Conference on Machine Learning, pp. 5132-5143. PMLR.

Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J. (2018), “Decentralized training over decentralized data,” in International Conference on Machine Learning, PMLR, pp. 4848–4856.

Vanhaesebrouck, P., Bellet, A., and Tommasi, M. (2017), “Decentralized collaborative learning of personalized models over networks,” in Artificial Intelligence and Statistics, PMLR, pp. 509–517.

Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. “Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent,” In NIPS, 2017.

Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. “On the convergence of FedAvg on non-IID data,” arXiv preprint arXiv:1907.02189, 2019.

- END -