FEDERATED LEARNING: STRATEGIES FOR IMPROVING COMMUNICATION EFFICIENCY

下载链接

0x00 Abstract

在本文中提出了两种减少上传开销的更新策略：structured updates 和 sketched updates。

structured updates：从限制的参数空间使用较少数量的变量来更新。

sketched updates:学习完整模型，利用量化、随机旋转、二次取样等方法进行压缩传输。

KEY WORDS:COMMUNICATION EFFICIENCY,uplink communication cost

0x01 Introduction

现状：

传统的聚合过程，每轮都需要发送完整的模型。
上传速度往往低于下载速度（体现模型压缩的需求）
现有的网络压缩模型能够降低下载的带宽占用，结合加密技术能好糊用户的隐私。

$H_t^i=W_t^i-W_t,for\ i \in S_t.\\ W_{t+1}=W_{t}+\eta _{t}H_t,\ \ H_t:=\frac{1}{n_t}\Sigma_{i \in S_t}H_t^i.$

为了简化，往往选取 $\eta_t=1$ .

本文贡献：

主旨：力求减少上传开销。

structured updates：从限制的参数空间使用较少数量的变量来更新。

sketched updates:学习完整模型，利用量化、随机旋转、二次取样等方法进行压缩传输。

实验：CIFAR data

结果：在损失一点收敛速度的情况下，能够减少两个数量级的开销。

0x02 Structured Update

两种特殊的结构：低秩矩阵&随机掩码

Low Rank

要求每轮更新本地模型 $H_t^i\in\mathbb{R}^{d_1×d_2}$ ,是一个秩不超过 $k$ 的矩阵（ $k$ 是固定的）。为了达到这个要求，用以下方法进行构造：

$H_t^i=A_t^iB_t^i，A_t^i \in \mathbb{R}^{d_1×k}，B_t^i \in \mathbb{R}^{k×d_2}$

在后续计算中， $A_t^i$ 可以随机生成（在传输过程中只需要传输随机数即可），然后去优化矩阵 $B_t^i$ ，这种方法能实现较少 $d_1/k$ 的通信开销。

Random Mask

$H_t^i$ 为预先定义的随机稀疏模式（如，随机掩码），与上面的方法相似，稀疏模式可以由随机种子生成，在传输过程中仅需要传输非零项，与种子即可。

0x03 Sketched Update

基本过程：首先在本地计算整个 $H_t^i$ ，然后在传输给服务器之前进行估值近似、编码等一些压缩过程。服务器会在聚合前解码。

常见压缩：二次抽样、概率量化

Subsampling

每个客户端只传输 $\hat{H}_t^i$ ( $H_t^i$ 的随机子集)
服务器进行二次抽样的平均，获得全局更新 $H_t$ 。这样做的原因是样本更新的均值是一个无偏估计： $\mathbb{E}[\hat{H_t}]=H_t$ 。
与随机掩码模式一样，每轮需要一个独立的随机掩码，该掩码可以作为同步种子存储。

Probabilistic quantization

将每个标量量化成一个比特。

$h=(h_1,...,h_{d_1×d_2})=vec(H_t^i)\\ h_{max}=max_j(h_j),h_{min}=min_j(h_j)\\$

$\begin{aligned} \tilde{h}_j=\left\{ \begin{array}{lcr} h_{max},\ with\ probability\ \frac{h_j-h_{min}}{h_{max}-h_{min}}\\ h_{min},\ with\ probability\ \frac{h_{max}-h_j}{h_{max}-h_{min}} \end{array} \right. \end{aligned}$

很容易证明 $\tilde{h}$ 是 $h$ 的无偏估计。
对于4字节浮点数，能实现32倍的压缩。
可以扩展到 $b-bit$ ，将 $[h_{min},h_{max}]$ 均匀分成 $2^b$ 个间隔。假设 $h_i$ 在 $h'-h''$ 之间，就用 $h',h''$ 代替上面的 $h_{max},h_{min}$

Improving the quantization by structured random rotations

使用上面的方法在某些情况下会产生比较大的误差，引入随机旋转解决问题(乘随机正交矩阵)。

本文构建的随机旋转能够降低 $O(d/logd)$ 的量化误差， $d$ 是 $h$ 的维度。
利用WH矩阵和二进制对角阵，减低解码的困难度至 $O(d)$ 和 $O(dlogd)$

it is computationally prohibitive to generate ( $O(d^3)$ ) and apply ( $O(d^2)$ ) a general rotation matrix.