Gradient Descent for Linear Regression

Hello! Welcome to the final lesson in our module on Matrix Calculus and Optimization.

In our last lesson, we mastered the Gradient Descent algorithm, our tool for finding the minimum of a function by taking iterative steps "downhill." We saw that the core of the algorithm is the update rule $w_{k + 1} = w_{k} - η \nabla f (w_{k})$ , which requires the gradient, $\nabla f$ .

Today, we'll put all the pieces together. Our goal is to apply this to a foundational machine learning model: linear regression. To do this, we need to:

Define the model and its associated cost function.
Use our matrix calculus skills to derive the gradient of that cost function.

This is a milestone lesson. By the end, you will have derived the complete update rule for training a linear regression model, a cornerstone of both statistics and machine learning, and a key pattern you'll see again in your deep learning studies.

1. Setting Up the Linear Regression Problem

Let's start by formalizing what we mean by "linear regression." Imagine we want to predict house prices based on features like size, number of bedrooms, etc. This is a classic regression task.

The following video from Stanford's CS229 Machine Learning course provides an excellent introduction. It defines the model's structure (the "hypothesis"), the notation, and the cost function we aim to minimize.

Stanford CS229: Machine Learning - Linear Regression and Gradient Descent | Lecture 2 (Autumn 2018)

Watch this segment from Andrew Ng's lecture on Linear Regression. It will set up the entire problem, from defining the hypothesis function to formalizing the cost function that measures our model's error.

Please watch from 01:46 to 17:15. Part 1 (01:46 - 12:36): Focus on how the hypothesis function, h(x), is defined. Pay attention to the introduction of the 'dummy feature' x_0=1, which allows the intercept term ( heta_0) to be included in the vector dot product. This is a standard and very useful trick. Part 2 (12:46 - 17:15): This part introduces the cost function, J( heta), which is the Mean Squared Error (MSE). Understand its structure as the average squared difference between predictions and actual values.

Let's summarize the key definitions from the video:

Hypothesis Function: Our model's prediction for a given input $x$ is a linear function of its features:
$h_{θ} (x) = θ_{0} + θ_{1} x_{1} + θ_{2} x_{2} + \dots + θ_{n} x_{n}$
By defining $x_{0} = 1$ , we can write this compactly using vector notation:
$h_{θ} (x) = j = 0 \sum n θ_{j} x_{j} = θ^{T} x$
Here, $θ = [θ_{0}, θ_{1}, \dots, θ_{n}]^{T}$ is the vector of parameters (or weights) we want to learn.
Cost Function (Mean Squared Error): To measure how well our model performs, we use the cost function $J (θ)$ . It calculates the average of the squared errors over all $m$ training examples.
$J (θ) = \frac{1}{2 m} i = 1 \sum m (h_{θ} (x^{(i)}) - y^{(i)})^{2}$
The $\frac{1}{2}$ is included for mathematical convenience, as it will cancel out when we take the derivative. Minimizing this function means finding the parameters $θ$ that make our predictions $h_{θ} (x^{(i)})$ as close as possible to the true values $y^{(i)}$ .

Scatterplot with Regression Line for Linear Regression Model Evaluation — This plot visualizes the goal of linear regression. The green dots are the actual data points. The blue line is our model's prediction, $h_\theta(x)$, determined by the parameters $\theta$. Our task is to find the $\theta$ that makes this line the "best fit" by minimizing the cost function.

2. Deriving the Gradient of the Cost Function

Now for the main event. We have our optimization algorithm (Gradient Descent) and our target function to minimize ( $J (θ)$ ). The missing ingredient is the gradient, $\nabla_{θ} J (θ)$ . We will derive this first using familiar single-variable calculus rules, and then using the more powerful matrix calculus notation.

2.1 The Scalar (Component-wise) Approach

Let's find the partial derivative of $J (θ)$ with respect to a single parameter, $θ_{j}$ . This tells us how a small change in just one weight affects the total error.

The video you just watched provides a quick derivation. The following video from StatQuest gives a more deliberate, step-by-step walkthrough of the same process. Seeing it twice from different perspectives will help solidify your understanding.

Gradient Descent, Step-by-Step

This StatQuest video breaks down the derivative calculation very clearly. It starts with the derivative for the intercept and then generalizes to the slope, which maps directly to our heta_j.

