Federated learning (FL) enables multiple clients to collaboratively train a
shared model without disclosing their local datasets. This is achieved by
exchanging local model updates with the help of a parameter server (PS).
However, due to the increasing size of the trained models, the communication
load due to the iterative exchanges between the clients and the PS often
becomes a bottleneck in the performance. Sparse communication is often employed
to reduce the communication load, where only a small subset of the model
updates are communicated from the clients to the PS. In this paper, we
introduce a novel time-correlated sparsification (TCS) scheme, which builds
upon the notion that sparse communication framework can be considered as
identifying the most significant elements of the underlying model. Hence, TCS
seeks a certain correlation between the sparse representations used at
consecutive iterations in FL, so that the overhead due to encoding and
transmission of the sparse representation can be significantly reduced without
compromising the test accuracy. Through extensive simulations on the CIFAR-10
dataset, we show that TCS can achieve centralized training accuracy with 100
times sparsification, and up to 2000 times reduction in the communication load
when employed together with quantization.

本文介绍了一种基于稀疏通信框架的时间相关稀疏化（TCS）方案，通过寻找联邦学习中连续迭代中使用的稀疏表示之间的相关性，以显著减少编码和传输的开销，以提高测试准确性，并演示了在 CIFAR-10 数据集上使用量化加时间相关稀疏化方法时，可实现 100 倍稀疏化的集中式训练准确性并减少高达 2000 倍的通信负载。

通信高效的联邦学习时间相关稀疏化

Time-Correlated Sparsification for Communication-Efficient Federated  Learning

With the rapid growth of data, distributed stochastic gradient descent~(DSGD)
has been widely used for solving large-scale machine learning problems. Due to
the latency and limited bandwidth of network, communication has become the
bottleneck of DSGD when we need to train large scale models, like deep neural
networks. Communication compression with sparsified gradient, abbreviated as
\emph{sparse communication}, has been widely used for reducing communication
cost in DSGD. Recently, there has appeared one method, called deep gradient
compression~(DGC), to combine memory gradient and momentum SGD for sparse
communication. DGC has achieved promising performance in practise. However, the
theory about the convergence of DGC is lack. In this paper, we propose a novel
method, called \emph{\underline{g}}lobal \emph{\underline{m}}omentum
\emph{\underline{c}}ompression~(GMC), for sparse communication in DSGD. GMC
also combines memory gradient and momentum SGD. But different from DGC which
adopts local momentum, GMC adopts global momentum. We theoretically prove the
convergence rate of GMC for both convex and non-convex problems. To the best of
our knowledge, this is the first work that proves the convergence of
distributed momentum SGD~(DMSGD) with sparse communication and memory gradient.
Empirical results show that, compared with the DMSGD counterpart without sparse
communication, GMC can reduce the communication cost by approximately 100 fold
without loss of generalization accuracy. GMC can also achieve
comparable~(sometimes better) performance compared with DGC, with extra
theoretical guarantee.

提出了一种新的名为全局动量压缩的方法，其利用稀疏通信和记忆梯度与动量随机梯度下降相结合，能够在分布式机器学习任务中显著减少通信成本，同时证明了该方法在凸问题和非凸问题中的收敛速率。

分布式 SGD 中的全局动量压缩

Global Momentum Compression for Sparse Communication in Distributed SGD

Recently, the decentralized optimization problem is attracting growing
attention. Most existing methods are deterministic with high per-iteration cost
and have a convergence rate quadratically depending on the problem condition
number. Besides, the dense communication is necessary to ensure the convergence
even if the dataset is sparse. In this paper, we generalize the decentralized
optimization problem to a monotone operator root finding problem, and propose a
stochastic algorithm named DSBA that (i) converges geometrically with a rate
linearly depending on the problem condition number, and (ii) can be implemented
using sparse communication only. Additionally, DSBA handles learning problems
like AUC-maximization which cannot be tackled efficiently in the decentralized
setting. Experiments on convex minimization and AUC-maximization validate the
efficiency of our method.

本研究提出了一种名为 DSBA 的随机算法，通过将分散的优化问题推广为单调算子求根问题来解决这一问题，具有线性收敛速度和只需稀疏通讯的优点，同时还能有效地处理像 AUC 最大化这样的学习问题。