mini-batch stochastic gradient descent
Suppose you want the average opinion of a million people, but polling everyone before each decision is far too slow. So instead you poll a small random sample of, say, 64 people, act on that rough-but-cheap estimate, then poll a fresh sample next time. Over many rounds the noise averages out and you move in the right overall direction. Mini-batch stochastic gradient descent does exactly this for training: it estimates the gradient from a small random subset of the data instead of all of it.
In machine learning the objective is usually an average over a huge dataset, f(x) = (1/N) sum over i of f_i(x), where f_i is the loss on training example i and N can be millions. The true gradient is the average of all N example-gradients — far too expensive to compute every step. Mini-batch SGD picks a small random batch B of examples (say 32 to 512) and uses its average gradient as a cheap, noisy ESTIMATE of the true one: x_{k+1} = x_k - alpha_k * (1/|B|) sum over i in B of grad f_i(x_k). The estimate is unbiased (correct on average) but noisy. A full pass through the data is an 'epoch'; training does many epochs, reshuffling the data. Because each step costs only |B| gradients rather than N, SGD does vastly more update steps per unit of computation than full-batch gradient descent — and that throughput is what makes training large models feasible.
SGD is the foundational workhorse of deep-learning training, and its variants (momentum, Nesterov, Adam) build on it. Two honest points are essential. First, the step size (learning rate) must DECREASE over time (or be carefully scheduled) for the noisy iterate to settle near a minimum rather than rattle around it forever — formally, convergence in the convex case is only SUBLINEAR, on the order of O(1/sqrt(k)) for a fixed budget, much slower per-step than full-gradient methods. SGD wins not by converging fast per step but by making each step cheap. Second, the gradient NOISE is not purely a nuisance: it helps the iterate escape saddle points and shallow local minima, which is part of why SGD generalizes well in practice — a genuinely useful side effect, not just tolerated error.
Training on 1,000,000 images with batch size 256: one epoch is about 3,900 SGD updates. Full-batch gradient descent would make a single update per epoch using all 1,000,000 images — far slower to learn. SGD's 3,900 cheap, noisy steps make far more progress, even though each individual step is jittery.
Sample the gradient on a mini-batch: noisy steps, but many cheap ones.
SGD's per-step convergence is only sublinear, about O(1/sqrt(k)) — slower than full gradient descent's linear rate. It wins on wall-clock by making each step cheap, not by converging fast, and its step size must decay (or be scheduled) for the noisy iterate to settle rather than bounce around the minimum forever.