异构网络下一种带松弛步的联邦学习算法

A Federated Learning Algorithm with a Relaxation Step for Heterogeneous Networks

摘要: 联邦学习是一个在保护用户隐私、数据安全方面具有显著优势的机器学习框架。针对联邦学习中各个设备间存在的数据异质性与系统异质性，许多学者提出了相应的解决方案，如FedProx算法等。考虑到松弛步可以起到提高收敛速度的作用，本文我们在FedProx的基础上引入松弛步，提出一种带松弛步的联邦学习算法FedProx + Relaxation。本文对FedProx + Relaxation的收敛性进行了理论分析，并通过数值实验展示了该算法的有效性与稳健性。通过数值实验，本文说明了FedProx + Relaxation相比于FedProx具有更加稳健的收敛效果。

Abstract: Federated learning is a machine learning framework that has significant advantages in protecting user privacy and data security. Considering the data heterogeneity and system heterogeneity between various devices in federated learning, many scholars have proposed corresponding solutions, such as FedProx algorithm, etc. Considering that the relaxation step can play a role in improving the speed of convergence, a relaxation step on the basis of the FedProx algorithm was introduced. And then a federated learning algorithm with a relaxation step, i.e., FedProx + Relaxation is proposed here. The convergence of the FedProx + Relaxation is analyzed theoretically, the efficiency and robustness of the algorithm are demonstrated by numerical experiments. Through the numerical experiment, it shows that the FedProx + Relaxation has more robust convergence than FedProx.

1. 引言

传统的机器学习面临着隐私保护问题，在训练过程中，若将数据直接共享，就会有隐私泄露的风险。针对数据隐私问题，谷歌公司提出了一种联邦学习(Federated Learning)的算法框架。作为一种机器学习框架，它既能够一定程度地保护用户数据隐私，又使得用户数据能被人工智能系统更加高效地使用。

传统的机器学习建模是将数据样本集合到一个中心服务器再统一进行模型训练，然后利用获得的模型进行预测 [1] [2] [3] [4] 。联邦学习可以看作是一种数据储存在设备本地的分布式机器学习框架，所有设备在中心服务器的编排下协同训练模型，在训练过程中不直接共享数据，其目标是训练一个在大多数设备上表现良好的全局模型，在设备与中心服务器之间进行多轮模型更新，直到满足停机准则 [5] 。

目前，联邦学习面临的挑战之一就是异质性，其包含数据异质和系统异质两个方面。数据异质性往往是因为不同设备上的数据分布不一致导致，而系统异质主要是因为联邦网络中设备硬件，网络连接状况以及电源状态的差异导致。考虑到这两种异质性，Li等人 [6] 提出了FedProx算法，其通过在局部求解问题上增加邻近项来控制本地模型与全局模型差异程度，从而处理数据异质的问题；同时，该算法还允许参与模型更新的设备进行不同轮数的本地更新，从而处理系统异质的问题。

松弛法是一种加速迭代方法，起源于变分思想，其利用当前迭代点和前一迭代点的凸组合来对新的迭代点进行更新，这一方法对数值计算中的各种问题都可起到加速收敛的作用。除此之外，还有超松弛法、群松弛法、逐次超松弛法等改进的松弛方法 [7] 。进一步地，松弛方法已被应用到许多方面，如基于机器学习和线性规划松弛的近似混合整数规划解 [8] ，非齐次马尔可夫跳跃系统H∞滤波的广义松弛技术 [9] 以及基于改进临近丛法的拉格朗日松弛短期热液调度 [10] 等。为加速FedProx算法，我们在该算法的基础上添加松弛步，提出了异构网络下一种带松弛步的联邦学习算法，从而使得算法更加稳健，且迭代中步长参数的选择范围更大。针对该算法，本文给出了其收敛性的理论分析，并进一步地通过数值实验展示了该算法的有效性和稳健性。

2. 预备知识

在这一节中，我们介绍本文研究的问题，用到的定义以及引理。文中所用到的符号定义如下： $R^d$ 表示欧几里得空间， $\langle \cdot ,\cdot \rangle$ 表示向量内积， $\Vert \cdot \Vert$ 表示欧氏范数， $\nabla$ 表示梯度。我们用 $\left[m\right]$ 来简记集合 $\left\{1,2,\cdots ,m\right\}$ ， $\mathbb{E}[\cdot ]$ 表示数学期望。

