A Field Guide to Federated Optimization

注意目标：通信效率、数据异构性、隐私保护性

服务器和客户机之间的通信必要的，但是会带来大量的传递数据，更新轮数、数据压缩。

数据异构性：非i.i.d.数据，客户的训练样本来自不同的分布。

本地计算 ，客户机会有计算能力的限制；这种计算的不公平有可能导致结果模型的不公平

分层系统很复杂，客户机会掉线、离开、突然加入。

通信信道必须纳入考虑，带宽的限制，通信噪声和不稳定性，

B.1介绍了三种FL算法：FedAVG,FedAVGM,FedADAM 35页也有对比，并在4中具体描述的算法的测试情况

4.2介绍的建议很有帮助

本文还需要多看几遍，包含了很多FL的知识。

Client-Edge-Cloud Hierarchical Federated Learning

重点体会其分层的思想

云服务器-设备模式和边缘服务器-设备模式各有优缺点，CEC正是将其结合起来，但是同时带来一些问题：收敛性证明、聚合频率的选取、本地更新的延迟和功耗之间的平衡。

本文给出的：收敛证明+两级聚合频率选取的定性准则

云-设备和边缘-设备都被看做两层FL模型，FAVG算法；CEC看作三层模型，用HierFAVG算法

学习问题

问题为监督学习。训练数据 D = { x j , y j } j = 1 ∣ D ∣ \mathcal{D}=\{\textbf{x}_j,y_j\}^{|\mathcal{D}|}_{j=1} D={xj​,yj​}j=1∣D∣​，$|\mathcal{D}|$是数据样本的总数，${\text{x}}_j$是第j个输入样本，yi是对应的标签，$\omega$是ML模型的全部参数的实向量。$f_j(\omega )$是第j个数据样本的损失函数，优化目标：

损失函数F(w)取决于ML模型，可以是凸的，如logistic回归，或非凸的，如神经网络。这个F(w)因为数据分散的原因，没法直接得到全局的损失的，只能加权每个设备的来估计。

${\cup }_{i=1}^N{\mathcal{D}}_i=\mathcal{D}$中的U是取并集的意思

CEC的模型

L个边缘服务器标记为$l$，互不连接的客户端 { C l } l = 1 L {\{\mathcal{C}^l}\}^L_{l=1} {Cl}l=1L​，N个用户，有分布式的数据集 { D l } l = 1 L {\{\mathcal{D}^l}\}^L_{l=1} {Dl}l=1L​，边缘$l$负责从其客户端聚合数据集$D^l$。$k$为第k次的梯度更新，用户每过k1次，更新下边缘；边缘每更新k2次，更新云端。${\omega }_i^l(k)$是本地更新了k次之后的本地模型参数。

其实整个CEC的模型没有做太多事情，只是把原本的二层模型转换为三层模型

MACFL

在上文CEC的 基础上改进

数据的异构性，设备的移动性，导致原来的算法效率低下。

全局平均的模型不能很好的适配每一个用户。

本文假设了移动用户在基站之间的移动为马尔可夫的转移矩阵来描述移动性。（最简单的对移动性的考虑了）

面对移动性，到另一个簇就上传，会破坏异构性，因此需要更谨慎的加权，减少查差异性影响和SGD方差

Federated Learning for Task and Resource Allocation in Wireless High Altitude Balloon Networks

学习其数学模型！

分层聚合：垂直来看

分簇：相同层之间D2D聚合，但仍是一个集群内

大规模降低能耗（只需要顶部节点上传），减少网络负载（每一层进行了降维）。

适应移动性：快速接入集群(复制模型参数)、退出时传输学习结果到本地对等方、利用上一层进行广播减少局部偏差

D2D延时代价高，需要权衡哪些设备集群适合D2D

抑制误差噪声的累计放大，加快收敛

基于块的学习：位于网络不同层的设备可以形成不同的学习块，在垂直更新之间，他们可以进行多轮块内学习本地更新。研究不同学习块的聚合频率、块内节点的计算能力、模型精度和训练收敛速度之间的权衡是一个开放的方向

DRL在这样的问题下很有前景

B.计算模型

