Optimization

Stochastic Gradient Descent

Estimate the gradient from a random sample of the data each step, trading noise for enormous savings in per-step cost.

Motivation

Many objectives are sums over data: f(x) = (1/n) sum_i f_i(x). Full gradient descent computes all n gradients per step, which is prohibitive for large n. Stochastic gradient descent (SGD) replaces the full gradient with the gradient of one randomly chosen term f_i, or a small batch, giving an unbiased but noisy estimate.

The update

Kronos motion — data assimilation

x_{k+1} = x_k - a_k * grad f_{i_k}(x_k), where i_k is drawn at random. Each step is n times cheaper than full gradient descent, so many more steps run in the same time. The expectation of the stochastic gradient equals the true gradient, so on average steps point downhill.

Step sizes and convergence

Because the gradient estimate is noisy, a constant step size makes the iterates bounce around the minimum rather than settle. Classic theory uses a diminishing schedule satisfying sum a_k = infinity and sum a_k^2 < infinity, for example a_k = a0 / k. For strongly convex objectives SGD converges at rate O(1/k) in expectation, slower than full gradient descent per step but far faster per unit compute.

Variance reduction

Mini-batches average several samples to shrink gradient variance.
SVRG and SAG store past gradients to remove variance and recover linear convergence on finite sums.
Averaging iterates (Polyak-Ruppert) improves the final estimate.

Practical notes

SGD noise can help escape shallow saddle points and narrow local minima in non-convex deep learning, acting as implicit regularization. Shuffling data each epoch, tuning batch size, and warming up the learning rate are standard. SGD with momentum is a strong default for training neural networks.

python

for epoch in range(E):
    shuffle(data)
    for batch in batches(data, size=B):
        g = grad_batch(x, batch)
        x = x - lr * g

Its scalability makes SGD the default engine for training the surrogate and machine-learning models used across large scientific and engineering datasets.