标题： FedPAGE：一种用于通信高效的联邦学习的快速局部随机梯度方法 显示英文标题

标题： FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning

摘要： 联邦平均（FedAvg，也称为本地SGD）（McMahan等，2017）是一种经典的联邦学习算法，其中客户端在将更新发送到协调服务器之前运行多个本地SGD步骤。我们提出了一种新的联邦学习算法FedPAGE，通过利用最近的最优PAGE方法（Li等，2021）而不是FedAvg中的普通SGD，进一步减少了通信复杂性。我们证明了对于联邦凸和非凸优化，FedPAGE使用的通信轮次比之前的本地方法少得多。 具体来说，1）在凸设置中，FedPAGE的通信轮数为$O(\frac{N^{3/4}}{S\epsilon})$，相比SCAFFOLD（Karimireddy等，2020）的最佳已知结果$O(\frac{N}{S\epsilon})$提高了一个因子$N^{1/4}$，其中$N$是客户端的总数（在联邦学习中通常非常大），$S$是每轮通信中采样的客户端子集，$\epsilon$是目标误差；2）在非凸设置中，FedPAGE的通信轮数为$O(\frac{\sqrt{N}+S}{S\epsilon^2})$，相比SCAFFOLD（Karimireddy等，2020）的最佳已知结果$O(\frac{N^{2/3}}{S^{2/3}\epsilon^2})$提高了一个因子$N^{1/6}S^{1/3}$，如果采样的客户端$S\leq \sqrt{N}$。 请注意，在两种设置中，每轮通信成本对于FedPAGE和SCAFFOLD来说是相同的。 因此，FedPAGE在联邦凸和非凸优化的通信复杂性方面取得了新的最先进结果。 显示英文摘要

摘要： Federated Averaging (FedAvg, also known as Local-SGD) (McMahan et al., 2017) is a classical federated learning algorithm in which clients run multiple local SGD steps before communicating their update to an orchestrating server. We propose a new federated learning algorithm, FedPAGE, able to further reduce the communication complexity by utilizing the recent optimal PAGE method (Li et al., 2021) instead of plain SGD in FedAvg. We show that FedPAGE uses much fewer communication rounds than previous local methods for both federated convex and nonconvex optimization. Concretely, 1) in the convex setting, the number of communication rounds of FedPAGE is $O(\frac{N^{3/4}}{S\epsilon})$, improving the best-known result $O(\frac{N}{S\epsilon})$ of SCAFFOLD (Karimireddy et al.,2020) by a factor of $N^{1/4}$, where $N$ is the total number of clients (usually is very large in federated learning), $S$ is the sampled subset of clients in each communication round, and $\epsilon$ is the target error; 2) in the nonconvex setting, the number of communication rounds of FedPAGE is $O(\frac{\sqrt{N}+S}{S\epsilon^2})$, improving the best-known result $O(\frac{N^{2/3}}{S^{2/3}\epsilon^2})$ of SCAFFOLD (Karimireddy et al.,2020) by a factor of $N^{1/6}S^{1/3}$, if the sampled clients $S\leq \sqrt{N}$. Note that in both settings, the communication cost for each round is the same for both FedPAGE and SCAFFOLD. As a result, FedPAGE achieves new state-of-the-art results in terms of communication complexity for both federated convex and nonconvex optimization.