Watch from 07:18 to 09:00 and from 15:32 to 19:26. Part 1 (07:18 - 09:00): This shows the application of the chain rule to a squared error term for a single parameter (the intercept). Part 2 (15:32 - 19:26): This extends the concept to finding partial derivatives for both the intercept and the slope, defining the 'gradient' as the collection of these partial derivatives.

Let's write out the steps formally. We want to compute $\frac{\partial}{\partial θ _{j}} J (θ)$ .

Start with the cost function:
$J (θ) = \frac{1}{2 m} i = 1 \sum m (h_{θ} (x^{(i)}) - y^{(i)})^{2}$
Differentiate with respect to $θ_{j}$ . We can move the derivative inside the sum:
$\frac{\partial J ( θ )}{\partial θ _{j}} = \frac{1}{2 m} i = 1 \sum m \frac{\partial}{\partial θ _{j}} (h_{θ} (x^{(i)}) - y^{(i)})^{2}$
Apply the chain rule, $\frac{d}{d u} u^{2} = 2 u \frac{d u}{d x}$ :
$\frac{\partial J ( θ )}{\partial θ _{j}} = \frac{1}{2 m} i = 1 \sum m 2 \cdot (h_{θ} (x^{(i)}) - y^{(i)}) \cdot \frac{\partial}{\partial θ _{j}} (h_{θ} (x^{(i)}) - y^{(i)})$
The derivative of the inner part is $\frac{\partial}{\partial θ _{j}} (\sum_{k = 0}^{n} θ_{k} x_{k}^{(i)} - y^{(i)})$ . The only term in the sum that depends on $θ_{j}$ is $θ_{j} x_{j}^{(i)}$ , so the derivative is simply $x_{j}^{(i)}$ .
Substitute back and simplify (the 2 and $\frac{1}{2}$ cancel):
$\frac{\partial J ( θ )}{\partial θ _{j}} = \frac{1}{m} i = 1 \sum m (h_{θ} (x^{(i)}) - y^{(i)}) x_{j}^{(i)}$

This gives us the formula for each component of the gradient vector. We could implement gradient descent using this formula in a loop, but there is a more elegant way.

2.2 The Matrix Calculus Approach

Now, let's use matrix notation to find the entire gradient vector $\nabla_{θ} J (θ)$ in one go. This is more concise and, given your computer science background, you'll appreciate that it maps directly to highly optimized library functions (like in NumPy or PyTorch).

This article provides an excellent, compact derivation using the matrix calculus identities we've discussed.

Linear Regression, in Two Ways

The article 'Linear Regression, in Two Ways' by Jake Tae provides a beautiful derivation of the gradient using matrix calculus. It's exactly the application we've been building towards.

Read the sections 'The Gradient' and 'Error Minimization'. 'The Gradient' section will refresh your memory on the key identities: ( abla_x b^T x = b) and ( abla_x x^T A x = 2Ax). 'Error Minimization' is the core of this lesson. Follow the steps: rewriting the MSE in matrix form, expanding the terms, and finally taking the gradient.

Let's retrace the key steps from the article.

Define the Matrices:
- $X$ : The design matrix of size $m \times (n + 1)$ , where each row is a training example $(x^{(i)})^{T}$ .
- $y$ : The vector of true values of size $m \times 1$ .
- $θ$ : The vector of parameters of size $(n + 1) \times 1$ .
Rewrite the Cost Function in Matrix Form:
The vector of all predictions is $X θ$ . The vector of errors is $X θ - y$ . The sum of squared errors is the squared Euclidean norm of the error vector, which can be written as $(X θ - y)^{T} (X θ - y)$ .
$J (θ) = \frac{1}{2 m} (X θ - y)^{T} (X θ - y)$
Expand the Expression:
$J (θ) = \frac{1}{2 m} ((θ^{T} X^{T}) - y^{T}) (X θ - y)$ $J (θ) = \frac{1}{2 m} (θ^{T} X^{T} X θ - θ^{T} X^{T} y - y^{T} X θ + y^{T} y)$
Since $θ^{T} X^{T} y$ is a scalar, it equals its own transpose: $(θ^{T} X^{T} y)^{T} = y^{T} (X^{T})^{T} (θ^{T})^{T} = y^{T} X θ$ . So the two middle terms are identical.
$J (θ) = \frac{1}{2 m} (θ^{T} X^{T} X θ - 2 θ^{T} X^{T} y + y^{T} y)$
Take the Gradient: Now we differentiate this expression with respect to $θ$ , using the identities $\nabla_{x} (x^{T} A x) = 2 A x$ and $\nabla_{x} (b^{T} x) = b$ .
$\nabla_{θ} J (θ) = \frac{1}{2 m} \nabla_{θ} (θ^{T} (X^{T} X) θ - 2 θ^{T} (X^{T} y) + y^{T} y)$ $\nabla_{θ} J (θ) = \frac{1}{2 m} (2 X^{T} X θ - 2 X^{T} y + 0)$
Simplifying gives us our final result:
$\nabla_{θ} J (θ) = \frac{1}{m} (X^{T} X θ - X^{T} y) = \frac{1}{m} X^{T} (X θ - y)$

