note_Communication-Efficient Federated Learning for Heterogeneous Edge Devices Based on Adaptive Gra

Communication-Efficient Federated Learning for Heterogeneous Edge Devices Based on Adaptive
Gradient Quantization
Heting Liu, Fang He and Guohong Cao
arXiv
2022

一、动机和贡献

动机：解决FL通信问题的一种重要的方法是 “梯度量化”，但是现在的量化存在以下问题：1）“低精度”量化可以减少数据传输，却引入大的量化误差导致需要更多轮数去训练模型；“高精度”量化量化误差小，却需要传输较多的数据；2）现存量化方式大多基于固定且预设的量化精度，但是一方面由于最优量化精度随时间的推移而不同，另一方面不同client有着不同的通信资源，因此这种静态决定量化精度是不合理的。

贡献：本文通过动态对不同client分配不同的量化精度，旨在尽量减少FL训练过程中的 wall-clock training time，主要包括如下两方面的设计：

• 不同训练轮数有着不同的量化精度：根据量化过程中 “梯度范数gradient norm” 的不同，在训练刚开始时使用大精度量化，在训练后期使用小精度量化 ；
• 不同通信能力client有着不同量化精度：根据client的通信能力，快client赋予大精度量化，慢client赋予小精度量化。

二、算法

2.1 随机均匀量化（QSGD）

