Parallel gradient descent problem I'm new to ML so please go gentle on me in case I was missing something obvious.
I read that GD on parallel machines can be done by splitting points and then averaging the results. However, consider this example:
Applying GD on: (2,1),(3,2),(4,3) gives
theta0 = -0.997784, theta1 = 0.999308

Applying GD on: (4,5),(5,6),(6,7) gives
theta0 = 0.944353, theta1 = 1.010848

However, applying an average gives
theta0 ~ 0 , theta1 ~ 1

But when GD is applied on the whole data-set I get
theta0 = -2.399684, theta1 = 1.599928

Any ideas on what I'm missing here?
 A: "Averaging results" won't work on small samples in general.
Typically MLEs are asymptotically normally distributed, so in very large samples, each estimate based on independent subsets of equal size will be approximately normal with the same mean and variance -- and then you might reasonably average them.
A warning: This sort of scheme must be done with care.
Consider a biased estimator (outside a few nice cases MLEs are typically biased, but consistent).
If you have a large sample of size $N$ (say), the bias might be $O(1/N)$ (as an example consider the MLE for the variance of a normally distributed sample). But if you split your data up into $k=N/m$ samples of size $m$, your bias in each would then be $O(1/m)$ and this will not reduce when you average $k$ of them - the bias will remain the same. 
So as your sample size grows, you can't just throw more and more processors at the calculation (i.e. holding $m$ constant but increasing $k$) and hope that everything is fine ... eventually the bias will dominate the mean square error and there'll no longer be much value in obtaining more data. You might put up with splitting in 4 and tolerating 4 times the bias and maybe in some situations, splitting into ten pieces and having 10 times the bias ... but would you be willing to split into a thousand pieces? Often, probably not.
In MSE terms if the squared bias is small compared to the variance, such a split-and-average scheme will be useful, but only up to a point; some degree of assessment of the value  of continuing to split might be made by considering the effect of changing the value of $m$ one where the estimate tends to be.