This compact, elegant formula is the gradient of the linear regression cost function.

Test your understanding!

Look at the two forms of the gradient we derived:

Scalar component: $\frac{\partial J ( θ )}{\partial θ _{j}} = \frac{1}{m} \sum_{i = 1}^{m} (h_{θ} (x^{(i)}) - y^{(i)}) x_{j}^{(i)}$
Matrix form: $\nabla_{θ} J (θ) = \frac{1}{m} X^{T} (X θ - y)$

Can you explain why the $j$ -th row of the matrix result is equal to the scalar formula? (Hint: Think about what the matrix-vector product $X^{T} (X θ - y)$ represents).

Show answer

Let's break down the matrix form $\frac{1}{m} X^{T} (X θ - y)$ .

The term $(X θ - y)$ is an $m \times 1$ column vector of the errors for each training example: $[h_{θ} (x^{(1)}) - y^{(1)}, h_{θ} (x^{(2)}) - y^{(2)}, \dots, h_{θ} (x^{(m)}) - y^{(m)}]^{T}$ .
The matrix $X^{T}$ is an $(n + 1) \times m$ matrix. Its $j$ -th row is $[x_{j}^{(1)}, x_{j}^{(2)}, \dots, x_{j}^{(m)}]$ .

When we perform the matrix-vector multiplication $X^{T} (X θ - y)$ , the $j$ -th element of the resulting vector is the dot product of the $j$ -th row of $X^{T}$ and the error vector.

This dot product is:

Element j = x_{j}^{(1)} (h_{θ} (x^{(1)}) - y^{(1)}) + x_{j}^{(2)} (h_{θ} (x^{(2)}) - y^{(2)}) + \dots + x_{j}^{(m)} (h_{θ} (x^{(m)}) - y^{(m)})

Which can be written as a sum:

Element j = i = 1 \sum m (h_{θ} (x^{(i)}) - y^{(i)}) x_{j}^{(i)}

Finally, dividing by $m$ gives us $\frac{1}{m} \sum_{i = 1}^{m} (h_{θ} (x^{(i)}) - y^{(i)}) x_{j}^{(i)}$ , which is exactly the scalar formula for $\frac{\partial J ( θ )}{\partial θ _{j}}$ . This confirms the two derivations are consistent!

Conclusion

Congratulations on completing the final lesson of this module! We have successfully connected all the dots, from the abstract concept of a gradient to its practical application in a core machine learning algorithm.

Key Takeaways:

The linear regression model is defined by the hypothesis $h_{θ} (x) = θ^{T} x$ .
The performance of the model is measured by the Mean Squared Error cost function: $J (θ) = \frac{1}{2 m} (X θ - y)^{T} (X θ - y)$ .
Using matrix calculus, we derived the gradient of this cost function: $\nabla_{θ} J (θ) = \frac{1}{m} X^{T} (X θ - y)$ .
This gradient is the final piece needed to apply the Gradient Descent algorithm, whose update rule for linear regression is: $θ_{k + 1} = θ_{k} - η \frac{1}{m} X^{T} (X θ_{k} - y)$

Preview of the Next Module:

You have now completed the "Matrix Calculus and Optimization" module. We've journeyed from fundamental derivative rules to building and applying the most important optimization algorithm in machine learning.

In the Stanford video, you may have noticed a brief mention of the "Normal Equation," an alternative, non-iterative method for solving for $θ$ by setting the gradient to zero directly. This provides a perfect bridge to our next module, "Applications in Data Analysis." We will start by exploring this analytical solution to the least squares problem, connecting our optimization knowledge to direct methods of solving linear systems, which are heavily used in data science.

Recommended resources

1. Setting Up the Linear Regression Problem

2. Deriving the Gradient of the Cost Function

2.1 The Scalar (Component-wise) Approach

2.2 The Matrix Calculus Approach

Conclusion