Stochastic Gradient Descent

Computing the gradient over the whole dataset for every step is unaffordable. Stochastic gradient descent estimates it from a small random batch instead — noisier, but hundreds of times cheaper, so it takes many more steps in the same wall-clock time and gets further.

Sample a minibatch, compute its gradient, step. The noise is not purely a cost: it helps escape sharp regions and is part of why these methods generalise. Batch size trades gradient quality against step count, and the useful range is bounded at the top by diminishing returns rather than by memory alone.

θ sub _t+1  = θ sub _t  − η∇L sub _B (θ sub _t ) for a batch B, with E[∇L sub _B ] = ∇L and variance falling as 1/|B|. Halving noise therefore costs four times the batch, which is the shape of the diminishing return.