Subgradient
The linear object defined by the subgradient does not merely describe a local direction.
From Direct Steps to Expected Behavior
A deterministic gradient-descent argument can use the vector chosen at an iteration directly. Stochastic gradient descent changes that situation: the vector v_t used at iteration t is stochastic, so the useful subgradient relationship is stated for its expected value rather than for that particular random vector. The main lesson is not that stochastic gradient descent cannot be analyzed. It is that the analysis must move from an individual update to average behavior.
For stochastic gradient descent, the expected value of v_t belongs to the subgradient set at w(t). This is why the deterministic gradient-descent equation cannot simply be copied, even though a similar bound can still be derived for the expected output of the stochastic method.
Tracing the Stochastic Update
At iteration t, start with the current point w(t). The stochastic procedure produces a vector v_t. The source does not assume that this particular vector is itself a subgradient of f at w(t). Instead, it provides a relationship for the average vector E[v_t]. That expected vector belongs to the subgradient set at the current point. The analysis therefore has an intermediate step: random update, expectation, then subgradient relationship.
Why the Deterministic Bound Changes
The gradient-descent bound cannot be applied directly to stochastic gradient descent because the vector used in a stochastic iteration does not provide the same direct subgradient relationship. In the deterministic argument, the relevant relationship is available at the level of the algorithm's chosen vector. In the stochastic argument, it becomes available only after taking an expectation. That change interrupts a direct reuse of the earlier gradient-descent equation.
The analysis does not end with that obstacle. Once the expected stochastic vector is related to a subgradient, enough structure remains to derive a similar bound for the expected output of stochastic gradient descent. The guarantee is therefore stated at a different level: not as an unchanged deterministic statement about one stochastic run, but as an expectation-based statement about the method's output.
Supporting Slopes for Convex Functions
A subgradient is a vector that supplies a lower-supporting linear slope at a point. For a convex function, the geometric picture is a supporting tangent that touches the function at the reference point and remains below the function elsewhere. Convexity is characterized by the existence of such a vector at every point in the domain.
The word supporting is important. The linear object defined by the subgradient does not merely describe a local direction. It provides a lower comparison for the function across the domain. This is what makes the subgradient useful when a function has no single ordinary gradient at a point.
Testing a Candidate Vector
The subgradient inequality is the test for a candidate vector. Given a reference point w and a candidate vector v, form the linear expression f(w) + vT(u - w). The candidate has the required subgradient property at w when f(u) is at least this expression for every point u in the domain.
Checking a Candidate at a Reference Point
Determine the correct procedure for checking whether a candidate vector v is a subgradient of f at w.
- 1Choose the reference point
Fix the point w where the subgradient property is being tested.
- 2Choose a comparison point
Let u be an arbitrary point in the domain. The condition must work for every such u, not just one selected point.
- 3Build the supporting expression
Form f(w) + vT(u - w). This is the linear function determined by the value at w and the candidate slope v.
- 4Compare both sides
Check whether f(u) is at least f(w) + vT(u - w) for every u in the domain.
- 5Conclude from the universal check
If the inequality holds everywhere in the domain, v has the required subgradient property at w. If it fails at any point, v is not a valid subgradient at w.
The subgradient inequality converts the supporting-slope picture into a precise universal test.
Gradient and Subgradient
| Gradient | Subgradient |
|---|---|
| Tied to differentiability at the point | Selected through the supporting inequality |
| Provides the usual gradient-descent direction when available | Provides a descent-method vector even when the function is nondifferentiable |
| Described by the differentiable-function setting | Supports the broader convex-function setting |
The distinction is based on which condition is available at the current point.
Gradient descent is normally described using the gradient of a function. That requirement becomes restrictive at points where the function is not differentiable. A subgradient extends the descent idea by replacing the gradient with a vector that satisfies the subgradient condition. For convex functions, this vector can be understood as the slope of a supporting linear function that remains below the function.
Common Reasoning Errors
Common mistake Treating every stochastic vector v_t as a subgradient at w(t).
What it looks likeThe argument assumes that the vector generated by one stochastic update automatically satisfies the subgradient condition.
Why it failsThe source gives the subgradient relationship for the expected value of v_t, not for the individual stochastic vector.
Do this insteadState the relationship at the expectation level: E[v_t] belongs to the subgradient set at w(t).
Common mistake Copying the deterministic gradient-descent equation into the stochastic case without modification.
What it looks likeThe same bound is applied directly to a stochastic update because both methods use iterative vectors.
Why it failsThe direct subgradient relationship used by the deterministic argument is not available in the same form for the stochastic vector.
Do this insteadInsert the expectation-based step and derive a bound for the expected output of stochastic gradient descent.
Common mistake Checking the subgradient inequality at only one comparison point.
What it looks likeA candidate vector is accepted after the inequality succeeds for one selected u.
Why it failsThe supporting condition must hold for every u in the domain.
Do this insteadTreat u as arbitrary and verify the inequality across the domain.
Common mistake Defining a subgradient only through differentiability.
What it looks likeA vector is rejected because the function has no ordinary gradient at the reference point.
Why it failsSubgradients are introduced precisely to extend the descent discussion to nondifferentiable functions.
Do this insteadUse the supporting inequality to test whether a valid subgradient exists.
Practice the Two Tests
Explain the difference between these two claims: v_t is a subgradient of f at w(t), and E[v_t] belongs to the subgradient set of f at w(t). Then describe the exact steps you would use to test a candidate vector v at a reference point w.
Hints
- Identify whether the statement concerns one stochastic realization or an expected value.
- For the candidate-vector test, introduce an arbitrary comparison point u.
- Form f(w) + vT(u - w) and compare it with f(u) across the domain.
What do you think happens?
A stochastic analysis establishes that E[v_t] belongs to the subgradient set at w(t). Can the earlier deterministic gradient-descent equation be reused directly for the stochastic update?
Reveal answer
No, because the subgradient relationship is available after taking an expectation.
The stochastic vector does not provide the same direct relationship as the deterministic argument. An expectation-based analysis is required, although a similar bound can still be derived for the expected output.
Key Takeaways
- 1A subgradient is a vector that defines a lower-supporting linear slope at a point.
- 2For a convex function, the supporting linear function touches the function at the reference point and remains below it elsewhere.
- 3The subgradient inequality tests a candidate by comparing f(u) with f(w) + vT(u - w) for every u in the domain.
- 4Stochastic gradient descent requires an expectation-based analysis because E[v_t], rather than the individual stochastic vector itself, is related to the subgradient at w(t).
- 5The deterministic gradient-descent bound cannot be reused directly, but a similar bound can be obtained for the expected output of stochastic gradient descent.
At a glance
- A subgradient generalizes the gradient by satisfying a lower-supporting inequality.
- The subgradient inequality is a universal test over all comparison points in the domain.
- Subgradients allow descent methods to include nondifferentiable functions.
- In stochastic gradient descent, the expected vector E[v_t] belongs to the subgradient set at w(t).
- Because this relationship appears only after taking an expectation, the deterministic bound must be replaced by an expectation-based analysis that yields a similar bound for the expected output.