Is Stochastic gradient descent and Online gradient descent compatible with Map-Reduce? My initial thoughts to this problem was no, since online and stochastic both use single values at a time. But what if say you have different online servers that act independently for a limited period of time and the collaborate. Or splitting your data set and preforming stochastic gradient descent on the sets of data one already has then combining it? (As far as I am aware stochastic is additive)
 A: There has been a considerable amount of work on parallelized SGD, that has been extended to the Map-Reduce paradigm.
I would suggest looking at publications like Parallelized Stochastic Gradient Descent by Zinkevich et al. or at Optimal Distributed Online Prediction Using Mini-Batches by Dekel et al.
There are many approaches to take in a distributed setting. You can use strict synchronization like the papers above use, you can use async gradient calculation at each worker like the HOGWILD! paper mentioned, or you can use stale synchronous iterations, like the work coming out of Eric Xing's lab at CMU. 
For implementations you can look at the machine learning libraries of Apache Flink, Spark, and other distributed frameworks.
A: I work with Flink and right now I'm beginning to delve in this exact problem because I believe that the way Spark or Flink implement SGD is far from optimal. In particular Flink supports cyclic computation graph while Spark can't and that opens up a lot of possibilities for Flink that are precluded to Spark.
Bar's answer gave you a bit of insight on the problematic but I would like to give you an hint to research it starting from what is the actual state of the art.
Actually many frameworks implement what is known as Asynchronous SGD (the name "Downpour" is not really loved for some reason) or Sandblaster SGD. These allow you to parallelize well but they scale badly with the number of machines because network and disk overhead, together with the limitations of the specific implementations, waste a lot of time.
To my knowledge, one of the most interesting computational models to scale this kind of optimization is the one proposed by Petuum and implemented on their platform.
I've read the white paper and it looks really good.
Another and totally different model is the so called "parameter server" where the parameter set is held by a central node. This works well because even if you have a single point of failure and a computational bottleneck that you can't parallelize, the order of time required to apply a delta and broadcast it back is way less than the computation required by the other nodes. There are many different implementations but it's not really my field. Among them, I know that Microsoft's DMTK has crazy perfomances.
