Gradient Descent Optimization in Linear Regression

Hello and welcome to another session on "Regression and Gradient Descent." In today's syllabus, we will construct and fit the gradient descent algorithm into a linear regression problem. Though linear regression does have a direct solution, gradient descent is essential for computational efficiency, especially when handling larger datasets or complex models.

Gradient descent is an iterative optimization algorithm for minimizing a function, usually a loss function, quantifying the disparity between predicted and actual results. The goal of gradient descent is to find the parameters that minimize the value of the loss function. Importantly, gradient descent navigates its way to the minimum of the function by moving iteratively toward the direction of the steepest descent. However, to leverage gradient descent, the target function must be differentiable.

Gradient descent derives its name from its working mechanism: taking descents along the gradient. It operates in several iterative steps as follows:

1. Choose random values for initial parameters.
2. Calculate the cost (the difference between actual and predicted value).
3. Compute the gradient (the steepest slope of the function around that point).
4. Update the parameters using the gradient.
5. Repeat steps 2 to 4 until we reach an acceptable error rate or exhaust the maximum iterations.

A vital component of gradient descent is the learning rate, which determines the size of the descent towards the optimum solution. It is important to note that if the learning rate is too high, we may overshoot the minimum, and if it's too low, the convergence to the minimum may take too long.

Let's implement it from scratch with a basic understanding of the gradient descent algorithm. We will need two functions: one for calculating the cost and another for calculating and applying the gradient to update our parameters. Moreover, we'll add an early stop mechanism that will halt computations after a predefined number of iterations.

The cost function is as follows:

where $J$ is the cost, $X$ is the data, $y$ is the actual values, $\theta$ is the parameters, and $m$ is the length of $y$. It is the calculation of the mean square error.

import numpy as np

def cost(X, y, theta):
    m = len(y)
    predictions = X.dot(theta)
    cost = (1/m) * np.sum(np.square(predictions-y)) # Compute mean square error
    return cost