Journal article
Distributed Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement
Journal of machine learning research, Vol.18, pp.1-43
01/01/2017
Abstract
We study the round complexity of minimizing the average of convex functions under a new setting of distributed optimization where each machine can receive two subsets of functions. The first subset is from a random partition and the second subset is randomly sampled with replacement. Under this setting, we define a broad class of distributed algorithms whose local computation can utilize both subsets and design a distributed stochastic variance reduced gradient method belonging to in this class. When the condition number of the problem is small, our method achieves the optimal parallel runtime, amount of communication and rounds of communication among all distributed first-order methods up to constant factors. When the condition number is relatively large, a lower bound is provided for the number of rounds of communication needed by any algorithm in this class. Then, we present an accelerated version of our method whose the rounds of communication matches the lower bound up to logarithmic terms, which establishes that this accelerated algorithm has the lowest round complexity among all algorithms in our class under this new setting.
Details
- Title: Subtitle
- Distributed Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement
- Creators
- Jason D. Lee - Univ Southern Calif, Marshall Sch Business, Los Angeles, CA 90089 USAQihang Lin - Univ Iowa, Tippie Coll Business, Iowa City, IA 52242 USATengyu Ma - Princeton UniversityTianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USA
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.18, pp.1-43
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 43
- Grant note
- IIS-1463988; IIS-1545995 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2017
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984259411202771
Metrics
10 Record Views