Before revision:  } Our stochastic gradient computation complexity is the same as the  single-machine accelerated variance reduction methods, such as Katyusha, and our communication complexity is the same as the accelerated full batch decentralized methods, such as MSDA, and they are both optimal. We also propose the non-accelerated VR based EXTRA and DIGing, and provide explicit complexities, for example, the O(( \kappa_s +n)\log\frac{1}{\epsilon}) stochastic gradient computation complexity and the O((\kappa_b+\kappa_c) \log\frac{1}{\epsilon}) communication complexity for the VR based EXTRA.
After revision:  } Our stochastic gradient computation complexity is the same as the single-machine accelerated variance reduction methods, such as Katyusha, and our communication complexity is the same as those of EXTRA and DIGing, respectively. To further speed up the convergence, we also propose the non-accelerated VR based EXTRA and DIGing, and provide explicit complexities, for example, the O(( \kappa_s +n)\log\frac{1}{\epsilon}) stochastic gradient computation complexity and the O((\kappa_b+\kappa_c) \log\frac{1}{\epsilon}) communication complexity for the VR based EXTRA.