Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
arXiv:2002.08528
Abstract
We study distributed optimization algorithms for minimizing the average of \emph{heterogeneous} functions distributed across several machines with a focus on communication efficiency. In such settings, naively using the classical stochastic gradient descent (SGD) or its variants (e.g., SVRG) with a uniform sampling of machines typically yields poor performance. It often leads to the dependence of convergence rate on maximum Lipschitz constant of gradients across the devices. In this paper, we propose a novel \emph{adaptive} sampling of machines specially catered to these settings. Our method relies on an adaptive estimate of local Lipschitz constants base on the information of past gradients. We show that the new way improves the dependence of convergence rate from maximum Lipschitz constant to \emph{average} Lipschitz constant across machines, thereby, significantly accelerating the convergence. Our experiments demonstrate that our method indeed speeds up the convergence of the standard SVRG algorithm in heterogeneous environments.
References in corpus (13)
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- Decoupled Weight Decay Regularization
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Optimal Distributed Online Prediction using Mini-Batches
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- AIDE: Fast and Communication Efficient Distributed Optimization
- Not All Samples Are Created Equal: Deep Learning with Importance Sampling
- Variance Reduction in SGD by Distributed Importance Sampling
- Biased Importance Sampling for Deep Neural Network Training
- Online Learning to Sample