stochastic gradient descent

When the objective is a sum over many data points, f(x)=\frac1N\sum_{i=1}^N f_i(x), computing the full gradient \nabla f(x) at every step is expensive. Stochastic gradient descent instead updates using the gradient of a single term (or a small mini-batch), x^{(k+1)}=x^{(k)}-\alpha\nabla f_i(x^{(k)}) for a randomly chosen i — noisier per step, but each step is far cheaper, and the noise itself can help escape shallow local structure.