基于外推自适应步长的压缩联邦学习优化算法

Extrapolation Adaptive Step Size for Compressed Federated Learning Optimization Algorithm

摘要: 由于联邦学习中的通信成本高昂，依赖通信压缩的方法正日益受到关注。本文基于外推自适应步长和压缩联邦学习框架提出了外推压缩联邦学习算法(ExpFedCom)。ExpFedCom算法支持通信压缩并在凸、强凸以及非凸条件下实现了快速收敛。数值实验表明ExpFedCom算法既实现了快速收敛又节省了通信成本，这在实际生活中有着较好的应用价值。

Abstract: The high communication costs in federated learning have motivated increasing interest in communication compression methods. This paper proposes Extrapolated Federated Compression (ExpFedCom), a novel algorithm that integrates extrapolation adaptive step sizes with a communication compression federated learning framework. The ExpFedCom algorithm supports communication compression while achieving faster convergence rates under convex, strongly convex, and nonconvex settings. Numerical experiments demonstrate that ExpFedCom simultaneously attains faster convergence and significant communication savings, exhibiting strong practical potential for real-world applications.

1. 引言

传统的集中式学习通常将数据集中存储在中心服务器上，并在该服务器上完成模型训练。然而，这种训练方式往往伴随着严重的数据隐私风险。与之相比，联邦学习[1] [2]在多个设备或节点上对分布式数据集进行模型训练，即实现跨地域分布异构设备的协同模型训练，且在全局模型训练过程中，无需将本地数据传输至中心服务器。因此，联邦学习能够在保护数据隐私[3]的前提下，利用分布式数据进行高效的模型训练，现已成为大规模机器学习领域的重要研究方向。联邦学习通常解决的是以下优化问题：

$\underset{x\in {ℝ}^d}{\min }f\left(x\right):=\frac{1}{N}{\displaystyle \sum _{i=1}^N{f}_i}\left(x\right),$ (1)

其中$f_i\left(x\right):={{\rm E}}_{d_j~D_i}{f}_{i,j}\left(x;d_j\right)$ 是第$i$ 个客户端在本地数据集$D_i$ 上的损失函数。

在联邦学习系统中，由于本地数据集的规模越来越大且服务器和边缘设备之间的带宽有限，联邦学习面临着通信成本的问题，所以实现通信效率、隐私保护和模型性能三者之间的最优平衡是联邦学习的一个关键目标。

为了解决联邦通信成本问题，通常有两种解决方法：第一种是在本地进行多次更新，例如联邦平均算法(FedAvg) [4]，随机控制平均算法(SCAFFOLD) [5]；第二种是对本地通信信息进行压缩，例如分布式压缩梯度算法(DCGD) [6]，带压缩的联邦平均算法(FedCOM) [7]，基于方差缩减和梯度追踪的FedCOM算法[8]。

由于自适应的方法广泛应用于联邦学习当中，例如，FEDADAM算法[9]和FedExp算法[10]。本文受外推自适应步长的启发将其推广到了压缩联邦学习当中，并提出了外推压缩联邦学习算法(ExpFedCom)。

${\lambda }_t=\frac{{\displaystyle {\sum }_{i=1}^N{\Vert f_i\left(x^t\right)-x^t\Vert }^2}}{N{\Vert \frac{1}{N}{\displaystyle \sum _{i=1}^N{f}_i\left(x^t\right)-x^t}\Vert }^2}.$ (外推法步长)

2. ExpFedCom算法

首先给出无偏压缩算子的定义：

定义1 如果一个随机映射$C:{ℝ}^d\mapsto {ℝ}^d$ 是$\omega$ 压缩算子，若对任意$x\in {ℝ}^d$ ，满足：

${\rm E}\left[C\left(x\right)\right]=x,{\rm E}\left[{\Vert C\left(x\right)-x\Vert }^2\right]\le \omega {\Vert x\Vert }^2.$

若模型未压缩，即$C\left(x\right)\equiv x$ ，则$\omega =0$ 。

考虑基于压缩的外推自适应步长：

${\eta }_t=\frac{{\displaystyle {\sum }_{i=1}^N{\Vert C\left(x^t-x_{i,K}^t\right)\Vert }^2}}{N{\Vert \frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\Vert }^2},$

其中K是本地更新次数。提出的这一新步长通过比较客户端本地更新与全局平均更新的差异，来度量模型更新的“有效性”。如果客户端的更新方向高度一致，平均更新的范数会接近于单个更新的均值，比值较小，说明更新是有效的；反之，如果本地更新存在明显分歧，则平均更新的合力较弱，比值增大，提示更新效果不足。此外这一新步长不依赖于特定参数(例如李普希茨常数或压缩系数)，还有效节省了调节最优步长的时间。我们将提出的外推自适应步长与压缩联邦平均框架相结合，提出外推压缩联邦平均算法(ExpFedCom)，见算法1。

算法1：外推压缩联邦平均算法(ExpFedCom)

输入：服务器初始化全局模型$x^0$ 和本地步长$\alpha$

1：for $t=0,1,2,\cdots$ do

2： 客户端$i\in \left[N\right]$ 并行如下步骤

3： 初始化本地模型$x_{i,0}^t=x^t$

4： for $k=0,1,2,\cdots ,K-1$ do

5： 计算梯度信息$\nabla f_i\left(x_{i,k}^t\right)$

6： 更新本地模型$x_{i,k+1}^t=x_{i,k}^t-\alpha \nabla f_i\left(x_{i,k}^t\right)$

