论文笔记--FEDERATED LEARNING: STRATEGIES FOR IMPROVING COMMUNICATION EFFICIENCY

1. 文章简介

• 标题：FEDERATED LEARNING: STRATEGIES FOR IMPROVING COMMUNICATION EFFICIENCY
• 作者：Jakub Konecny, H. Brendan McMahan, Felix X. Yu, Ananda Theertha Suresh, Dave Bacon
• 日期：2016
• 期刊：arxiv

2. 文章概括

  文章给出了一种联邦学习(federated learning, FL)的新的方法，可以提升多终端之间的交流效率，从而支持多台设备在不稳定网络下的快速传输。

3 文章重点技术

3.1 联邦学习(federated learning, FL)

  先简要叙述下联邦学习的概念：一个共享的全局模型被部署于中央服务器，然后各个客户端通过本地数据进行训练，并将更新后的模型传输回中央服务器。假设FL的目的是学习一个参数为$W\in {\mathbb{R}}^{d_1\times d_2}$的模型，则联邦学习的第$t\ge 0$轮按如下几个步骤执行：

1. 随机选择$n_t$个可用的客户端集合$S_t$，在这些客户端上从中央服务器下载当前的模型$W$
2. 上述选定的客户端用各自的本地数据更新模型，得到更新后的参数分别为$W_t^1,\dots ,W_t^{n_t}$，从而各自的更新量为$H_t^i:=W_t^i-W_t,i=1,\dots ,n_t$，
3. 上述选定的客户端将更新量$H_t^1,\dots ,H_t^{n_t}$分别发送到中央服务器
4. 服务器将所有更新的模型进行聚合（通常采用均值）: $H_t:=\frac{1}{n_t}{\sum }_{i\in S_t}{H}_t^i$，并更新全局模型：$W_{t+1}=W_t+{\eta }_t{H}_t$。
   其中，${\eta }_t$表示每一轮的学习率，简单起见文章采用${\eta }_t=1$。
     上述步骤中，第3步耗时较长，尤其是模型很大或者网络不稳定的时候。文章提出了两种方法来减少第3步的耗时：Structured updates和Sketched updates。

3.2 Structured updates

  文章提出的第一种效率提升方式为结构更新，即限制更新的$H_t^i$为某种预定义的结构。文章考虑了两种预定义的结构

• low rank：限制每一轮更新的参数矩阵$H_t^i\in {\mathbb{R}}^{d_1,\dots ,d_2}$的秩最多为某个固定数值$k$。为此，我们可以将$H_t^i$表示为两个矩阵的乘积：$H_t^i=A_t^i{B}_t^i$，其中$A_t^i\in {\mathbb{R}}^{d_1,\dots ,k},B_t^i\in {\mathbb{R}}^{k,\dots ,d_2}$，则由$\text{rank}(AB)\le \text{rank}(A)$可以知道$H_t^i\le k$。我们初始化一个随机的$A_t^i$，然后训练的时候仅更新$B_t^i$的参数。则模型上传的时候我们只需上传$A_t^i$的随机种子和$B_t^i$的参数即可。故我们将效率从$d_1\times d_2$提升为$k\times d_2$，提升了$d_1/k$倍。
• random rank：限制每一轮更新的参数矩阵$H_t^i\in {\mathbb{R}}^{d_1,\dots ,d_2}$为一个稀疏矩阵，满足某种与定义的稀疏模式（只需随机选出non-zero的索引即可），更新的时候我们只更新non-zero的参数。上传模型的时候只需上传稀疏化的随机种子和非零元素的更新值即可。

3.3 Sketched Update

  文章提出的第二种效率提升方法为sketched update，核心思想为在各个客户端训练完整的参数更新，然后将更新的参数进行压缩上传，再在中央服务器上解压然后更新全局模型的参数。文章实验了几种不同的压缩方法：

• subsampling：各个客户端每次更新完模型之后从$H_t^i$中随机采样一小部分值${\hat{H}}_t^i$发送到中央服务器，然后取各个客户端的平均更新值作为全局的更新值。当每个客户端每一轮的随机mask独立时，我们有 $\mathbb{E}[{\hat{H}}^t]=H_t$。
• probabilistic quantiazation：首先介绍one-bit的情况。令$h=(h_1,\dots ,h_{d_1\times d_2})$为$H_t^i$的平铺向量，取$h_{max}={\max }_j(h_j)$, $h_{min}={\min }_j(h_j)$，则可以将$h$压缩为：$${\overline{h}}_j=\{\begin{array}{l}{h}_{max},\text{with probability}\frac{h_j-h_{min}}{h_{max}-h_{min}}\\ h_{min},\text{with probability}\frac{h_{max}-h_j}{h_{max}-h_{min}}\end{array}$$，则可以得到$\mathbb{E}[\overline{h}]=h_{max}\frac{h-h_{min}}{h_{max}-h_{min}}+h_{min}\frac{h_{max}-h}{h_{max}-h_{min}}=h$，从而$\overline{h}$为$h$的无偏估计。上述为one-bit的情况，我们可以增加bit数，将$[h_{min},h_{max}]$划分为$2^b$个区间，然后按照上述定义将每个子区间内的$h_j$进行压缩。发送的时候我们只需要发送区间数和每个子区间端点的个数即可，对应的发送量为$2^b$。
• Quantilization by structured random rotations：上述方法当不同维度的数值比较相近的时候效果较好。比如大部分的值为0，但$max=1,min=-1$，则上述压缩方法有明显的误差。为此，我们可以先对$h$应用一个旋转（乘一个随机正交矩阵），则上述误差可以得到有效控制（有其它研究可以支撑）。解码阶段，需要首先将压缩后的参数乘正交矩阵的逆阵再进行聚合、更新。

4. 文章亮点

  文章提出了两类联邦学习加速的算法：基于预定义参数和基于参数压缩的方法。数值实验表明我们的方法可以在精度损失很少的情况下更快地发送参数。

5. 原文传送门

FEDERATED LEARNING: STRATEGIES FOR IMPROVING COMMUNICATION EFFICIENCY