Distributed algorithm for non-convex stochastic optimization with variance reduction

This paper focuses on the distributed algorithm design for general smooth non-convex finite-sum optimization, which has wide applications in signal processing and machine learning communities. In distributed setting, large number of samples are allocated to multiple agents in the network. Each agent computes local stochastic gradient and communicates with its neighbors to seek for the global optimum. In this paper, we develop a modified variance reduction scheme to deal with the variance by stochastic gradients. Combining gradient tracking and variance reduction schemes, this paper proposes a distributed iterative algorithm, GT-VR, to solve large-scale non-convex finite-sum optimization over multi-agent networks. A complete and rigorous proof shows that the GT-VR algorithm converges to first-order stationary points with $O(\frac{1}{k})$ convergence rate. In addition, we provide the complexity analysis of the proposed algorithm. Compared with some existing distributed algorithms, the proposed algorithm has lower iteration and communication complexity. Experimental results of state-of-the-art algorithms and GT-VR verify the efficiency of the proposed algorithm by making comparison.