梯度压缩技术

正如章节引言中提到的，客户端与服务器之间传输的数据量巨大，尤其是客户端发送的梯度信息，常常限制了联邦学习系统的扩展性和效率。梯度压缩技术通过在传输前减少表示每个客户端梯度更新所需的比特数，直接处理这个问题。

其主要思想很简单：客户端不发送本地计算的、通常是全精度且稠密的梯度向量 (vector)（我们将其表示为 $g$ ），而是计算一个压缩版本 $g_{compressed} = C(g)$ ，发送 $g_{compressed}$ ，服务器随后使用一种适合这些压缩更新的聚合策略，可能在通过 $D(g_{compressed})$ 解压缩之后。压缩函数 $C$ 和解压缩函数 $D$ 被设计成使 $g_{compressed}$ 的大小远小于 $g$ 的大小。

两种主要方法主导了这一方面：量化 (quantization)和稀疏化。

梯度量化 (quantization)

量化减少了表示梯度向量 (vector)中每个数值所需的比特数。量化并非对梯度的每个分量都使用标准的32位或64位浮点数，而是将这些值映射到一组更小的离散级别，这些级别可以用更少的比特来表示。

量化类型：

标量量化： 梯度向量的每个分量 $g_i$ 都被独立量化。
向量量化： 成组的梯度分量被一起量化，可能捕获一些结构信息，但通常会增加复杂度。标量量化因其简单性而更常见。

机制：

一种常用方式是随机量化。对于梯度分量 $g_i$ ，我们不传输其精确值，而是可能传输一个随机选择的量化值 $q_i$ ，使其期望值等于原始值，即 $E[q_i] = g_i$ 。这会引入噪声，但平均而言保持过程无偏。

例如，考虑将范围在 $[0, 1]$ 的值 $x$ 量化为0或1。随机量化会以概率 $x$ 输出1，以概率 $1-x$ 输出0。

一种采用量化的知名算法是量化随机梯度下降 (gradient descent)（QSGD）。QSGD通常包含：

将梯度分量缩放到特定范围。
应用随机量化，将每个分量映射到一组预定义、有限的离散值（例如，可用4、8或16比特表示）。
有效编码这些量化值以供传输。

服务器接收这些量化梯度，对其解码，并进行聚合。

权衡： 量化直接减小了载荷大小。例如，从32位浮点数变为8位整数可实现4倍压缩。然而，这会引入量化误差（噪声）。尽管随机方法旨在无偏，但增加的方差会减缓收敛速度或略微降低最终模型精度。客户端执行量化以及服务器端执行解量化/聚合也存在计算成本。

比特数越少，通信开销显著降低，但潜在的量化误差会增加，可能影响模型的收敛和精度。

梯度稀疏化

稀疏化采取了不同的方式。它不是发送所有梯度分量的低精度版本，而是只发送一小部分分量，通常是那些被认为最重要、且以全精度表示的分量。其余分量在该通信轮次中被视为零。

机制：

最常用的技术是Top-k稀疏化：

计算完整的梯度向量 (vector) $g$ 。
识别 $g$ 中绝对值最大的 $k$ 个分量。
创建一个稀疏向量 $g_{sparse}$ ，其中只包含这 $k$ 个值及其原始位置。所有其他分量均设置为零。
传输 $g_{sparse}$ 。由于它是稀疏的，可以通过发送非零分量的（索引，值）对来高效编码。

$k$ 的值是一个超参数 (parameter) (hyperparameter)，通常表示为总参数数量的百分比（例如，发送梯度的前1%或前10%）。

示例： 如果 $g = [0.1, -2.5, 0.8, -0.3, 1.9]$ 且我们使用Top-2稀疏化：最大的幅值是 $|-2.5| = 2.5$ 和 $|1.9| = 1.9$ 。发送的稀疏梯度将表示为 $[0, -2.5, 0, 0, 1.9]$ 。这可以编码为 [(1, -2.5), (4, 1.9)]。

权衡： 稀疏化可以显著减小通信规模，特别是当 $k$ 远小于梯度的总维度时。然而，丢弃较小梯度分量的信息会显著影响收敛。如果不同客户端始终对不同参数有大的梯度，聚合效果可能会变差。效率也取决于梯度的性质；梯度自然稀疏的模型受益更多。连同值一起发送索引会增加开销，因此实际压缩比取决于 $k$ 和编码格式。与量化 (quantization)类似，稀疏化在选择Top- $k$ 值时会增加计算开销。

Top-k梯度稀疏化的处理流程。

组合技术

