Stochastic Gradient Descent
The gradient identifies the direction in which the function increases fastest around the current vector.
The Direction of Descent
Optimization begins with a current vector and asks a local question: which direction makes the function increase fastest here? The gradient answers that question. Because the goal is minimization, the algorithm reverses the gradient direction and takes a scaled step away from increasing values. It then treats the new vector as the current vector and repeats the process.
One Gradient Descent Update
For a differentiable function, the gradient at the current vector identifies the direction in which the function increases fastest around that vector. Gradient descent uses the opposite direction because it is seeking lower function values.
w(t+1) = w(t) − η∇f(w(t))The current vector w(t) is the point where the gradient is evaluated. The gradient ∇f(w(t)) supplies the direction of fastest local increase. The positive parameter η, commonly called the learning rate, scales how far the algorithm moves. Subtraction reverses the gradient direction. The resulting vector w(t+1) becomes the current vector for the next iteration.
Tracing the Arithmetic
A Single Scalar Update
Suppose the current value is w(t) = 10, the gradient is 2, and the positive learning rate is η = 0.5. Find the next value.
Start with the rule: Use w(t+1) = w(t) − η∇f(w(t)).
Scale the gradient: The scaled movement is 0.5 × 2 = 1.
Subtract the movement: The next value is 10 − 1 = 9.
The next value is w(t+1) = 9. The update moves opposite to the positive gradient direction.
The important pattern is not the particular numbers. The current value supplies the location, the gradient supplies the direction, the learning rate controls the scale of the movement, and subtraction produces the next value. In a vector update, the same operations apply component by component through vector arithmetic.
What Makes the Method Stochastic
Stochastic gradient descent is an optimization algorithm for minimizing a function f(w) using randomly selected update vectors. At iteration t, it uses the current parameters w(t), selects a random vector v(t) from an appropriate distribution, and updates the parameters by subtracting the learning-rate-scaled random vector.
w(t+1) = w(t) − ηv(t)The random vector v(t) does not need to equal the exact gradient at one iteration. Its conditional expected value must be a subgradient at the current vector. This requirement lets an individual update be random while preserving the required gradient-like direction in expectation. Repeated iterations use these random directions to form a sequence of parameter vectors.
Reading the SGD Rule
w(t+1) = w(t) − ηv(t)| Symbol | Role |
|---|---|
| w(t) | The current parameter vector at iteration t. |
| η | A positive parameter that scales the movement. |
| v(t) | The randomly selected update vector for iteration t. |
| w(t+1) | The newly calculated parameter vector. |
| t through T | The iteration range: repeat the update from t = 1 through the chosen final iteration T. |
Reading each part of the stochastic gradient descent update
The SGD Procedure
The stated SGD procedure follows a fixed cycle. It begins with an initial parameter vector. For each iteration from t = 1 through T, it uses the current vector to determine the condition the random choice must satisfy, selects v(t) from an appropriate distribution, and calculates the next vector with the update rule. After the final iteration, the procedure outputs the average of the iteration vectors w(t).
A Symbolic SGD Update
Updating a Parameter Vector
Let the current parameter vector be w(t) = (a, b), let the randomly selected update vector be v(t) = (p, q), and let the positive learning rate be η. Find w(t+1).
Write the SGD rule: Use w(t+1) = w(t) − ηv(t).
Substitute the vectors: Replace w(t) with (a, b) and v(t) with (p, q), giving w(t+1) = (a, b) − η(p, q).
Distribute the scalar: The scaled random vector is (ηp, ηq).
Subtract component by component: The next vector is (a − ηp, b − ηq).
w(t+1) = (a − ηp, b − ηq).
This symbolic update separates the four roles in the rule. The current parameters provide the starting point, the random vector provides the direction used for this iteration, the learning rate controls the movement's scale, and t identifies which update in the sequence is being performed.
What do you think happens?
If the current vector is (a, b) and the random vector is (p, q), what happens to the first coordinate after applying w(t+1) = w(t) − ηv(t)?
Reveal answer
Answer: It becomes a − ηp.
The random vector is first scaled by the learning rate and then subtracted from the current parameter vector.
Implementation Checks
Adding the update vector instead of subtracting it.
The stated update rule subtracts the learning-rate-scaled random vector, reversing the direction used for the update.
Fix:
Use w(t+1) = w(t) − ηv(t).Reusing the initial vector at every iteration.
Each newly produced vector becomes the current vector for the next iteration.
Fix:
After calculating w(t+1), use it as the current vector in the next cycle.Assuming the random vector must equal the exact gradient.
SGD allows an individual random vector to differ from the exact gradient; its conditional expected value must be a subgradient at the current vector.
Fix:
Check the required expected-value condition rather than demanding equality at every iteration.Returning the last vector when the specified procedure requires an average.
The stated SGD procedure outputs the average of the iteration vectors, while last-vector output is only one possible choice in the broader discussion of gradient descent outputs.
Fix:
Preserve the required final averaging step.Omitting initialization or changing the iteration range.
A correct implementation must preserve initialization, the iteration process, the update rule, and the final averaging step.
Fix:
Check all four parts against the required procedure.
When checking an SGD procedure, audit it in order: confirm the initial vector, verify the iteration range, verify that v(t) is selected under the required condition, check the subtraction update, confirm that each new vector becomes current, and inspect the final output rule.
Practice the Update
Let w(t) = (6, -2), η = 0.25, and v(t) = (4, -8). Apply the SGD update rule and write w(t+1). Then state which vector must be used as the current vector in the next iteration.
Hints
- First calculate ηv(t).
- Subtract the scaled vector from w(t).
- The newly calculated vector is the next current vector.
Practice Check
Using w(t) = (6, -2), η = 0.25, and v(t) = (4, -8), find w(t+1).
Scale the random vector: ηv(t) = 0.25(4, -8) = (1, -2).
Subtract from the current vector: w(t+1) = (6, -2) − (1, -2).
w(t+1) = (5, 0). The vector (5, 0) becomes the current vector for the next iteration.
Key Takeaways
- The gradient points in the direction of fastest local increase, so gradient descent moves in the opposite direction.
- The gradient descent update subtracts the learning-rate-scaled gradient from the current vector.
- SGD replaces the exact gradient at an individual iteration with a random update vector whose conditional expected value must be a subgradient at the current vector.
- Each new parameter vector becomes the current vector for the next iteration.
- The stated SGD procedure initializes the parameters, repeats the random selection and update through T iterations, and returns the average of the iteration vectors.
Key Takeaways
- The gradient identifies the fastest local increase, and reversing it gives the direction used for descent.
- Gradient descent updates the current vector by subtracting a learning-rate-scaled gradient.
- SGD uses a random update vector whose conditional expected value has the required subgradient direction.
- The current vector, learning rate, random vector, and iteration count each have a distinct role in the update.
- A correct SGD procedure preserves initialization, iteration, update, state replacement, and final averaging.