Cost function (MSE) and gradient descent fitting

Overview

In linear regression, we want to find the best-fit line through our data. But what does "best" mean? We need a way to measure how wrong our predictions are, and then systematically improve them. The Mean Squared Error (MSE) is our measure of wrongness, and gradient descent is our systematic improvement algorithm.

We square instead of using absolute values because squared functions are differentiable everywhere, which lets us use calculus to find the minimum efficiently.

Cost Function: Mean Squared Error

$J(\theta) = \frac{1}{2n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2$

Where:

• $J(\theta)$ = cost function (what we want to minimize)
• $\theta$ = parameters (weights and bias: $\theta_0, \theta_1, ..$)
• $h_\theta(x_i) = \theta_0 + \theta_1 x_i$ for simple linear regression
• The $\frac{1}{2}$ is a convenience factor that cancels when we take derivatives

Derivation from first principles

Why do we need a cost function? We have $n$ training examples $(x_i, y_i)$. Our hypothesis makes predictions $\hat{y}_i = h_\theta(x_i)$. Each prediction has an error: $e_i = \hat{y}_i - y_i$.

Step 1: Measure total error Sum of errors: $\sum e_i$ won't work (positive and negative cancel) Sum of absolute errors: $\sum |e_i|$ works but isn't differentiable at zero

Step 2: Square the errors $\text{Total squared error} = \sum_{i=1}^{n} e_i^2 = \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2$

Why this step? Squaring makes all errors positive, penalizes large errors more, and creates a smooth surface we can optimize with calculus.

Step 3: Average to get MSE $J(\theta) = \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2$

Why this step? Dividing by $n$ makes the cost independent of dataset size—10 errors of size 5 should cost the same whether we have 100 or 1000 examples.

Step 4: Add the $\frac{1}{2}$ factor $J(\theta) = \frac{1}{2n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2$

Why this step? When we take the derivative, the power rule brings down a factor of 2 from squaring, which cancels the $\frac{1}{2}$. This makes the gradient cleaner.

• Outer sum: Accumulates errors across all training examples
• Inner difference: Prediction minus actual (residual)
• Square: Penalizes errors quadratically
• Division by 2n: Normalizes and simplifies derivatives

Gradient Descent: Finding the Minimum

The gradient $\nabla J(\theta)$ is a vector pointing in the direction of stepest increase. We go in the opposite direction to descend.

Deriving the Gradient Descent Update Rule

Step 1: Write the update formula (general form) $\theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j}$

Where:

• $:=$ means "update to"
• $\alpha$ is the learning rate (step size)
• $\frac{\partial J(\theta)}{\partial \theta_j}$ is the partial derivative (slope) with respect to parameter $\theta_j$

Why this form? If the slope is positive (we're on an uphill), the derivative is positive, so we subtract it (go left/down). If the slope is negative (we're on a downhill), we subtract a negative (go right/down).

Step 2: Compute the partial derivative Start with the cost function: $J(\theta) = \frac{1}{2n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2$

For simple linear regression, $h_\theta(x_i) = \theta_0 + \theta_1 x_i$.

Take the derivative with respect to $\theta_j$: $\frac{\partial J(\theta)}{\partial \theta_j} = \frac{\partial}{\partial \theta_j} \left[ \frac{1}{2n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2 \right]$

Why this step? We need to know how much a small change in $\theta_j$ changes the cost.

Step 3: Apply chain rule $= \frac{1}{2n} \sum_{i=1}^{n} \frac{\partial}{\partial \theta_j} (h_\theta(x_i) - y_i)^2$

$= \frac{1}{2n} \sum_{i=1}^{n} 2(h_\theta(x_i) - y_i) \cdot \frac{\partial}{\partial \theta_j}(h_\theta(x_i) - y_i)$

Why this step? Chain rule: derivative of $u^2$ is $2u \cdot u'$. Here $u = h_\theta(x_i) - y_i$.

The 2 cancels with $\frac{1}{2}$: $= \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i) \cdot \frac{\partial h_\theta(x_i)}{\partial \theta_j}$

Step 4: Compute $\frac{\partial h_\theta(x_i)}{\partial \theta_j}$

For $\theta_0$ (bias/intercept): $\frac{\partial}{\partial \theta_0}(\theta_0 + \theta_1 x_i) = 1$

For $\theta_1$ (slope): $\frac{\partial}{\partial \theta_1}(\theta_0 + \theta_1 x_i) = x_i$

In general, for $\theta_j$: $\frac{\partial h_\theta(x_i)}{\partial \theta_j} = x_i^{(j)}$ where $x_i^{(j)}$ is the $j$-th feature of example $i$ (with $x_i^{(0)} = 1$ for the bias term).

Step 5: Final gradient $\frac{\partial J(\theta)}{\partial \theta_j} = \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i) \cdot x_i^{(j)}$

Update all parameters simultaneously:

• $\theta_0 := \theta_0 - \alpha \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)$
• $\theta_1 := \theta_1 - \alpha \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i) \cdot x_i$