量化 (quantization)和稀疏化也可以结合使用。例如，可以先选择Top-k梯度，然后在传输前只对这些值进行量化。这提供了一种实现更大压缩的可能途径，但需要仔细调整，因为这两种技术带来的误差和信息损失可能会叠加。

量化和稀疏化都是活跃的研究方向。它们的效率高度依赖于特定的联邦学习配置，包括机器学习 (machine learning)模型、客户端数据分布（异构性）、所用的优化算法以及选择的压缩参数 (parameter)（量化的比特数、稀疏化的 $k$ 值）。下一节将讨论误差补偿技术，这些技术常与压缩结合使用，以减轻对模型训练的不利影响。

这部分内容有帮助吗？

参考文献

QSGD: Communication-Efficient SGD via Gradient Quantization, Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, Milan Vojnovic, 2017 Advances in Neural Information Processing Systems, Vol. 30 (NeurIPS) - 本文介绍了量化SGD（QSGD），这是一种用于通信高效分布式训练的基础性随机量化方法，与梯度量化直接相关。
Sparsified SGD with Memory, Stich, Sebastian U., Cordonnier, Jean-Baptiste, Jaggi, Martin, 2018 Advances in Neural Information Processing Systems, Vol. 31 (NeurIPS) - 这项研究分析了稀疏化SGD，包括Top-k选择，并讨论了减少信息损失的记忆机制，直接针对梯度稀疏化。
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, Lin, Yujun and Han, Song and Mao, Huizi and Wang, Yu and Diao, Wei and Xun, Shang and Tang, Wei and Yang, Myron and Fan, Xiangyu and Gan, Rong, 2018 International Conference on Learning Representations (ICLR) DOI: 10.48550/arXiv.1712.01887 - 本文提出了一种有影响力的方法，结合稀疏化、量化和误差补偿，在分布式训练中显著减少通信量。

梯度压缩技术

两种主要方法主导了这一方面：量化 (quantization)和稀疏化。

梯度量化 (quantization)

量化类型：

标量量化： 梯度向量的每个分量 $g_i$ 都被独立量化。
向量量化： 成组的梯度分量被一起量化，可能捕获一些结构信息，但通常会增加复杂度。标量量化因其简单性而更常见。

机制：

例如，考虑将范围在 $[0, 1]$ 的值 $x$ 量化为0或1。随机量化会以概率 $x$ 输出1，以概率 $1-x$ 输出0。

一种采用量化的知名算法是量化随机梯度下降 (gradient descent)（QSGD）。QSGD通常包含：

将梯度分量缩放到特定范围。
应用随机量化，将每个分量映射到一组预定义、有限的离散值（例如，可用4、8或16比特表示）。
有效编码这些量化值以供传输。

服务器接收这些量化梯度，对其解码，并进行聚合。

比特数越少，通信开销显著降低，但潜在的量化误差会增加，可能影响模型的收敛和精度。

梯度稀疏化

机制：

最常用的技术是Top-k稀疏化：

计算完整的梯度向量 (vector) $g$ 。
识别 $g$ 中绝对值最大的 $k$ 个分量。
创建一个稀疏向量 $g_{sparse}$ ，其中只包含这 $k$ 个值及其原始位置。所有其他分量均设置为零。
传输 $g_{sparse}$ 。由于它是稀疏的，可以通过发送非零分量的（索引，值）对来高效编码。

$k$ 的值是一个超参数 (parameter) (hyperparameter)，通常表示为总参数数量的百分比（例如，发送梯度的前1%或前10%）。

Top-k梯度稀疏化的处理流程。

组合技术

这部分内容有帮助吗？

参考文献

QSGD: Communication-Efficient SGD via Gradient Quantization, Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, Milan Vojnovic, 2017 Advances in Neural Information Processing Systems, Vol. 30 (NeurIPS) - 本文介绍了量化SGD（QSGD），这是一种用于通信高效分布式训练的基础性随机量化方法，与梯度量化直接相关。
Sparsified SGD with Memory, Stich, Sebastian U., Cordonnier, Jean-Baptiste, Jaggi, Martin, 2018 Advances in Neural Information Processing Systems, Vol. 31 (NeurIPS) - 这项研究分析了稀疏化SGD，包括Top-k选择，并讨论了减少信息损失的记忆机制，直接针对梯度稀疏化。
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, Lin, Yujun and Han, Song and Mao, Huizi and Wang, Yu and Diao, Wei and Xun, Shang and Tang, Wei and Yang, Myron and Fan, Xiangyu and Gan, Rong, 2018 International Conference on Learning Representations (ICLR) DOI: 10.48550/arXiv.1712.01887 - 本文提出了一种有影响力的方法，结合稀疏化、量化和误差补偿，在分布式训练中显著减少通信量。