Preprint
Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
IACAPAP ArXiv (Online)
07/27/2015
DOI: 10.48550/arxiv.1507.07595
Abstract
We study distributed optimization algorithms for minimizing the average of
convex functions. The applications include empirical risk minimization problems
in statistical machine learning where the datasets are large and have to be
stored on different machines. We design a distributed stochastic variance
reduced gradient algorithm that, under certain conditions on the condition
number, simultaneously achieves the optimal parallel runtime, amount of
communication and rounds of communication among all distributed first-order
methods up to constant factors. Our method and its accelerated extension also
outperform existing distributed algorithms in terms of the rounds of
communication as long as the condition number is not too large compared to the
size of data in each machine. We also prove a lower bound for the number of
rounds of communication for a broad class of distributed first-order methods
including the proposed algorithms in this paper. We show that our accelerated
distributed stochastic variance reduced gradient algorithm achieves this lower
bound so that it uses the fewest rounds of communication among all distributed
first-order algorithms.
Details
- Title: Subtitle
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- Creators
- Jason D LeeQihang LinTengyu MaTianbao Yang
- Resource Type
- Preprint
- Publication Details
- IACAPAP ArXiv (Online)
- DOI
- 10.48550/arxiv.1507.07595
- ISSN
- 2717-6991
- Language
- English
- Date posted
- 07/27/2015
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380599402771
Metrics
28 Record Views