2.1. 本文问题

联邦学习涉及到对一个优化问题的求解，通过对该优化问题的求解得到联邦学习中模型的参数，该优化问题可抽象为如下形式

$\underset{\omega }{\min }f\left(\omega \right)={\displaystyle \underset{k=1}{\overset{N}{\sum }}{p}_k{F}_k}\left(\omega \right)={\mathbb{E}}_k\left[F_k\left(\omega \right)\right],$ (1)

其中N是设备总数，概率 $p_k\ge 0$ 且 ${\displaystyle \underset{k=1}{\overset{N}{\sum }}{p}_k=1}$ 。通常，在联邦学习中每个设备拥有的数据分布 $D_k$ 是不同的，局部目标函数 $F_k\left(\omega \right):={\mathbb{E}}_{x_k\sim D_k}\left[f_k\left(\omega ;x_k\right)\right]$ 是非凸的，其用来度量各设备的局部期望风险。若设备k有 $n_k$ 个可用样本，则可令 $p_k=\frac{n_k}{n}$ ，其中 $n={\displaystyle \underset{k=1}{\overset{N}{\sum }}{n}_k}$ 为样本总数。

2.2. 相关定义与引理

在算法中，通过对内循环中子问题的非精确求解，可以灵活的调整每个设备的局部计算量与通信量。我们在下面正式介绍这种非精确解的概念。

定义1 (γ-非精确解)令函数 $h\left(\omega ;{\omega }_0\right)=F\left(\omega \right)+\frac{\mu }{2}{\Vert \omega -{\omega }_0\Vert }^2$ 且参数 $\gamma \in \left[0,1\right]$ 。如果

$\Vert \nabla h\left({\omega }^{\text{*}};{\omega }_0\right)\Vert \le \gamma \Vert \nabla h\left({\omega }_0;{\omega }_0\right)\Vert$ ,

其中 $\nabla h\left(\omega ;{\omega }_0\right)=\nabla F\left(\omega \right)+\mu \left(\omega -{\omega }_0\right)$ ，则我们就定义 ${\omega }^{*}$ 为 $\underset{\omega }{\min }h\left(\omega ;{\omega }_0\right)$ 的一个γ-非精确解。明显地，上述定义中γ越小求解精确度越高。

为分析算法收敛性，我们需要量化局部目标函数与全局目标函数间的差异程度。Li等人 [6] 提出了一种联邦网络中设备差异性的度量准则，即B-局部差异，其定义如下所示。该度量准则在文献 [11] [12] 中均有应用。

定义2 (B-局部差异)我们称 $F_k$ 在 $\omega$ 处满足B-局部差异，如果局部函数 $F_k$ 在 $\omega$ 处满足以下条件

${\mathbb{E}}_k\left[{\Vert \nabla F_k\left(\omega \right)\Vert }^2\right]\le B^2{\Vert \nabla f\left(\omega \right)\Vert }^2$ .

进一步地， $\forall {\Vert \nabla f\left(\omega \right)\Vert }^2\ne 0$ ，我们定义 $B\left(\omega \right)=\sqrt{\frac{{\mathbb{E}}_k{\Vert \nabla F_k\left(\omega \right)\Vert }^2}{{\Vert \nabla f\left(\omega \right)\Vert }^2}}$ .

引理1给出光滑函数的相关性质，其在算法收敛性证明中起到了重要作用，具体证明可以参考( [13] ，引理1.2.3)。

引理1 (下降引理 [13] )若函数 $f:R^d\to R$ 且梯度 $\nabla f$ 是L-Lipschitz连续的，其中 $L>0$ ，则我们有

$\left|f\left(y\right)-f\left(x\right)-\langle \nabla f\left(x\right),y-x\rangle \right|\le \frac{L}{2}{\Vert y-x\Vert }^2,\forall x,y\in {ℝ}^n$ .

3. 算法与收敛分析

