Motivation
Many computing problems reduce to minimizing an average over a large collection of records. A parameter vector describes a model or approximation; each record contributes a loss. Evaluating the complete gradient may require scanning every record, even when a rough direction would already produce a useful update. Minibatch methods trade the accuracy of one direction against the cost of obtaining it.
That trade is mathematical and computational at the same time. Averaging more independently sampled gradients reduces variance. Yet it consumes more record evaluations, can require more buffer memory, and may reduce the number of parameter updates possible within a fixed budget. A machine can also process a moderately sized matrix much more efficiently than many tiny operations. Consequently, neither the smallest nor the largest possible batch is automatically best.
The relevant outcome must be stated precisely. An algorithm may reduce the expected squared gradient, lower the objective after one step, process more records each second, or fit into available memory. These are different claims. A faster data pipeline does not prove faster optimization, and a stationarity bound does not prove convergence to a global minimum for a nonconvex objective.
Definitions
Definition 3.1.1
(Finite-sum objective and with-replacement minibatch gradient)
Let be the parameter vector and consider the finite-sum objective
where every component loss is differentiable. A full gradient evaluates all components at the same parameter. A minibatch gradient of size samples indices independently and uniformly from , with replacement, and forms
Repeated indices are allowed by this definition. Sampling a subset without replacement is a different design with a finite-population variance correction. A shuffled pass through the data is different again: later indices within the pass are not independent uniform draws conditional on the earlier ones. Do not transfer a proof between these procedures without checking its assumptions.
Definition 3.1.2
(-smoothness)
Use the Euclidean norm and inner product. A differentiable objective is -smooth, for a constant , when for all .
Smoothness yields the upper quadratic model
It follows by integrating the gradient along the line segment from to and bounding the gradient change. Smoothness is not convexity. A smooth function may have several local minima, saddles, or be unbounded below. The later theorem therefore separately assumes a finite lower bound .
Definition 3.1.3
(Stochastic iteration and conditional unbiasedness)
The stochastic iteration is , with fixed step size . Let contain the initial state and all randomness used before sampling the batch at step , so the current parameter is known conditional on . The gradient estimates are conditionally unbiased if for every .
This is stronger and more useful here than a vague assertion that gradients average correctly over an entire run.
Theorem/proposition
Proposition 3.1.4
(Independent minibatches reduce conditional variance)
At a fixed parameter , define
For the with-replacement minibatch above,
The same identities hold conditionally at step when a fresh independent batch is drawn after is fixed.
The proposition measures a batch by update noise alone. In practice the same number enters several other accounts as well.
Concept lensAlgorithmic
One batch size, several distinct denominators
Viewed statistically, increasing reduces independent gradient noise per update. Viewed as an algorithmic budget, it consumes component evaluations each time the parameter moves. Viewed as a system, it changes buffer size, matrix-operation efficiency and communication frequency. Compare methods using the denominator that matches the question: updates, record evaluations, elapsed time or memory. Quoting only a per-iteration improvement hides the costs needed to obtain that iteration.
The second result turns the variance identity into a guarantee about many updates.
Theorem 3.1.5
(A smooth stochastic stationarity bound)
Suppose is globally -smooth and bounded below by . Let be deterministic, , and . Assume conditional unbiasedness and conditional noise bound at every step, with finite moments for the displayed expectations. Then
This bounds average expected squared gradient. It does not assert that every iterate improves, that the final iterate is best, or that a global minimizer has been reached.
Proof sketch or proof idea
Proof
(Cross terms vanish for independent centered draws)
Each sampled component gradient has mean . Center the independent vectors and expand the squared norm of their sum. The expected cross inner products vanish by independence and zero means. The remaining terms contribute , divided by . This proves the first theorem, including its vector-valued form.
Proof
(One-step descent in conditional expectation, then telescoping)
For the second theorem, apply the smoothness inequality with and condition on . Unbiasedness handles the linear term, and the centered second-moment identity gives
Because , the coefficient of the squared gradient is at least . Take expectations, sum from zero to , and telescope the objective terms. The final expected objective is at least , so rearranging proves the displayed bound. Conditioning is essential: the parameter depends on previous randomness, while the newly drawn batch must still be unbiased at that parameter.
Proof X-ray
Where each assumption is used in the stationarity bound
Smoothness is used once, as the quadratic upper model at and ; it converts a random step into a bound with a linear term in and a quadratic term in . The key move is to take the conditional expectation given before anything else. Because is fixed under that conditioning, unbiasedness turns the linear term into , and the noise bound splits the quadratic term as . The step restriction is used only to make the net coefficient at least ; any fixed fraction would do with a different constant, but the coefficient must stay positive. Telescoping cancels every intermediate objective value, and the lower bound is used exactly once, to control the last one. Without the right side would contain , which can grow without bound.
With fixed positive step size, the bound has a noise term that does not disappear merely by increasing . A smaller step reduces that term but enlarges the transient term for a fixed iteration budget. For positive noise level, balancing the two terms suggests a step proportional to , subject to , with constants depending on the objective gap and variance. Such a suggestion is not an implementable oracle when those constants are unknown.
If the same assumptions hold uniformly and one chooses an iterate index uniformly from , independently of the run, its expected squared gradient equals the left side. This gives a precise output interpretation of the average bound. Small gradient is a first-order stationarity criterion; additional assumptions are needed to turn it into a function-value guarantee.
Worked examples
Worked example 3.1.6
(One-dimensional losses with visible gradient noise)
Take two losses and . Their average is , whose minimizer is and whose smoothness constant is . The component gradients are and . Their average is and each differs from it by in magnitude, so everywhere.
At , a full gradient step of size gives , reducing the objective from to . A single randomly selected component instead gives or , each with probability one half. Their objective values are and , so the expected new objective is .
For a batch of size , the update noise has variance . Because the objective is quadratic, its expected value after the update is exactly . For this is . A larger batch improves the expected one-step result at a common step size, but uses more component evaluations. At the minimizer, component gradients are still and : stochastic gradients need not vanish when the full gradient vanishes.
Worked example 3.1.7
(Comparing budgets rather than iteration counts)
For the same objective, start at . The objective gap is , and is valid. Set , and . The stationarity theorem gives an average expected squared-gradient bound of . Its two terms are and ; the estimate need not be tight.
If the component-evaluation budget is , a batch of size one permits updates. Keeping the same step gives the bound . A batch of size sixteen permits only updates, giving . For these particular choices the bound is smallest at the intermediate batch. This compares upper bounds, not exact expected outcomes or a universal optimum.
The algebra explains the competition. If , the transient term becomes , increasing with batch size, while the noise term decreases with it. Changing the step size changes the comparison. An actual throughput budget can also differ from a record-evaluation budget because hardware utilization depends on batch size.
Worked example 3.1.8
(Memory and a transparent timing model)
Suppose there are dense feature records of dimension , stored as eight-byte numbers. Keeping the feature matrix alone requires bytes, or eight decimal gigabytes. A batch buffer for such records needs bytes. A parameter vector or accumulated gradient needs bytes. Labels, optimizer state, temporary arrays and runtime overhead are additional costs; these figures are not a total memory promise.
As an illustrative model rather than a measurement, suppose a step costs milliseconds. The first term represents fixed overhead and the second per-record work. Then batch sizes one and process about and records per millisecond, respectively. The throughput approaches records per millisecond in this model as grows. That limit does not mean arbitrarily large batches are desirable: memory grows, and fewer parameter updates occur for a fixed number of processed records.
For synchronous data-parallel gradients on workers, each worker can accumulate a vector of length locally before communicating. Aggregation then moves gradient-sized information rather than every raw record, but communication topology, latency and slow workers still affect time. Every worker's contribution must be evaluated at the same parameter version for the simple minibatch estimator above. Gradients from stale versions require a different analysis.
Common mistakes
The step-size hypothesis of the stationarity theorem is easy to treat as a technicality. It is not.
Counterexample mode
A too-large step breaks the bound even without noise
Claim: the stationarity bound holds for every fixed step size. Take with , so , and ; the iteration is deterministic. With and , the update is , so . For the left side is , while the right side is . The claimed inequality fails, and the iterates grow like . The repaired statement keeps the hypothesis , which guarantees a positive descent coefficient.
Common mistake
(Changing the sampling law without reweighting)
Uniform sampling is also part of the estimator. If record is sampled with a positive probability and one uses its unweighted gradient, the expectation becomes a probability-weighted objective gradient. To estimate the original uniform objective unbiasedly, the single-sample correction is . That correction can have high variance when probabilities are tiny; unbiasedness by itself is not an efficiency guarantee. Zero-probability records cannot be recovered by this formula.
Counterexample mode
Distinct indices do not give the same variance
Claim: any sampled indices give minibatch variance . In the first worked example, and . With replacement and , the variance is ; for instance the batch , of probability , gives , off by . Without replacement, the only batch of size two is , so exactly and the variance is . The repaired statement for distinct indices drawn uniformly is the finite-population formula for , which gives here.
Common mistake
(Applying the theorem to a modified iteration)
Gradient clipping, momentum, adaptive scaling, sampling without replacement and asynchronous updates each change the iteration being analyzed. They may be useful, but the theorem does not silently cover them. A check of whether the objective decreases on one example is likewise not a proof of the conditional assumptions used in the expected bound.
Summary
Independent with-replacement minibatches give an unbiased gradient with variance proportional to . Smoothness, a finite objective lower bound and conditional noise control yield an average stationarity estimate. Larger batches trade lower noise per step for more work and memory. A useful computing argument names its statistical assumptions, output criterion and resource budget before comparing methods.
Exercises
Exercise 3.1.9
(At a fixed scalar parameter, three component gradients are . Find the full gradient and the variance of a uniformly sampled component. Find the variance of a four-draw with-replacement minibatch average.)
Foundation
Solution · Answer
The full gradient is . Deviations are , whose mean squared value is . Independent averaging of four draws has variance . The result assumes replacement and independence; drawing four distinct indices from only three records is not the specified procedure.
Exercise 3.1.10
(Let with deterministic full-gradient updates. Show exactly when a positive step size decreases for every nonzero starting point. Compare with the sufficient restriction in the theorem.)
Foundation
Solution · Answer
The update is , so for nonzero . Strict decrease occurs exactly when . At the value is unchanged, and for larger positive steps it grows. The theorem uses the sufficient, more restrictive range , because it guarantees the particular descent coefficient used in its proof.
Exercise 3.1.11
(In the stationarity bound, let , , , , and . Evaluate the bound and identify its transient and noise terms. Is a global-minimum guarantee established?)
Core
Solution · Answer
The transient term is . The noise term is . Their sum is . The step satisfies . Subject to all other hypotheses, the conclusion bounds average expected squared gradient. Without further structure such as an appropriate convexity condition, small gradient does not certify a global minimum.
Exercise 3.1.12
(There are two component gradients and , sampled with probabilities and . Compute the expected unweighted gradient and the two importance-corrected values for the uniform objective. Verify unbiasedness and explain why both probabilities must be positive.)
Core
Solution · Answer
The desired uniform gradient is . Unweighted sampling instead has expectation . The corrected values are and . Their expected value is . A component with zero sampling probability is never observed, and division by its probability is undefined. Unbiased recovery of its arbitrary contribution therefore cannot be justified by this scheme.