Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets

We study distributed optimization algorithms for minimizing the average of\n\\emph{heterogeneous} functions distributed across several machines with a focus\non communication efficiency. In such settings, naively using the classical\nstochastic gradient descent (SGD) or its variants (e.g., SVRG) with a uniform\nsampling of machines typically yields poor performance. It often leads to the\ndependence of convergence rate on maximum Lipschitz constant of gradients\nacross the devices. In this paper, we propose a novel \\emph{adaptive} sampling\nof machines specially catered to these settings. Our method relies on an\nadaptive estimate of local Lipschitz constants base on the information of past\ngradients. We show that the new way improves the dependence of convergence rate\nfrom maximum Lipschitz constant to \\emph{average} Lipschitz constant across\nmachines, thereby, significantly accelerating the convergence. Our experiments\ndemonstrate that our method indeed speeds up the convergence of the standard\nSVRG algorithm in heterogeneous environments.\n