Gradient Descent

Why We Need Gradient Descent

Gradient descent is the optimization engine behind most modern machine learning algorithms.

In the linear regression lesson, we predicted a house price from the house area, number of bedrooms, number of toilets, and number of balconies. We had a dataset of $n$ samples:

Each $x_i$ is $d$-dimensional, and each $y_i$ is a real value.

We then put all the samples into a matrix $X$, where each row is one data sample. This made $Xw$ the vector of predicted outputs. Our objective was to minimize the squared error:

We can also divide this by $n$ to get the mean squared error, and minimize that instead:

Solving the objective directly gave us:

This has two problems. $X^T X$ has to be invertible, or else we need the pseudo-inverse. And for a large dataset, the computation is highly expensive.

So we need another way to find $w$.

Using a Convex Function

The squared error is a squared function, and a squared function is convex.

For a simple picture, think of $y = x^2$ in two dimensions, which is a bowl shape with one minimum at the bottom.

For a convex function, we can use an iterative algorithm like gradient descent.

To find the optimal $w$, we start with some initial weights and update them in each iteration. Writing $w^{(t)}$ for the weights at iteration $t$, the update is:

Here, $\nabla E$ is the gradient of the error function, and $\alpha$ is a positive number. In each iteration, we subtract a multiple of the gradient from the previous weights to get the new weights.

Let's look at each part of this update.

What the Gradient Tells Us

The gradient represents the slope of a function, and it points in the direction of steepest ascent.

To see why this helps, picture a convex function of one variable, with its minimum at the bottom of the bowl:

• On the right side of the minimum, the gradient is positive. To reach the minimum, we have to move left, in the negative direction.
• On the left side of the minimum, the gradient is negative. To reach the minimum, we have to move right, in the positive direction.

In both cases, we move in the direction opposite to the gradient. That's why the update subtracts a multiple of the gradient from $w$.

So we initialize the weights, which gives us some starting value of the loss. From that starting position, we take incremental steps down the curve until we reach the minimum loss.

The Learning Rate

The multiple $\alpha$ is called the learning rate. It decides how fast we move towards the minimum.

• If $\alpha$ is too small, we take tiny baby steps. We'll need more iterations, so reaching the minimum takes more time.
• If $\alpha$ is too large, we overshoot the minimum and land on the other side. The next step overshoots again, so instead of converging, we diverge.
• If $\alpha$ is just right, we reach the minimum in a reasonable number of steps.

The Algorithm

Let $E(w)$ be the error function, or loss function, that we want to minimize.

After convergence, the loss is at its minimum, and the $w^{(t)}$ that produces it gives us the weights for our model.

Summary

The key ideas are:

• The closed-form solution for linear regression is too expensive for large datasets, so we use an iterative algorithm.
• Squared error is convex, which makes it a good fit for gradient descent.
• The gradient points in the direction of steepest ascent, so we step in the opposite direction.
• The learning rate controls the step size. Too small is slow, and too large can diverge.
• We repeat the update until convergence, and the final weights are the weights for our model.