Gradient Descent Algorithm
The gradient identifies the direction in which the function increases fastest around the current vector.
Try it: Gradient Descent
How gradient descent minimises a loss by repeatedly stepping against the gradient, and how the learning rate controls whether it converges, oscillates or diverges.
How it works
- The loss is f(x) = (x − 3)² + 1, lowest at x = 3.
- At the current x, compute the gradient f′(x) = 2(x − 3).
- Update x ← x − learning rate × gradient.
- Repeat. Small learning rates creep in, good ones converge quickly, rates above 1 overshoot further each step and diverge.
Default run (40 steps): Start at x = -3. Loss f(x) = (x − 3)² + 1 = 37. Learning rate 0.1. … Update 39: gradient f′ = 2(x − 3) = -0.0025; step = −0.1 × -0.0025 = 0.0002; new x = 2.999; loss 1 → 1. x is within 0.001 of the minimum at x = 3 — converged.
Simplified: One parameter and a perfectly smooth loss. Real models optimise millions of parameters on noisy losses.
Loading the simulation…
The Repeated Descent Decision
Gradient descent does not jump directly to a final answer. It starts with an initial vector, examines the function at that current vector, determines the direction in which the function increases fastest, and then moves in the opposite direction. The vector produced by that update becomes the current vector for the next iteration.
Reading the Update Rule
For a differentiable function, the gradient identifies the direction in which the function increases fastest around the current vector. Gradient descent reverses that direction and scales the movement using a positive parameter η.
The gradient is evaluated at the current vector, often written as w(t). The learning-rate parameter η controls the scale of the movement. The next vector is obtained by subtracting the learning-rate-scaled gradient from the current vector. In symbolic form, the update is w(t+1) = w(t) − η times the gradient at w(t). The subtraction matters: the gradient indicates fastest local increase, so reversing it supplies the direction used for descent.
Tracing a Symbolic Update
Suppose the current vector is w(t), the gradient evaluated there is g(t), and the learning rate is η.
Evaluate: Use the current vector w(t) as the point where the gradient is determined.
Scale: Multiply the gradient g(t) by the positive learning rate η. This gives the scaled movement ηg(t).
Reverse: Subtract the scaled movement from the current vector rather than adding it.
Advance: The resulting vector becomes w(t+1), the current vector for the next iteration.
w(t+1) = w(t) − ηg(t). The current vector supplies the starting point, the gradient supplies the direction, η controls the movement scale, and subtraction produces the next vector.
Choosing the Final Vector
The repeated updates create a sequence of vectors. After T iterations, the algorithm still needs a defined output. The stated choices include the average vector, the last vector, or the best-performing vector. The output choice is part of the algorithm's definition rather than merely a formatting decision.
| Output choice | What is returned | Source-grounded role |
|---|---|---|
| Average vector | The average of vectors produced during the iterations | Especially useful when gradient descent is extended to nondifferentiable functions and to the stochastic case |
| Last vector | The vector from the final iteration | Uses the final state of the repeated update process |
| Best-performing vector | The vector that performed best during the iterations | Selects a vector according to its observed performance |
Exact and Stochastic Directions
Stochastic gradient descent, or SGD, is an optimization algorithm for minimizing a function f(w) using randomly selected update vectors.
SGD follows the same broad update pattern as gradient descent, but the direction used at one iteration does not need to equal the exact gradient. Instead, SGD selects a random vector whose conditional expected value must be a subgradient at the current vector. The parameter update subtracts the learning-rate-scaled random vector from the current parameters.
The SGD Iteration Cycle
The stated SGD procedure begins with an initial parameter vector and repeats a cycle for t equal to 1 through T. At each iteration, it uses the current vector w(t) to determine the condition the random choice must satisfy, chooses v(t) from an appropriate distribution, and calculates the next vector by subtracting the learning-rate-scaled random vector. After the final iteration, the procedure outputs the average of the iteration vectors w(t).
A Symbolic SGD Update
At iteration t, the current parameters are w(t), the learning rate is η, and the selected random update vector is v(t).
Start with the current parameters: Use w(t) as the vector currently being optimized.
Select the random vector: Choose v(t) from an appropriate distribution. It need not equal the exact gradient, but its conditional expected value must have the required gradient-like property at the current vector.
Scale the direction: Multiply v(t) by the positive learning rate η.
Update: Subtract the scaled random vector from the current parameters.
w(t+1) = w(t) − ηv(t). The next iteration uses this new vector as its current parameter vector.
Implementation Checkpoints
An SGD procedure can diverge from the required algorithm if it changes one of the essential stages: initialization, iteration, update, or final averaging. Checking these stages helps distinguish the stated algorithm from a superficially similar procedure.
Using the random vector without subtracting it
The stated parameter update subtracts the learning-rate-scaled random vector.
Fix:
Preserve the subtraction in the update rule.Treating each random vector as the exact gradient
SGD allows the individual random vector to differ from the exact gradient.
Fix:
Check the required conditional expected-value condition instead.Using the wrong current parameter vector
Each new vector becomes the current vector for the next iteration.
Fix:
Pass w(t+1) forward as the current vector at the next step.Returning an unspecified final vector
The SGD procedure described here outputs the average of the iteration vectors w(t).
Fix:
Include the required final averaging step when implementing this procedure.
Practice the Update
Write the next-vector expression for an SGD iteration whose current parameters are w(t), learning rate is η, and selected random vector is v(t). Then state what vector supplies the current parameters on the following iteration.
Hints
- The SGD update subtracts the learning-rate-scaled random vector.
- The result of the update becomes the current vector for the next iteration.
What do you think happens?
After calculating w(t+1) from w(t), which vector should be used as the current vector at iteration t+1?
Reveal answer
Answer: The newly produced vector w(t+1).
Gradient descent and SGD repeat the calculation by using each new vector as the next current point.
Key Takeaways
- The gradient points in the direction where a differentiable function increases fastest around the current vector.
- Gradient descent moves in the opposite direction by subtracting a learning-rate-scaled gradient.
- Each updated vector becomes the current vector for the next iteration, creating a sequence of vectors.
- The final output may be an average vector, the last vector, or the best-performing vector.
- SGD replaces the exact per-iteration gradient with a random update vector whose conditional expected value has the required gradient-like property, then subtracts its learning-rate-scaled value.
Key Takeaways
- A gradient identifies the local direction of fastest increase, so descent reverses it.
- The update combines the current vector, a positive learning rate, and a gradient or random update vector.
- The next vector becomes the current vector at the following iteration.
- The algorithm must define how its final vector is selected, including possible averaging.
- SGD uses random update vectors whose conditional expected value satisfies the required gradient-like condition.