Linear Regression Using Gradient Descent

Problem

Implement linear regression using gradient descent. Given features X, targets y, learning rate, and number of iterations, update weights to minimize the mean squared error.

Solution

import numpy as np

def linear_regression_gradient_descent(X: list[list[float]], y: list[float],
                                        alpha: float, iterations: int) -> list[float]:
    X = np.array(X, dtype=float)
    y = np.array(y, dtype=float)
    n = len(y)
    theta = np.zeros(X.shape[1])

    for _ in range(iterations):
        predictions = X @ theta
        errors = predictions - y
        gradient = (1 / n) * (X.T @ errors)
        theta = theta - alpha * gradient

    return np.round(theta, 4).tolist()

Explanation

1. Initialize the weight vector theta to zeros.
2. In each iteration:
3. - Compute predictions: X * theta.
4. - Compute errors: predictions - y.
5. - Compute the gradient: (1/n) X^T errors.
6. - Update theta: theta = theta - alpha * gradient.
7. After the specified number of iterations, return the learned weights.

Complexity

• Time: O(iterations n f) where n is samples and f is features
• Space: O(f) for the weight vector plus O(n) for predictions