Stochastic Gradients and Noisy Optimization

The sampling rule changes both the estimand and the variance of the gradient estimate. Uniform sampling with replacement draws each example independently from the empirical distribution. The expectation analysis is then simple, it is natural for streaming, it allows repeated examples, and it may ignore rare strata. Shuffling without replacement — traversing a random permutation each epoch — is what most training loops actually do. The literature calls it random reshuffling, or RR. It often reduces duplicate draws. But it introduces dependence within an epoch, and the classical iid proofs do not apply directly to it.

That gap took decades to close, and the paper that closed it says so in its own abstract. Mishchenko and two co-authors, writing in 2020, set out the state of the literature they had inherited: “The convergence rate of RR has attracted substantial attention recently and, for strongly convex and smooth functions, it was shown to converge faster than SGD if 1) the stepsize is small, 2) the gradients are bounded, and 3) the number of epochs is large.” Their own analysis needs none of those three. It proves convergence without them, improves the condition-number dependence from κ² to κ in the strongly convex case, and shows that Random Reshuffling has a different type of variance from with-replacement SGD. They also give a result for Shuffle-Once, which shuffles the data only once at the start. The practical reading is blunt: the scheme in your data loader has its own theory, and it is not the with-replacement theory.

Stratified sampling controls representation from declared groups. It can reduce variance and it improves rare-group coverage. But it depends on the strata being correct, and it requires weighting if the intended objective is still the unstratified one.

Importance sampling goes further: sample from one distribution and reweight toward another. Katharopoulos and Fleuret open their 2018 abstract with the motivation — “Deep neural network training spends most of the computation on examples that are properly handled, and could be ignored.” Their scheme samples by an upper bound on the per-sample gradient norm. It also carries an estimator of how much variance the reweighting actually removes, so reweighted sampling is switched on only when it will pay. For a fixed wall-clock budget they measured training-loss reductions of up to an order of magnitude, and relative test-error improvements between 5% and 17%. The weights can still explode, support overlap is still required, and the effective sample size still changes. That is exactly why they measure the payoff before spending it.

Empirical risk is often a sum or average over many examples. Computing its exact gradient can be expensive. Training uses a random subset to estimate the direction. The estimate is noisy but can be unbiased under the sampling design. Its variance depends on batch size, data heterogeneity, weighting, and dependence among examples. Stochastic optimization therefore combines geometry with sampling theory. The update rule cannot be understood from the learning rate alone.

Everything this lesson claims about that estimator comes from a published run or a published paper. A 1951 result in the Annals of Mathematical Statistics. A lock-free training scheme from 2011. A differentially private optimizer whose authors state in their own text that their gradient estimate is not unbiased. A study of batch size across many workloads, in the Journal of Machine Learning Research. And a normalisation defect that shipped in a widely used trainer until October 2024.

Comparisons can become misleading when they use different notions of progress. The example clock counts how many training examples or tokens have been processed. The update clock counts how many optimizer steps have been applied. The compute clock counts wall time, energy, or accelerator work spent. The data-pass clock counts effective epochs completed. A run can be ahead on one and behind on the others, and a single headline number rarely says which.

The most consequential recent result in language modelling is a re-allocation between two of those clocks. Model size and training tokens should grow together, in step. Hoffmann and 21 co-authors established that in 2022, and their abstract carries the evidence in one sentence: “By training over 400 language models ranging from 70 million to over 16 billion parameters on 5 to 500 billion tokens, we find that for compute-optimal training, the model size and the number of training tokens should be scaled equally: for every doubling of model size the number of training tokens should also be doubled.”

Chinchilla is the demonstration. 70B parameters, four times more data, the same compute budget as the 280B-parameter Gopher — and a state-of-the-art 67.5% average on MMLU, more than a 7% improvement over Gopher. The compute clock was held fixed. The example clock was advanced and the parameter count cut by a factor of four, and the model got better. Anyone comparing those two runs by parameter count alone would have read the result backwards.

For classical stochastic approximation, decreasing step sizes balance carrying on exploring against eventually settling down. Foundational analyses state that balance as two conditions: a divergent sum of step sizes, and a convergent sum of squared step sizes. Those conditions descend from the choice Robbins and Monro made in 1951 — pick the successive experiment levels so the iterates tend to the root in probability. Modern deep learning often uses finite-horizon schedules that do not satisfy the asymptotic textbook conditions exactly. Their value is empirical and problem-dependent.

The correct conclusion is not that theory is irrelevant. It is that each guarantee belongs to a specific objective, noise model, and schedule. That is why Mishchenko and his co-authors had to name the small stepsize, the bounded gradients and the large number of epochs as assumptions before they could remove them.

Two training runs can behave differently despite using the same optimizer name. Work through six things when they do. First, define the full objective: state the population or empirical quantity being estimated. Second, describe the sampling: record replacement, shuffling, grouping, and stratification. Third, record the weights, including class weights, importance ratios, and masks. Fourth, measure gradient statistics: norms, variance, outliers, and group differences. Fifth, align the clocks, comparing examples, updates, compute, and epochs separately. Sixth, test estimator changes by ablating clipping, accumulation, staleness, and sampling policy.

The sixth step is not hypothetical. The largest recent example was a normalisation bug in a mainstream trainer. In October 2024 Hugging Face confirmed that gradient accumulation in its Trainer was not mathematically equivalent to full-batch training for token-level tasks. The per-micro-batch cross-entropy losses were averaged, rather than summed and divided by the total non-padding tokens. The maintainers' own account opens with the symptom: “Gradient accumulation is supposed to be mathematically equivalent to full batch training; however, losses did not match between training runs where the setting was toggled on and off.”

The timeline is four days long. Benjamin Marie reported the issue first. Unsloth shared it on 15 October, the Hugging Face blog described it on 16 October, and transformers PR #34191, opened by ArthurZucker, was merged on 17 October. The fix changed reduction="mean" to reduction="sum" divided by the token count.

The size of the discrepancy is the reason step four exists. Marie measured loss gaps of roughly 0.2–0.3 between batch size 32 without accumulation and batch size 1 with 32 accumulation steps, at 2048-token sequences. With high sequence-length diversity the gap widened to 0.45–0.70. After the fix it fell to about 0.0004. Nobody had changed the objective on purpose. A configuration flag that was supposed to be a memory-management detail was quietly changing the quantity being minimised, and it took a comparison of two runs that should have matched to see it.

Suppose independent per-example gradients have variance σ² in one direction.