Parallel minibatch gradient descent algorithms

Question

I've implemented a neural network using batch gradient descent. Now I want to try minibatch, largely in order to avoid problems with local minima.

In ESL's chapter on neural networks, the authors make the point that SGD is amenable to parallelization, given that it takes one training example at a time. I suppose that the algorithm would be to calculate the parameter updates for each batch, and then average them into a single update for that epoch.

But reading elsewhere, I see that serial implementations of SGD (or minibatch) are useful because their jumpiness helps them to escape local minima. Intuitively, it seems like parallel SGD (or minibatch) in which the parameters are averaged and updated once per epoch would have the same local minima problems as batch. Is this true?

Then I came across this algorithm, which seems to be a compromise -- basically one's processors take turns updating the parameters, and when they are not updating they continue iterating. I don't imagine that this is possible to implement in high-level languages like R (which I use). There are also other algorithms optimized for MapReduce (rather than simple multicore) settings -- this is beyond the scope of what I'm trying to do.

So my question is:

What are some good parallel algorithms for minibatch gradient descent that both (1) help avoid local minima and (2) can take advantage of multiple cores on a single machine?

Answer 1

I suggest you to read this paper: Large Scale Distributed Deep Networks

As far as I know, this approach is common in industry.

As you know, SGD is an iterative and serial (not parallel) method with updates to the model vector $x$ of the form

$$x_{k+1} = x_{k} - \mathop{\nabla}\limits{f(x_k;z_i)} $$

For SGD every iteration depends on the previous iteration. Most schemes learn local models independently and communicate to update the global model. The algorithm differ in how the update is performed. There are several algorithm, that solve the problem of applying SGD on large data sets.

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

• CYCLADES: Conflict-free Asynchronous Machine Learning

• Parallel Stochastic Gradient Descent with Sound Combiners