Gradient Descent Bound
In the deterministic gradient descent argument, the update supports a direct bound for the algorithm.
Why the Proof Must Change
The important distinction is not whether stochastic gradient descent can be analyzed. It can. The distinction is the level at which the useful subgradient relationship is available. In the deterministic gradient descent argument, the update supports a direct bound for the algorithm. In the stochastic setting, the vector used at iteration t is v_t, and that particular vector is not assumed to be a subgradient of f at w(t). Instead, the relationship appears after taking an expected value.
Tracing the Stochastic Vector
At iteration t, think of v_t as the vector produced for the stochastic step. The source does not give permission to treat this particular vector as a subgradient of f at the current point w(t). The useful statement concerns its average behavior: the expected value of v_t belongs to the subgradient set of f at w(t). Thus, the analysis must distinguish the individual random vector from the expected vector obtained by considering its randomness.
Separating one draw from its expectation
Suppose v_t is the vector produced at iteration t of a stochastic method. What relationship is available for analyzing the method?
- 1Identify the per-step object
The per-step object is the particular stochastic vector v_t used at iteration t.
- 2Avoid the unsupported shortcut
Do not assume that this particular v_t is itself a subgradient of f at w(t). The source does not make that assumption.
- 3Take the expected value
Move from the individual stochastic vector to its expected value.
- 4Apply the available relationship
The expected value of v_t belongs to the subgradient set of f at w(t).
The subgradient relationship is available after taking the expectation, not as a direct relationship for the individual stochastic vector.
Where Direct Reuse Fails
The earlier gradient descent equation depends on a direct relationship between the vector used by the update and the subgradient condition at the current point. In stochastic gradient descent, the vector used at an iteration is v_t, but the source provides the subgradient relationship only for the expected value of v_t. Because the relationship has moved from an individual update to an expectation, the gradient descent equation cannot be copied and applied directly to the stochastic case.
Common mistake Treating every stochastic vector v_t as a subgradient of f at w(t).
What it looks likeThe vector used at iteration t is assumed to satisfy the same direct subgradient relationship as in deterministic gradient descent.
Why it failsThe source gives the subgradient relationship for the expected value of v_t, not for the particular stochastic vector itself.
Do this insteadFirst distinguish v_t from its expected value. Then use the fact that the expected value belongs to the subgradient set at w(t).
Common mistake Reusing the gradient descent equation without changing the level of analysis.
What it looks likeA deterministic bound is copied directly into the stochastic argument.
Why it failsThe stochastic update does not provide the same direct subgradient relationship at each iteration.
Do this insteadReplace the direct argument with an expectation-based analysis.
Common mistake Claiming that stochastic gradient descent has no useful bound.
What it looks likeBecause the deterministic equation cannot be reused directly, the entire analysis is abandoned.
Why it failsA similar bound can still be derived for the expected output of stochastic gradient descent.
Do this insteadState the guarantee at the expected-output level.
The Expectation-Based Route
The stochastic analysis proceeds in stages. First, consider the stochastic vector produced at the current iteration. Next, take its expected value and use the fact that this expected value belongs to the subgradient set of f at w(t). Finally, formulate the guarantee for the expected output of stochastic gradient descent. This preserves enough of the deterministic structure to derive a similar bound, but the conclusion is no longer obtained by directly reusing the deterministic equation.
| Method | Available relationship | Form of conclusion |
|---|---|---|
| Gradient descent | A direct relationship used in the gradient descent argument | A bound for the algorithm |
| Stochastic gradient descent | The expected value of v_t belongs to the subgradient set at w(t) | A similar bound for the expected output |
The methods aim for related guarantees, but the stochastic argument must pass through an expectation.
Practice the Distinction
A learner says: “Because v_t is used at iteration t, v_t is a subgradient of f at w(t), so the gradient descent equation applies without change.” Identify the incorrect step and replace it with the source-supported reasoning.
Hints
- Separate the individual stochastic vector from its expected value.
- Recall which quantity belongs to the subgradient set at w(t).
- State what kind of output the stochastic bound concerns.
Practice solution
Correct the claim that the deterministic gradient descent equation can be applied directly to v_t.
- 1Locate the error
The claim treats the particular stochastic vector v_t as though it directly supplied the deterministic subgradient relationship.
- 2State the valid relationship
The expected value of v_t belongs to the subgradient set of f at w(t).
- 3Change the analysis
Because the relationship is available after taking an expectation, the deterministic gradient descent equation cannot be reused directly.
- 4State the resulting guarantee
An expectation-based analysis can still derive a similar bound for the expected output of stochastic gradient descent.
The correct argument replaces direct reuse of the deterministic equation with an expectation-based argument and gives a bound for the expected output.
Summary
- 1The stochastic vector v_t is not assumed to be a subgradient of f at w(t).
- 2The expected value of v_t belongs to the subgradient set of f at w(t).
- 3This expectation-based relationship prevents direct reuse of the gradient descent equation.
- 4A similar bound can nevertheless be derived for the expected output of stochastic gradient descent.
- 5The key difference is the level at which the guarantee is stated: deterministic gradient descent has its recalled algorithmic bound, while stochastic gradient descent requires an expected-output bound.
At a glance
- SGD requires an expectation-based analysis rather than a direct copy of the gradient descent argument.
- The expected value of v_t belongs to the subgradient set at w(t).
- The individual stochastic vector does not provide the same direct subgradient relationship.
- A similar bound can still be obtained for the expected output of SGD.