  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.

Optimization and Control