7： end for

8： 将压缩信息${\Delta }_i^t=C\left(x^t-x_{i,K}^t\right)$ 传输给服务器

9： 服务器聚合${\Delta }^t=\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Delta }_i^t}$

10： 计算外推步长${\eta }_t=\max \left\{1,\frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{2N\left({\Vert {\Delta }^t\Vert }^2+\epsilon \right)}\right\}$

11： 服务器更新全局模型$x^{t+1}=x^t-{\eta }_t{\Delta }^t$

12：end for

在算法中，我们在提出的新步长中引入了$\frac{1}{2}$ ，这可以抑制过大的步长的扩张，使得算法在面对高度

异质的数据和压缩时更稳定，同时仍能保留自适应调节的特性。在步长分母中引入$\epsilon$ 是为了防止分母为0的情况。将步长与1比较取最大，是为了避免步长过小，而导致收敛过慢或更新停滞，这也使得步长有下界。注意到，当${\eta }_t$ 取常数步长时，ExpFedCom算法可以退化为FedCOM算法[7]。

3. 收敛性分析

假设x^*是问题(1)的全局最优解且满足$f\left(x^{\ast }\right)=f^{\ast }$ 以及对任意$i\in \left[N\right]$ ，$\nabla f_i\left(x^{\ast }\right)=0$ 。文章出现的E记为对所有随机变量取期望。本节通过一些引理，在凸以及强凸情况下对ExpFedCom算法做出了收敛性分析。

3.1. 凸情况分析

引理1 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的，则对任意$t\ge 0$ 和$\alpha \le \frac{1}{L}$ 有

${\Vert x_{i,K}^t-x^{\ast }\Vert }^2\le {\Vert x^t-x^{\ast }\Vert }^2-\frac{1}{KL\alpha }{\Vert x^t-x_{i,K}^t\Vert }^2.$

证明：对任意$t\ge 0$ ，有

$\begin{array}{c}{\Vert x_{i,k}^t-x^{\ast }\Vert }^2={\Vert x_{i,k-1}^t-\alpha \nabla f_i\left(x_{i,k-1}^t\right)-x^{\ast }\Vert }^2\\ ={\Vert x_{i,k-1}^t-x^{\ast }\Vert }^2-2\alpha \langle \nabla f_i\left(x_{i,k-1}^t\right),x_{i,k-1}^t-x^{\ast }\rangle +{\alpha }^2{\Vert \nabla f_i\left(x_{i,k-1}^t\right)\Vert }^2\\ \le {\Vert x_{i,k-1}^t-x^{\ast }\Vert }^2-\alpha \left(\frac{2}{L}-\alpha \right){\Vert \nabla f_i\left(x_{i,k-1}^t\right)\Vert }^2\\ \le {\Vert x_{i,k-1}^t-x^{\ast }\Vert }^2-\frac{\alpha }{L}{\Vert \nabla f_i\left(x_{i,k-1}^t\right)\Vert }^2\\ \le {\Vert x_{i,0}^t-x^{\ast }\Vert }^2-\frac{\alpha }{L}{\displaystyle \sum _{j=0}^{k-1}{\Vert \nabla f_i\left(x_{i,j}^t\right)\Vert }^2},\end{array}$

其中第一个不等于利用了$f_i$ 是L-光滑的，第二个不等式利用了$\alpha \le \frac{1}{L}$ 。令$k=K$ 则有

$\begin{array}{c}{\Vert x_{i,K}^t-x^{\ast }\Vert }^2\le {\Vert x_{i,0}^t-x^{\ast }\Vert }^2-\frac{\alpha }{L}{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}\\ ={\Vert x^t-x^{\ast }\Vert }^2-\frac{1}{L\alpha }{\displaystyle \sum _{k=0}^{K-1}{\Vert x_{i,k}^t-x_{i,k+1}^t\Vert }^2}\\ \le {\Vert x^t-x^{\ast }\Vert }^2-\frac{1}{KL\alpha }{\Vert {\displaystyle \sum _{k=0}^{K-1}\left(x_{i,k}^t-x_{i,k+1}^t\right)}\Vert }^2\\ ={\Vert x^t-x^{\ast }\Vert }^2-\frac{1}{KL\alpha }{\Vert x^t-x_{i,K}^t\Vert }^2,\end{array}$

其中第三个不等于利用了均值不等式，证毕。

引理2 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的，则对任意$t\ge 0$ 和$\alpha \le \min \left\{\frac{1}{L},\frac{1}{KL\omega }\right\}$ 有

$\frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{2N{\Vert {\Delta }^t\Vert }^2}\le {\eta }_t\le \frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{N{\Vert {\Delta }^t\Vert }^2}.$

证明：对任意$t\ge 0$ ，有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]={\rm E}\left[{\Vert x^t-{\eta }_t{\Delta }^t-x^{\ast }\Vert }^2\right]\\ ={\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\langle {\Delta }^t,x^t-x^{\ast }\rangle +{\eta }_t{}^2{\Vert {\Delta }^t\Vert }^2\right].\end{array}$

对${\eta }_t$ 取微分，有

${\rm E}\left[2{\eta }_t{\Vert {\Delta }^t\Vert }^2-2\langle {\Delta }^t,x^t-x^{\ast }\rangle \right]=0,$

所以

