摘要

提出了一种FetchSGD算法来克服通信瓶颈，使用 Count Sketch 技术压缩模型更新，并且利用sketches的可并堆性的优点来合并模型更新。由于 Count Sketch 是线性的，动量和误差的累积计算可以从客户端迁移至*聚合器，克服了稀疏客户端参与的挑战，同时保持了高压缩率和良好的收敛性。

Count Sketch 算法：基本原理是数组每个单元维持一个计数器，当数据流的元素哈希索引到数组的某个位置，此位置计算器加一。查询某个元素的出现频率只需哈希索引到对应计数器即可。很明显，由于不同元素可能索引到同一个位置，这种方法得到的计数值一般是偏大的。
hash 函数：即散列函数，或叫哈希函数。它可以将不定长的输入，通过散列算法转换成一个定长的输出，这个输出就是hash值（散列值）。需要注意的是，不同的输入通过散列函数，也可能会得到同一个散列值。同样的对象，必须生产同样的hashCode，而equals就是用来比较对象是否相同，因此，这两个函数方法是强相关的。