# Parallel minibatch gradient descent algorithms

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?

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)}$$