Motivation
A finite-horizon bound says how accurate an average iterate is after a prescribed number of updates. It does not by itself say that one infinite run settles at the minimizer. To study the latter question, we must control the noise accumulated over all future updates, not just the noise in one step. A decreasing learning rate offers a compromise: its sum must be infinite so that the algorithm can keep correcting an initial error, while the sum of its squares must be finite so that the total conditional variance can be controlled.
The conclusion below concerns a single sequence of iterates, with probability one. It is different from a guarantee for the expectation of an average. We prove a useful version under strong convexity and a bounded second moment; these conditions are sufficient, not a definition of all situations in which SGD converges.
Definitions
Definition 23.1.1
(Strong convexity and the projected stochastic-gradient scheme)
Let be a nonempty closed convex subset of . A differentiable function is -strongly convex, for , if for every ,
Let be a filtration representing the information available before update , with measurable with respect to . Given deterministic positive steps , the projected update and the oracle assumptions are
where and is the point of nearest to .
Here is measurable at the next time. The bound is on the full conditional second moment, not merely the variance of . Projection ensures feasibility even when the stochastic step leaves the set. Suppose attains its minimum over at ; the lemma below shows that strong convexity makes this point unique.
Theorem/Proposition
The first result converts strong convexity into the inequality the convergence proof actually uses. It holds at a boundary minimizer, where the gradient need not vanish.
Lemma 23.1.2
(Strong monotonicity at a constrained minimizer)
Let be differentiable and -strongly convex on , and let minimize over . Then is the only minimizer, and for every ,
The main theorem combines this inequality with two conditions on the step sequence.
Theorem 23.1.3
(Convergence of the individual iterates)
Assume the conditions above, is deterministic, and
Then almost surely. For example, with satisfies both conditions precisely when .
The full-moment hypothesis is not automatic on an unbounded domain: a strongly convex quadratic has an unbounded gradient. One may establish the moment bound on a bounded feasible set, or use a different theorem with a growth condition. Nor does almost-sure convergence give a finite-sample confidence interval or a universal convergence rate.
Proof sketch or proof idea
We prove the lemma first, then the theorem.
Proof
(Optimality condition plus two strong-convexity inequalities)
For and , convexity of gives , so is minimized at . Its right derivative there is therefore nonnegative:
Write the strong-convexity inequality once from to and once from to , and add them. The function values cancel, leaving
Adding the optimality inequality gives the lemma. For uniqueness, the inequality from to together with the optimality condition gives whenever .
The theorem's proof reduces everything to the scalar .
Proof
(A one-step inequality, then a supermartingale that pays for future noise)
If and , minimizing the distance to along the segment from to gives , and expanding yields . With and ,
Take conditional expectations given . Since is -measurable, unbiasedness replaces in the inner product by , and the moment bound controls the last term. The lemma then gives, with ,
Define the deterministic tail , which is finite because , and
Each is nonnegative and -measurable. It is integrable, because and is a constant. Using ,
By the nonnegative supermartingale convergence theorem, converges almost surely to a finite limit. The last sum in is nondecreasing and bounded by , so it converges; in particular almost surely. As , also has an almost-sure finite limit . If on some outcome, then for all large there, and would make diverge. Hence almost surely.
Proof X-ray
Pay for all future noise at once
The two step conditions enter at different places. Square-summability is used only to make finite and to send it to zero; divergence of is used only in the last line, to rule out a positive limit. The one-step inequality alone cannot be iterated pathwise, because it holds only in conditional expectation and the noise term keeps arriving.
The key move is to prepay that noise. Adding the whole future budget to absorbs the of each step, and adding the accumulated progress absorbs the , so the sum becomes a supermartingale. This works only because the steps are deterministic: then is a known number and is adapted. Strong convexity supplies the progress term through the lemma, and the projection needs closed and convex with .
The standard supermartingale theorem used here follows from the upcrossing inequality: a nonnegative supermartingale has finite expectation uniformly in time, so infinitely many crossings of any fixed rational interval have probability zero; its liminf and limsup must coincide. We use it for a scalar bookkeeping process, not as an assertion that the iterates themselves are supermartingales.
Worked examples
Worked example 23.1.4
(A noisy quadratic becomes a sample mean)
Let , , , and , where independent take values and with equal probability. Take (trivial at ) and . The oracle is conditionally unbiased, , and on . The unprojected recursion gives, by induction,
The right side lies in , so projection never changes it. Its expectation is zero and : the cross terms vanish by independence and centering. The theorem gives almost-sure convergence to zero; the displayed second moment describes a separate finite-time average over runs.
Worked example 23.1.5
(Choose a power schedule)
For , the -series test gives and . Thus the theorem applies when its other assumptions hold. In contrast, fails the square-summability condition and fails the infinite-sum condition. Failure of a sufficient condition alone does not prove that every problem with that schedule diverges.
Worked example 23.1.6
(A boundary minimizer reached through the projection)
Let , , exact gradients , and . Here , on , and the constrained minimizer is , where . The first step gives . From then on , so for every . Without projection the same recursion gives and then : it settles at the unconstrained minimizer, outside . In the constrained problem the iterates converge although the gradient tends to , not to .
Common mistakes
Counterexample mode
A finite total step can freeze an error
Even without noise, take on , and . Then , and the iterates converge to the strictly positive product . Indeed, the logarithms have a finite sum because for . Every step decreases the objective, but the finite total movement cannot guarantee reaching the minimizer.
A constant step has the opposite difficulty. In the noisy quadratic example without active projection, a fixed gives , whose limit is . This noise floor shows why a fixed-step last iterate need not converge in mean square. It does not say that every constant-step problem fails: zero noise changes the conclusion.
Common mistake
(Expecting the gradient to vanish at the limit)
The theorem concerns for a minimizer over . When lies on the boundary, need not be zero; in the boundary example it equals . A stopping rule of the form “stop when the stochastic gradient is small” can then never trigger, and the inequality used in the proof is the lemma, not .
Common mistake
(Reading the conditional inequality as a pathwise decrease)
The inequality holds in conditional expectation only. Individual distances can increase: in the noisy quadratic example , but gives . This is why the proof needs a supermartingale argument rather than a deterministic recursion along each run.
Summary
Infinite total step length supplies persistent correction; finite squared step length makes the accumulated error term summable. Under conditional unbiasedness, bounded full second moment and strong convexity, the supermartingale argument combines these facts into almost-sure convergence of the individual projected iterates.
Exercises
Quick check
(For , determine all that meet both step conditions. Does multiplying by change the answer?)
Solution · Answer
The -series criterion requires for the first sum to diverge and for the second to converge. Thus . Multiplying by a positive finite constant changes neither classification.
Quick check
(In the noisy quadratic example, compute and .)
Solution · Answer
, so . It equals one exactly when all three signs are , with probability .
Quick check
(Let and . Find its constrained minimizer and verify the lemma's inequality at a general with .)
Solution · Answer
The minimizer is , even though . For , . The boundary optimality inequality supplies the extra nonnegative term .
Quick check
(For the constant-step quadratic recursion in the common-mistakes section, derive the limiting second moment from the scalar recurrence.)
Solution · Answer
Writing , centering and independence give . Since , the geometric multiplier is below one, and the fixed point is .