Existing approaches to federated learning suffer from a communication
bottleneck as well as convergence issues due to sparse client participation. In
this paper we introduce a novel algorithm, called FetchSGD, to overcome these
challenges. FetchSGD compresses model updates using a Count Sketch, and then
takes advantage of the mergeability of sketches to combine model updates from
many workers. A key insight in the design of FetchSGD is that, because the
Count Sketch is linear, momentum and error accumulation can both be carried out
within the sketch. This allows the algorithm to move momentum and error
accumulation from clients to the central aggregator, overcoming the challenges
of sparse client participation while still achieving high compression rates and
good convergence. We prove that FetchSGD has favorable convergence guarantees,
and we demonstrate its empirical effectiveness by training two residual
networks and a transformer model.

本文介绍了一种名为 FetchSGD 的算法，该算法通过使用 Count Sketch 压缩模型更新，并利用 Sketch 合并性从众多工作者中组合模型更新来克服联合学习中的通信瓶颈和因稀疏客户参与而导致的收敛问题。我们证明了 FetchSGD 具有良好的收敛性能，并通过训练两个残差网络和一个 Transformer 模型来证明其实证效果。