本节，我们将给出所提算法FedProx + Relaxation，并对其进行收敛分析。

3.1. 联邦优化算法

首先我们给出FedProx + Relaxation的具体迭代格式如下所示：

该算法与FedProx算法的主要区别为在第5迭代步中引入了凸松弛的思想，利用了前一迭代步的全局模型信息。为证明算法的收敛性，我们对优化问题中的目标函数进行一些假设。

假设1 (光滑，有界) $\forall k\in \left[m\right]$ ，设备k的局部目标函数 $F_k(\cdot )$ 是非凸可微且L-光滑的，即

$\Vert \nabla F_k\left(u\right)-\nabla F_k\left(v\right)\Vert \le L\Vert u-v\Vert ，\forall u,v\in R^d$ .

此外目标函数 $f(·)$ 的最优值是有下界的，满足 $f^{\ast }=\underset{\omega }{\min }f\left(\omega \right)>-\infty$ .

假设2 (差异有界性)对于 $\epsilon >0$ ，存在 $B_{\epsilon }$ ，使得对于任意点 $\omega \in \left\{\omega |{\Vert \nabla f\left(\omega \right)\Vert }^2>\epsilon \right\}$ ，满足 $B\left(\omega \right)\le B_{\epsilon }$ 。

3.2. 收敛性分析

基于以上假设，我们将给出FedProx + Relaxation算法的收敛性分析结果。为简便起见，我们在证明过程中取 ${\gamma }_k^t=\gamma$ 。在此之前我们将首先给出相关引理，引理2证明与文献 [6] 中类似，为保证文章的完整性，本文给出相关证明过程。

引理2 令假设1~2成立， ${\nabla }^2{F}_k\underset{\_}{\succ }-L_{-}I$ ，其中 $L_{-}>0$ ，且 $\bar{\mu }:=\mu -L_{-}>0$ 。设 ${\omega }^t$ 不是问题(1)的一个稳定点，且局部函数 $F_k$ 在 ${\omega }^t$ 上是B-局部差异的，即满足 $B\left({\omega }^t\right)\le B$ 。则我们有

$\Vert {\bar{\omega }}^{t+1}-{\omega }^t\Vert \le \frac{B\left(1+\gamma \right)}{\bar{\mu }}\Vert \nabla f\left({\omega }^t\right)\Vert$ , (2)

$\Vert M_{t+1}\Vert \le \left(\frac{L\left(1+\gamma \right)}{\bar{\mu }}+\gamma \right)B\Vert \nabla f\left({\omega }^t\right)\Vert$ , (3)

其中 ${\bar{\omega }}^{t+1}:=E_k\left[{\omega }_k^{t+1}\right]$ ， $M_{t+1}=-\nabla f\left({\omega }^t\right)-\mu \left({\bar{\omega }}^{t+1}-{\omega }^t\right)$ 。

证明考虑到算法中 ${\omega }_k^{t+1}$ 的更新为子问题的一个γ-非精确解，则我们定义误差变量

$e_k^{t+1}=\nabla F_k\left({\omega }_k^{t+1}\right)+\mu \left({\omega }_k^{t+1}-{\omega }^t\right)$ , (4)

且该误差变量满足

$\Vert e_k^{t+1}\Vert \le \gamma \Vert \nabla F_k\left({\omega }^t\right)\Vert$ . (5)

对公式(4)取期望，并结合 ${\bar{\omega }}^{t+1}$ 的定义，我们有 ${\mathbb{E}}_k\left[e_k^{t+1}\right]={\mathbb{E}}_k\left[\nabla F_k\left({\omega }_k^{t+1}\right)\right]+\mu \left({\bar{\omega }}^{t+1}-{\omega }^t\right)$ ，进一步整理可得

${\bar{\omega }}^{t+1}-{\omega }^t=-\frac{1}{\mu }{\mathbb{E}}_k\left[\nabla F_k\left({\omega }_k^{t+1}\right)\right]+\frac{1}{\mu }{\mathbb{E}}_k\left[e_k^{t+1}\right]$ .

由于 $\bar{\mu }:=\mu -L_{-}>0$ ，故可知 $h_k$ 是 $\bar{\mu }$ -强凸的，则有

