Stochastic gradient descent

Stochastic gradient descent (SGD) uses the gradient of the loss on a single random example per step: $\mathbf{\theta }\leftarrow \mathbf{\theta }-\eta \nabla L_i(\mathbf{\theta })$. On average this equals the full gradient, so it points the right way in expectation.

Each step is $n$ times cheaper, so SGD makes progress long before full-batch GD has finished a single step. The price is noise: the loss zig-zags instead of falling smoothly.

The noise can help — it can bounce the parameters out of shallow local minima and saddle points — but near the end it stops precise convergence, so the learning rate is usually decreased over time (a learning-rate schedule).