$\begin{array}{c}{\eta }_t=\frac{{\rm E}\left[2\langle \frac{1}{N}{\displaystyle \sum _{i=1}^N{\Delta }_i^t},x^t-x^{\ast }\rangle \right]}{2{\Vert {\Delta }^t\Vert }^2}\\ =\frac{{\displaystyle \sum _{i=1}^N{\rm E}\left[{\Vert {\Delta }_i^t\Vert }^2+{\Vert x^t-x^{\ast }\Vert }^2-{\Vert {\Delta }_i^t-\left(x^t-x^{\ast }\right)\Vert }^2\right]}}{2N{\Vert {\Delta }^t\Vert }^2}.\end{array}$

结合${\Delta }_i^t$ 的定义，有

$\begin{array}{c}{\eta }_t=\frac{{\displaystyle \sum _{i=1}^N{\rm E}\left[{\Vert {\Delta }_i^t\Vert }^2+{\Vert x^t-x^{\ast }\Vert }^2-{\Vert x^t-x^{\ast }-C\left(x^t-x_{i,K}^t\right)\Vert }^2\right]}}{2N{\Vert {\Delta }^t\Vert }^2}\\ =\frac{{\displaystyle \sum _{i=1}^N{\rm E}\left[{\Vert {\Delta }_i^t\Vert }^2+{\Vert x^t-x^{\ast }\Vert }^2-{\Vert x^t-x_{i,K}^t-C\left(x^t-x_{i,K}^t\right)\Vert }^2-{\Vert x_{i,K}^t-x^{\ast }\Vert }^2\right]}}{2N{\Vert {\Delta }^t\Vert }^2}\\ \ge \frac{{\displaystyle \sum _{i=1}^N\left({\Vert {\Delta }_i^t\Vert }^2+{\Vert x^t-x^{\ast }\Vert }^2-\omega {\Vert x^t-x_{i,K}^t\Vert }^2-{\Vert x_{i,K}^t-x^{\ast }\Vert }^2\right)}}{2N{\Vert {\Delta }^t\Vert }^2},\end{array}$

其中第四个等式和最后一个不等式利用了定义1。结合引理1，则有

$\begin{array}{c}{\eta }_t\ge \frac{{\displaystyle \sum _{i=1}^N\left({\Vert {\Delta }_i^t\Vert }^2+{\Vert x^t-x^{\ast }\Vert }^2-\omega {\Vert x^t-x_{i,K}^t\Vert }^2-{\Vert x^t-x^{\ast }\Vert }^2+\frac{1}{KL\alpha }{\Vert x^t-x_{i,K}^t\Vert }^2\right)}}{2N{\Vert {\Delta }^t\Vert }^2}\\ =\frac{{\displaystyle \sum _{i=1}^N\left({\Vert {\Delta }_i^t\Vert }^2-\left(\omega -\frac{1}{KL\alpha }\right){\Vert x^t-x_{i,K}^t\Vert }^2\right)}}{2N{\Vert {\Delta }^t\Vert }^2}\\ \ge \frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{2N{\Vert {\Delta }^t\Vert }^2},\end{array}$

其中最后一个不等式利用了$\alpha \le \min \left\{\frac{1}{L},\frac{1}{KL\omega }\right\}$ 。又因为${\eta }_t=\max \left\{1,\frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{2N\left({\Vert {\Delta }^t\Vert }^2+\epsilon \right)}\right\}$ ，且下述不等式成立

$\frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{2N{\Vert {\Delta }^t\Vert }^2}\le \frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{N{\Vert {\Delta }^t\Vert }^2},\frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{N{\Vert {\Delta }^t\Vert }^2}\ge 1,$

所以有

$\frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{2N{\Vert {\Delta }^t\Vert }^2}\le {\eta }_t\le \frac{{\displaystyle {\sum }_{i=1}^N{\Vert {\Delta }_i^t\Vert }^2}}{N{\Vert {\Delta }^t\Vert }^2}.$

证毕。

引理3 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的，则对任意$t\ge 0$ 有

$\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}\le \frac{2L^2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+4KL\left(f\left(x^t\right)-f^{\ast }\right).$

证明：对任意$t\ge 0$ ，根据均值不等式有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}\le \frac{2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\left({\Vert \nabla f_i\left(x_{i,k}^t\right)-\nabla f_i\left(x^t\right)\Vert }^2+{\Vert \nabla f_i\left(x^t\right)\Vert }^2\right)}}\\ =\frac{2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\left({\Vert \nabla f_i\left(x_{i,k}^t\right)-\nabla f_i\left(x^t\right)\Vert }^2+{\Vert \nabla f_i\left(x^t\right)-\nabla f_i\left(x^{\ast }\right)\Vert }^2\right)}}.\end{array}$

结合$f_i$ 是L-光滑的，有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}\le \frac{2L^2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+\frac{4KL}{N}{\displaystyle \sum _{i=1}^N\left(f_i\left(x^t\right)-f_i\left(x^{\ast }\right)\right)}\\ =\frac{2L^2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+4KL\left(f\left(x^t\right)-f^{\ast }\right).\end{array}$

证毕。

引理4 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的，则对任意$t\ge 0$ 和$\alpha \le \min \left\{\frac{1}{2KL},\frac{1}{KL\omega }\right\}$ 有

$\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\le 8L\left(K-1\right)K^2{\alpha }^2\left(f\left(x^t\right)-f^{\ast }\right).$

证明：对任意$t\ge 0$ ，根据均值不等式有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}={\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert {\displaystyle \sum _{c=0}^{k-1}\nabla f_i\left(x_{i,c}^t\right)}\Vert }^2}}\\ \le {\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}k{\displaystyle \sum _{c=0}^{k-1}{\Vert \nabla f_i\left(x_{i,c}^t\right)\Vert }^2}}}\\ \le K\left(K-1\right){\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}},\end{array}$

