Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking -- Part II: GT-SVRG

Decentralized stochastic optimization has recently benefited from gradient tracking methods citeDSGTPu,DSGTXin providing efficient solutions for large-scale empirical risk minimization problems. In Part I citeGTSAGA of this work, we develop textbftextttGT-SAGA that is based on a decentralized implementation of SAGA citeSAGA using gradient tracking and discuss regimes of practical interest where textbftextttGT-SAGA outperforms existing decentralized approaches in terms of the total number of local gradient computations. In this paper, we describe textbftextttGT-SVRG that develops a decentralized gradient tracking based implementation of SVRG citeSVRG, another well-known variance-reduction technique. We show that the convergence rate of textbftextttGT-SVRG matches that of textbftextttGT-SAGA for smooth and strongly-convex functions and highlight different trade-offs between the two algorithms in various settings.