A single iteration of gradient descent can be parallelised across many worker nodes. We simple split the training set across the worker nodes, pass the parameters to each worker, each worker computes gradients for their subset of the training set, and then passes it back to the master to be averaged. With some effort, we can even use model parallelism.
However, stochastic gradient descent is an inherently serial proces. Each update must be performed sequentially. Each iteration, we must perform a broadcast and gather of all parameters. This is bad for performance. Ultimately, number of updates is the limiting factor of deep model training speed.
Why must we perform many updates? With how few updates can we achieve good accuracy?
What factors affect the minimum number of updates requires to reach some accuracy?