其中第一个不等式利用了均值不等式，第二个不等式利用了下述等式关系：

${\displaystyle \sum _{k=0}^{K-1}k{\displaystyle \sum _{c=0}^{k-1}{\Vert \nabla f_i\left(x_{i,c}^t\right)\Vert }^2}}={\displaystyle \sum _{k=0}^{K-2}\left(\frac{K\left(K-1\right)}{2}-\frac{k\left(k+1\right)}{2}\right){\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}.$

结合引理3有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\le K\left(K-1\right){\alpha }^2\left(\frac{2L^2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+4KL\left(f\left(x^t\right)-f^{\ast }\right)\right)\\ =2K\left(K-1\right)L^2{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+4L\left(K-1\right)K^2{\alpha }^2\left(f\left(x^t\right)-f^{\ast }\right)\\ \le \frac{1}{2N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+4L\left(K-1\right)K^2{\alpha }^2\left(f\left(x^t\right)-f^{\ast }\right),\end{array}$

其中最后一个不等式利用了$\alpha \le \min \left\{\frac{1}{2KL},\frac{1}{KL\omega }\right\}$ 。因此

$\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\le 8L\left(K-1\right)K^2{\alpha }^2\left(f\left(x^t\right)-f^{\ast }\right).$

证毕。

定理1 假设对任意$i\in \left[N\right]$ ，$f_i$ 是光滑的且凸的，则对任意$t\ge 0$ 和$\alpha \le \frac{1}{7KL\left(1+\omega \right)}$ 有

${\rm E}\left[f\left(\overline{x}\right)-f^{\ast }\right]\le \frac{7{\Vert x^0-x^{\ast }\Vert }^2}{\alpha K{\inf }_t{\eta }_{t}T},$

其中设$p_t=\frac{{\eta }_t}{{\displaystyle {\sum }_{t=0}^{T-1}{\eta }_t}}$ ，$\overline{x}$ 是从$\left\{x^0,x^1,\cdots ,x^{T-1}\right\}$ 中以$p_t$ 概率选取。

证明：对任意$t\ge 0$ ，有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]={\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\langle x^t-x^{\ast },\frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\rangle +{\eta }_t^2{\Vert \frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\Vert }^2\right]\\ ={\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\frac{1}{N}{\displaystyle \sum _{i=1}^N\langle x^t-x^{\ast },x^t-x_{i,K}^t\rangle }+{\eta }_t^2{\Vert \frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\Vert }^2\right].\end{array}$

结合引理2，有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\frac{1}{N}{\displaystyle \sum _{i=1}^N\langle x^t-x^{\ast },x^t-x_{i,K}^t\rangle }+{\eta }_t\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert C\left(x^t-x_{i,K}^t\right)\Vert }^2}\right]\\ \le {\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\frac{1}{N}{\displaystyle \sum _{i=1}^N\langle x^t-x^{\ast },x^t-x_{i,K}^t\rangle }+\left(1+\omega \right){\eta }_t\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert x^t-x_{i,K}^t\Vert }^2}\right]\\ ={\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\langle x^t-x^{\ast },\nabla f_i\left(x_{i,k}^t\right)\rangle }}+\left(1+\omega \right){\eta }_t{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert {\displaystyle \sum _{k=0}^{K-1}\nabla f_i\left(x_{i,k}^t\right)}\Vert }^2}\right]\\ \le {\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\langle x^t-x^{\ast },\nabla f_i\left(x_{i,k}^t\right)\rangle }}+\left(1+\omega \right)K{\eta }_t{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}\right],\end{array}$

其中第二个不等式利用了定义1，最后一个不等式利用了均值不等式。因此

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2-2{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\left(\langle x^t-x_{i,k}^t,\nabla f_i\left(x_{i,k}^t\right)\rangle +\langle x_{i,k}^t-x^{\ast },\nabla f_i\left(x_{i,k}^t\right)\rangle \right)}}\\ +\left(1+\omega \right)K{\eta }_t{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}]\\ \le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2+2{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\left(f_i\left(x_{i,k}^t\right)-f_i\left(x^t\right)+\frac{L}{2}{\Vert x^t-x_{i,k}^t\Vert }^2+\langle x^{\ast }-x_{i,k}^t,\nabla f_i\left(x_{i,k}^t\right)\rangle \right)}}\\ +\left(1+\omega \right)K{\eta }_t{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}]\\ \le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2+2{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\left(f_i\left(x_{i,k}^t\right)-f_i\left(x^t\right)+\frac{L}{2}{\Vert x^t-x_{i,k}^t\Vert }^2+f_i\left(x^{\ast }\right)-f_i\left(x_{i,k}^t\right)\right)}}\\ +\left(1+\omega \right)K{\eta }_t{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}]\\ \le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2+2{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}\left(f_i\left(x^{\ast }\right)-f_i\left(x^t\right)+\frac{L}{2}{\Vert x^t-x_{i,k}^t\Vert }^2\right)}}\\ +\left(1+\omega \right)K{\eta }_t{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}],\end{array}$

