5 ms·

I don't quite understand the gradient descent section. How do you parallelize stochastic gradient descent? Each iteration changes theta, so any parallel computa

by rm999 14y ago

I don't quite understand the gradient descent section. How do you parallelize stochastic gradient descent? Each iteration changes theta, so any parallel computations will be computing the wrong gradient. His citation for that section doesn't seem to address this, but I only skimmed that paper so I could be wrong.

bravura 14y ago
You are correct that each iteration changes theta. You are also correct that parallel computations will be computing the wrong gradient. However, this is not bad. Stochastic gradient descent (non-parallel, simply sequential) also computes the "wrong" gradient. If you compute the gradient over the entire example set, you get the "true" gradient. Nonetheless, SGD (stochastic gradient descent) converges faster than batch gradient descent, because the cost of each update is cheaper (one example vs. all example gradient computation). More importantly, doing a stochastic gradient descent sometimes leads to finding better local optimum. Batch tends to get you into easy-to-find local optimum, and you have no stochasticity that temporarily pops you out of a local minimum and allows you to find a better one. (See Lecun paper from 97 or 98, "Efficient Backprop".) [edit: I initially wrote the following: "So computing a stochastic gradient over each example in parallel, and them aggregating them, isn't necessarily a bad idea. It's particularly a good idea when you are operating over zipf-ian sparse distributions, like natural language inputs, where many words will be quite rare and infrequently updated in a sequential SGD approach." Jimmy Lin presents that approach, but points out that the aggregator step is a bottleneck. So, as pointed out by iskander's child comment, each mapper trains SGD on a subset of the examples, and the trained models are aggregated into an ensemble. Thank you for the correction. The point stands that stochastic updates can give superior generalization accuracy to batch updates.]
- iskander 14y ago
  >So computing a stochastic gradient over each example in parallel, and them aggregating them, isn't necessarily a bad idea. Wait a minute, I don't think that's what the paper is suggesting. The communication costs of aggregating every micro-step of SGD would be extreme. I think Jimmy Lin is saying you should partition the data, train one model per partition using SGD, and then combine the models in an ensemble.
- rm999 14y ago
  I still don't get how it's parallelized, what's the reduce step? Is it averaging all the gradients from the maps? If so, that seems like what you were originally saying from your edit (and sounds like the functional equivalent of batch gradient descent).
iskander 14y ago
He doesn't! Each mapper trains a model using stochastic gradient descent on a subset of the data and they are then combined into an ensemble. A more sophisticated alternative is the Terascale Learning Algorithm (http://www.slideshare.net/pauldix/terascale-learning http://www.slideshare.net/pauldix/terascale-learning) from John Langford & friends.
- deleted 14y ago
  [deleted]
- rm999 14y ago
  I used to do a cheap man's version of this for neural networks: train many models in parallel on subsets of my data and then choose the one with the best validation performance (I avoided ensembles for speed reasons). But I often found with good model parameters and good quality data most of the models came out very similarly, except a few unlucky ones who found bad local minima. So I usually just downsampled the hell out of my data and built one or two models.
  - iskander 14y ago
    My officemate was playing with training neural networks in parallel and he found that iterating what you were doing ended up with faster training times and lower error in the long run. 1. Seed every worker with a random initial parameter 2. Run SGD locally for some large number of steps 3. Choose the parameter with lowest training (or validation, but never test) error 4. Re-seed all workers with the best parameter 5. Go to 5 until you're satisfied.
    - rm999 14y ago
      What do you mean by parameter? If you mean hyperparameters, that's pretty standard, it's a hyperparameter search followed by training. Randomized hyperparameter search is actually pretty state of the art though (as opposed to a grid search, for example): http://jmlr.csail.mit.edu/papers/volume13/bergstra12a/bergstra12a.pdf http://jmlr.csail.mit.edu/papers/volume13/bergstra12a/bergst...

by rm999 14y ago

bravura 14y ago

You are correct that each iteration changes theta. You are also correct that parallel computations will be computing the wrong gradient. However, this is not bad. Stochastic gradient descent (non-parallel, simply sequential) also computes the "wrong" gradient. If you compute the gradient over the entire example set, you get the "true" gradient. Nonetheless, SGD (stochastic gradient descent) converges faster than batch gradient descent, because the cost of each update is cheaper (one example vs. all example gradient computation). More importantly, doing a stochastic gradient descent sometimes leads to finding better local optimum. Batch tends to get you into easy-to-find local optimum, and you have no stochasticity that temporarily pops you out of a local minimum and allows you to find a better one. (See Lecun paper from 97 or 98, "Efficient Backprop".) [edit: I initially wrote the following: "So computing a stochastic gradient over each example in parallel, and them aggregating them, isn't necessarily a bad idea. It's particularly a good idea when you are operating over zipf-ian sparse distributions, like natural language inputs, where many words will be quite rare and infrequently updated in a sequential SGD approach." Jimmy Lin presents that approach, but points out that the aggregator step is a bottleneck. So, as pointed out by iskander's child comment, each mapper trains SGD on a subset of the examples, and the trained models are aggregated into an ensemble. Thank you for the correction. The point stands that stochastic updates can give superior generalization accuracy to batch updates.]

iskander 14y ago
>So computing a stochastic gradient over each example in parallel, and them aggregating them, isn't necessarily a bad idea. Wait a minute, I don't think that's what the paper is suggesting. The communication costs of aggregating every micro-step of SGD would be extreme. I think Jimmy Lin is saying you should partition the data, train one model per partition using SGD, and then combine the models in an ensemble.
rm999 14y ago
I still don't get how it's parallelized, what's the reduce step? Is it averaging all the gradients from the maps? If so, that seems like what you were originally saying from your edit (and sounds like the functional equivalent of batch gradient descent).

iskander 14y ago

He doesn't! Each mapper trains a model using stochastic gradient descent on a subset of the data and they are then combined into an ensemble. A more sophisticated alternative is the Terascale Learning Algorithm (http://www.slideshare.net/pauldix/terascale-learning http://www.slideshare.net/pauldix/terascale-learning) from John Langford & friends.

deleted 14y ago
[deleted]
rm999 14y ago
I used to do a cheap man's version of this for neural networks: train many models in parallel on subsets of my data and then choose the one with the best validation performance (I avoided ensembles for speed reasons). But I often found with good model parameters and good quality data most of the models came out very similarly, except a few unlucky ones who found bad local minima. So I usually just downsampled the hell out of my data and built one or two models.
- iskander 14y ago
  My officemate was playing with training neural networks in parallel and he found that iterating what you were doing ended up with faster training times and lower error in the long run. 1. Seed every worker with a random initial parameter 2. Run SGD locally for some large number of steps 3. Choose the parameter with lowest training (or validation, but never test) error 4. Re-seed all workers with the best parameter 5. Go to 5 until you're satisfied.
  - rm999 14y ago
    What do you mean by parameter? If you mean hyperparameters, that's pretty standard, it's a hyperparameter search followed by training. Randomized hyperparameter search is actually pretty state of the art though (as opposed to a grid search, for example): http://jmlr.csail.mit.edu/papers/volume13/bergstra12a/bergstra12a.pdf http://jmlr.csail.mit.edu/papers/volume13/bergstra12a/bergst...