这一段给出了计算耗时的模型：max{本地计算，边缘计算+传输延时}

C. 能量消耗模型

在我们的模型中，每个用户的能量消耗由三部分组成：a）设备操作，b）数据传输和c）数据计算。

问题提出

接下来，我们提出了我们的优化问题，其目标是最小化每个用户的能量和时间消耗的加权和。该最小化问题涉及根据以下公式确定用户关联、服务序列和必须传输到HAB的数据的大小

任务是用户产生的，由于每个n只能收集和该任务有关的用户的信息而不是全体，传统的迭代器难以达到全局优化，需要机器学习来预测连接，从而n可以选择和任务量相同的用户连接

面向主动用户关联的联邦学习

SVM的机器学习的组成

a) agents, b) input, c) output, d) SVM model

算法输入：$X_{mn}$,m的历史时刻上的连接和任务大小

算法输出：HAB n为预测用户m在时刻k的未来关联而执行的所提出的算法的输出是$a_{mn,k+1}$，它表示HAB n和用户m在时刻k1的用户关联。

SVM模型：每个基站m，我们定义一个SVM模型由向量${\omega }_{mn}$和矩阵${\Omega }_m\in {\mathbb{R}}^{N\times N}$表示，${\omega }_{mn}$是用来近似输入$x_{m,k}$和输出$a_{mn,k+1}$之间的预测函数，从而建立未来用户关联和用户m当前需要处理的任务的数据大小之间的关系。${\Omega }_m$是用来度量由基站n生成的SVM模型和由其它基站生成的SVM模型之间的差异。事实上，优化${\Omega }_m$能够提升n的本地SVM模型预测效果。

先利用和自己相关的连接的过往任务分配训练$W_m$，然后只把SVM模型${\omega }_m$发给别的，别的基站就能根据模型生成$W_m$，然后用这些$W_m$训练${\Omega }_m$

服务序列优化与任务分配

用户连接确定后，优化服务序列和任务分配。每个基站是独立决定这样优化分配的。上述两个问题是独立的可以分成两个子问题。

A.固定任务分配下的服务序列优化

B.固定服务顺序下的任务分配优化

Multi-task Federated Edge Learning (MtFEEL) in Wireless Networks

每个边缘设备定制模型。。。应对异构数据分布。。。

Ⅱ.系统模型

N个设备，一个中心，每一个设备都有一个特定的任务。第k个用户有nk个训练数据表示为 S k = { ( x k 1 , y k 1 ) , ( x k 2 , y k 2 ) , … , ( x k n k , y k n k ) } S_k=\{(\textbf{x}_{k1},y_{k1}),(\textbf{x}_{k2},y_{k2}),\dots,(\textbf{x}_{kn_k},y_{kn_k})\} Sk​={(xk1​,yk1​),(xk2​,yk2​),…,(xknk​​,yknk​​)}，

此外，假设跨设备的数据是独立的，但不一定是同分布。而且不能传递原始数据，因此考虑的学习规则是 $h_{\omega k}:\mathcal{X}\to \mathcal{Y},k=1,2,3$ ，${\mathcal{L}}_k(\omega )$是损失函数！

在经典的联邦设置中，目标是解决以下优化问题，即在所有设备上找到一个神经网络$\omega \in {\mathbb{R}}^d$

这个$\Phi$就是所有设备上面的网络模型的损失函数的和！！！要优化的全局的损失

n为样本总数${\sum }_{k=1}^N{n}_k$，需要注意的是，在实践中，上述问题的解可以通过SGD算法中Lk(w)的梯度估计得到。FL的挑战在于，总体梯度是单个平均损失梯度的总和。解决方案,比如FedAvg[9],1bit基于梯度的多数投票[17],和更多的人提出了文献[16]在于 系数nk / n将决定相应用户的损失函数的重要性k。然而，如果将来从用户k采样的数量减少，然后，通过解决上述问题返回的模型可能会导致多个设备的性能较差。解决上述问题的一个方法是看看最坏的情况，如下[3]所述:

因为相关数据的分布问题，很可能训练第k设备的损失函数的时候不只依赖自己的数据，因此需要将全局学习到的损失进行加权综合，但又不是简单的平均

