A full gradient sums a contribution from every training example. A stochastic gradient uses a smaller random selection, reducing work per update while introducing noise. We will quantify that noise and show what a descent argument does—and does not—guarantee.
Sampling a finite sum
Definition 12.1.1
(Mini-batch gradient and gradient variance)
Let for differentiable , with . At a fixed current point , independently draw uniformly from , with replacement, where is an integer. For a step size define
The gradient variance at is .
The indices are sampled afresh after the current point is fixed; the same example may occur twice. All expectations below are conditional on .
Theorem 12.1.2
(Unbiasedness and variance of the mini-batch gradient)
Conditional on ,
and consequently .
Proof
(Center each draw and expand the square)
Set . Because is uniform, , so , and by the definition of . Since , the mean statement follows at once.
Expand . For the draws are conditionally independent, so . Hence the expectation is , and dividing by gives .
Finally, . The middle term has expectation zero by unbiasedness, which gives the formula for .
Proof X-ray
Where independence and replacement enter
Three ingredients carry the proof. Centering by the full gradient makes each term mean zero; this uses that each index is uniform. Conditional independence of the draws removes every cross term, so the variances simply add to before the factor . Independence is what sampling with replacement provides. Without replacement the cross terms are negative, and for the variance is multiplied by , so that taking returns the full gradient exactly. At the other extreme, reusing one index times makes a single draw with variance . The factor is the reward for independent pieces of information, not for averaging as such.
Expected descent from smoothness
Definition 12.1.3
(Lipschitz gradient)
A differentiable has an -Lipschitz gradient, for some , if for all .
Proposition 12.1.4
(Expected descent of a mini-batch step)
Let have an -Lipschitz gradient and let be the mini-batch step above. For every ,
In particular, for ,
Proof
(Quadratic upper bound, then expectation)
For any points and , the fundamental theorem of calculus along the segment gives
by the Cauchy–Schwarz inequality and the Lipschitz condition. Substituting gives .
Conditional on , and . Taking expectations therefore yields the first inequality. When , , which gives the second. Only unbiasedness and the second moment were used, so convexity is not required.
Proof X-ray
Which assumption controls which term
The linear term needs unbiasedness: it turns the noisy inner product into . The quadratic term is where noise is charged, because is not unbiased for ; it carries the extra . The step restriction is used once, to make the coefficient of at least . If , that coefficient is negative and the bound promises no decrease even when . Convexity is never invoked, so the argument covers nonconvex , but for that reason it can only speak about the size of the gradient, not about the distance to a minimizer.
The bound is an upper bound, not a promise that every step, or even every expected step, decreases. A larger batch reduces the displayed variance term under these sampling assumptions, at the cost of more component gradients per update.
A fully computed update
Take , , and . Then and . Thus and at every , because the two component gradients are and , which differ from by and .
Worked example 12.1.5
(One step with a single sampled example)
At , with and , the sampled gradient is or , each with probability . The next point is or , respectively, and
The first inequality of the theorem, evaluated with , , , gives , exactly matching this quadratic example. The simplified bound gives and remains valid, though loose.
Worked example 12.1.6
(Batch size two with a repeated draw)
Keep and , but take . The ordered pairs are equally likely. The pairs and each have probability and give and . The pairs and together have probability and both give . The next point is , or , with objective values , and . Hence
The mean of is , and its variance is , as the theorem says. The first inequality of the proposition gives , again exact. The edge case to notice is that with replacement is still random: the pair never sees the second example.
Counterexample mode
An unbiased gradient need not decrease the objective
Suppose someone argues that an unbiased gradient estimate is enough to guarantee . At the minimizer of the same example, the component gradients are and . With and any , the next point is or with equal probability, and the objective rises from to in either case. The gradient estimate is unbiased, but its variance is nonzero, and the variance term of the proposition is exactly what appears: with the bound reads and is attained. Unbiasedness controls the linear term only; a descent claim also has to control the noise.
From one step to an average guarantee
Proposition 12.1.7
(Average squared gradient bound)
Suppose has an -Lipschitz gradient and is bounded below by . Run steps with a fixed , where each step draws a fresh independent mini-batch of size conditional on its history, and at every iterate. Then
Proof
(Telescoping the conditional bounds)
Apply the second inequality of the previous proposition at , conditional on the history, and take total expectation with the tower property. This gives ; every expectation is finite because and each step adds a finite amount. Rearranging and summing over , the function values telescope:
Multiplying by gives the claim.
The left side is an average of expected squared gradient norms, not a bound on every iterate or on distance to a global optimizer. With a fixed step the second term need not vanish as grows. Convexity, stronger assumptions or a different step schedule are needed for other kinds of guarantee; this calculation does not establish them.
Worked example 12.1.8
(The averaged bound on the quadratic example)
Use the example above with , , . Here , , and , so the right-hand side is .
Now compute the left side exactly. Put . The sampled gradient is with equally likely and independent of the past, so . The cross term vanishes in expectation, hence satisfies with . The solution is ; for instance and . The average over is . At it equals , and at it equals .
The edge case is the limit: as the true average tends to , not to zero, while the bound tends to . With a fixed step the noise floor is real and of the same order as the second term of the bound, so no proof of this type can make it vanish.
Common mistakes
Common mistake
(An unbiased gradient does not give an unbiased squared norm)
Because , it is tempting to write . The correct value is . At in the example, while the sampled gradients are , so . The quadratic term of the smoothness inequality sees exactly this extra amount.
Common mistake
(Four times the batch halves the error, not quarters it)
The variance of is , so divides the variance by four. The typical size of the error is its square root and is only halved. Reading the variance factor as a factor on the error itself overstates what a larger batch buys per additional gradient evaluation.
Exercises
Quick check
(At in the example, what is ?)
Compute the two component gradients and their mean.
Solution · Answer
The component gradients at are and , and their mean is . The squared deviations are and , so . This agrees with the constant value found earlier.
Quick check
(With independent sampling with replacement, how does change from to ?)
Use the variance formula.
Solution · Answer
It becomes one quarter as large. The root-mean-square error of is therefore halved, not quartered.
Quick check
(If all are identical, what is , and what does the descent bound become?)
Compare each component gradient with .
Solution · Answer
Every equals , so for every , and whatever the batch. The proposition then gives the deterministic decrease .
Quick check
(Does the average-gradient bound guarantee that the final iterate has a small gradient?)
Look at what the left side averages over.
Solution · Answer
Not by itself: it bounds an average of expectations over all iterates. In the quadratic example with and , even stays above for every , so the last iterate does not have a small gradient in expectation either.