$\begin{array}{l}\bar{\mu }{\Vert {\omega }_k^{t+1}-{\omega }^t\Vert }^2\le \langle {\omega }_k^{t+1}-{\omega }^t,\nabla F_k\left({\omega }_k^{t+1}\right)+\mu \left({\omega }_k^{t+1}-{\omega }^t\right)-\nabla F_k\left({\omega }^t\right)\rangle \\ \le \langle {\omega }_k^{t+1}-{\omega }^t,e_k^{t+1}-\nabla F_k\left({\omega }^t\right)\rangle \le \Vert {\omega }_k^{t+1}-{\omega }^t\Vert \Vert e_k^{t+1}-\nabla F_k\left({\omega }^t\right)\Vert \\ \le \Vert {\omega }_k^{t+1}-{\omega }^t\Vert \left(\Vert e_k^{t+1}\Vert +\Vert \nabla F_k\left({\omega }^t\right)\Vert \right)\le \left(1+\gamma \right)\Vert {\omega }_k^{t+1}-{\omega }^t\Vert \Vert \nabla F_k\left({\omega }^t\right)\Vert ,\end{array}$

其中第二个不等式是根据误差变量的定义(4)得到，最后一个不等式是根据(5)式所得。整理上式，我们有

$\Vert {\omega }_k^{t+1}-{\omega }^t\Vert \le \frac{\left(1+\gamma \right)\Vert \nabla F_k\left({\omega }^t\right)\Vert }{\bar{\mu }}$ (6)

根据 ${\bar{\omega }}^{t+1}$ 的定义，即 ${\bar{\omega }}^{t+1}:={\mathbb{E}}_k\left[{\omega }_k^{t+1}\right]$ ，结合三角不等式，我们有

$\begin{array}{c}\Vert {\bar{\omega }}^{t+1}-{\omega }^t\Vert \le {\mathbb{E}}_k\left[\Vert {\omega }_k^{t+1}-{\omega }^t\Vert \right]\le \frac{\left(1+\gamma \right)}{\bar{\mu }}{\mathbb{E}}_k\left[\Vert \nabla F_k\left({\omega }^t\right)\Vert \right]\\ \le \frac{\left(1+\gamma \right)}{\bar{\mu }}\sqrt{{\mathbb{E}}_k\left[{\Vert \nabla F_k\left({\omega }^t\right)\Vert }^2\right]}\le \frac{B\left(1+\gamma \right)}{\bar{\mu }}\Vert \nabla f\left({\omega }^t\right)\Vert ,\end{array}$

其中第二个不等式是由(6)式所得，第三个不等式是根据Jensen’s不等式得到，最后一个不等式利用了B-局部差异的定义，则(2)式得证。

根据 $M_{t+1}$ 的定义，可得 $M_{t+1}={\mathbb{E}}_k\left[\nabla F_k\left({\omega }_k^{t+1}\right)-\nabla F_k\left({\omega }^t\right)-e_k^{t+1}\right]$ 。由假设1可知

$\Vert M_{t+1}\Vert \le {\mathbb{E}}_k\Vert \nabla F_k\left({\omega }_k^{t+1}\right)-\nabla F_k\left({\omega }^t\right)-e_k^{t+1}\Vert \le {\mathbb{E}}_k\left[L\Vert {\omega }_k^{t+1}-{\omega }^t\Vert +\Vert e_k^{t+1}\Vert \right].$

根据公式(5-6)，我们有

$\Vert M_{t+1}\Vert \le \left(\frac{L\left(1+\gamma \right)}{\bar{\mu }}+\gamma \right){\mathbb{E}}_k\Vert \nabla F_k\left({\omega }^t\right)\Vert \le \left(\frac{L\left(1+\gamma \right)}{\bar{\mu }}+\gamma \right)\sqrt{{\mathbb{E}}_k{\Vert \nabla F_k\left({\omega }^t\right)\Vert }^2}\le \left(\frac{L\left(1+\gamma \right)}{\bar{\mu }}+\gamma \right)B\Vert \nabla f\left({\omega }^t\right)\Vert ,$

