Stochastic Gradient Descent: Direction Under Noise

A mini-batch may contain unusual examples, so its gradient can point away from the direction favored by the full dataset. The next step may raise both batch loss and validation loss.

SGD is useful because repeated inexpensive estimates can discover good parameter regions. Its behavior must be judged over windows, distributions, and held-out evidence rather than one noisy step.

The idea is older than deep learning. In 1951 Robbins and Monro replaced an exact measurement with a noisy one, then asked what the step sizes have to satisfy. Two conditions, pulling opposite ways. The steps must sum to infinity, so the iterate can still travel. Their squares must sum to a finite value, so the noise dies out. Every schedule since is a negotiation between those two.

Fix the step size instead and the guarantee shrinks. A 2016 survey of optimization methods for large-scale machine learning states the other half: on a strongly convex objective, “it will not be possible to prove convergence to the solution, but only to a neighborhood of the optimal value”. Its Theorem 4.6 sizes that neighbourhood. The limiting optimality gap is ᾱLM/(2cµ), proportional to the step size and to the variance bound. Repeated estimates buy a region, not a point.

Neither method is universally superior, and the card below says only that mini-batch noise is “adjustable through batching”. What adjusting it costs has been measured twice, with two different verdicts.

Train the same six networks two ways and the training accuracy comes out near-identical. The test accuracy does not. Keskar and colleagues ran that experiment in 2017: ADAM, batch 256 against a batch equal to 10% of the training set, five runs each from random starts. On their F2 network the small-batch runs scored 64.02% ±0.2% against the large-batch 59.45% ±1.05%. On C4, 63.08% ±0.5% against 57.81% ±0.17%. Their diagnosis is in the abstract: “large-batch methods tend to converge to sharp minimizers of the training and testing functions - and as is well known, sharp minima lead to poorer generalization”.

An independent group at the Technion reproduced that gap on Keskar's own F1/C1/C3 networks later the same year — and then made it go away. Lengthening the training regime took ResNet-44 on CIFAR-10 from 92.83% (small batch) and 86.10% (large batch) to 93.07%, and the gap “completely disappears when the training regime is adapted”. Two published measurements of the same networks. They disagree about whether the penalty belongs to the batch size or to the number of updates. Turning the noise down is a trade you make with your eyes open, not a free setting.

The word “noise” covers several distinct phenomena. One of them is not noise at all but a modelling choice with proved consequences, made silently by the default training loop.

Unbiasedness describes the expected estimate under a sampling scheme. It does not bound variance, step size, tail events, or the damage from corrupted examples. Real pipelines may also sample non-uniformly or apply weights incorrectly. Verify the estimator created by data loading and reduction rather than assuming textbook conditions.

The PaLM team met this at scale. They “observed spikes in the loss roughly 20 times during training, despite the fact that gradient clipping was enabled”. The spikes appeared only in the largest model, at irregular intervals. Their fix was to restart about 100 steps earlier and skip 200 to 500 batches. Replaying those same batches from an earlier checkpoint produced no spike, which implies that “spikes only occur due to the combination of specific data batches with a particular model parameter state”. The damage came from a pairing, not from bad data.

Notice what the defence they had enabled actually is. Norm clipping rescales the gradient whenever its norm exceeds a threshold. Pascanu and colleagues gave it as Algorithm 1 in 2013, and its one hyperparameter is chosen empirically. “One good heuristic for setting this threshold is to look at statistics on the average norm over a sufficiently large number of updates.”, they write, and report that “values from half to ten times this average can still yield convergence”.

The justification arrived seven years later. Zhang and colleagues measured, on AWD-LSTM/Penn Treebank, that the local gradient Lipschitz constant grows with the gradient norm. Under their (L0,L1)-smoothness condition ‖∇²f(x)‖ ≤ L0 + L1‖∇f(x)‖ they then proved that “gradient clipping and normalized gradient, converge arbitrarily faster than gradient descent with fixed stepsize”. The standard protection against tail events works precisely by throwing away the unbiasedness this section is warning you not to lean on.

Use aggregated diagnostics before changing the optimizer. Two of the steps below have a published price tag, and neither is small.

