Before revision:  The two complexities are also the same as the ones of single-machine  VR methods, such as SAG, SAGA, and SVRG, and the non-accelerated full batch decentralized methods, such as EXTRA, respectively .
After revision:  The two complexities are also the same as the ones of single-machine accelerated VR methods, such as SAG, SAGA, and SVRG, and the non-accelerated full batch decentralized methods, such as EXTRA, respectively .