其中第二个不等式利用了$f_i$ 是L-光滑的，第三个不等式利用了$f_i$ 是凸的。结合引理3有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2-2K{\eta }_t\alpha \left(f\left(x^t\right)-f^{\ast }\right)+L{\eta }_t\alpha \frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\\ +\left(1+\omega \right)K{\eta }_t{\alpha }^2\left(\frac{2L^2}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}+4KL\left(f\left(x^t\right)-f^{\ast }\right)\right)]\\ \le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2-2K{\eta }_t\alpha \left(1-2KL\left(1+\omega \right)\alpha \right)\left(f\left(x^t\right)-f^{\ast }\right)\\ +L{\eta }_t\alpha \left(1+2KL\left(1+\omega \right)\alpha \right)\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}].\end{array}$

结合引理4有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2-2K{\eta }_t\alpha \left(1-2KL\left(1+\omega \right)\alpha \right)\left(f\left(x^t\right)-f^{\ast }\right)\\ +8{\eta }_t\left(K-1\right)L^2{K}^2{\alpha }^3\left(1+2KL\left(1+\omega \right)\alpha \right)\left(f\left(x^t\right)-f^{\ast }\right)].\end{array}$

取$\alpha \le \min \left\{\frac{1}{3KL},\frac{1}{KL\omega }\right\}$ ，则有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\rm E}[{\Vert x^t-x^{\ast }\Vert }^2-K{\eta }_t\alpha \left(2-4KL\left(1+\omega \right)\alpha \right)\left(f\left(x^t\right)-f^{\ast }\right)\\ +K{\eta }_t\alpha \left(1+2KL\left(1+\omega \right)\alpha \right)\left(f\left(x^t\right)-f^{\ast }\right)]\\ ={\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-K{\eta }_t\alpha \left(1-6KL\left(1+\omega \right)\alpha \right)\left(f\left(x^t\right)-f^{\ast }\right)\right]\\ \le {\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-\frac{K{\eta }_t\alpha }{7}\left(f\left(x^t\right)-f^{\ast }\right)\right],\end{array}$

其中最后一个不等式利用了$\alpha \le \frac{1}{7KL\left(1+\omega \right)}$ 。因此有

${\rm E}\left[{\displaystyle \sum _{t=0}^{T-1}{\eta }_t\left(f\left(x^t\right)-f^{\ast }\right)}\right]\le \frac{7{\Vert x^0-x^{\ast }\Vert }^2}{\alpha K}.$

对任意$t=0,1,\cdots ,T-1$ ，设$p_t=\frac{{\eta }_t}{{\displaystyle {\sum }_{t=0}^{T-1}{\eta }_t}}$ 且，$\overline{x}$ 是从$\left\{x^0,x^1,\cdots ,x^{T-1}\right\}$ 中以$p_t$ 概率选取，则有

${\rm E}\left[f\left(\overline{x}\right)-f^{\ast }\right]\le \frac{7{\Vert x^0-x^{\ast }\Vert }^2}{\alpha K{\displaystyle {\sum }_{t=0}^{T-1}{\eta }_t}}\le \frac{7{\Vert x^0-x^{\ast }\Vert }^2}{\alpha K{\inf }_t{\eta }_{t}T}.$

证毕。

3.2. 强凸情况分析

定理2 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的且$\mu$ -强凸的，则对任意$t\ge 0$ 和$\alpha \le \min \left\{\frac{1}{7KL\left(1+\omega \right)},\frac{14}{\mu K{\inf }_t{\eta }_t}\right\}$ 有

${\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\left(1-\frac{\mu K{\inf }_t{\eta }_t\alpha }{14}\right)}^{t+1}{\Vert x^0-x^{\ast }\Vert }^2.$

证明：根据定理1证明，当$\alpha \le \frac{1}{7KL\left(1+\omega \right)}$ ，有

$\begin{array}{c}{\rm E}\left[{\Vert x^{t+1}-x^{\ast }\Vert }^2\right]\le {\rm E}\left[{\Vert x^t-x^{\ast }\Vert }^2-\frac{K{\inf }_t{\eta }_t\alpha }{7}\left(f\left(x^t\right)-f^{\ast }\right)\right]\\ \le {\rm E}\left[\left(1-\frac{\mu K{\inf }_t{\eta }_t\alpha }{14}\right){\Vert x^t-x^{\ast }\Vert }^2\right]\\ \le {\left(1-\frac{\mu K{\inf }_t{\eta }_t\alpha }{14}\right)}^{t+1}{\Vert x^0-x^{\ast }\Vert }^2,\end{array}$

其中第二个不等式利用了$f_i$ 的强凸性，最后一个不等式利用了$\alpha \le \min \left\{\frac{1}{7KL\left(1+\omega \right)},\frac{14}{\mu K{\inf }_t{\eta }_t}\right\}$ ，证毕。

3.3. 非凸情况分析

假设1 假设梯度方差有界，即对任意$i\in \left[N\right]$ ，存在$\sigma \ge 0$ 使得下式成立

$\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x\right)-\nabla f\left(x\right)\Vert }^2}\le {\sigma }^2.$

引理5 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的，假设梯度方差有界，则对任意$t\ge 0$ 和$\alpha \le \frac{1}{2KL}$ 有

$\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x^t\right)-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i\left(x_{i,k}^t\right)}\Vert }^2}\le \frac{3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}+\frac{3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}.$