假设 $s\in \mathbb{N}$表示量化精度，$\mathbf{v}=[v_1,\cdots ,v_d]\in {\mathbb{R}}^d,\mathbf{v}\ne 0$表示$d$维梯度向量，那么 $v_j$ 可以由量化函数 $Q_s(\cdot )$ 定义为：
$$Q_s(v_j)=||\mathbf{v}|{|}_2\cdot sign(v_j)\cdot {\zeta }_j(\mathbf{v},s),$$其中 ${\zeta }_j(\mathbf{v},s)$ 表示随机变量，定义为：
ζ j ( v , s ) = { l / s , w i t h   p r o b a b i l i t y   ( 1 − ∣ v j ∣ ∣ ∣ v ∣ ∣ 2 s + l ) ( l + 1 ) / s , o t h e r w i s e . \zeta_j(\mathbf{v},s)=\left\{

$$\begin{array}{cc}l/s,&with~probability~(1-\frac{|v_j|}{||\mathbf{v}||_2}s+l)\\(l+1)/s,&otherwise.\end{array}$$ \right. ζj​(v,s)={l/s,(l+1)/s,​with probability (1−∣∣v∣∣2​∣vj​∣​s+l)otherwise.​其中，$0\le l<s$ 是一个整数，使得 $\frac{|v_j|}{||\mathbf{v}|{|}_2}\in [l/s,(l+1)/s]$。特别的，当 $\mathbf{v}=0$，可以有 $Q_s(\mathbf{v})=0$。

QSGD可以解释为：将 $[0,\Vert \mathbf{v}{\Vert }_2]$ 之间 “均匀” 划分为 $s-1$(包括一个符号位) 个桶，因此桶的端点可以表示为 $0={\tau }_1<{\tau }_2<\cdots <{\tau }_s=||\mathbf{v}|{|}_2$。因为 $|v_j|\in [0,||\mathbf{v}|{|}_2]$，因此每个 $|v_j|$ 必定属于某个桶 $[{\tau }_i,{\tau }_{i+1})$。最后，根据概率（${\zeta }_j(\mathbf{v},s)$）决定 $Q_s(v_j)$ 取左边界 ${\tau }_i$ 还是有边界 ${\tau }_{i+1}$。

注：这里 $s$ 有两层含义，表达量化后梯度所需要的比特数或者真值，需要注意区分。

2.2 Overview of AdaGQ

上图展示了 AdaGQ 的基本流程，其中黑色加粗字体表示的是这篇文章的创新之处，具体表现为如下两方面：

1. adaptive：根据 loss decrease rate 和 gradient norm 在不同训练轮数给出不同的量化精度；
2. heterogeneous：根据 通信时间 的差异，给不同client不同量化精度以对齐通信时间。

注：与之前QSGD中 $s$ 的两层含义不同，在后续写作中，$s$ 表示不带符号位的量化后梯度的真值，$b=\lfloor {\log }_2(s)+1\rfloor$ 表示相应的比特数。

2.3 Adaptive Quantization

定义 loss decrease rate $R_k$ 为：
$$R_k=(L_{k-1}-L_k)/T_{k-1,k},$$其中，$L_k$ 表示 $k$ 轮时所有客户端的平均损失；$T_{k-1,k}$ 表示 $k-1$ 轮结束到 $k$ 轮结束所需的时间（这里应该也是平均时间，因为所有client的执行时间都将被对齐）。

假设 $R_k^{\ast }$ 表示$k$ 轮时由最佳量化精度 $s_k^{\ast }$ 得到的最佳 loss decrease rate，那么定义函数：（$L$ 和 $T$ 都是关于 $s$ 的函数，因此 $R$ 也是关于 $s$ 的函数）
$$f(s_k)=R_k^{\ast }-R_k.$$因此，量化精度 $s$ 可以以如下方式更新：
$$s_{k+1}=s_k-\lambda \nabla f(s_k),$$其中，$\lambda$ 表示步长。但是遗憾的是，由于函数 $f(s_k)$ 关于自变量 $s_k$ 的具体表达形式不清楚，所以直接求导数 $\nabla f(s_k)$ 是不可行的。因此这篇文章利用和 “导数定义” 相似的思想解决，即：选取一个靠近 $s_k$ 的量化精度 $s_k^{\prime }$，并得到相应的 $R_k^{\prime }$，这样就可以得到导数 $\nabla f(s_k)$ 的符号为：
$$sign(\nabla f(s_k))=sign(\frac{R_k^{\prime }-R_k}{s_k-s_k^{\prime }})$$ 这里如何得到 $R_k^{\prime }$ 将在 “Implementation of AdaGQ“ 小节中给出。因此，更新规则变为：
{ s ^ k + 1 = s k − λ 1 , i f s i g n ( ∇ f ( s k ) ) = 1 s ^ k + 1 = s k + λ 2 , i f s i g n ( ∇ f ( s k ) ) = − 1. \left\{

$$\begin{matrix}&\hat{s}_{k+1}=s_k-\lambda_1,&if&sign(\nabla f(s_k))=1\\&\hat{s}_{k+1}=s_k+\lambda_2,&if&sign(\nabla f(s_k))=-1.\end{matrix}$$ \right. {​s^k+1​=sk​−λ1​,s^k+1​=sk​+λ2​,​ifif​sign(∇f(sk​))=1sign(∇f(sk​))=−1.​其中，${\lambda }_1=\frac{s_k}{2},{\lambda }_2=2\times s_k$。
注：梯度其实最重要的就是表示更新的方向（即它的符号），至于其绝对值大小可以由”步长“决定，因此这里只考虑梯度的符号是合理的。

最后，根据 ”梯度范数“ 对 ${\hat{s}}_{k+1}$ 进行校准：
$$s_{k+1}={\hat{s}}_{k+1}+{\lambda }_{\mathbf{g}}({\log }_2||{\mathbf{g}}_k||-{\log }_2||{\mathbf{g}}_{k-1}||)$$其中，${\lambda }_{\mathbf{g}}$ 表示相应的系数。

2.4 Heterogeneous Quantization

根据client ”历史运行时间“ 确定相应的量化精度，定义为：
$$\mathbb{E}(t_{i,k+1}^r)=\mathbb{E}(t_{i,k+1}^{cp})+\mathbb{E}(t_{i,k+1}^{cm})\approx \mathbb{E}(t_{i,k+1}^{cp})+b_{i,k+1}\times \mathbb{E}(\frac{P}{r_{i.k+1}^{trans}}),$$其中，$t_{i,k+1}^{cp}$ 表示client执行 SGD和量化梯度的时间；$t_{i,k+1}^{cm}$ 表示上传量化后梯度到sever的时间；$P$ 是一个常数表示梯度总数；$r_{i.k+1}^{trans}$ 表示client $i$ 在 $k+1$ 轮时的数据传输率。

因此，对齐通信时间可以描述为 $\mathbb{E}(t_{1,k+1}^r)=\mathbb{E}(t_{2,k+1}^r)=\cdots =\mathbb{E}(t_{n,k+1}^r)$。那么对于client $i$ 和 $j$，其量化精度的关系可以表示为：
$$b_{j,k+1}=\frac{1}{\mathbb{E}(\frac{P}{r_{j,k+1}^{trans}})}(\mathbb{E}(t_{i,k+1}^{cp})-\mathbb{E}(t_{j,k+1}^{cp})+b_{i,k+1}\times \mathbb{E}(\frac{P}{r_{i,k+1}^{trans}}))$$这里需要定义两个变量：

• $\begin{array}{r}\mathbb{E}(t_{i,k+1}^{cp})=\frac{1}{k}\sum _{k^{\prime }=1}^k{t}_{i,k^{\prime }}^{cp}\end{array}$，根据历史时间的平均得到；
• $\mathbb{E}(\frac{P}{r_{i,k+1}^{t\mathbf{r}a\mathbf{n}s}})\approx \frac{P}{r_{i,k}^{t\mathbf{r}a\mathbf{n}s}}=t_{i,k}^{c\mathbf{m}}/b_{i,k}$，认为传出率在小时间范围内的变化是不明显的。

因此，如果给定 client $i$ 的量化精度，client $j$ 的量化精度可以表示为：
b j , k + 1 = b j , k t j , k c m ( 1 k ∑ k ′ = 1 k t i , k ′ c p − 1 k ∑ k ′ = 1 k − 1 t j , k ′ c p + b i , k + 1 × t i , k c m b i , k ) , ∀ j ∈ { 1 , ⋯   , n } , j ≠ i .

$$\begin{aligned}b_{j,k+1}=\frac{b_{j,k}}{t_{j,k}^{cm}}(\frac1k\sum_{k^{\prime}=1}^{k}t_{i,k^{\prime}}^{cp}-\frac1k\sum_{k^{\prime}=1}^{k-1}t_{j,k^{\prime}}^{cp}+b_{i,k+1}\times\frac{t_{i,k}^{cm}}{b_{i,k}}),\forall j\in\{1,\cdots,n\},j\neq i.\end{aligned}$$ bj,k+1​=tj,kcm​bj,k​​(k1​k′=1∑k​ti,k′cp​−k1​k′=1∑k−1​tj,k′cp​+bi,k+1​×bi,k​ti,kcm​​),∀j∈{1,⋯,n},j=i.​

2.5 Implementation of AdaGQ

上图表示 AdaGQ 在 $k+1$ 轮时的时间线图。其中，$t_{k+1}^{down}$ 表示sever发送同时client接收模型所需要的时间；$t_{k+1}^{sever}$ sever执行模型聚合的时间。

关于如何得到 $R_k^{\prime }$，分为如下两个步骤：

1. 这篇文章定义 $s_k=\frac{1}{n}{\sum }_{i=1}^n{s}_{i,k}$，且 $s_k^{\prime }=\lfloor s_k/2\rfloor$（即比特数 $b_k^{\prime }=b_k-1$）。
2. 同时sever端定义$k-1$ 到 $k$ 轮之间的执行时间 T k − 1 , k = m a x { t i , k c p + t i , k c m + t i , k d o w n } + t k s e r v e r . T_{k-1,k}=max\{t_{i,k}^{cp}+t_{i,k}^{cm}+t_{i,k}^{down}\}+t_{k}^{server}. Tk−1,k​=max{ti,kcp​+ti,kcm​+ti,kdown​}+tkserver​.可以容易知道，$T_{k-1,k}^{\prime }$ 和 $T_{k-1,k}$ 的主要差异是关于 传输时间$t_{i,k}^{\prime cm}$ 和 $t_{i,k}^{\prime cm}$，而传输时间的差异和相应的比特数成比例关系的（即 $b_{i,k}^{\prime }$ 和 $b_{i,k}$），因此可以得到 T k − 1 , k ′ = m a x { t i , k c p + ⌊ log ⁡ 2 ( s i , k ′ ) ⌋ + 1 ⌊ log ⁡ 2 ( s i , k ) ⌋ + 1 t i , k c m + t i , k d o w n } + t k s e r v e r . T_{k-1,k}^{\prime}=max\{t_{i,k}^{cp}+\frac{\lfloor\log_{2}(s_{i,k}^{\prime})\rfloor+1}{\lfloor\log_{2}(s_{i,k})\rfloor+1}t_{i,k}^{cm}+t_{i,k}^{down}\}+t_{k}^{server}. Tk−1,k′​=max{ti,kcp​+⌊log2​(si,k​)⌋+1⌊log2​(si,k′​)⌋+1​ti,kcm​+ti,kdown​}+tkserver​.
   这样就可以得到相应的 $R_k^{\prime }$。

关于如何根据client通信异质得到相应的量化精度。这篇文章中只是说明了：如果得到 client $i$ 的量化精度就可以得出 client $j$ 的量化精度。那么第一个client 的量化精度如何得出呢？原文中没有说明，我的理解是 ”可以给速度中等的client赋予平均精度，然后依次计算其他client的量化精度“。

AdaGQ 伪代码如下：

三、讨论

本文主要关注的是FL中，尽量减少总训练时间的问题（包括减少每轮执行时间 和 总执行轮数）。同时为了兼顾 模型准确性，根据量化过程中使用范数的特点，在训练开始时尽量使用大精度，在训练后期使用小精度。

主要特点是：

• 提出对不同训练时期使用不同的量化精度
• 量化了各个client通信能力，即使用时间来衡量

不足之处：

• 没有考虑对不同量化精度的模型进行个性化聚合，只是直接使用了FedAvg中根据数据量的大小聚合
• 只考虑 client 之间通信能力的差异，对于 ”算力、存储等“差异没有考虑
• 本文出现的时间线图感觉并行能力不强，是否具有改善的可能