mathematics//optimization//gradient descent//stochastic gradient descent

Stochastic gradient descent is gradient descent in which the gradient at each step is estimated from a small random sample of the data, a **minibatch**, instead of the whole dataset; it is what neural networks are trained with and, in its one-sample form, what adapts the weights of the LMS filters in echo cancellers, modem equalizers and active noise control. The cost of a step no longer grows with the size of the dataset.

Stochastic gradient descent is gradient descent in which the gradient at each step is estimated from a small random sample of the data, a minibatch, instead of the whole dataset; it is what neural networks are trained with and, in its one-sample form, what adapts the weights of the LMS filters in echo cancellers, modem equalizers and active noise control. The cost of a step no longer grows with the size of the dataset.

θk+1=θk−η 1∣Bk∣∑i∈Bk∇ℓi(θk)\theta_{k+1} = \theta_k - \eta\,\frac{1}{|B_k|}\sum_{i\in B_k}\nabla \ell_i(\theta_k)θk+1​=θk​−η∣Bk​∣1​i∈Bk​∑​∇ℓi​(θk​)

ℓi\ell_iℓi​ is the loss on example iii and BkB_kBk​ the minibatch drawn at step kkk, typically 32 to a few thousand examples. With a million training examples, a full gradient costs a pass over all of them for a single step, while a batch of 64 costs about fifteen thousand times less and points roughly the same way; the error of each estimate averages out over many steps. One pass over the whole dataset is an epoch, and training runs many of them.

SGD trades exact steps for many cheap noisy ones, which is the only way to optimize over datasets that do not fit in one computation. The noise has a price: at a fixed learning rate the parameters keep jittering around the minimum instead of settling, so the rate is lowered over the course of training.

The batch size is a hardware choice as much as a statistical one. Larger batches give less noisy gradients and keep a GPU busy, with diminishing returns in progress per example; the learning rate is retuned when the batch changes (learning rate), and a running velocity smooths the noise further (momentum).

The LMS filter of Widrow and Hoff (1960) is SGD with a batch of one, run sample by sample in real time. An adaptive FIR filter predicts a signal, the error between prediction and measurement multiplies the input samples, and the weights move by a small step μ\muμ times that product; the step must be small relative to the input's power or the filter diverges, the same stability limit as in batch descent.

The same update shape appears in adaptive control and in the Kalman filter, a correspondence the optimization note gathers. For training networks in practice, SGD with momentum and Adam are the two defaults (optimizer).