证明：利用均值不等式，有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x^t\right)-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i\left(x_{i,k}^t\right)}\Vert }^2}\le \frac{1}{N}{\displaystyle \sum _{i=1}^N\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x^t\right)-\nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}\\ \le \frac{L^2}{K}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\\ =\frac{L^2{\alpha }^2}{K}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert {\displaystyle \sum _{c=0}^{k-1}\nabla f_i\left(x_{i,c}^t\right)}\Vert }^2}}\\ \le \frac{L^2{\alpha }^2}{K}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}k{\displaystyle \sum _{c=0}^{k-1}{\Vert \nabla f_i\left(x_{i,c}^t\right)\Vert }^2}}}\end{array}$

其中第二个不等式利用了$f_i$ 是L-光滑的，最后一个不等式利用了均值不等式。再根据下述等式关系：

${\displaystyle \sum _{k=0}^{K-1}k{\displaystyle \sum _{c=0}^{k-1}{\Vert \nabla f_i\left(x_{i,c}^t\right)\Vert }^2}}={\displaystyle \sum _{k=0}^{K-2}\left(\frac{K\left(K-1\right)}{2}-\frac{k\left(k+1\right)}{2}\right){\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2},$

则有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x^t\right)-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i\left(x_{i,k}^t\right)}\Vert }^2}\le \left(K-1\right)L^2{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)\Vert }^2}}\\ \le 3\left(K-1\right)L^2{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}({\Vert \nabla f_i\left(x_{i,k}^t\right)-\nabla f\left(x_{i,k}^t\right)\Vert }^2}}\\ +{\Vert \nabla f\left(x_{i,k}^t\right)-\nabla f\left(x^t\right)\Vert }^2+{\Vert \nabla f\left(x^t\right)\Vert }^2)\\ \le 3\left(K-1\right)L^2{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}({\Vert \nabla f_i\left(x_{i,k}^t\right)-\nabla f\left(x_{i,k}^t\right)\Vert }^2}}\\ +\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x_{i,k}^t\right)-\nabla f_i\left(x^t\right)\Vert }^2}+{\Vert \nabla f\left(x^t\right)\Vert }^2),\end{array}$

其中最后两个不等式利用了均值不等式。结合假设1梯度方差有界，则有

$\begin{array}{c}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x^t\right)-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i\left(x_{i,k}^t\right)}\Vert }^2}\le 3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2+3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2\\ +3\left(K-1\right)L^2{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert \nabla f_i\left(x_{i,k}^t\right)-\nabla f_i\left(x^t\right)\Vert }^2}}\\ \le 3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2+3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2\\ +3\left(K-1\right)L^4{\alpha }^2\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x_{i,k}^t-x^t\Vert }^2}},\end{array}$

其中第二个不等式利用了$f_i$ 是L-光滑的。注意到

$\begin{array}{c}\frac{L^2}{K}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\le 3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2+3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2\\ +3K\left(K-1\right)L^2{\alpha }^2\left(\frac{L^2}{K}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\right).\end{array}$

取$\alpha \le \frac{1}{2KL}$ ，则有

$\frac{L^2}{K}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\displaystyle \sum _{k=0}^{K-1}{\Vert x^t-x_{i,k}^t\Vert }^2}}\le \frac{3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}+\frac{3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}.$

因此有

$\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \nabla f_i\left(x^t\right)-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i\left(x_{i,k}^t\right)}\Vert }^2}\le \frac{3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}+\frac{3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}.$

证毕。

定理3 假设对任意$i\in \left[N\right]$ ，$f_i$ 是L-光滑的，假设梯度方差有界，则对任意$t\ge 0$ 和$\alpha \le \frac{1}{6KL\left(1+\omega \right)}$ ，有

${\rm E}\left[{\Vert \nabla f\left(\overline{x}\right)\Vert }^2\right]\le \frac{8\left(f\left(x^0\right)-f^{\ast }\right)}{\alpha K{\inf }_t{\eta }_{t}T}+3{\sigma }^2,$

其中设$p_t=\frac{{\eta }_t}{{\displaystyle {\sum }_{t=0}^{T-1}{\eta }_t}}$ ，$\overline{x}$ 是从$\left\{x^0,x^1,\cdots ,x^{T-1}\right\}$ 中以$p_t$ 概率选取。

证明：根据$f_i$ 是L-光滑的，有

$\begin{array}{c}{\rm E}\left[f\left(x^{t+1}\right)-f^{\ast }\right]\le {\rm E}\left[f\left(x^t\right)-f^{\ast }+\langle \nabla f\left(x^t\right),x^{t+1}-x^t\rangle +\frac{L}{2}{\Vert x^{t+1}-x^t\Vert }^2\right]\\ ={\rm E}\left[f\left(x^t\right)-f^{\ast }-{\eta }_t\langle \nabla f\left(x^t\right),\frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\rangle +\frac{L{\eta }_t^2}{2}{\Vert \frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\Vert }^2\right]\\ \le {\rm E}\left[f\left(x^t\right)-f^{\ast }-{\eta }_t\langle \nabla f\left(x^t\right),\frac{1}{N}{\displaystyle \sum _{i=1}^{N}C\left(x^t-x_{i,K}^t\right)}\rangle +\frac{L{\eta }_t}{2}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert C\left(x^t-x_{i,K}^t\right)\Vert }^2}\right],\end{array}$

其中最后一个不等式利用了引理2。结合定义1，有

