Stochastic in this case means the computation of the gradient. Instead of computing the gradient over the entire data set and making a single update per pass ov

Stochastic in this case means the computation of the gradient. Instead of computing the gradient over the entire data set and making a single update per pass over the data, in SGD you compute and update for each data point. This means noisier (hence stochastic) estimates of the gradient but generally faster convergence. Gradient descent is a general purpose method. There are generally two approaches to problems with many local minima: - modify the algorithm to try to get out of minima (e.g. simulated annealing, evolutionary methods, etc.); or - make some simplifying assumptions and solve an approximate problem that is convex.