Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA

arXiv1909.11774MaRDI QIDQ6325992FDOQ6325992

Authors: Ran Xin, Usman A. Khan, Soummya Kar 

Publication date: 25 September 2019

Abstract: In this paper, we study decentralized empirical risk minimization problems, where the goal is to minimize a finite-sum of smooth and strongly-convex functions available over a network of nodes. In this Part I, we propose extbf{ exttt{GT-SAGA}}, a decentralized stochastic first-order algorithm based on gradient tracking cite{DSGT_Pu,DSGT_Xin} and a variance-reduction technique called SAGA cite{SAGA}. We develop the convergence analysis and the iteration complexity of this algorithm. We further demonstrate various trade-offs and discuss scenarios in which extbf{ exttt{GT-SAGA}} achieves superior performance (in terms of the number of local gradient computations required) with respect to existing decentralized schemes. In Part II cite{GT_SVRG} of this two-part paper, we develop and analyze extbf{ exttt{GT-SVRG}}, a decentralized gradient tracking based implementation of SVRG cite{SVRG}, another well-known variance-reduction technique.

This page was built for publication: Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325992)