Asynchronous Federated Optimization论文阅读笔记

摘要

联邦学习使得可以在大量的边缘设备上进行训练。为了提高灵活性和拓展性，我们提出了一种新的异步联邦学习优化算法。我们证明了对于强凸问题和非凸问题，以及有限类非凸问题，提出的方法都具有接近线性收敛的全局最优解。实验结果表明，提出的算法在不同的场景中都能快速收敛且能容忍陈旧（这边翻译可能不合理）。

简介

联邦学习系统一般会有多个server和worker（即client）组成，其组成结构与参数服务器相似。worker会在当地的隐私数据上进行训练，server会聚合各个worker的学习模型并更新全局模型。
联邦学习有三个关键属性：

1. 任务执行不频繁：对于薄弱的边缘设备来说，学习任务只会在设备空闲、充电或者连接到未测量网络的情况下被执行；
2. 通信不频繁：边缘设备与较远的server之间的连接可能会不可达、缓慢甚至代价昂贵。
3. 非独立同分布的训练数据：对于联邦学习来说，不同设备上的数据可能是没有交集的，这代表可能会存在非同分布的样本。

联邦学习一般采用同步的方法，“落后者”可能会拖慢任务的进程。当需要处理庞大的边缘设备时，可能会存在很多的“落后者”。因为可用性和计算完成时间因设备而异，以及设备的有限容量和电池时间，实现全局同步是困难的，尤其是在联邦学习场景之中。
因为存在“落后者”和异构延迟，异步训练被广泛应用在传统的分布式随机梯度下降场景中。在此文中，我们将异步训练的优点与联邦优化相结合。
我们提出了一种联邦优化的新型异步算法。其关键想法在于：

1. 解决正则化局部问题以证明收敛性；
2. 使用了加权平均更新全局模型，混合权值会根据陈旧度自适应变化；

本文的主要贡献如下：

1. 提出了一种新型的异步联邦优化算法并设计了系统的雏形；
2. 证明了这种方法对于有限类非凸问题的收敛性；
3. 提出了解决异步过程中产生的错误的方法。为了实现这一目的，我们提出了一种混合超参数可以根据陈旧度自适应地协调收敛率与方差衰减之间的均衡。
4. 我们凭借经验证明该算法收敛速度快且在实际场景中优于一般同步同步联邦优化。

本文中的一些符号及其含义

0.调度触发器通过协调器进行训练
1.2.worker通过协调器从server上上接收模型$x_{t-\tau }$
3.worker使用算法1计算当地更新（梯度）。worker可以在空闲和工作两种状态中进行选择
4.5.6.worker通过协调器将局部更新后的模型发送给server。协调器会将收到的模型在5处进行排队，然后将它们有序地发送给6。
7.8.server更新全局模型并为协调器再次读取模型做准备。
1.5操作是并行异步的。

问题表述

考虑有$n$个设备的联邦学习。在每一个设备上，worker使用当地的数据训练模型。最终目标是使用所有设备上的数据训练一个全局模型$x\in R^d$。比较正式的说法是，我们要解决${\min }_{x\in R^d}F(x)$，其中$F(x)=\frac{1}{n}{\sum }_{i\in [n]}{E}_{z^i\sim {\mathcal{D}}^{i}f(x;z^i)}$且$\forall i\in [n]$，有$z^i$是第$i$个设备上本地数据集${\mathcal{D}}^i$的样本。注意$\forall i\ne j,{\mathcal{D}}^i\ne {\mathcal{D}}^j$。

做法

有$T$轮训练。在第$t$轮中，server会从任意一台worker中收到一个局部模型$w_{new}$，然后通过加权平均公式$x_t=(1-\alpha )x_{t-1}+\alpha x_{new}$更新全局模型，其中$\alpha \in (0,1)$是一个混合超参数。
在任意一台设备$i$上，在从server收到全局模型$x_t$后，会通过以下公式使用SGD进行多次迭代：${\min }_{x\in R^d}{E}_{x^i\sim {\mathcal{D}}^i}f(x;z^i)+\frac{\rho }{2}\Vert x-x_t{\Vert }^2$。为了方便，我们定义$g_x^{\prime }(x;z)=f(x;z)+\frac{\rho }{2}\Vert x-x^{\prime }{\Vert }^2$

server和worker之间是异步更新的。server不论是否收到局部模型都是立即更新全局模型的。server和worker之间的通信是无阻塞的。所以server和worker可以无需同步地随时更新模型。

实验

数据集

在两个基准CIFAR-10和WikiText-2上进行了实验。训练集被分到了$n=100$个设备上。小批量分别为$50$和$20$。

评估

baseline是同步联邦优化算法FedAvg。选择的FedAvg算法中每轮随机选择了$k=10$个设备进行局部模型的更新。我们也考虑了单线程SGD作为baseline。在FedAsync算法中，我们是在一个均匀分布中随机选择了$t-\tau$进行异步的模拟。
我们重复试验了$10$次并取了平均值。对于CIFAR-10，使用了测试集的最高精确度作为评估指标。
对于混合超参数的更新，采用了三种策略陈旧度函数进行了试验：

1. 常数：$s(t-\tau )=1$
2. Hinge：$s_{a,b}(t-\tau )=\{\begin{array}{ll}1& 如果t-\tau \le b\\ \frac{1}{a(t-\tau -b)+1}& 其他\end{array}$
3. 多项式：$s_a(t-\tau )=(t-\tau +1{)}^{-a}$