Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks
This work addresses faster training in decentralized learning systems, offering a significant improvement over prior methods, though it is incremental as it builds on existing variance reduction techniques.
The paper tackles the problem of slow convergence in decentralized stochastic proximal gradient methods due to stochastic gradient variance by proposing DPSVRG, a novel algorithm that uses variance reduction to achieve an O(1/T) convergence rate for convex objectives with non-smooth regularization, compared to the O(1/√T) rate of existing methods.
In decentralized learning, a network of nodes cooperate to minimize an overall objective function that is usually the finite-sum of their local objectives, and incorporates a non-smooth regularization term for the better generalization ability. Decentralized stochastic proximal gradient (DSPG) method is commonly used to train this type of learning models, while the convergence rate is retarded by the variance of stochastic gradients. In this paper, we propose a novel algorithm, namely DPSVRG, to accelerate the decentralized training by leveraging the variance reduction technique. The basic idea is to introduce an estimator in each node, which tracks the local full gradient periodically, to correct the stochastic gradient at each iteration. By transforming our decentralized algorithm into a centralized inexact proximal gradient algorithm with variance reduction, and controlling the bounds of error sequences, we prove that DPSVRG converges at the rate of $O(1/T)$ for general convex objectives plus a non-smooth term with $T$ as the number of iterations, while DSPG converges at the rate $O(\frac{1}{\sqrt{T}})$. Our experiments on different applications, network topologies and learning models demonstrate that DPSVRG converges much faster than DSPG, and the loss function of DPSVRG decreases smoothly along with the training epochs.