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:

(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)

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:

E(w) = \|Xw - y\|^2

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

E(w) = \frac{1}{n} \|Xw - y\|^2

Solving the objective directly gave us:

w = (X^T X)^{-1} X^T y

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.

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:

(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)

Each

x_i

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:

E(w) = \|Xw - y\|^2

We can also divide this by

n

to get the mean squared error, and minimize that instead:

E(w) = \frac{1}{n} \|Xw - y\|^2

Solving the objective directly gave us:

w = (X^T X)^{-1} X^T y

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.