其中第二个不等式利用了Jensen’s不等式，第三个不等式由B-局部差异可得，则(3)式得证。证毕

引理3令假设2成立， ${\nabla }^2{F}_k\underset{\_}{\succ }-L_{-}I$ ，其中 $L_{-}>0$ ，且 $\bar{\mu }:=\mu -L_{-}>0$ 。设 ${\omega }^t$ 不是问题(1)的一个稳定点，且局部函数 $F_k$ 在 ${\omega }^t$ 上是B-局部差异的，即满足 $B\left({\omega }^t\right)\le B$ 。则我们有

${\mathbb{E}}_{s_t}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2\le \frac{2{\left(1+\gamma \right)}^2{B}^2}{K{\bar{\mu }}^2}\left(K{\alpha }^2+4{\left(1-\alpha \right)}^2\right){\Vert \nabla f\left({\omega }^t\right)\Vert }^2$ ,(7)

${\mathbb{E}}_{S_t}\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert \le \frac{\sqrt{2}\left(1+\gamma \right)B}{\sqrt{K}\bar{\mu }}\sqrt{K{\alpha }^2+4{\left(1-\alpha \right)}^2}\Vert \nabla f\left({\omega }^t\right)\Vert$ , (8)

其中 ${\mathbb{E}}_{S_t}[\cdot ]$ 表示在第t次迭代关于所选设备集 $S_t$ 的期望。

证明根据算法1的迭代公式可知

$\begin{array}{c}{\mathbb{E}}_{s_t}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2={\mathbb{E}}_{s_t}{\Vert \alpha \left({\omega }^t-{\bar{\omega }}^{t+1}\right)+\left(1-\alpha \right)\frac{1}{K}{\displaystyle \underset{k\in S_t}{\sum }\left({\omega }_k^{t+1}-{\bar{\omega }}^{t+1}\right)}\Vert }^2\\ \le 2{\alpha }^2{\Vert {\omega }^t-{\bar{\omega }}^{t+1}\Vert }^2+2{\mathbb{E}}_{s_t}{\Vert \frac{1-\alpha }{K}{\displaystyle \underset{k\in S_t}{\sum }\left({\omega }_k^{t+1}-{\bar{\omega }}^{t+1}\right)}\Vert }^2.\end{array}$ (9)

考虑到设备间的相互独立性，我们有

