FedAsync Asynchronous Federated Optimization

Introduction

联邦学习有三个关键属性:

1. 不频繁的任务激活。对于弱边缘设备，学习任务只在设备空闲、充电、连接非计量网络时执行.
2. 沟通不频繁。边缘设备和远程服务器之间的连接可能经常不可用、缓慢或昂贵(就通信成本或电池电量使用而言)。
3. 非iid训练数据。对于联邦学习，不同设备上的数据是不相交的，因此可能代表来自总体的非相同分布的样本。

存在的问题：

• 联邦学习通常是使用同步方法实现的，由于离散者的存在，同步方法可能会很慢。当处理大量边缘设备时，可能会有大量的掉队者。由于不同设备的可用性和完成时间不同，由于计算能力和电池时间的限制，全局同步是困难的，特别是在联邦学习场景中。

解决方案：

• 异步训练[9,14,15]被广泛应用于传统的分布式随机梯度下降(SGD)算法中，以解决离散者和异构延迟问题[9,14,15]。在本文中，我们利用异步训练的优势，并将其与联邦优化相结合。提出了一种新的异步联邦优化算法。关键思想是:

1. 解决正则化的局部问题以保证收敛性;
2. 然后使用加权平均来更新全局模型，其中混合权值作为过时性的函数自适应设置。

本文贡献：

• 提出了一种新的异步联邦优化算法和原型系统设计。
• 我们证明了该方法对于一类受限的非凸问题的收敛性。
• 我们提出了控制由异步引起的错误的策略。为此，我们引入了一个混合超参数，该参数可以自适应地控制收敛速度和方差减少之间的权衡。
• 我们的经验表明，所提出的算法收敛速度快，并且在实际设置中通常优于同步联邦优化。

Methodology

服务器和工作器异步地进行更新，也就是说，服务器在接收到本地模型时立即更新全局模型。服务器和工作线程之间的通信是非阻塞的。因此，服务器和工作人员可以随时更新模型而不需要同步，这对于设备具有异构条件时是有利的。

• 在服务器端，调度器和更新程序异步并行运行。调度程序周期性地触发训练任务，并控制训练任务的延迟(更新t-T)
• 更新器从worker接收模型并更新全局模型。我们的架构允许在全局模型上使用读写锁的多个更新线程，这提高了吞吐量。
• 更新全局模型时，更大的过时性会导致更大的错误。
• 对于陈旧度较大(t−τ)的局部模型，我们可以减小α来减轻陈旧度带来的误差。
• 如算法1所示，我们可以选择使用函数s(t−τ)来确定α的值。一般来说，当t = τ时，s(t−τ)应为1，当(t−τ)增大时，s(t−τ)单调减小。
  

Convergence analysis

收敛性证明,有心情的时候再看

Experiments

数据集：CIFAR-10和WikiText-2。训练集被划分为n＝100个设备。小批量大小分别为50和20。
基线算法是引入的FedAvg，它实现了同步联邦优化。对于fedag，在每个epoch中，随机选择k = 10个设备启动本地更新。我们还将单线程SGD作为基准。对于FedAsync，我们通过从均匀分布中随机采样陈旧度(t−τ)来模拟异步。

我们用不同的学习率γ、正则化权值ρ、混合超参数α和过时性来测试FedAsync