This paper considers a type of incremental aggregated gradient (IAG) method
for large-scale distributed optimization. The IAG method is well suited for the
parameter server architecture as the latter can easily aggregate potentially
staled gradients contributed by workers. Although the convergence of IAG in the
case of deterministic gradient is well known, there are only a few results for
the case of its stochastic variant based on streaming data. Considering
strongly convex optimization, this paper shows that the streaming IAG method
achieves linear speedup when the workers are updating frequently enough, even
if the data sample distribution across workers are heterogeneous. We show that
the expected squared distance to optimal solution decays at O((1+T)/(nt)),
where $n$ is the number of workers, t is the iteration number, and T/n is the
update frequency of workers. Our analysis involves careful treatments of the
conditional expectations with staled gradients and a recursive system with both
delayed and noise terms, which are new to the analysis of IAG-type algorithms.
Numerical results are presented to verify our findings.

本论文研究了一种用于大规模分布式优化的增量聚合梯度（IAG）方法，证明了基于流式数据的随机变体的 IAG 方法在强凸优化情况下实现了线性加速，并且即使在数据样本在工作者之间分布不均匀的情况下，该方法仍可以保证达到最优解的期望平方距离以 O ((1+T)/(nt)) 的速率衰减。

流式数据上增量聚合梯度方法的线性加速

Linear Speedup of Incremental Aggregated Gradient Methods on Streaming  Data

Large-scale distributed optimization is of great importance in various
applications. For data-parallel based distributed learning, the inter-node
gradient communication often becomes the performance bottleneck. In this paper,
we propose the error compensated quantized stochastic gradient descent
algorithm to improve the training efficiency. Local gradients are quantized to
reduce the communication overhead, and accumulated quantization error is
utilized to speed up the convergence. Furthermore, we present theoretical
analysis on the convergence behaviour, and demonstrate its advantage over
competitors. Extensive experiments indicate that our algorithm can compress
gradients by a factor of up to two magnitudes without performance degradation.

本文提出了误差补偿量化随机梯度下降算法以优化数据分布式学习中的性能瓶颈，并对其收敛性行为进行了理论分析，同时通过实验证明了该算法在梯度压缩方面具有较大优势。