We study stochastic decentralized optimization for the problem of training machine learning models with large-scale distributed data. We extend the famous EXTRA and DIGing methods with accelerated variance reduction (VR), and propose two methods , which require the time of O(( \sqrt{n\kappa_s +n)\log1{\epsilon}) stochastic gradient evaluations and O( \sqrt{\kappa_b\kappa_c \log1{\epsilon}) communication rounds to reach precision \epsilon, where \kappa_s and \kappa_b are the stochastic condition number and batch condition number for strongly convex and smooth problems,  \kappa_c is the condition number of the communication network, and n is the sample size on each distributed node. {\epsilon}). } 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. 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 .
We study stochastic decentralized optimization for the problem of training machine learning models with large-scale distributed data. We extend the widely used EXTRA and DIGing methods with variance reduction (VR), and propose two methods : VR-EXTRA and VR-DIGing. The proposed VR-EXTRA requires the time of O(( \kappa_s +n)\log1{\epsilon}) stochastic gradient evaluations and O( (\kappa_b+\kappa_c) \log1{\epsilon}) communication rounds to reach precision \epsilon, where \kappa_s and \kappa_b are the stochastic condition number and batch condition number for strongly convex and smooth problems, respectively, \kappa_c is the condition number of the communication network, and n is the sample size on each distributed node. The proposed VR-DIGing has a little higher communication cost of O((\kappa_b+\kappa_c^2)\log\frac{1{\epsilon}). } Our stochastic gradient computation complexities are the same as the ones of single-machine VR methods, such as SAG, SAGA, and SVRG, and our communication complexities keep the same as those of EXTRA and DIGing, respectively. To further speed up the convergence, we also propose the accelerated VR-EXTRA and VR-DIGing with both the optimal O(( \sqrt{n\kappa_s +n)\log\frac{1}{\epsilon}) stochastic gradient computation complexity and O(\sqrt{\kappa_b\kappa_c \log\frac{1}{\epsilon}) communication complexity . Our stochastic gradient computation complexity is also the same as the ones of single-machine accelerated VR methods, such as Katyusha, and our communication complexity keeps the same as those of accelerated full batch decentralized methods, such as MSDA .
R
famous
widely used
D
accelerated
R
, which require
: VR-EXTRA and VR-DIGing. The proposed VR-EXTRA requires
R
\sqrt{n\kappa_s
\kappa_s
R
\sqrt{\kappa_b\kappa_c
(\kappa_b+\kappa_c)
A
respectively,
A
The proposed VR-DIGing has a little higher communication cost of O((\kappa_b+\kappa_c^2)\log\frac{1
R
complexity is
complexities are
A
ones of
R
accelerated variance reduction
VR
R
Katyusha, and our communication complexity is
SAG, SAGA, and SVRG, and our communication complexities keep
R
the accelerated full batch decentralized methods, such as MSDA, and they are both optimal. We
those of EXTRA and DIGing, respectively. To further speed up the convergence, we
R
non-accelerated VR based EXTRA and DIGing, and provide explicit complexities, for example, the
accelerated VR-EXTRA and VR-DIGing with both the optimal
R
\kappa_s
\sqrt{n\kappa_s
R
the O((\kappa_b+\kappa_c)
O(\sqrt{\kappa_b\kappa_c
R
for the VR based EXTRA. The two complexities are
. Our stochastic gradient computation complexity is
A
accelerated
R
SAG, SAGA, and SVRG, and the non-accelerated
Katyusha, and our communication complexity keeps the same as those of accelerated
R
EXTRA, respectively
MSDA