Motivation
A stochastic gradient is useful because its computation can be cheaper than that of a complete gradient. Its randomness also changes what a convergence statement can reasonably promise. A single update can increase the objective, and the last iterate can fluctuate even when a carefully chosen average has a small expected gap. To understand the guarantee, we must specify what is known before each update, what is averaged, and whether an assumption bounds noise variance or the entire gradient second moment.
The basic convex argument measures squared distance to an optimizer. Projection helps preserve feasibility and can only improve the distance comparison. Convexity then converts a gradient inner product into an objective gap. Strong convexity contributes an additional distance term, which can be used more efficiently than in the ordinary convex proof. The correct decreasing steps and weights make these extra terms cancel exactly.
We will develop that cancellation rather than merely quote a faster rate. It explains why later iterates receive larger weights and why the first iterate does not appear through an unexplained initial-distance constant. The result concerns expected optimization error for a fixed objective. Population generalization, biased data sampling, and conclusions about an individual noisy trajectory require separate arguments.
Definitions
Definition 18.1.1
(History, unbiasedness, and two different moment bounds)
Let be nonempty, closed and convex. Suppose is differentiable and convex on an open neighborhood containing , and attains its minimum over at . Choose deterministic . A filtration describes the history before update ; is -measurable. The oracle output is -measurable and satisfies
We separately assume a full conditional second-moment bound along the iterates. A sufficient condition is on , with .
Indeed the centered noise has zero conditional mean, so the cross term vanishes when expanding its squared norm. The variance bound alone cannot supply the full bound unless the mean gradient is also controlled. A globally strongly convex function on the whole Euclidean space cannot have a globally bounded gradient; bounded feasible sets often make these assumptions compatible. More generally, the theorem needs the stated full bound only along the actual iterates.
The update is , with deterministic positive steps. Projection is the nearest point in Euclidean distance. For nonnegative deterministic weights with positive sum, the weighted average is . It is feasible by convexity of .
The faster rate below needs one more hypothesis, a uniform curvature lower bound on the feasible set.
Definition 18.1.2
(Strong convexity on )
Let . The function is -strongly convex on if
The optimizer can lie on the boundary, so its ordinary gradient need not vanish. Nothing below assumes an unconstrained stationary equation at that optimizer.
Theorem/Proposition
Theorem 18.1.3
(Convex averaging with a declared second moment)
Under the stated oracle assumptions, with , constant step , and ,
If , choosing gives . For varying deterministic steps, the step-weighted average satisfies
Theorem 18.1.4
(A strong-convexity rate without an unexplained logarithm)
If is also -strongly convex, set and use the different weighted average
Then
The strong average is weighted by increasing indices, not by decreasing steps. Substituting it into the first theorem would not prove the second. The proof instead uses strong convexity before summing and chooses weights to match the resulting distance coefficients. No smoothness constant or almost-sure convergence claim is part of these statements.
Proof sketch or proof idea
Proof
(Projected distance recursion and the convex averages)
Let . Since the segment from to any is feasible, differentiating the squared-distance objective at its minimum gives . Expanding then proves . With , every realized update therefore satisfies
Take conditional expectation. The current displacement is already known given , so unbiasedness replaces inside the inner product by . Convexity bounds this inner product below by . Taking total expectations and writing , , gives
Sum without dividing by the varying step. The distances telescope, the final squared distance is nonnegative, and convexity gives . This proves the varying-step formula. Equal steps give the arithmetic-average formula; minimizing its two-term upper bound gives the prescribed horizon-based step. Degenerate cases or can be treated directly rather than inserting zero into a step required to be positive.
The proof works at three distinct levels: a deterministic inequality for each realized projection, an average over the new noise given the current history, and finally a total expectation over the whole history. Treating the current point as a fixed non-random number from the start would hide its dependence on earlier samples; taking only unconditional averages would not remove the correlated inner-product term. The filtration is what makes each step legitimate.
Proof
(Weighted telescoping under strong convexity)
Use the strong-convexity inequality with and . Rearrangement strengthens the inner-product lower bound by , and the same conditional-expectation step as before gives
Insert and divide by :
Multiply by . The positive coefficient of is , exactly the negative coefficient left by the preceding index. At the positive initial coefficient is zero. Summing leaves
Divide by , the sum of the weights, and apply convexity to the corresponding average. This proves the stated rate.
Proof X-ray
Which hypothesis acts where in the weighted telescoping
Measurability of with respect to is used once: it lets the displacement leave the conditional expectation, so unbiasedness removes the noise from the inner product. The noise is not removed from ; that term is exactly where the full moment , not the variance , is needed. Projection is used pathwise, before any expectation, so no independence between projection and oracle is required.
The non-obvious move is the pairing of steps and weights. Strong convexity turns the coefficient of into after division, and the weight makes it equal to the coefficient that the previous index leaves with a minus sign. The sum closes because the first coefficient is , which is why never appears (the moment constant still depends on where the iterates can lie), and the last term is dropped as nonpositive.
The weights also decide the noise total. With equal weights the distance coefficients still have the right sign, but the noise contributes , which grows like ; dividing by gives a bound of order . The weight turns each noise term into , and the logarithm disappears.
Choosing an output and interpreting a rate
The theorem specifies an output that an implementation must actually compute. For the strong average, an accumulator can store the weighted sum and total weight; it does not need the entire trajectory. However, replacing that accumulator by the final iterate changes the mathematical object. A last-iterate theorem may be available under further assumptions, but it is not proved by this averaging argument.
The objective here can be an empirical loss or a population expectation accessible through an unbiased oracle. These are different uses of the same optimization theorem. If fresh samples estimate a population gradient, independence must hold conditionally on the current history. If an algorithm cycles deterministically through a finite dataset, the next component gradient need not be an unbiased estimate of the full empirical gradient given that history.
An upper bound can also be conservative. The uniform controls every conditional second moment encountered by the proof; it need not equal the moment near the solution. A decreasing noise level or a more local gradient estimate may support a better analysis. Until such an analysis is supplied, substituting an observed small gradient for the uniform constant is not justified.
From an objective gap to a distance guarantee
Concept lensGeometric
Objective accuracy and location
Strong convexity also explains what the expected gap says about location. At the constrained minimizer, differentiating every feasible segment gives . Apply strong convexity at that point to conclude . The weighted-output theorem therefore implies expected squared distance at most . This conclusion concerns the specified weighted output, just as the objective bound does. It is not obtained by asserting that a boundary gradient is zero.
The step schedule requires a valid positive curvature lower bound. If only a certified smaller bound is known, it can replace in both the proof and schedule, giving a weaker but valid guarantee. A curvature estimate at a single observed point does not establish strong convexity on the feasible set. In particular, a noisy Hessian estimate cannot be treated as a global certificate without additional control. The theorem's constants encode information about the objective, rather than quantities the algorithm is automatically entitled to know.
Counterexample mode
The schedule needs a true curvature constant
Claim: running the schedule with some gives the strong rate for any convex . Take on , exact gradients (so ), and . The steps are , so and . For the weighted output is , its gap, while the claimed bound is . A linear function is -strongly convex for no ; the repair is to use a valid lower bound , and otherwise only the convex theorem applies.
The same quadratic growth inequality also proves uniqueness of the constrained optimizer: any second minimizer would have zero gap and hence zero distance from the first. Existence was assumed separately and is not a consequence of this uniqueness argument.
Worked examples
Worked example 18.1.5
(Projection and a boundary optimizer)
Take on , deterministic oracle , , and . Here . Then and . The theorem's two-iterate average uses , hence equals . Its bound is . The optimizer is zero and its derivative is one, so an unconstrained zero-gradient test would miss this perfectly valid minimum. Projection makes the second step feasible by truncating a proposed negative point.
Worked example 18.1.6
(A strongly convex noisy mean problem)
Let take and equally likely, , and . Its optimizer is one, strong-convexity parameter is one, and . A fresh sample gives , with noise variance four and mean gradient bounded by two, so suffices. Starting at , draws with steps give , . The weighted output is , whose realized gap is . The theorem bounds expected gap over all possible draws, not each realized gap. At its guaranteed expected gap is at most .
Worked example 18.1.7
(Variance alone is not a full moment)
For on the real line, use with independent mean-zero noise of variance one. At , the conditional variance is one but the full second moment is . Using in the theorem would discard the entire mean gradient. On a bounded feasible interval , the sufficient replacement is . This is also why a noise estimate gathered close to the optimizer cannot automatically certify every earlier update.
Common mistakes
Counterexample mode
Unconditional centering does not control a history-dependent inner product
Suppose the current point is equally likely to be or , the objective is identically zero, and an oracle returns . Its unconditional mean is zero, the same as the expected true gradient. Yet given the current history its mean is , and , rather than zero. The distance proof needs conditional unbiasedness at the actual point; unconditional cancellation is insufficient.
Strong convexity does not make a noisy update decrease the objective on every realization, and knowing that the objective is convex does not establish a usable uniform moment constant. Each ingredient has a distinct role. Finally, a rate in oracle calls is not automatically a rate in wall-clock time when oracle costs differ between methods.
Common mistake
(Reporting the last iterate or the wrong average)
The strong-convexity theorem bounds , whose weights grow like . Reporting , the plain average , or the step-weighted average (whose weights decrease like ) changes the object; none of them is covered by this proof. The step-weighted average is the right output only for the convex theorem.
Common mistake
(Using the noise variance as the moment constant)
The quadratic term of the recursion is . Substituting for drops , which is large far from the optimizer, as the variance example shows. Use with a gradient bound valid wherever the iterates can lie.
Summary
Projection controls realized distances, conditional unbiasedness handles the first-order noise term, and a full second-moment bound controls the remaining quadratic term. Ordinary convexity yields a step-weighted rate. Strong convexity supports a different cancellation and an increasing-weight output with expected gap of order .
Exercises
Quick check
(Why must the varying-step proof sum before dividing by the step? Write the bound for weights in terms of and .)
Solution · Answer
Before division, the distance term is and telescopes exactly. Dividing by differing steps first produces unequal neighboring coefficients and requires additional analysis. The resulting direct bound is for the average weighted by .
Quick check
(For and , list the steps and normalized strong-average weights. Identify the coefficients that cancel at .)
Solution · Answer
The steps are , that is , while the normalized output weights are , that is . At , the negative weighted coefficient is , and the positive coefficient is . They cancel. The output includes , not .
Quick check
(Suppose the conditional noise variance is at most nine and the mean gradient norm is at most four. Find a sufficient and the optimized convex bound when , .)
Solution · Answer
Conditional centering gives , hence . The step is , and the optimized expected-gap bound is . This can be conservative; its validity does not imply the actual error equals one.
Quick check
(Minimize on . Show that its boundary optimizer is compatible with the strong-convexity inner-product inequality used in the proof.)
Solution · Answer
The optimizer is zero and its derivative is one. For feasible , the gap is , and . Since , this equals the gap plus , exactly the strong inequality used above. No vanishing gradient at the constrained optimizer is needed.