Linear Speedup of Incremental Aggregated Gradient Methods on Streaming
  Data
Xiaolu Wang Cheng Jin Hoi-To Wai Yuantao Gu
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.