Gradient Descent

You have a function. You want to find where it is smallest. That is the entire problem.

Walk downhill#

Start with one variable. If the derivative is positive, the function is increasing, so move left. If the derivative is negative, the function is decreasing, so move right. Always walk downhill.

That gives a rule: take your current position and subtract the derivative, scaled by a small positive number $\alpha$,

$$x_{n+1}=x_n-\alpha f^{\prime }\left(x_n\right).$$

That is one step of gradient descent. Watch it run on a curve and each step moves the point closer to the bottom.

The learning rate#

$\alpha$ is called the learning rate, and it is a tradeoff. Set it too large and you overshoot the minimum, bouncing back and forth across it. Set it too small and you inch forward, wasting computation. The right $\alpha$ depends on the problem.

Pause and try: take $f\left(x\right)=x^2$, start at $x_0=1$, and run two steps by hand with $\alpha =0.1$. Then try $\alpha =1$.

The derivative is $f^{\prime }\left(x\right)=2x$, so the update is $x_{n+1}=x_n-0.2x_n=0.8x_n$. Two steps: $x_1=0.8$, $x_2=0.64$. Every step multiplies the distance to the minimum by $0.8$, steady convergence.

With $\alpha =1$ the update is $x_{n+1}=x_n-2x_n=-x_n$. From $x_0=1$ you get $1,-1,1,-1,\cdots$ forever: the overshoot exactly mirrors you to the other side of the valley, and you never descend at all. Same function, same rule, wrong $\alpha$.

Millions of variables#

One variable is a toy. In practice you minimize functions of thousands or millions of variables, and the derivative becomes the gradient, the vector of all partial derivatives. The key geometric fact: the gradient at a point is the direction of steepest ascent. To minimize, go the opposite way. Negative gradient, steepest descent.

The update rule keeps the same shape. Take your current parameter vector, subtract $\alpha$ times the gradient, repeat:

$${\theta }_{n+1}={\theta }_n-\alpha \nabla f\left({\theta }_n\right).$$

On a contour plot, each step cuts across the level curves toward the center.

The catch#

Gradient descent follows the local slope, so it finds local minima. If the function has many valleys, you might land in a shallow one and miss the deepest.

Despite this, gradient descent is the engine behind modern machine learning. Neural networks have loss functions with millions of parameters and countless local minima, and yet gradient descent consistently finds parameters that generalize well. The theory of why is still an active area of research, though in high dimensions the dominant obstacles appear to be saddle points and plateaus, not bad local minima.

One rule, walk downhill. Applied at scale, it learns to recognize faces, translate languages, and fold proteins.

If you remember three things#

1. Gradient descent is one rule applied repeatedly: ${\theta }_{n+1}={\theta }_n-\alpha \nabla f\left({\theta }_n\right)$, a step against the gradient, which is the direction of steepest ascent.
2. The learning rate $\alpha$ is a tradeoff: too large overshoots and oscillates, too small crawls, and the right value depends on the problem.
3. It only promises local minima, yet at the scale of modern machine learning it reliably finds parameters that generalize, and explaining why is still open research.