Stochastic Gradient Descent: Minibatches and a Finite-Horizon Expected Stationarity Bound
How the deterministic descent lemma extends to noisy gradient estimates. Covers conditional unbiasedness, bounded conditional variance, minibatch variance reduction, sampling pitfalls, and an expected stationarity bound with a genuine noise floor.
§3.3Estimated reading time: 31 min
From exact gradients to estimated gradients
For an L-smooth function f that is bounded below, gradient descent with step 0<η≤1/L does not increase the objective at any step. The decrease is controlled by the descent lemma:
f(y)≤f(x)+⟨∇f(x),y−x⟩+2L∥y−x∥2for all x,y∈Rd.
The same Lipschitz argument also gives the two-sided version ∣f(y)−f(x)−⟨∇f(x),y−x⟩∣≤2L∥y−x∥2.
In many problems ∇f(x) is too expensive to evaluate exactly. A typical case is an average of many component functions. We then replace it by a random estimate gk and update
xk+1=xk−ηgk.
The deterministic argument does not survive this change unchanged. Because gk is random, a single step can move uphill even when the true gradient is zero. Our guarantee is stated in expectation and accounts for how much the estimate fluctuates; other kinds of guarantee require their own assumptions and proof. This note builds that argument carefully. It also marks exactly what the resulting bound does and does not say.
Standing assumptions
Throughout, we assume:
f:Rd→R is differentiable, and ∇f is globally L-Lipschitz for some L>0.
There is a finite number finf with f(x)≥finf for all x.
The starting point x0 is deterministic, and the step size is constant with 0<η≤1/L.
Information structure. Let F0⊆F1⊆⋯ be a filtration. Read Fk as "everything that has happened before the kth sample is drawn." The estimate gk is Fk+1-measurable, since it is known once the kth sample is drawn. Since x0 is deterministic and xk+1=xk−ηgk, induction shows that each xk is Fk-measurable. Informally, the current point is known before the next sample is drawn.
Definition 3.3.1
(Conditionally unbiased gradient oracle with variance bound σ2)
The estimates (gk) form a conditionally unbiased gradient oracle with variance bound σ2 if, for every k:
gk is square integrable, that is, E∥gk∥2<∞;
conditional unbiasedness:E[gk∣Fk]=∇f(xk) almost surely;
bounded conditional variance:E[∥gk−∇f(xk)∥2∣Fk]≤σ2 almost surely, for a finite constant σ2≥0.
The standing assumptions include that the estimates satisfy this definition.
Conditioning on Fk matters here. Unbiasedness "on average over everything" would not be enough. We need the estimate to be correct given the point at which it is evaluated, because the descent lemma is applied at that specific point.
Integrability comes for free
Every expectation used below is finite. By induction, ∥xk+1∥2≤2∥xk∥2+2η2∥gk∥2, so each xk is square integrable. The Lipschitz property gives ∥∇f(xk)∥≤∥∇f(0)∥+L∥xk∥, so ∇f(xk) is square integrable. The two-sided descent bound with base point 0 gives
∣f(xk)∣≤∣f(0)∣+∥∇f(0)∥∥xk∥+2L∥xk∥2,
so f(xk) is integrable. Finally, ∣⟨∇f(xk),gk⟩∣≤21∥∇f(xk)∥2+21∥gk∥2, so this inner product is integrable as well. This justifies every conditional expectation we take.
The one-step bound
The key algebraic fact is an exact decomposition of the second moment. Write ek=gk−∇f(xk). Then
∥gk∥2=∥∇f(xk)∥2+2⟨∇f(xk),ek⟩+∥ek∥2.
Since ∇f(xk) is Fk-measurable, we may take it outside the conditional expectation. Then E[⟨∇f(xk),ek⟩∣Fk]=⟨∇f(xk),E[ek∣Fk]⟩=0. The cross term cancels exactly, and
E[∥gk∥2∣Fk]=∥∇f(xk)∥2+E[∥gk−∇f(xk)∥2∣Fk].
Theorem 3.3.2
(Expected one-step decrease)
Under the standing assumptions, for every k≥0,
E[f(xk+1)∣Fk]≤f(xk)−2η∥∇f(xk)∥2+2Lη2σ2a.s.,
and consequently
Ef(xk+1)≤Ef(xk)−2ηE∥∇f(xk)∥2+2Lη2σ2.
Proof
(Conditioning the pointwise descent inequality)
Apply the descent lemma with x=xk and y=xk+1=xk−ηgk. This inequality holds pointwise, for every outcome:
f(xk+1)≤f(xk)−η⟨∇f(xk),gk⟩+2Lη2∥gk∥2.
All terms are integrable, so we may take conditional expectations given Fk. Monotonicity preserves the inequality. The term f(xk) is Fk-measurable and stays as it is. By unbiasedness, E[⟨∇f(xk),gk⟩∣Fk]=∥∇f(xk)∥2. By the decomposition above and the variance bound, E[∥gk∥2∣Fk]≤∥∇f(xk)∥2+σ2. Hence
Because η≤1/L, we have 1−Lη/2≥1/2. This gives the first claim. Taking full expectations and using the tower property E[E[⋅∣Fk]]=E[⋅] gives the second.
Proof X-ray
What conditioning does in the one-step proof
The descent inequality holds outcome by outcome, but it contains two random quantities, ⟨∇f(xk),gk⟩ and ∥gk∥2. The proof replaces each by its conditional expectation given Fk, and each oracle hypothesis is used exactly where one of them is replaced. Conditional unbiasedness turns the linear term into ∥∇f(xk)∥2, and it is used a second time inside the second-moment identity, where it removes the cross term. The variance bound then replaces E[∥ek∥2∣Fk] by σ2.
Both replacements require that ∇f(xk) can be taken outside the conditional expectation, that is, that xk is Fk-measurable. This is why the information structure is fixed before the oracle is described.
The step size enters only at the very end. The bound with coefficient η(1−Lη/2) holds for every η>0; the restriction η≤1/L only simplifies that coefficient to at least η/2.
Compare this with the deterministic case. There the extra term 2Lη2σ2 is absent, and f decreases monotonically. Here the expected objective can increase whenever ∥∇f(xk)∥2 is small relative to Lησ2. The noise term is the price of using an estimate.
The finite-horizon stationarity bound
Theorem 3.3.3
(Average expected squared gradient)
Under the standing assumptions, for every positive integer T,
T1k=0∑T−1E∥∇f(xk)∥2≤ηT2(f(x0)−finf)+Lησ2.
Proof
(Telescoping the one-step bound)
Rearrange the expected one-step bound:
2ηE∥∇f(xk)∥2≤Ef(xk)−Ef(xk+1)+2Lη2σ2.
Sum over k=0,…,T−1. The objective values telescope:
2ηk=0∑T−1E∥∇f(xk)∥2≤f(x0)−Ef(xT)+2TLη2σ2.
Here Ef(x0)=f(x0) because x0 is deterministic. Since f(xT)≥finf pointwise, Ef(xT)≥finf. Substitute this and multiply by 2/(ηT).
How to read the bound
A randomized output. Let R be uniform on {0,…,T−1} and independent of the whole run. Then
The second equality uses the independence of R. So the theorem bounds E∥∇f(xR)∥2 exactly. It also implies kminE∥∇f(xk)∥2≤ (right-hand side), because a minimum never exceeds an average.
Three different quantities. Keep these apart:
Expected squared norm, E∥∇f(xR)∥2. This is what the theorem controls.
Expected norm, E∥∇f(xR)∥. Jensen's inequality gives E∥∇f(xR)∥≤E∥∇f(xR)∥2. This is a consequence of the bound, not the same statement.
Pathwise behavior. Nothing here says that a particular run has a small gradient. Markov's inequality gives only a probability statement: P(∥∇f(xR)∥2≥ε)≤ε−1E∥∇f(xR)∥2.
Two terms. The first term, 2(f(x0)−finf)/(ηT), is the deterministic term and shrinks as T grows. The second term, Lησ2, does not depend on T. With a constant step it remains no matter how long we run. The theorem is an upper bound. It does not claim that the error is always at least Lησ2. When σ2=0 we recover the deterministic rate with no floor at all. The worked example below shows that in a genuinely noisy problem a strictly positive floor can actually occur.
What is not claimed. The bound says nothing about convergence of the iterates xk. It does not say they approach a global minimizer, which is false in general for nonconvex f. It gives no rate for the last iterate xT. And it says nothing about performance on data not included in f.
Finite sums and minibatches
Suppose f=n1i=1∑nfi, where each fi:Rd→R is a deterministic differentiable function. The smoothness and lower-bound assumptions are imposed on f. At step k, draw an index Ik that is uniform on {1,…,n} and independent of Fk, and set gk=∇fIk(xk).
Define V(x):=n−1i=1∑n∥∇fi(x)−∇f(x)∥2 and, for this construction, assume V(x)≤σ2 for every x. Starting from deterministic x0, induction gives square-integrable xk: the Lipschitz gradient and the variance bound give a square-integrable sampled gradient, so the next iterate is square-integrable. Thus the conditional expectations below are well defined. Since xk is Fk-measurable and Ik is independent of Fk, we can freeze xk and average over the index:
The global condition above is sufficient, but not necessary: a suitable bound along the iterates, together with integrability, also suffices. This condition does not follow from smoothness of f. For example, take n=2, f1(x)=x2 and f2(x)=−x2. Then f≡0 is smooth and bounded below, yet V(x)=4x2 is unbounded. Uniform bounded variance is a separate hypothesis.
Once the variance bound holds, square integrability also follows. We have E∥gk∥2=E∥∇f(xk)∥2+EV(xk). The second term is at most σ2, and the first is finite whenever xk is square integrable, so the induction from the integrability section goes through.
Minibatches with replacement. Now draw b≥1 indices Ik,1,…,Ik,b, independent of each other and of Fk, each uniform. All of them are evaluated at the same point xk:
gˉk=b1j=1∑b∇fIk,j(xk).
Proposition 3.3.4
(Variance of a minibatch drawn with replacement)
In the finite-sum setting with V(x)≤σ2 for every x, let gˉk be the average of b component gradients at xk whose indices are independent, uniform on {1,…,n} and independent of Fk. Then
Every cross term vanishes. Since gˉk−∇f(xk)=b1j∑ej, dividing by b2 gives the stated variance.
The stationarity theorem therefore applies with σ2 replaced by σ2/b. The noise term becomes Lησ2/b, at the cost of b component gradients per step.
Common mistake
(Enlarging the step together with the batch size)
Because a minibatch shrinks the noise term, it is tempting to enlarge the step as well, for instance in proportion to b. The bound proved here gives no license for that. Its proof uses η≤1/L, and L is a property of f, not of the estimator, so the admissible step sizes are the same for every b. Averaging b gradients reduces the noise term from Lησ2 to Lησ2/b; the deterministic term 2(f(x0)−finf)/(ηT) is unchanged.
Counterexample mode
When sampling breaks the argument
Without replacement inside a minibatch. Draw bdistinct indices uniformly, with 2≤b≤n. Each single index is still uniform, so gˉk is still unbiased. The cross terms, however, no longer vanish. For distinct i=m chosen uniformly,
So E∥j∑ej∥2=bV−b(b−1)n−1V=bVn−1n−b, and the conditional variance is bV⋅n−1n−b. The factor n−1n−b is the finite-population correction. The result is still smaller than V/b, but the derivation is different.
Without replacement across steps. Suppose instead the indices are reshuffled once and then used in order. Take n=2 with the example functions below. If I0=1, then I1=2 is forced, and g1=x1+1=∇f(x1)=x1 given F1. Conditional unbiasedness fails, so the theorem above does not apply. Such schemes need a different analysis.
Nonuniform sampling without reweighting. Use the example functions below. Suppose that at x=0 the method picks f1 with probability 3/4 and f2 with probability 1/4. Then
Eg=43(0−1)+41(0+1)=−21=0=∇f(0).
From the exact minimizer, the expected step moves the point by +η/2. If these probabilities are used at every x, the method is effectively running SGD on 43f1+41f2=21x2−21x+21. That function is minimized at x=1/2, which is the wrong point. The remedy is reweighting. Let positive probabilities qi sum to one, be Fk-measurable, and satisfy P(Ik=i∣Fk)=qi. If g=∇fIk(xk)/(nqIk) is integrable, it is conditionally unbiased, even when q depends on xk: i∑qi⋅nqi∇fi=∇f. A separate conditional variance bound is still required.
The finite-population factor is easy to check by enumerating a small case.
Worked example 3.3.5
(The finite-population factor on three data points)
Take n=3 and suppose that at the current point the deviations di=∇fi(xk)−∇f(xk) are the scalars d1=−2, d2=0, d3=2. They sum to zero, and V=31(4+0+4)=38.
With replacement, b=2. By the proposition, the averaged deviation has variance V/b=34.
Without replacement, b=2. The three unordered pairs are equally likely and give averaged deviations 21(d1+d2)=−1, 21(d1+d3)=0 and 21(d2+d3)=1. Their mean is 0 and their variance is 31(1+0+1)=32. The formula gives bV⋅n−1n−b=34⋅21=32, in agreement.
Edge case b=n=3. Without replacement the batch is the whole dataset, so the averaged deviation is 31(d1+d2+d3)=0 every time, and the factor n−1n−b=0 predicts exactly this. With replacement the variance is still V/3=98, because repeated indices remain possible.
Common mistake
(Unbiased on average is not unbiased at the current point)
In the reshuffled scheme with the example functions below, I0 is uniform and I1 is the other index. The error e1=g1−∇f(x1) equals +1 if I0=1 and −1 if I0=2, so Ee1=0: the estimate is unbiased on average. The proof, however, needs E⟨∇f(x1),e1⟩=0, and x1 depends on I0: it equals (1−η)x0+η if I0=1 and (1−η)x0−η if I0=2. Hence
E[x1e1]=21[(1−η)x0+η]−21[(1−η)x0−η]=η=0.
Unconditional unbiasedness does not remove the cross term; unbiasedness given Fk does.
A worked one-dimensional example
Let f1(x)=21(x−1)2 and f2(x)=21(x+1)2. Then
f(x)=21(f1+f2)=21x2+21,
with ∇f(x)=x, L=1 and finf=21. A uniform single index gives g=x−1 or g=x+1, each with probability 21. Its mean is x and its variance is 21(1)+21(1)=1 for everyx, so σ2=1 holds uniformly.
Worked example 3.3.6
(A step from the minimizer goes uphill)
Take x0=0 and η=21. The full gradient is ∇f(0)=0. The two possible steps are
x1=0−21(0∓1)=±21.
Both outcomes give f(±21)=21⋅41+21=85>21=f(x0). The realized objective increases with probability one. The one-step bound predicts Ef(x1)≤21−0+21⋅(1/4)⋅1=85, and here it holds with equality. Two facts make it exact: f is quadratic with curvature exactly L, so the descent lemma is an equality, and the slack between 1−Lη/2 and 21 multiplies ∇f(x0)=0.
With b independent indices drawn with replacement, the variance is 1/b. The expected increase becomes 8b1.
Worked example 3.3.7
(An exact noise floor)
Write gk=xk+εk, where εk=±1 with equal probability and εk is independent of Fk. Then
xk+1=(1−η)xk−ηεk,0<η≤1.
Let ak=Exk2. Squaring the recursion, the cross term is E[xkεk]=E[xkE[εk∣Fk]]=0. Hence
ak+1=(1−η)2ak+η2,a0=0.
Unrolling gives a geometric sum, ak=η2j=0∑k−1(1−η)2j. Its ratio is (1−η)2, and 1−(1−η)2=η(2−η). Therefore
Exk2=2−ηη[1−(1−η)2k]⟶2−ηη>0.
Here ∥∇f(xk)∥2=xk2. The averages T1k<T∑ak therefore also tend to 2−ηη, because averages of a convergent sequence share its limit. The theorem's bound in this case is 0+Lησ2=η, since f(x0)=finf. For η=21 the true limit is 31 and the bound is 21. The floor is real and strictly positive, and the bound overestimates it by the factor 2−η≤2.
This clean recursion depends on special structure: the noise εk has the same distribution at every x. For general finite data, the noise ∇fI(x)−∇f(x) changes with x, and no such exact formula is available without further assumptions.
Exercises
Exercise 3.3.8
(In the example, use b=2 indices drawn with replacement. List the distribution of gˉ at a point x and compute its conditional variance. Then repeat with two distinct indices.)
Foundation
Solution(3)
1
Enumerate the ordered pairs
There are four equally likely ordered pairs. The pair (1,1) gives gˉ=x−1, the pair (2,2) gives x+1, and each of (1,2) and (2,1) gives x. So gˉ equals x−1 with probability 41, x with probability 21, and x+1 with probability 41.
2
Compute mean and variance
The mean is x. Since V=1, the variance is
41(1)2+21(0)2+41(1)2=21=bV.
3
Distinct indices
With distinct indices, gˉ=x always, so the variance is 0. This agrees with bV⋅n−1n−b=21⋅0.
Exercise 3.3.9
(Take η=21 and x0=0 in the example. Find the distribution of x2, then Ex22 and Ef(x2). Check the one-step bound from k=1 to k=2.)
Core
Solution(4)
1
Distribution of x2
With η=21, x1=−ε0/2 and x2=21x1−21ε1=−4ε0−2ε1. The four sign combinations give x2∈{±43,±41}, each with probability 41.
2
Second moment and expected objective
Ex22=21⋅169+21⋅161=165,
which matches the formula 31(1−161)=165. Next, Ef(x2)=21⋅165+21=3221.
3
Check the one-step bound
Ef(x2)≤85−41⋅41+81=3220−2+4=3222,
and indeed 3221≤3222.
Because: Ef(x1)=85 and E∥∇f(x1)∥2=Ex12=41.
4
Locate the gap
The exact step uses the factor η(1−η/2)=83 instead of 2η=41, and 3220−3+4=3221. The gap of 321 is exactly the slack introduced by replacing 1−Lη/2 with 21.
Exercise 3.3.10
(Suppose f(x0)−finf=10, L=4, σ2=9 and T=1000. (a) Evaluate the bound for η=81. (b) Evaluate it with minibatches of size 9 drawn with replacement, assuming the single-index variance bound 9 holds uniformly. (c) Find the step size that minimizes the bound for this T.)
Core
Solution(3)
1
(a) Evaluate the bound
The step is admissible, since 81≤41=L1. The bound is
(1/8)⋅10002⋅10+4⋅81⋅9=0.16+4.5=4.66.
So for uniform random R, E∥∇f(xR)∥≤4.66≈2.159, and P(∥∇f(xR)∥2≥10)≤0.466.
2
(b) Minibatches of size 9
The variance becomes 9/9=1, so the bound is 0.16+4⋅81⋅1=0.66. This costs 9000 component gradients instead of 1000.
3
(c) Optimize the step for fixed T
Minimize ηT2Δ+Lησ2, where Δ=10. Setting the derivative to zero gives
η∗=TLσ22Δ=3600020=18001≈0.02357≤41.
At η∗ both terms equal 36η∗≈0.8485, so the bound is ≈1.697. This tuning depends on T. It is not a convergence statement.
Exercise 3.3.11
(In the example, sample I=1 with probability q1=43 and I=2 with probability q2=41, independently of the past. Use g=∇fI(x)/(2qI). Show that g is unbiased, compute its conditional variance, and decide whether the theorem's variance hypothesis holds on R.)
Synthesis
Solution(3)
1
The two values of g and their mean
If I=1, then g=3/2x−1=32(x−1). If I=2, then g=1/2x+1=2(x+1). The mean is
43⋅32(x−1)+41⋅2(x+1)=21(x−1)+21(x+1)=x,
so g is unbiased.
2
Conditional variance
The deviations from the mean are 32(x−1)−x=−3x+2 and 2(x+1)−x=x+2. Hence
As a check, the second moment is 31(x−1)2+(x+1)2, and subtracting x2 gives 3x2+4x+4.
3
Decide the global hypothesis
At x=0 the variance is 34, which exceeds the uniform-sampling value 1. Moreover, 3(x+2)2 is unbounded on R, so no finite σ2 works globally. Reweighting restores unbiasedness, but a poorly chosen q can destroy the global variance bound. This calculation alone does not rule out a bound along a particular iterate sequence.
Summary
The stochastic analysis rests on two conditional facts. First, unbiasedness at the current point turns the linear term of the descent lemma into −η∥∇f(xk)∥2. Second, the exact identity E[∥gk∥2∣Fk]=∥∇f(xk)∥2+E[∥gk−∇f(xk)∥2∣Fk] isolates the noise. Telescoping then bounds the average expected squared gradient by a term of order 1/(ηT) plus a constant-step noise term Lησ2.
Independent minibatches divide that noise term by b. Other sampling schemes, such as sampling without replacement, reshuffling, or nonuniform sampling, each need their own check of unbiasedness and variance before the theorem can be used.