一言以蔽之，我们在对不同的设备生成的损失进行适当加权，要求最后和（2）中的优化目标尽可能接近

A. 信道模型

该通信模型由单个BS单输入单输出(SISO)系统和多个用户或边缘设备组成。特别地，假设时间是时隙的，并且假设任何设备k和BS之间的信道是一个无线瑞利平坦衰落信道。对于输入xk(t)∈C，设备k在BS处**接收到的复基带信号y(t)**∈C为

其中（i.i.d.为独立同分布）为设备k与BS之间的衰落信道系数。噪声
为圆对称复高斯随机变量。通常，这些设备是移动电话，因此功率有限。因此，设备k处的功率约束为$\mathbb{E}|x_k(t){|}^2\le P_k$。==（E代表均值吗）==另一方面，BS被假定有足够的能力进行通信而不会出现任何错误。这个假设是为了简单和易于解释。在任何给定的时隙，都假定调度程序将带宽B的信道分配给希望通信的任何边缘设备。例如，在OFDMA系统中，一个资源块被分配给希望传输的用户。为简单起见，本文忽略了调度方案对算法收敛性的影响。

DFL算法

值得注意的是，为了解决(7)，需要了解差异。然而，设备可以访问数据，因此需要以分布式的方式估计差异。这个估计值将被用作(7)中设计联邦算法的代理。在接下来的小节中，提出了一种估计误差的算法。

估计分布差异DDE

从差异的定义来看，DDE算法相当于求解${\sup }_{\omega \in {\mathbb{R}}^d}|{\mathcal{L}}_k(\omega )-{\mathcal{L}}_j(\omega )|$，（对所有的k，j）。由于差异定义式的真实均值未知，因此这两项可以被估计为${\hat{\mathcal{L}}}_k(\omega ,S_k)和{\hat{\mathcal{L}}}_k(\omega ,S_j)$，解决这一问题的一种自然方法是采用分布式的梯度上升算法。利用差异估计，开发了一种分布式联邦学习算法。

本文的重点是表明，在保持通信复杂度为标称值的情况下，使用差异估计可以提高联邦算法的性能。

我们提出的DFL算法

在解决(7)中的问题时，DDE算法得到的差异估计可以作为真实差异的代理。可以使用经典的联邦算法来解决这个问题。然而，这需要交换梯度，这在许多问题中可能是非常高的维度，导致通信瓶颈。因此，在本节中，我们提出了一种不同于[17]的带符号梯度法。虽然在这种情况下可以使用量化梯度的一般方法，但为了简单起见，将使用一个简单的带符号梯度，并将量化梯度的分析降级到未来的工作。

==！！！！==具体来说，每个设备m发送带符号的梯度sign(gkm) 和损失$\hat{\mathcal{L}}({\omega }_k,S_m)$给BS，BS根据(9)和(10)汇总这些，得到估计的梯度
。这些估计用于获得最优权值wk和重要性系数αkj的改进估计给每个设备k。为了满足约束${\sum }_{j=1}^N{\alpha }_{kj}=1$。注意，(7)相对于α的梯度依赖于估计的差异。计算这个梯度很简单，因此在算法中没有明确提到。

自己的思考

联邦学习架构，目前看到的，有分层（CEC），部分讲了分簇（MACFL），有的考虑了通信信道（气球那个）和移动性（MACFL），但是，对于D2D网络似乎还没有提到，D2D通信对于本地模型的聚合应该有很大帮助。

非i.i.d.数据、异构数据；用户移动性；通信不稳定和噪声；都是FL的一些约束问题，上文基本上注重其中某几点。

异构环境：全局的模型不能很好的适配每一个用户（MINIST分数字学习很有意思）

• 对本地client的数据，能否有选择性的进行采集？抛弃一部分？动态权重？

• 怎么和D2D结合发挥最大性优势。

• 由移动性启发，一个簇不一定是一成不变的，层是不是也可以呢？更灵活的结果。

• FL不只是纯机器学习计算中的问题，还应该和网络架构、通信策略等结合起来，综合为FL服务。

• 效率、能耗、时延、收敛性，成为不可忽略的问题。

• 。。。

1.怎么