$\begin{array}{c}{\mathbb{E}}_{s_t}{\Vert \frac{1-\alpha }{K}{\displaystyle \underset{k\in S_t}{\sum }\left({\omega }_k^{t+1}-{\bar{\omega }}^{t+1}\right)}\Vert }^2\le \frac{{\left(1-\alpha \right)}^2}{K}{\mathbb{E}}_k\left[{\Vert {\omega }_k^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2\right]\\ \le \frac{{\left(1-\alpha \right)}^2}{K}{\mathbb{E}}_k\left[2{\Vert {\omega }_k^{t+1}-{\omega }^t\Vert }^2+2{\Vert {\omega }^t-{\bar{\omega }}^{t+1}\Vert }^2\right]\\ \le \frac{{\left(1-\alpha \right)}^2}{K}{\mathbb{E}}_k\left[2{\left(\frac{\left(1+\gamma \right)\Vert \nabla F_k\left({\omega }^t\right)\Vert }{\bar{\mu }}\right)}^2+2{\left(\frac{B\left(1+\gamma \right)}{\bar{\mu }}\Vert \nabla f\left({\omega }^t\right)\Vert \right)}^2\right]\\ \le \frac{4{\left(1-\alpha \right)}^2{\left(1+\gamma \right)}^2}{K{\bar{\mu }}^2}{B}^2{\Vert \nabla f\left({\omega }^t\right)\Vert }^2.\end{array}$

其中第三个不等式是根据公式(2)和(6)所得，最后一个不等式利用了B-局部差异的定义。由上式及公式(2)，我们对公式(9)整理可得

$\begin{array}{c}{\mathbb{E}}_{s_t}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2\le 2{\alpha }^2{\left(\frac{B\left(1+\gamma \right)}{\bar{\mu }}\Vert \nabla f\left({\omega }^t\right)\Vert \right)}^2+\frac{8{\left(1-\alpha \right)}^2{\left(1+\gamma \right)}^2}{K{\bar{\mu }}^2}{B}^2{\Vert \nabla f\left({\omega }^t\right)\Vert }^2\\ =\frac{2{\left(1+\gamma \right)}^2{B}^2}{K{\bar{\mu }}^2}\left(K{\alpha }^2+4{\left(1-\alpha \right)}^2\right){\Vert \nabla f\left({\omega }^t\right)\Vert }^2.\end{array}$

进一步地，根据Jensen’s不等式，我们有

${\mathbb{E}}_{S_t}\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert \le \sqrt{{\mathbb{E}}_{S_t}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2}=\frac{\sqrt{2}\left(1+\gamma \right)B}{\sqrt{K}\bar{\mu }}\sqrt{K{\alpha }^2+4{\left(1-\alpha \right)}^2}\Vert \nabla f\left({\omega }^t\right)\Vert .$ 证毕

下面我们给出算法1在期望意义下目标函数的梯度可达到 $O\left(1/T\right)$ 的次线性收敛率。

定理1若引理2的条件成立，选取算法1中的参数 $\alpha ,\mu ,K$ 和 $\gamma$ ，使得

$\begin{array}{l}\rho =[\frac{1-\gamma B}{\mu }-\frac{LB\left(1+\gamma \right)}{\mu \bar{\mu }}-\frac{L{\left(1+\gamma \right)}^2{B}^2}{2{\bar{\mu }}^2}-\frac{L{\left(1+\gamma \right)}^2{B}^2}{K{\bar{\mu }}^2}\left(K{\alpha }^2+4{\left(1-\alpha \right)}^2\right)\\ -\left(\frac{2LB\left(1+\gamma \right)}{\bar{\mu }}+1\right)\frac{\sqrt{2}\left(1+\gamma \right)B}{\sqrt{K}\bar{\mu }}\sqrt{K{\alpha }^2+4{\left(1-\alpha \right)}^2}]>0\end{array}$

成立，则有

$\frac{1}{T}{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\mathbb{E}\left[{\Vert \nabla f\left({\omega }^t\right)\Vert }^2\right]}\le \frac{f\left({\omega }^0\right)-f^{\text{*}}}{T\rho }$ ,

其中 $f^{\ast }=\underset{\omega }{\min }f\left(\omega \right)>-\infty$ 。

证明一方面，由于f是L-光滑的，则根据下降引理1可知

$\begin{array}{c}f\left({\bar{\omega }}^{t+1}\right)\le f\left({\omega }^t\right)+\langle \nabla f\left({\omega }^t\right),{\bar{\omega }}^{t+1}-{\omega }^t\rangle +\frac{L}{2}{\Vert {\bar{\omega }}^{t+1}-{\omega }^t\Vert }^2\\ \text{=}f\left({\omega }^t\right)+\langle \nabla f\left({\omega }^t\right),-\frac{1}{\mu }\nabla f\left({\omega }^t\right)-\frac{1}{\mu }{M}_{t+1}\rangle +\frac{L}{2}{\Vert {\bar{\omega }}^{t+1}-{\omega }^t\Vert }^2\\ \le f\left({\omega }^t\right)-\frac{1}{\mu }{\Vert \nabla f\left({\omega }^t\right)\Vert }^2+\frac{1}{\mu }\Vert \nabla f\left({\omega }^t\right)\Vert \Vert M_{t+1}\Vert +\frac{L}{2}{\left(\frac{1+\gamma }{\bar{\mu }}\right)}^2{B}^2{\Vert \nabla f\left({\omega }^t\right)\Vert }^2,\end{array}$

其中等式是根据 $M_{t+1}$ 的定义所得，第二个不等式是根据公式(2)及Schwarz不等式所得。进一步，根据公式(3)，我们有

$\begin{array}{l}f\left({\bar{\omega }}^{t\text{+}1}\right)\le f\left({\omega }^t\right)-\frac{1}{\mu }{\Vert \nabla f\left({\omega }^t\right)\Vert }^2+\frac{B}{\mu }\left(\frac{L\left(1+\gamma \right)}{\bar{\mu }}+\gamma \right){\Vert \nabla f\left({\omega }^t\right)\Vert }^2+\frac{L{\left(1+\gamma \right)}^2{B}^2}{2{\bar{\mu }}^2}{\Vert \nabla f\left({\omega }^t\right)\Vert }^2\\ =f\left({\omega }^t\right)-\left(\frac{1-\gamma B}{\mu }-\frac{LB\left(1+\gamma \right)}{\mu \bar{\mu }}-\frac{L{\left(1+\gamma \right)}^2{B}^2}{2{\bar{\mu }}^2}\right){\Vert \nabla f\left({\omega }^t\right)\Vert }^2.\end{array}$ (10)

另一方面，根据下降引理1，我们有

$f\left({\omega }^{t+1}\right)\le f\left({\bar{\omega }}^{t+1}\right)+\langle \nabla f\left({\bar{\omega }}^{t+1}\right),{\omega }^{t+1}-{\bar{\omega }}^{t+1}\rangle +\frac{L}{2}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2$ .

对上式两边关于 $S_t$ 取期望，并利用Schwarz不等式，可得

$\begin{array}{c}{\mathbb{E}}_{S_t}\left[f\left({\omega }^{t+1}\right)\right]\le f\left({\bar{\omega }}^{t+1}\right)+{\mathbb{E}}_{S_t}\left[\Vert \nabla f\left({\bar{\omega }}^{t+1}\right)\Vert \cdot \Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert +\frac{L}{2}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2\right]\\ =f\left({\bar{\omega }}^{t+1}\right)+{\mathbb{E}}_{S_t}\left[\left(\Vert \nabla f\left({\bar{\omega }}^{t+1}\right)-\nabla f\left({\omega }^t\right)+\nabla f\left({\omega }^t\right)\Vert +\frac{L}{2}\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert \right)\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert \right]\\ \le f\left({\bar{\omega }}^{t+1}\right)+{\mathbb{E}}_{S_t}\left[\left(L\Vert {\bar{\omega }}^{t+1}-{\omega }^t\Vert +\Vert \nabla f\left({\omega }^t\right)\Vert +\frac{L}{2}\Vert {\omega }^{t+1}-{\omega }^t\Vert +\frac{L}{2}\Vert {\omega }^t-{\bar{\omega }}^{t+1}\Vert \right)\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert \right]\\ \le f\left({\bar{\omega }}^{t+1}\right)+{\mathbb{E}}_{S_t}\left[\left(2L\Vert {\bar{\omega }}^{t+1}-{\omega }^t\Vert +\Vert \nabla f\left({\omega }^t\right)\Vert \right)\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert +\frac{L}{2}{\Vert {\omega }^{t+1}-{\bar{\omega }}^{t+1}\Vert }^2\right].\end{array}$

其中第二个不等式利用了三角不等式及f的L-光滑性。根据引理2-3，我们整理上式可得

$\begin{array}{c}{\mathbb{E}}_{S_t}\left[f\left({\omega }^{t+1}\right)\right]\le f\left({\bar{\omega }}^{t+1}\right)+[\left(\frac{2LB\left(1+\gamma \right)}{\bar{\mu }}+1\right)\frac{\sqrt{2}\left(1+\gamma \right)B}{\sqrt{K}\bar{\mu }}\sqrt{K{\alpha }^2+4{\left(1-\alpha \right)}^2}\\ +\frac{L{\left(1+\gamma \right)}^2{B}^2}{K{\bar{\mu }}^2}\left(K{\alpha }^2+4{\left(1-\alpha \right)}^2\right)]{\Vert \nabla f\left({\omega }^t\right)\Vert }^2.\end{array}$ (11)

联立公式(10)和(11)，我们得出算法1在前后步迭代点上目标函数值之间的关系，即

$\begin{array}{c}{\mathbb{E}}_{S_t}\left[f\left({\omega }^{t+1}\right)\right]\le f\left({\omega }^t\right)-[\frac{1-\gamma B}{\mu }-\frac{LB\left(1+\gamma \right)}{\mu \bar{\mu }}-\frac{L{\left(1+\gamma \right)}^2{B}^2}{2{\bar{\mu }}^2}-\frac{L{\left(1+\gamma \right)}^2{B}^2}{K{\bar{\mu }}^2}\left(K{\alpha }^2+4{\left(1-\alpha \right)}^2\right)\\ \begin{array}{c}-\left(\frac{2LB\left(1+\gamma \right)}{\bar{\mu }}+1\right)\frac{\sqrt{2}\left(1+\gamma \right)B}{\sqrt{K}\bar{\mu }}\sqrt{K{\alpha }^2+4{\left(1-\alpha \right)}^2}\\ \end{array}]{\Vert \nabla f\left({\omega }^t\right)\Vert }^2.\end{array}$

在上述公式中，对t从 $0~T-1$ 进行累和并移项可得

$\frac{1}{T}{\displaystyle \underset{t=0}{\overset{T-1}{\sum }}\mathbb{E}\left[{\Vert \nabla f\left({\omega }^t\right)\Vert }^2\right]}\le \frac{f\left({\omega }^0\right)-f^{\text{*}}}{T\rho }$ ,

其中 $f^{\ast }=\underset{\omega }{\min }f\left(\omega \right)>-\infty$ 。证毕

4. 数值实验

本节将通过数值实验来说明FedProx + Relaxation的收敛效果。我们采用与文献 [14] 类似的方法来生成实验数据，对于每个设备k，我们使用模型 $y=\arg \max \left(softmax\left(Wx+b\right)\right)$ ， $x\in R^{60},W\in R^{10\times 60},b\in R^{10}$ 来生成样本 $\left(X_k,Y_k\right)$ 。我们设置 $W_k\sim \mathcal{N}\left(u_k,1\right),b_k\sim \mathcal{N}\left(u_k,1\right),u_k\sim \mathcal{N}\left(0,a\right)，x_k\sim \mathcal{N}\left(v_k,\Sigma \right)$ ，其中协方差矩阵 $\Sigma$ 是对角阵，且有 ${\Sigma }_{j,j}=j^{-1.2}$ ；均值向量 $v_k$ 中的每个元素服从 $\mathcal{N}\left(B_k,1\right),B_k\sim \mathcal{N}\left(0,b\right)$ 的分布；a控制局部模型之间的差异；b控制每台设备上的本地数据与其他设备上的本地数据的差异程度。我们分别令 $\left(a,b\right)=\left(0.5,0.5\right),\left(1,1\right)$ 来生成两组异构的分布式数据集。实验的目标是学习全局W和b。每个设备上的数据按8:2的比例被随机分为训练集和测试集。

我们在Tensorflow中实现所提的FedProx + Relaxation算法和现有的FedProx算法。这两个算法的局部求解器都是随机梯度算法(SGD)，且在每轮迭代中采用均匀抽样的方式选择设备。网络中设置了30个设备，每个设备上的样本数均遵循幂律，我们将每轮选定的设备数量固定为10。对于所有合成数据实验，学习率选定为0.0001。

图1中横坐标为外循环迭代次数，对应算法中的t，纵坐标为全局损失函数。显然图1中的曲线下降越快代表算法求解速度越快。图2中横坐标为外循环迭代次数，对应算法中的t，纵坐标为预测准确率。显然图2中曲线上升越快越高代表算法求得的模型的预测准确率越高。观察图中曲线可知，FedProx-Relaxation相较于FedProx在求解该问题时更加稳健，同时也具有更高的预测准确性。

Figure 1. Convergence comparison between FedProx + relaxation algorithm and FedProx algorithm

图1. FedProx + Relaxation算法与FedProx算法的收敛效果对比

Figure 2. Prediction accuracy comparison between FedProx + relaxation algorithm and FedProx algorithm

图2. FedProx + Relaxation算法与FedProx算法的预测准确率对比

5. 总结

本文在FedProx基础上添加了松弛步，提出了一种带松弛步的联邦学习算法FedProx + Relaxation。文中对算法进行了理论分析，证明了目标函数的梯度在期望意义下的次线性收敛率。同时，本文也通过数值实验展示了FedProx + Relaxation相对于原算法的改进效果。