Motivation
Empirical risk minimization specifies a destination but does not supply a way to reach it. Even a well-behaved statistical class can produce a large optimization problem. For a finite sum of losses, one can compute the complete gradient by visiting every observation, or estimate it from a randomly selected observation. The first choice uses more work per step. The second introduces fluctuations that must be controlled over time. A useful comparison therefore asks what is guaranteed after a fixed amount of computation and under which assumptions.
There are several possible destinations. For a differentiable convex function, a zero gradient identifies a global minimizer. For a nonconvex function, a small gradient can merely identify a nearly stationary point, possibly near a saddle or a maximum. Meanwhile, minimizing training loss does not establish that the selected predictor has small population risk. Optimization and generalization interact, but their conclusions answer different questions. We will keep those conclusions separate in both the deterministic and stochastic arguments.
The central tool is a squared distance to a comparator. Expanding its change produces a useful inner product, and convexity relates that inner product to an objective gap. Smoothness supplies a second way of measuring progress, through the change in the objective itself. These elementary identities explain why averaging appears in stochastic methods and why an unbiased noisy gradient can still fail to decrease the loss at an individual step.
Definitions
Definition 2.1.1
(Convexity and smoothness)
A differentiable function is convex if
Its gradient is -Lipschitz, or is -smooth, if and
Convexity is a global statement about tangent planes. Smoothness limits how fast a gradient can change; it does not assert convexity. For a twice continuously differentiable function, a uniform Hessian bound in operator norm implies smoothness. A convex quadratic with symmetric matrix is smooth with when this eigenvalue is positive. If every direction has zero curvature, any positive upper bound also serves.
Deterministic gradient descent is , with fixed step . For stochastic descent on a nonempty closed convex set , choose the initial point deterministically. Let contain all randomness revealed before step . The current iterate is -measurable. An oracle returns satisfying
The second condition bounds the entire second moment, not just the variance. The projected update is , where is the unique point of minimizing Euclidean distance to . Closedness, convexity, and nonemptiness guarantee existence and uniqueness in finite dimensions. Projection can be omitted when and the stated oracle moment bound remains valid along the iterates.
For a finite empirical objective , a fresh uniform index gives the unbiased estimator . Uniformity and freshness are assumptions, not consequences of calling a method stochastic. With probabilities , the unbiased estimator is instead .
Concept lensAnalytic
A projected step minimizes a linear model plus a proximity penalty
Completing the square shows that
Each step trusts the linear model given by the sampled gradient only within a distance governed by , and stays feasible. Written this way, the step size is a weight on proximity to the current point, which is why both proofs track the squared distance .
Theorem/Proposition
Theorem 2.1.2
(Smooth descent and a convex objective rate)
Suppose is differentiable and -smooth on . For ,
If in addition is convex, attains its minimum at , and , then for ,
Theorem 2.1.3
(Projected SGD with an unbiased bounded-second-moment oracle)
Suppose is differentiable and convex on , minimizes it over , and the oracle assumptions above hold. Set and . For a fixed ,
When , choosing makes this at most .
Smoothness is not required for the second theorem. The oracle condition is stronger than unbiasedness alone and must be checked in the actual problem. The step selected for a known horizon is constant during that run. This is different from a theorem for a decreasing sequence of steps; the proof below does not automatically establish almost-sure convergence of every iterate.
Proof sketch or proof idea
The deterministic proof uses smoothness for the decrease and convexity for the gap.
Proof
(Descent inequality, then a telescoping distance)
Write . Integrate the derivative of and subtract the linear term:
Substitute to obtain the descent inequality. It guarantees strict decrease at a nonstationary point when . The more restrictive interval will make the distance argument particularly simple.
For a convex objective, convexity bounds by . Combining this with smooth descent, for , gives
To verify the right-hand side, expand the new squared distance: it equals the inner product just written minus . Sum from to . Distances telescope, while monotonicity gives . Discard the final nonnegative squared distance to finish the deterministic rate.
The stochastic proof cannot rely on monotone decrease, so it keeps only the distance argument.
Proof
(Projection, conditioning and averaging)
Projection preserves the useful distance inequality. If , minimizing along the segment from to any gives . Expanding then gives . Apply this with :
Conditioning on replaces in the inner product by , because the comparator and current iterate are already fixed given this information. Convexity supplies the objective gap, and the second-moment assumption bounds the final term. After taking total expectations and summing, we obtain
Convexity once more gives . This explains exactly which average the theorem controls: it includes through , rather than silently replacing it by a last iterate.
Proof X-ray
Each oracle assumption enters exactly one term
Smoothness never appears in the stochastic proof; the only object tracked is . The projection step needs closed, convex and nonempty and needs : then moves no point farther from , so projection can be ignored in the expansion. Expanding the square produces two random terms. The cross term is handled by conditional unbiasedness, which requires to be known given ; the quadratic term is handled by the second-moment bound, which is why a variance bound alone is not enough.
Convexity is used twice: once to turn into the gap , and once, through Jensen's inequality, to pass from the average of gaps to the gap at the average point. The key move is that the distance terms telescope without any monotonicity of , which noisy steps do not have. The price is that the conclusion concerns , not .
What remains true without convexity
For a smooth function bounded below by , the descent inequality at still telescopes to
No convexity was used in this assertion. It controls stationarity, not the gap to a global minimum. For example is not globally smooth on the whole real line, but it illustrates the logical issue: at its gradient vanishes although the objective is one above its global minimum. A globally smooth example is ; starting at zero gives a stationary global maximum with value two. A theorem about small gradients cannot rule out that initialization.
Counterexample mode
Without convexity the rate for the gap fails
Claim: for an -smooth function with a minimizer and , gradient descent satisfies . Take , which has and so is -smooth, with and . Then , so for every and . The claimed bound is , which is below as soon as . The descent inequality and the gradient-norm bound remain true here; only the gap rate needs the convexity hypothesis.
Reading the two terms in the stochastic bound
The distance term decreases as the run becomes longer at a fixed step, whereas the second-moment term increases with that step. A small step suppresses the influence of a single noisy update but spends more iterations moving away from the initial point. The horizon-based choice balances these two contributions; it is obtained by minimizing the displayed upper bound, not by asserting that every real trajectory follows that expression exactly.
The average is feasible because the feasible set is convex. If feasibility meant belonging to a nonconvex discrete set, averaging feasible points might leave that set and the last step of the proof would fail. Projection onto a nonconvex set can also have several nearest points and need not satisfy the comparator distance inequality used above. These details explain why the theorem explicitly requires a closed convex set instead of treating projection as an arbitrary repair operation.
Every expectation covers both the earlier sampled indices and the fresh noise at the current step. Conditioning on the history before taking the total expectation is not a formality: it makes the current position, although random, a known quantity for the analysis of that step. If a sampling rule uses the history to change the index probabilities, unbiasedness and the second moment must be rechecked with the true conditional probabilities; the uniform-sampling calculation cannot simply be reused.
In applications the comparator distance may be unknown. A known upper bound can replace it throughout the proof and in the step choice. A bound on the diameter of a bounded feasible set is one such option. The resulting guarantee may be conservative, but every constant then has a clear mathematical origin.
Worked examples
Worked example 2.1.4
(Curvature decides a safe deterministic step)
Consider , , . The minimum is zero at , and . With and , the error recurrence is . Thus and . The objective values are , , and . Both coordinates improve, but the first improves slowly. If , the second error multiplier becomes , so that coordinate alternates and grows. The direction of the negative gradient does not justify any chosen displacement length.
Worked example 2.1.5
(Unbiasedness does not imply a monotone noisy trajectory)
Let and , with fresh independent noise taking and equally often in distribution. Write and . For constant ,
This follows by expanding the square; the cross term has zero conditional expectation. At the exact minimum, the next noisy step moves away with probability one if . For , , the limiting mean squared error is and limiting expected loss is . This exact recurrence concerns last iterates under constant noise. It does not contradict an averaged-iterate theorem with a step shrinking as the prescribed horizon grows.
Worked example 2.1.6
(A finite-sum sampling calculation)
At a particular point, two component gradients are and , so the average gradient is . Uniform sampling gives mean and variance . If the first index is chosen with probability , using the raw component gradient instead gives mean , which points in the wrong direction. Correct importance weighting produces and ; their weighted average is again . Unbiasedness is restored, though variance is now , larger than nine. Importance weighting can change efficiency as well as correctness. With independent uniform samples, averaging unbiased gradients at the same current point divides their noise variance by ; it does not divide the squared norm of their common mean by .
Common mistakes
Common mistake
(Treating an unbiased stochastic step as a descent step)
An unbiased estimator has the correct conditional mean. It need not be close to the gradient in any one realization, and its negative need not be a descent direction at that realization; the noisy scalar example moves away from the exact minimum with probability one. Conditioning matters because the current parameter depends on earlier random indices. An estimator whose unconditional mean happens to be correct at the first step need not remain unbiased later.
Common mistake
(Substituting a variance bound for the second-moment bound)
The SGD theorem bounds the second moment by . A variance bound alone permits a very large deterministic gradient and cannot simply be substituted for . If and conditional noise variance is at most , then , so is sufficient. On a compact feasible set, continuity and bounded component gradients often make such a condition easy to verify.
Common mistake
(Comparing the two rates by iteration count alone)
A full finite-sum gradient costs roughly component evaluations, whereas one SGD step costs one. A comparison in iterations alone may therefore be misleading. Conversely, lower work per step is not a proof that SGD always reaches a requested tolerance faster. Geometry, variance, implementation, and the requested accuracy matter.
Summary
Smoothness controls objective change, convexity links a gradient inner product to a global gap, and conditional unbiasedness makes the distance argument work in expectation. Each assumption has a visible role in the proof. Averaging and the step-size tradeoff manage stochastic fluctuations, while statistical generalization remains a separate question about the predictor returned by optimization.
Exercises
Quick check
(For the quadratic in the first example, find the exact interval of constant steps giving convergence from every starting point, and explain the boundary at the largest permitted step.)
Solution · Answer
The error multipliers are and . Both must have absolute value below one, so . At the second multiplier is ; a nonzero second-coordinate error alternates without shrinking. The theorem's interval is sufficient for its simple rate but is not the exact stability interval of this quadratic.
Quick check
(Under the SGD theorem, take , , . Find the prescribed step and bound. How many iterations does this bound require for expected gap at most ?)
Solution · Answer
The step is , and the bound is the same number. Requiring gives . This uses a known bound on the initial distance and the full oracle second moment, not a variance-only estimate.
Quick check
(In the noisy scalar example set , , and . Calculate , and the limiting expected objective value.)
Solution · Answer
Here and . Hence and . The limit is , so the expected objective tends to . The initial expected loss is ; with this noise level, it rises toward the constant-step noise floor.
Quick check
(Two independent oracle noises at the same point have mean zero and variance . Find the variance of their average, and explain why the same calculation generally fails for two successive SGD steps.)
Solution · Answer
The variance is , because independence makes the cross covariance zero. Successive SGD gradients are evaluated at different random points, and the second point depends on the first noise. They are not two independent copies of the same fixed-point oracle, so a fresh conditional analysis is required.