Gradient Descent

w w - f'(w) — roll downhill to a minimum.

The idea

Gradient descent is the standard method for minimizing a function $f(w)$ that is too complicated to minimize by solving equations directly. What we can compute is the derivative $f'(w)$ at the current $w$. That number is a slope: when $f'(w) > 0$, raising $w$ raises $f$, and when $f'(w) < 0$, raising $w$ lowers $f$. In either case, moving $w$ against the sign of the derivative lowers $f$.

Gradient descent repeats exactly that move: $w \leftarrow w - \eta\, f'(w).$ The learning rate $\eta > 0$ fixes the length of each step. Some choice of step length is unavoidable: the derivative describes $f$ only near the current $w$, and says nothing about how far that description remains accurate. A step that outruns it can land higher than it started, and repeating that can send $w$ off to infinity instead of to a minimum. Starting from an initial guess $w_{0}$, the update produces iterates $w_{1}, w_{2}, \dots$ that march downhill, each step shorter than the last as the slope flattens.

Algorithm.

Algorithm: Gradient Descent Input: differentiable f, learning rate η > 0, starting point w Output: an approximate minimizer of f 1. g = f'(w) // the slope at the current point 2. if g = 0, return w // converged 3. w = w - η g // step against the sign of the slope 4. go to step 1

Where $f'(w) = 0$ the update subtracts nothing and $w$ stops; descent has converged. If $f$ has several minima, the starting point decides which one the iteration reaches.

Ways to work on it

• Walkthrough. The update rule, learning rate, and convergence at a minimum.
• Practice. Take one descent step on a one-variable quadratic.
• Hardest. Iterate on a shifted parabola and find the target minimum.

Not sure where to start? Take the ten-question placement test.