$\begin{array}{c}{\rm E}\left[f\left(x^{t+1}\right)-f^{\ast }\right]\le {\rm E}\left[f\left(x^t\right)-f^{\ast }-{\eta }_t\langle \nabla f\left(x^t\right),\frac{1}{N}{\displaystyle \sum _{i=1}^N\left(x^t-x_{i,K}^t\right)}\rangle +\frac{\left(1+\omega \right)L{\eta }_t}{2}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert x^t-x_{i,K}^t\Vert }^2}\right]\\ ={\rm E}[f\left(x^t\right)-f^{\ast }-\alpha K{\eta }_t\langle \nabla f\left(x^t\right),\frac{1}{N}{\displaystyle \sum _{i=1}^N\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)}\rangle \\ +\frac{\left(1+\omega \right)L{K}^2{\alpha }^2{\eta }_t}{2}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)\Vert }^2}]\\ ={\rm E}[f\left(x^t\right)-f^{\ast }-\frac{\alpha K{\eta }_t}{2}({\Vert \nabla f\left(x^t\right)\Vert }^2+{\Vert \frac{1}{N}{\displaystyle \sum _{i=1}^N\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)}\Vert }^2\\ -{\Vert \nabla f\left(x^t\right)-\frac{1}{N}{\displaystyle \sum _{i=1}^N\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)}\Vert }^2)+\frac{\left(1+\omega \right)L{K}^2{\alpha }^2{\eta }_t}{2}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)\Vert }^2}]\\ \le {\rm E}[f\left(x^t\right)-f^{\ast }-\frac{\alpha K{\eta }_t}{2}{\Vert \nabla f\left(x^t\right)\Vert }^2+\frac{\alpha K{\eta }_t}{2}{\Vert \nabla f\left(x^t\right)-\frac{1}{N}{\displaystyle \sum _{i=1}^N\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)}\Vert }^2\\ +\frac{\left(1+\omega \right)L{K}^2{\alpha }^2{\eta }_t}{2}\frac{1}{N}{\displaystyle \sum _{i=1}^N{\Vert \frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\nabla f_i}\left(x_{i,k}^t\right)\Vert }^2}].\end{array}$

利用均值不等式，有

其中最后一个不等式利用了假设1梯度方差有界。结合引理5，则有

$\begin{array}{c}{\rm E}\left[f\left(x^{t+1}\right)-f^{\ast }\right]\le {\rm E}[f\left(x^t\right)-f^{\ast }-\frac{\alpha K{\eta }_t}{2}\left(1-3\left(1+\omega \right)LK\alpha \right){\Vert \nabla f\left(x^t\right)\Vert }^2+\frac{3\left(1+\omega \right)L{K}^2{\alpha }^2{\sigma }^2{\eta }_t}{2}\begin{array}{c}\underset{}{\overset{}{}}\\ \end{array}\\ +\frac{\alpha K{\eta }_t}{2}\left(1+3\left(1+\omega \right)LK\alpha \right)\left(\frac{3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}+\frac{3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}\right)].\end{array}$

利用$\alpha \le \frac{1}{6KL\left(1+\omega \right)}$ ，则有

$\begin{array}{c}{\rm E}\left[f\left(x^{t+1}\right)-f^{\ast }\right]\le {\rm E}[f\left(x^t\right)-f^{\ast }-\frac{\alpha K{\eta }_t}{4}{\Vert \nabla f\left(x^t\right)\Vert }^2+\frac{\alpha K{\eta }_t{\sigma }^2}{4}\begin{array}{c}\underset{}{\overset{}{}}\\ \end{array}\\ +\frac{3\alpha K{\eta }_t}{4}\left(\frac{3K\left(K-1\right)L^2{\alpha }^2{\sigma }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}+\frac{3K\left(K-1\right)L^2{\alpha }^2{\Vert \nabla f\left(x^t\right)\Vert }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}\right)]\\ ={\rm E}[f\left(x^t\right)-f^{\ast }-\frac{\alpha K{\eta }_t}{4}\left(1-\frac{9K\left(K-1\right)L^2{\alpha }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}\right){\Vert \nabla f\left(x^t\right)\Vert }^2\\ +\frac{\alpha K{\eta }_t{\sigma }^2}{4}\left(1+\frac{9K\left(K-1\right)L^2{\alpha }^2}{1-3K\left(K-1\right)L^2{\alpha }^2}\right)].\end{array}$

取$\alpha \le \min \left\{\frac{1}{5KL},\frac{1}{6KL\left(1+\omega \right)}\right\}=\frac{1}{6KL\left(1+\omega \right)}$ ，则有

${\rm E}\left[f\left(x^{t+1}\right)-f^{\ast }\right]\le {\rm E}\left[f\left(x^t\right)-f^{\ast }-\frac{\alpha K{\eta }_t}{8}{\Vert \nabla f\left(x^t\right)\Vert }^2+\frac{3\alpha K{\eta }_t{\sigma }^2}{8}\right].$

因此有

${\rm E}\left[{\displaystyle \sum _{t=0}^{T-1}{\eta }_t{\Vert \nabla f\left(x^t\right)\Vert }^2}\right]\le \frac{8\left(f\left(x^0\right)-f^{\ast }\right)}{\alpha K}+3{\sigma }^2{\displaystyle \sum _{t=0}^{T-1}{\eta }_t}.$

对任意$t=0,1,\cdots ,T-1$ ，设$p_t=\frac{{\eta }_t}{{\displaystyle {\sum }_{t=0}^{T-1}{\eta }_t}}$ 且，$\overline{x}$ 是从$\left\{x^0,x^1,\cdots ,x^{T-1}\right\}$ 中以$p_t$ 概率选取，则有

