Concepts / Gradient Descent Algorithm

Gradient Descent Algorithm

The gradient identifies the direction in which the function increases fastest around the current vector.

  • Programming
Interactive lab

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

  1. The loss is f(x) = (x − 3)² + 1, lowest at x = 3.
  2. At the current x, compute the gradient f′(x) = 2(x − 3).
  3. Update x ← x − learning rate × gradient.
  4. 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.

Educational simulation

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.

Current vectorw(t)Gradientdirection of fastestincreaseScaled movementη times gradientNext vectorw(t+1)evaluate atscale by ηsubtract
How does applying the update rule change the current parameter vector into the next vector?

Reading the Update Rule

Definition

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.

Current vectorGradientfastest increaseNegative gradientdescent directionNext vectorgradient points towardreverse directionmove by scaled amount
If the gradient points toward the direction of fastest increase, how does moving in the negative-gradient direction reduce the function value?
Worked example

Tracing a Symbolic Update

Suppose the current vector is w(t), the gradient evaluated there is g(t), and the learning rate is η.

  1. 1
    Evaluate

    Use the current vector w(t) as the point where the gradient is determined.

  2. 2
    Scale

    Multiply the gradient g(t) by the positive learning rate η. This gives the scaled movement ηg(t).

  3. 3
    Reverse

    Subtract the scaled movement from the current vector rather than adding it.

  4. 4
    Advance

    The resulting vector becomes w(t+1), the current vector for the next iteration.

Result

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.

w(t+1)next vector=assign resultw(t)current vector−reverse directionηlearning rategradientdirection of fastestincreasestarting pointscalesubtract scaled direction
What does each part of the update equation control, and where does each value enter the calculation?

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 choiceWhat is returnedSource-grounded role
Average vectorThe average of vectors produced during the iterationsEspecially useful when gradient descent is extended to nondifferentiable functions and to the stochastic case
Last vectorThe vector from the final iterationUses the final state of the repeated update process
Best-performing vectorThe vector that performed best during the iterationsSelects a vector according to its observed performance

Gradient descent can define its final output in more than one way.

Exact and Stochastic Directions

Definition

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.

Current vectorCurrent vectorExact gradientRandom vectorexpected value has requireddirectionUpdated vectorUpdated vectorevaluate exact gradientsubtract scaled directionchoose random vectorsubtract scaled direction
What is the difference between using the exact gradient and using a random or sample-based update direction?

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).

Worked example

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).

  1. 1
    Start with the current parameters

    Use w(t) as the vector currently being optimized.

  2. 2
    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.

  3. 3
    Scale the direction

    Multiply v(t) by the positive learning rate η.

  4. 4
    Update

    Subtract the scaled random vector from the current parameters.

Result

w(t+1) = w(t) − ηv(t). The next iteration uses this new vector as its current parameter vector.

w(1)initial vectorv(1)random update vectorw(2)updated parametersv(2)new random update vectorw(3)updated parametersuse current vectorsubtract ηv(1)use new current vectorsubtract ηv(2)
How do the parameters change from one iteration to the next when each update uses a different random direction or sample?

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.

Initializeinitial parameter vectorChoose v(t)appropriate random vectorUpdate w(t+1)subtract ηv(t)Repeat through Titeration countAverage vectorsstated final outputbegin iterationuse selected directionadvance iterationif iterations remainafter final iteration
At which step can an implementation use the wrong direction, learning rate, parameter value, stopping rule, or output?
  • Common mistake

    Using the random vector without subtracting it

    What it looks like
    Replacing w(t+1) = w(t) − ηv(t) with an addition.
    Why it fails

    The stated parameter update subtracts the learning-rate-scaled random vector.

    Do this instead

    Preserve the subtraction in the update rule.

  • Common mistake

    Treating each random vector as the exact gradient

    What it looks like

    Assuming v(t) must equal the gradient at w(t) on every iteration.

    Why it fails

    SGD allows the individual random vector to differ from the exact gradient.

    Do this instead

    Check the required conditional expected-value condition instead.

  • Common mistake

    Using the wrong current parameter vector

    What it looks like

    Computing the next update from an old vector instead of the vector produced by the preceding iteration.

    Why it fails

    Each new vector becomes the current vector for the next iteration.

    Do this instead

    Pass w(t+1) forward as the current vector at the next step.

  • Common mistake

    Returning an unspecified final vector

    What it looks like

    Stopping after T updates without applying the procedure's stated averaging step.

    Why it fails

    The SGD procedure described here outputs the average of the iteration vectors w(t).

    Do this instead

    Include the required final averaging step when implementing this procedure.

Practice the Update

EASY

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?

  • The original initial vector

  • The gradient or random vector by itself

  • The newly produced vector w(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

  1. 1
    The gradient points in the direction where a differentiable function increases fastest around the current vector.
  2. 2
    Gradient descent moves in the opposite direction by subtracting a learning-rate-scaled gradient.
  3. 3
    Each updated vector becomes the current vector for the next iteration, creating a sequence of vectors.
  4. 4
    The final output may be an average vector, the last vector, or the best-performing vector.
  5. 5
    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.

At a glance

  • 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.

Related Topics

Related concepts

More concepts starting with G