Simultaneous means: compute all new values using the old $\theta$ values, then update all at once.

The Learning Rate $\alpha$

Too small: Convergence is slow (many iterations needed) Too large: We overshoot the minimum and may diverge (cost increases) Just right: Fast convergence to the minimum

Typical values: $0.001, 0.01, 0.1, 1$. Often found by trial and error or adaptive methods.

The gradient tells you the direction; $\alpha$ tells you how far to go.

Worked Examples

Goal: Fit $y = \theta_0 + \theta_1 x$ using gradient descent.

Initialize: $\theta_0 = 0, \theta_1 = 0$, learning rate $\alpha = 0.1$

Iteration 1:

1. Compute predictions:

   • $h_\theta(1) = 0 + 0(1) = 0$
   • $h_\theta(2) = 0 + 0(2) = 0$
   • $h_\theta(3) = 0 + 0(3) = 0$

2. Compute errors (residuals):

   • $e_1 = 0 - 2 = -2$
   • $e_2 = 0 - 4 = -4$
   • $e_3 = 0 - 5 = -5$

3. Compute cost: $J(\theta) = \frac{1}{2\cdot 3}[(-2)^2 + (-4)^2 + (-5)^2] = \frac{1}{6}[4 + 16 + 25] = \frac{45}{6} = 7.5$

4. Compute gradients: $\frac{\partial J}{\partial \theta_0} = \frac{1}{3}[(-2)(1) + (-4)(1) + (-5)(1)] = \frac{-11}{3} = -3.67$ Why this step? Each error is multiplied by $x^{(0)} = 1$ for the bias term.

   $\frac{\partial J}{\partial \theta_1} = \frac{1}{3}[(-2)(1) + (-4)(2) + (-5)(3)] = \frac{-25}{3} = -8.33$

   Why this step? Each error is multiplied by the corresponding $x_i$ value.

5. Update parameters: $\theta_0 := 0 - 0.1(-3.67) = 0.367$ $\theta_1 := 0 - 0.1(-8.33) = 0.833$

   Why this step? We move in the direction opposite to the gradient (downhill).

Iteration 2 (using new $\theta$):

1. Predictions:

   • $h_\theta(1) = 0.367 + 0.833(1) = 1.2$
   • $h_\theta(2) = 0.367 + 0.833(2) = 2.033$
   • $h_\theta(3) = 0.367 + 0.833(3) = 2.866$

2. Errors:

   • $e_1 = 1.2 - 2= -0.8$
   • $e_2 = 2.033 - 4 = -1.967$
   • $e_3 = 2.866 - 5 = -2.134$

3. Cost: $J(\theta) = \frac{1}{6}[0.64 + 3.87 + 4.55] = 1.51$

   Why this step? Cost decreased from 7.5 to 1.51—we're moving downhill!

Continue until cost stops decreasing significantly (convergence).

Step 1: Compute prediction and error

• $h_\theta(2) = 1 \cdot 2 = 2$
• Error: $e = 2 - 5 = -3$

Step 2: Compute cost $J(\theta_1) = \frac{1}{2 \cdot 1}(-3)^2 = 4.5$

Step 3: Compute gradient $\frac{\partial J}{\partial \theta_1} = \frac{1}{1}[(-3)(2)] = -6$

Why is it negative? Our prediction (2) is less than the actual (5). The error is negative. When multiplied by $x = 2$, we get -6. This negative gradient tells us: increase $\theta_1$ to make better predictions.

Step 4: Update (with $\alpha = 0.1$) $\theta_1 := 1 - 0.1(-6) = 1 + 0.6 = 1.6$

Why this step? Subtracting a negative gradient means adding, so $\theta_1$ increases, which will increase our predictions (moving from 2 toward 5).

Verification:

• New prediction: $h_\theta(2) = 1.6 \cdot 2 = 3.2$ (closer to 5 ✓)
• New cost: $J = \frac{1}{2}(3.2 - 5)^2 = 1.62$ (less than 4.5 ✓)

Common Mistakes

Why it feels right: It seems logical to use the most recent value.

Why it's wrong: The gradient was computed assuming both parameters at their old values. Using a partially updated value corrupts the gradient direction.

Fix: Compute all gradients first, then update all parameters at once.

# Wrong
theta_0 = theta_0 - alpha * grad_0
theta_1 = theta_1 - alpha * grad_1  # Uses NEW theta_0 indirectly
 