Step 3 asks for several seeds; the literature says how few is too few. Ten runs of TRPO on HalfCheetah-v1, one identical hyperparameter configuration, nothing varying but the random seed. Split the ten into two groups of five, average each group, and the two curves come out statistically distinguishable: t = −9.0916, p = 0.0016. That is Henderson and colleagues in 2018, and their sentence is blunt: “We demonstrate that the variance between runs is enough to create statistically different distributions just from varying random seeds.” Five against five, one configuration, a significant result made of nothing. Agarwal and colleagues later computed 95% confidence intervals on sample medians for varying run counts and found that “this number is closer to 50–100 runs in Atari 100k – far too many to be computationally feasible for most research projects”.

Step 4 is not a free measurement either, because enlarging the batch changes the run. In 2017 Facebook trained ResNet-50 on ImageNet at minibatch 8,192 across 256 GPUs in one hour. It reached the small-batch baseline only after two changes: rescale the learning rate — “Linear Scaling Rule: When the minibatch size is multiplied by k, multiply the learning rate by k.” — and add a 5-epoch gradual warmup. Top-1 validation error, mean and standard deviation over 5 trials: 23.60% ±0.12 at kn=256; 23.74% ±0.09 at kn=8k with gradual warmup; 24.84% ±0.37 at the same 8k with no warmup; 25.88% ±0.56 with constant warmup. Beyond roughly 8k, “accuracy degrades rapidly”.

And the rule is local, not universal. A Google Brain study tested it across 35 workloads with per-batch-size metaparameter tuning and reported that “popular learning rate heuristics—such as linearly scaling the learning rate with the batch size— do not hold across all problems or across all batch sizes”. A larger diagnostic batch answers your question only if you also re-tune the schedule it broke.

Several random choices contribute to the gradient estimate. The last layer, numerical execution, is the one practitioners assume is negligible, and it has been measured with everything else nailed down.

Sixteen training runs with every algorithmic source of randomness fixed — same seeds, same initial weights, same batch order, same libraries, same RTX 2080Ti — should give sixteen copies of one model. WideResNet-28-10 on CIFAR-100 did not. “However, we found that the accuracies of these 16 models vary between 77.3% and 80.2% (a 2.9% difference).” That is the opening of a distinguished paper by Pham and colleagues at a 2020 software-engineering conference. Per-class accuracy on “camel” ran from 38.1% to 90.5%. ResNet-56 convergence time ran from 2,986 to 7,324 seconds. Their survey of 901 respondents found 83.8% unaware of or unsure about implementation-level variance.

A separate group isolated the same floating-point accumulation-order noise in 2022. On ResNet-50/ImageNet it produced 14.68% predictive churn, against 14.89% for all algorithmic noise combined. The reduction order alone moved almost as many predictions as every seed in the pipeline. Top-1 accuracy standard deviation ran between 0.05% and 0.91%, and forcing determinism cost “up to 746%”. This layer is not a rounding footnote. It is the size of the effect you were trying to measure.

A useful report includes the number of examples or tokens processed, learning-rate phase, validation uncertainty, and compute consumed. Epoch counts alone can mislead when sampling or dataset size changes.

When two runs process different evidence, compare them at matched budgets as well as matched wall-clock time. That trade-off has a measured shape rather than a rule of thumb. A Google Brain study trained 168,160 models across 35 workloads and released 71,638,836 loss measurements. It found the same three regions everywhere. First perfect scaling, where the steps needed to reach a goal halve for each doubling of the batch size. Then, in its own words, “for all problems, this is followed by a region of diminishing returns that eventually leads to a regime of maximal data parallelism where additional parallelism provides no benefit whatsoever”.

A different route reached the same boundary and made it something you can compute in advance. OpenAI's 2018 measurement: “a simple and easy-to-measure statistic called the gradient noise scale predicts the largest useful batch size across many domains”. They checked it across MNIST, SVHN, CIFAR-10, ImageNet, Billion Word, Atari and Dota. The useful batch ranges from tens of thousands on ImageNet to millions in Dota 2. Where your own budget stops paying is a property of your problem, not of the hardware.