下载链接

0x00 Abstract

在本文中提出了两种减少上传开销的更新策略:structured updatessketched updates

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

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

0x01 Introduction

现状:

  • 传统的聚合过程,每轮都需要发送完整的模型。

  • 上传速度往往低于下载速度(体现模型压缩的需求)

  • 现有的网络压缩模型能够降低下载的带宽占用,结合加密技术能好糊用户的隐私。

Hti=WtiWt,for iSt.Wt+1=Wt+ηtHt,  Ht:=1ntΣiStHti.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.

为了简化,往往选取ηt=1\eta_t=1.

本文贡献:

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

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

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

实验:CIFAR data

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

0x02 Structured Update

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

Low Rank

要求每轮更新本地模型HtiRd1×d2H_t^i\in\mathbb{R}^{d_1×d_2},是一个秩不超过kk的矩阵(kk是固定的)。为了达到这个要求,用以下方法进行构造:

Hti=AtiBtiAtiRd1×kBtiRk×d2H_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}

在后续计算中,AtiA_t^i可以随机生成(在传输过程中只需要传输随机数即可),然后去优化矩阵BtiB_t^i,这种方法能实现较少d1/kd_1/k的通信开销。

Random Mask

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

0x03 Sketched Update

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

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

Subsampling

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

Probabilistic quantization

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

h=(h1,...,hd1×d2)=vec(Hti)hmax=maxj(hj),hmin=minj(hj)h=(h_1,...,h_{d_1×d_2})=vec(H_t^i)\\ h_{max}=max_j(h_j),h_{min}=min_j(h_j)\\

h~j={hmax, with probability hjhminhmaxhminhmin, with probability hmaxhjhmaxhmin\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}

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

Improving the quantization by structured random rotations

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

  • 本文构建的随机旋转能够降低O(d/logd)O(d/logd)的量化误差,ddhh的维度。

  • 利用WH矩阵和二进制对角阵,减低解码的困难度至O(d)O(d)O(dlogd)O(dlogd)

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

0x04 Experiments

Note:

  • 随机掩码
  • 二次抽样
  • 无偏估计
  • 随机旋转