# Right
temp_0 = theta_0 - alpha * grad_0
temp_1 = theta_1 - alpha * grad_1
theta_0 = temp_0
theta_1 = temp_1

Why it feels right: The derivation shows a sum, so just use the sum.

Why it's wrong: Without dividing by $n$, your effective learning rate scales with dataset size. Adding more data would require shrinking $\alpha$, making it non-transferable.

Fix: Always divide by $n$: $\theta_j := \theta_j - \alpha \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i) \cdot x_i^{(j)}$

Why it feels right: Seems like it would be faster than using all data.

Actually: This is stochastic gradient descent (SGD), not batch gradient descent. It's not wrong per se, but it's a different algorithm with different properties:

• Batch GD: Uses all data, stable convergence, slower per iteration
• SGD: Uses one point, noisy updates, faster per iteration, may not converge exactly

Both are valid; just know which you're using!

Why it happens: You're overshooting the minimum. Each update jumps to the opposite side of the valley.

Fix:

1. Reduce $\alpha$ (try dividing by 10)
2. Monitor cost per iteration—it should decrease monotonically in batch GD
3. Use learning rate schedules or adaptive methods (Adam, RMSprop)

Visual: If plotting cost vs. iteration shows a jagged upward trend, $\alpha$ is too large.

Convergence Criteria

In practice, monitor the cost function. If it stops decreasing meaningfully, you've converged.

Batch vs. Stochastic vs. Mini-Batch

Batch GD (what we derived): $\theta_j := \theta_j - \alpha \frac{1}{n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i) x_i^{(j)}$

Stochastic GD: $\theta_j := \theta_j - \alpha (h_\theta(x_i) - y_i) x_i^{(j)} \quad \text{for a random } i$

Mini-batch GD: $\theta_j := \theta_j - \alpha \frac{1}{b} \sum_{i \in \text{batch}} (h_\theta(x_i) - y_i) x_i^{(j)}$

Feature Scaling Impact

Solution: Normalize features to similar scales (e.g., mean 0, std 1): $x_j^{(i)} := \frac{x_j^{(i)} - \mu_j}{\sigma_j}$

This makes the cost function more circular/spherical, allowing gradient descent to converge faster with larger learning rates.

Now, how do you find the best line? You start with a random line. Then you look at which way you should tilt it to make the cost smaller—like rolling a ball downhill. You tilt it a little bit in that direction. Then you check again and tilt more. You keep doing this over and over until your line is so good that tilting it any more doesn't help. That's gradient descent—it's like teaching your line to walk downhill until it reaches the bottom of a valley, where the cost is lowest.

The "learning rate" is how big your steps are. Too big and you'll jump over the valley. Too small and you'll take forever to get there.

• Measure: Compute $J(\theta)$ = how wrong you are
• Squared: Errors are squared (big mistakes hurt more)
• Errors: Difference between prediction and actual
• Go: Move parameters in a direction
• Downhill: Opposite of gradient (stepest descent)

Or think: "Mean Squared Errors Guide Descent"

Connections

• 2.2.03-Hypothesis-representation-in-linear-regression — The hypothesis $h_\theta(x)$ is what we're optimizing
• 2.2.05-Normal-equation — Closed-form alternative to gradient descent
• 2.06-Feature-scaling-and-normalization — Makes gradient descent converge faster
• 2.3.02-Logistic-cost-function — Different cost function for classification
• 2.4.01-Gradient-descent-for-neural-networks — Backpropagation extends this idea
• 3.1.02-Convex-optimization — MSE is convex, guaranteing global minimum
• 4.2.01-Stochastic-gradient-descent — Faster variant for large datasets
• 4.2.03-Learning-rate-schedules — Adaptive strategies for $\alpha$

#flashcards/ai-ml

What is the Mean Squared Error (MSE) cost function for linear regression? :: $J(\theta) = \frac{1}{2n} \sum_{i=1}^{n} (h_\theta(x_i) - y_i)^2$, where $h_\theta(x_i)$ is the prediction and $y_i$ is the actual value. The $\frac{1}{2n}$ normalizes by dataset size and simplifies derivatives.

What is the gradient descent update rule for a parameter $\theta_j$? :: $\theta_j := \theta_j - \alpha \frac{\partial J(\theta)}{\partial \theta_j}$, where $\alpha$ is the learning rate and the partial derivative is the gradient (slope) of the cost function with respect to that parameter.

What does a negative gradient mean in gradient descent? :: A negative gradient means the cost decreases as the parameter increases, so we should increase the parameter. Since we subtract the gradient ($\theta := \theta - \alpha \cdot \text{negative value}$), we effectively add to $\theta$, moving it in the direction that reduces cost.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)