联邦学习论文阅读：Fair Resource Allocation in Federated Learning

arXiv上刚刚挂的一篇文章Fair Resource Allocation in Federated Learning，作者是CMU的AP Virginia Smith组的，搜了一下主页，居然是一个超级年轻的小姐姐~

这篇文章思路很straight-forward，逻辑也很清楚，唯一有点缺点的是可能时间比较赶，第一版上传的还是draft，文章还没修改完

Motivation
之前横向联邦学习一般都是follow google的FedAvg算法，将所有用户（或者随机一部分）更新的梯度取个平均作为中心模型的更新参数。显然，这种做法虽然对于所有用户来说，全局模型最后会收敛到一个最优值，但是对于单个用户，这个模型并不一定能达到局部最优。作者将之视为一个resource allocation fairness的问题，希望在全局最优的情况下，让所有用户个体都尽可能地达到最优值。

那么现在的问题是：怎么在全局模型的准确率不变的情况下，让每个用户模型的本地准确率也达到最高。作者认为当用户本地模型准确率偏离全局模型准确率的方差最小时可以认为这个模型就是公平的了。具体定义如下：

Definition 1 (Fairness of performance distribution): For trained models w and w', we say that model w provides a more fair solution to the federated learning objective (1) than model w' if the variance of the performance of model w on the m devices, {a_1, ..., a_m}, is smaller than the variance of the performance of model w' on the m devices, i.e., Var(a_1, ... , a_m) ≤ Var(a'_1, ... , a'_m).

模型
FedAvg：
min_w F(w) = \sum\limits_{k=1}^m p_k F_k(w) \\
p_k = \frac{n_k}{N}

其中F_k(w)是第k个用户本地的loss，n_k是该用户具有的样本数量，N是总的样本数量。

作者改为
min_w F_q(w) = \sum\limits_{k=1}^m \frac{p_k}{q+1} F_k^{q+1}(w)

当q的取值越大时，对于本身值很大的F_k(w)来说，其占的权重也会越大。

然后利用利普希茨条件可以得到梯度的一个上界，下图中equation 4符号有一些问题，已经和作者Tian Li邮件确认过了，应改为下式：

\begin{aligned} \nabla^2[\frac{1}{q+1}F_k^{q+1}(w)] &= \nabla[F_k^q(w) \cdot \nabla F(w)] \\ &= qF_k^{q-1}(w) \cdot \nabla F(w) \cdot \nabla F(w) + F_k^q(w) \cdot \nabla^2 F(w) \end{aligned}

算法
q-FedSGD算法梯度更新用的是一阶导之和除以二阶导之和，收敛性之前已经证明了。原因是如果想实验多个q值，或者说考虑多种fairness的情况，可能需要对每一个q都fine tune一个step size。一般的做法是grid search，那么当需要考虑的q值很多的时候，grid space会explode。如果用一阶导之和除以二阶导之和，只需要在q=0时调出一个步长后，直接应用到其它q值即可。

对于q-FedAvg，文章中给的理由是如果直接用FedAvg会变成优化前面的第一个式子，而不是作者修改的损失函数，所以提出了algorithm 3。作者说至于不用二阶导，是因为local update中会有交叉项，所以用w而不是直接计算。

感觉这一块的理由有一些绕，可能还需要再解释得清楚一些