Summary: Stochastic gradient descent method is popular for large scale optimization but has slow convergence asymptotically due to the inherent variance. To remedy this problem, there have been many explicit variance reduction methods for stochastic descent, such as SVRG [R. Johnson and T. Zhang, “Accelerating stochastic gradient descent using predictive variance reduction”, in: Proceedings of the 26th international conference on neural information processing systems, NIPS 2013. New York, NY: Association for Computing Machinery (ACM). 315–323 (2013; doi:10.5555/2999611.2999647)], SAG [N. Le Roux et al., “A stochastic gradient method with an exponential convergence rate for finite training sets”, in: Proceedings of the 25th international conference on neural information processing systems, NIPS 2012. New York, NY: Association for Computing Machinery (ACM). 2663–2671 (2012; doi:10.5555/2999325.2999432)], SAGA [A. Defazio et al., “A fast incremental gradient method with support for non-strongly convex composite objectives”, in: Proceedings of the 27th international conference on neural information processing systems, NIPS 2014. New York, NY: Association for Computing Machinery (ACM). 1646–1654 (2014; doi:10.5555/2968826.2969010)] and so on. Conjugate gradient method, which has the same computation cost with gradient descent method, is considered. In this paper, in the spirit of SAGA, we propose a stochastic conjugate gradient algorithm which we call SCGA. With the Fletcher and Reeves type choices, we prove a linear convergence rate for smooth and strongly convex functions. We experimentally demonstrate that SCGA converges faster than the popular SGD type algorithms for four machine learning models, which may be convex, nonconvex or nonsmooth. Solving regression problems, SCGA is competitive with CGVR, which is the only one stochastic conjugate gradient algorithm with variance reduction so far, as we know.