论文笔记 ASYNCHRONOUS FEDERATED OPTIMIZATION

论文笔记 ASYNCHRONOUS FEDERATED OPTIMIZATION

论文中提出了一种异步联邦优化算法。

联邦优化的同步特性是不可伸缩的、低效的和不灵活的。同时签入的设备过多会导致服务器端的网络拥塞。在每个全局epoch中，服务器仅限于从可用设备的子集中选择以触发训练任务。

经典的异步SGD在每次本地更新后直接向服务器发送梯度，这对于边缘设备来说是不可行的，因为它的通信不可靠且缓慢。

 

论文采用了异步的优化，并用加权平均来更新全局模型。

每个客户端设备都有一个worker可以出发本地训练，并将本地训练结果上传到服务器。服务器和worker异步执行更新，二者之间的通信是非阻塞的。

 

算法：

                                                                                                

选择使用函数s（t-τ）来确定α的值。我们列出了s（t-τ）的一些选择，参数化为a>0，b≥0：

实验结果

 

 

 

 

 

结论

1. 当整体 staleness 很小时，FedAsync的收敛速度与SGD一样快，也比FedAvg快。当 staleness 较大时，FedAsync收敛较慢。在最坏的情况下，FedAsync的收敛速度与FedAvg相似。当α太大时，收敛可能不稳定。利用自适应α，收敛性对大α具有鲁棒性。请注意，当最大staleness 为4时，FedAsync和FedAsync+Hinge（b=4）是相同的。
2. 在通信开销相同的情况下，当 staleness 很小时，FedAsync的收敛速度比FedAvg快。当 staleness 较大时，FedAsync的性能与FedAvg类似。
3. 更大的 staleness 会使收敛速度变慢，但影响并不是灾难性的。此外，使用自适应混合超参数，可以减轻因大滞后引起的不稳定性。
4. 通常，FedAsync对不同的α具有鲁棒性。请注意，差异是如此之小，以至于我们必须放大。当 staleness 较小时，自适应混合超参数就没有必要了。当 staleness 较大时，较小的α对FedAsync更好，而较大的α对FedAsync + Poly和FedAsync + Hinge更好。那是因为自适应性α在 staleness 较大时会自动调整为较小，因此我们不应该手动减小α。

个人解读

FedAVG算法是在每次选择占比为C的客户端进行本地训练，并将训练结果上传到服务器。每次只会选择当前当前可用的设备进行训练任务的触发。

本文中的FedAsync不管设备当前是否可用都可触发训练。服务器不会等到worker响应，当前不可用的worker可以等稍后可用后再开始训练任务。

FedAVG算法中，服务器要等响应的客户端数达到C*n后，才进行加权平均，求全局模型参数；而FedAsync不等待，有worker发来参数（模型参数和staleness）就进行加权平均，只是更新全局模型受staleness的影响，使用混合参数α来控制权重。

对staleness的理解：

数t是服务器接收到参数时所处的epoch数

数τ：表示服务器发给worker的参数用于第τ次epoch中初始化参数

所以定义的staleness应该就是该参数本应用于的epoch和实际所用于的epoch

也就是说，因为服务器和worker并不是同步工作，所以服务器不会一直等待直到worker响应后。由于设备通信的延迟，那设备收到服务器的参数xt-1后，进行本地训练并得到本地参数x'，上传服务器。但是服务器接收到该参数时，可能已经更新过本次迭代的结果了。该延迟越大对结果的影响也就越大。因此，文中提出了一个混合超参数α，来控制延迟参数对更新的权重。

这种机制，使得其更具有灵活性和可伸缩性，很大程度上减少了网络拥塞。

 

大家如果有什么不同的理解，欢迎评论探讨，一起学习！