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

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 \textbf{\texttt{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 \textbf{\texttt{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 \textbf{\texttt{GT-SVRG}}, a decentralized gradient tracking based implementation of SVRG \cite{SVRG}, another well-known variance-reduction technique.

References in corpus (13)

• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• D${}^2$: Decentralized Training over Decentralized Data
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Barzilai-Borwein Step Size for Stochastic Gradient Descent
• A Simple Practical Accelerated Method for Finite Sums
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• Optimization over time-varying directed graphs with row and column-stochastic matrices

Cited by in corpus (7)

• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• An introduction to decentralized stochastic optimization with gradient tracking
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning