Distributed Stochastic Variance Reduced Gradient Methods

By Jason D. Lee, Tengyu Ma, Qihang Lin. 2015

16 citations recorded by the source corpus.

We study the problem of minimizing the average of $N$ convex functions using $m$ machines with each machine being able to access $n=\frac{N}{m}$ functions. We design a distributed stochastic variance reduced gradient (DSVRG) algorithm which, when the condition number $\kappa$ of the problem is less than $n^{0.9}$ and when the data is assumed to be randomly partitioned onto the machines, simultaneously achieves the optimal parallel runtime, communication and rounds of communication among all first order methods up to constant factors. DSVRG and its extension DPPASVRG also outperform existing distributed algorithms in terms of the rounds of communication as long as $\kappa$ is not too large compared to $n$. For the regime when $n$ is relatively small, we propose a distributed accelerated SVRG algorithm which further reduces the parallel runtime.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “A scheme for replicating data to simulate iid sampling in distributed environment was proposed in [50].”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “In fact, very recent work [12] has cleverly shown that for randomly partitioned data, and for certain reasonable regimes of strong convexity and smoothness, it is actually possible to get better performance than what is indicated by our lower bounds.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A scheme for replicating data to simulate iid sampling in distributed environment was proposed in [95].”
Without-Replacement Sampling for Stochastic Gradient Methods (2016, unknown): “Then for any 1 T ≤ m, if we run SGD for T iterations with step size ηt = 2/λt, we have (for a universal positive constant c) E [ 1 T T∑ t=1 F (wt)− F (w∗) ] ≤ c · ((L+ µB) 2 +G2) log(T ) λT .”