Federated learning (FL) is an emerging technique for training machine
learning models using geographically dispersed data collected by local
entities. It includes local computation and synchronization steps. To reduce
the communication overhead and improve the overall efficiency of FL, gradient
sparsification (GS) can be applied, where instead of the full gradient, only a
small subset of important elements of the gradient is communicated. Existing
work on GS uses a fixed degree of gradient sparsity for i.i.d.-distributed data
within a datacenter. In this paper, we consider adaptive degree of sparsity and
non-i.i.d. local datasets. We first present a fairness-aware GS method which
ensures that different clients provide a similar amount of updates. Then, with
the goal of minimizing the overall training time, we propose a novel online
learning formulation and algorithm for automatically determining the
near-optimal communication and computation trade-off that is controlled by the
degree of gradient sparsity. The online learning algorithm uses an estimated
sign of the derivative of the objective function, which gives a regret bound
that is asymptotically equal to the case where exact derivative is available.
Experiments with real datasets confirm the benefits of our proposed approaches,
showing up to $40\%$ improvement in model accuracy for a finite training time.

本文提出了一种公平性感知的梯度稀疏化方法，以及一种自适应梯度稀疏化技术，能够在控制梯度稀疏度的情况下，最小化整体训练时间，实验结果表明，相对于传统方法，通过本文所提方法，能够在有限的训练时间内提升 40% 的模型准确度。