Linear Speedup of Incremental Aggregated Gradient Methods on Streaming Data
This provides incremental theoretical guarantees for distributed optimization methods in parameter server architectures, addressing a gap in stochastic gradient analysis.
The paper tackles the problem of analyzing the convergence of a stochastic incremental aggregated gradient method on streaming data in distributed optimization, showing that it achieves linear speedup with heterogeneous data across workers, with the expected squared distance to the optimal solution decaying at O((1+T)/(nt)).
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.