${\rm E}\left[{\Vert \nabla f\left(\overline{x}\right)\Vert }^2\right]\le \frac{8\left(f\left(x^0\right)-f^{\ast }\right)}{\alpha K{\displaystyle {\sum }_{t=0}^{T-1}{\eta }_t}}+3{\sigma }^2\le \frac{8\left(f\left(x^0\right)-f^{\ast }\right)}{\alpha K{\inf }_t{\eta }_{t}T}+3{\sigma }^2.$

证毕。

综合上述三小节收敛性分析，我们可以得到以下三个结论：

(1) 在凸条件下，如果$\alpha =\frac{1}{7KL\left(1+\omega \right)}$ ，那么ExpFedCom可以在$T=O\left(\frac{L\left(1+\omega \right)}{\epsilon }\right)$ 通信轮数内找到一个点$x$ ，使得${\rm E}\left[f\left(x\right)\right]-f^{\ast }\le \epsilon$ 。

(2) 在强凸条件下，如果$\alpha \le \min \left\{\frac{1}{7KL\left(1+\omega \right)},\frac{14}{\mu K{\inf }_t{\eta }_t}\right\}$ ，那么ExpFedCom可以在$T=O\left(\frac{1}{\mu K\alpha }\log \left(\frac{1}{\epsilon }\right)\right)$ 通信轮数内找到一个点$x$ ，使得${\rm E}\left[{\Vert x-x^{\ast }\Vert }^2\right]\le \epsilon$ 。

(3) 在非凸条件下，如果$\alpha =\frac{1}{6KL\left(1+\omega \right)}$ 以及$\sigma \le \frac{\epsilon }{6}$ ，那么ExpFedCom可以在$T=O\left(\frac{1+\omega }{{\epsilon }^2}\right)$ 通信轮数内找到一个点$x$ ，使得${\rm E}\left[\Vert \nabla f\left(x\right)\Vert \right]\le \epsilon$ 。

综合上述三小节收敛性分析，我们可以得到以下三个结论(表1)：

Table 1. Communication complexity comparison of algorithms

表1. 算法通信复杂度比较

算法	凸	强凸	非凸
FedAvg	$T=O\left(\frac{L}{\epsilon }\right)$	$T=O\left(\frac{L}{\mu }\log \left(\frac{1}{\epsilon }\right)\right)$	$T=O\left(\frac{1}{{\epsilon }^2}\right)$
FedCOM	$T=O\left(\frac{N+\omega }{N\epsilon }\log \left(\frac{1}{\epsilon }\right)\right)$	$T=O\left(\frac{L}{\mu }\left(1+\frac{\omega }{N}\right)\log \left(\frac{1}{\epsilon }\right)\right)$	$T=O\left(\frac{1}{{\epsilon }^2}\right)$
Ours (ExpFedCom)	$T=O\left(\frac{L\left(1+\omega \right)}{\epsilon }\right)$	$T=O\left(\frac{1}{\mu K\alpha }\log \left(\frac{1}{\epsilon }\right)\right)$	$T=O\left(\frac{1+\omega }{{\epsilon }^2}\right)$

4. 数值实验

我们分别在MNIST数据集上对MLP模型[7]和在EMNIST数据集上对CNN模型进行了训练。对于每个实验，我们都分别进行100回合的通信。对于MNIST数据集，每回合我们从200个客户端中随机均匀抽取100个客户端进行通信。对于EMNIST数据集，每回合我们从200个客户端中随机均匀抽取20个客户端进行通信。压缩方式与文献[7]方法一致，采取无偏量化的方式。本地损失函数采用交叉熵损失函数。每个算法选择理论上得到的最佳步长，最终实验结果如下(图1~4)：

Figure 1. The communication rounds versus loss and accuracy on the MNIST dataset

图1. MNIST数据集下的通信轮数与损失和精度实验图

Figure 2. The communication bits versus loss and accuracy on the MNIST dataset

图2. MNIST数据集下的通信比特数与损失和精度实验图

Figure 3. The communication rounds versus loss and accuracy on the EMNIST dataset

图3. EMNIST数据集下的通信轮数与损失和精度实验图

Figure 4. The communication bits versus loss and accuracy on the EMNIST dataset

图4. EMNIST数据集下的通信比特数与损失和精度实验图

5. 讨论

在本工作中，我们在联邦学习优化的标准假设下对所提出的算法进行了理论分析。值得注意的是，真实数据往往呈现高度非独立同分布(Non-IID)的特性，客户端之间存在显著的异质性。此外，深度神经网络本质上是非凸的，这使得我们的收敛性结论在应用到实际任务时存在一定局限。尽管存在这些差异，我们的实验结果表明，所提出的算法在现实条件下依旧取得了较好的性能，同时显著节省了通信成本，并优于一些主流基线方法。

尽管如此，我们承认，在实践中，数据异质性、客户端部分参与以及模型的非凸性等因素可能导致收敛速度变慢或出现残余误差邻域。我们认为，尽管我们的理论发现源于理想化的设定，它们仍然为算法设计提供了宝贵的见解和指导。未来的工作值得去开发一个更通用的分析框架，以更好地兼顾理论严谨性与实际适用性，从而为联邦学习的探索和发展提供更强的保证。

6. 总结

基于外推的自适应步长应用于压缩联邦学习当中表现出了良好的性质，并且通过数值实验可以看到ExpFedCom较不带压缩或者不带自适应步长的方法展现出了较好的优势。ExpFedCom既支持通信压缩又实现了在凸、强凸以及非凸条件下的快速收敛，这大大提高了通信效率，节省了通信成本，具有广泛的应用价值。