Gradient Descent for Linear Regression

hardFREELinear RegressionMachine Learning 1

Implement batch gradient descent for simple linear regression.

Given data points $(x, y)$ , initial weight $w$ and bias $b$ , learning rate $\alpha$ , and number of iterations, update $w$ and $b$ to minimize Mean Squared Error:

$MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - (w \cdot x_i + b))^2$

The gradients are: $\frac{\partial MSE}{\partial w} = \frac{-2}{n} \sum_{i=1}^{n} x_i(y_i - (w \cdot x_i + b))$ $\frac{\partial MSE}{\partial b} = \frac{-2}{n} \sum_{i=1}^{n} (y_i - (w \cdot x_i + b))$

Each iteration computes both gradients from the current $w$ and $b$ , then updates them together: $w \leftarrow w - \alpha \frac{\partial MSE}{\partial w}, \qquad b \leftarrow b - \alpha \frac{\partial MSE}{\partial b}$

Return a tuple (w, b) after all iterations, both rounded to 4 decimal places.

Example

Input

X = [1, 2, 3]
y = [2, 4, 6]
w = 0.0, b = 0.0
learning_rate = 0.1, iterations = 100

Output

(1.9715, 0.0647)

Reasoning

Inputs: three points $(1, 2), (2, 4), (3, 6)$ , so $n = 3$ . They lie exactly on $y = 2x$ , so the ideal fit is $w = 2$ , $b = 0$ . Start: $w = b = 0$ , $\alpha = 0.1$ , 100 updates.
First update: with $w = b = 0$ every prediction is $0$ , so the residuals $y_i - (w x_i + b)$ are just $2, 4, 6$ .
$\frac{\partial MSE}{\partial w} = \frac{-2}{3}(1 \cdot 2 + 2 \cdot 4 + 3 \cdot 6) = \frac{-2}{3} \cdot 28 \approx -18.6667$ and $\frac{\partial MSE}{\partial b} = \frac{-2}{3}(2 + 4 + 6) = -8$ .
Stepping against the gradients: $w = 0 - 0.1 \cdot (-18.6667) = 1.8667$ and $b = 0 - 0.1 \cdot (-8) = 0.8$ .
Later updates: $b$ overshot, so the residuals turn negative and $b$ slowly drains toward 0 while $w$ creeps toward 2.
Output: after 100 updates, rounded to 4 decimal places, $(w, b) =$ (1.9715, 0.0647). Notice it hasn't reached $(2, 0)$ yet; more iterations get closer.

Constraints

X and y are lists of equal length
learning_rate > 0, iterations >= 1
Initial w and b are given as floats
Return tuple (w, b) rounded to 4 decimal places

Learn this in

Linear RegressionML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

Linear Regression is a fundamental concept in Machine Learning that involves modeling the relationship between a dependent variable (target) and one or more independent variables (features) using a linear equation. The goal is to find the best-fitting line that minimizes the difference between predicted and actual values. In simple linear regression, we have one feature and one target variable, and the equation takes the form of $y = wx + b$ , where $w$ is the weight, $x$ is the feature, and $b$ is the bias.

The Mean Squared Error (MSE) is a common loss function used to evaluate the performance of a linear regression model. It calculates the average squared difference between predicted and actual values. The gradient descent algorithm is an optimization technique used to minimize the loss function by iteratively updating the model parameters ( $w$ and $b$ ) in the direction of the negative gradient. The gradients of the loss function with respect to the model parameters are used to compute the updates.

In batch gradient descent, the model parameters are updated after computing the gradients using the entire training dataset. This is in contrast to stochastic gradient descent, where the parameters are updated after computing the gradients using a single data point. Batch gradient descent is more computationally expensive but can lead to more stable convergence.

Algorithm/Approach

The general approach to solving this problem involves implementing the batch gradient descent algorithm to minimize the Mean Squared Error (MSE) loss function. The algorithm iteratively updates the model parameters ( $w$ and $b$ ) using the gradients of the loss function with respect to these parameters. The key components of the algorithm include:

Computing the predicted values using the current model parameters
Calculating the gradients of the loss function with respect to the model parameters
Updating the model parameters using the gradients and the learning rate
Repeating the process for a specified number of iterations

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize the model parameters ( $w$ and $b$ ) with the given values.
Compute the predicted values using the current model parameters and the feature values.
Calculate the gradients of the loss function with respect to the model parameters ( $w$ and $b$ ) using the predicted values and the actual values.
Update the model parameters using the gradients, the learning rate, and the update rules.
Repeat steps 2-4 for the specified number of iterations.
Return the final model parameters ( $w$ and $b$ ) rounded to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Incorrectly computing the gradients of the loss function
Using the wrong update rules for the model parameters
Not properly initializing the model parameters
Not checking for convergence or using a sufficient number of iterations

Time & Space Complexity

The time complexity of the batch gradient descent algorithm is O(n * iterations), where n is the number of data points and iterations is the number of iterations. The space complexity is O(n), as we need to store the feature values, actual values, and predicted values. Note that the time and space complexity can vary depending on the specific implementation and the size of the dataset.

solution.py

Python 3.13

Test results