Gradient Descent Bound

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.

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.

• Treating every stochastic vector v_t as a subgradient of f at w(t).

  The source gives the subgradient relationship for the expected value of v_t, not for the particular stochastic vector itself.

  Fix: First distinguish v_t from its expected value. Then use the fact that the expected value belongs to the subgradient set at w(t).

• Reusing the gradient descent equation without changing the level of analysis.

  The stochastic update does not provide the same direct subgradient relationship at each iteration.

  Fix: Replace the direct argument with an expectation-based analysis.

• Claiming that stochastic gradient descent has no useful bound.

  A similar bound can still be derived for the expected output of stochastic gradient descent.

  Fix: State 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.

Practice the Distinction

Summary

1. The stochastic vector v_t is not assumed to be a subgradient of f at w(t).
2. The expected value of v_t belongs to the subgradient set of f at w(t).
3. This expectation-based relationship prevents direct reuse of the gradient descent equation.
4. A similar bound can nevertheless be derived for the expected output of stochastic gradient descent.
5. The 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.