Variance reduced stochastic diffusion algorithm for large-scale distributed optimisation

This paper focuses on large-scale distributed stochastic optimisation problems, where a collection of nodes cooperatively solves a global objective over an undirected network, and each node has access only to its own local objective function. Specifically, each local objective function is assumed to be the average of a finite set of component functions. To reduce the computational burden of evaluating full gradients, we propose a variance-reduced stochastic diffusion algorithm, termed S-Diffusion, for distributed optimisation. Building on S-Diffusion, we further develop a variance-reduced proximal stochastic diffusion algorithm, termed Prox-S-Diffusion, for large-scale distributed composite optimisation. Under strong convexity and smoothness assumptions on the local objective functions, both S-Diffusion and Prox-S-Diffusion achieve a linear convergence rate in expectation to the optimal solution. Numerical experiments based on logistic regression demonstrate the effectiveness of the proposed algorithms. We further show that S-Diffusion has a wider stability range and better convergence performance than the DSA strategy.