Gradient Descent for Least Squares

Linear regression is a statistical method used to model the relationship between a dependent variable and one or more independent variables by fitting a linear equation to observed data. The simplest form of the linear equation with one dependent and one independent variable is represented as $y = mx + b$, where $m$ is the slope of the line and $b$ is the y-intercept. This method is widely used in predictive modeling and quantitative forecasting.

Gradient Descent for Linear Regression

Gradient Descent is an optimization algorithm used to minimize some function by iteratively moving in the direction of steepest descent as defined by the negative of the gradient. In the context of linear regression, gradient descent is used to find the values of $m$ and $b$ that minimize the cost function, which is typically the sum of squared differences between the observed values and the values predicted by the model.

Cost Function

The mean squared error cost function for linear regression quantifies the difference between the observed values and the values predicted by the linear model. It is given by:

$$E(m, b) = \frac{1}{n} \sum_{i=1}^{n} (y_i - (mx_i + b))^2$$

where:

• $n$ is the number of observations,
• $y_i$ is the observed value,
• $x_i$ is the independent variable,
• $m$ is the slope, and
• $b$ is the y-intercept.

Gradient Descent Algorithm

The gradient descent algorithm updates the parameters $m$ and $b$ iteratively to minimize the cost function $E(m, b)$. The update rules for $m$ and $b$ at each iteration are:

$$m_{k+1} = m_k - \alpha \frac{\partial E}{\partial m}$$ $$b_{k+1} = b_k - \alpha \frac{\partial E}{\partial b}$$

where $\alpha$ is the learning rate, a hyperparameter that controls the size of the steps taken towards the minimum of the cost function.

Partial Derivatives of the Cost Function

The partial derivatives of $E(m, b)$ with respect to $m$ and $b$ are:

$$\frac{\partial E}{\partial m} = -\frac{2}{n} \sum_{i=1}^{n} x_i(y_i - (mx_i + b))$$ $$\frac{\partial E}{\partial b} = -\frac{2}{n} \sum_{i=1}^{n} (y_i - (mx_i + b))$$

These gradients are used to update the values of $m$ and $b$ iteratively along the negative gradient; a suitable step size is needed to decrease the cost function.

Implementation Steps

1. Initialization: Start with initial guesses for the values of $m$ and $b$.
2. Gradient Calculation: Compute the gradients of the cost function with respect to $m$ and $b$.
3. Update Parameters: Update the values of $m$ and $b$ using the gradient descent update rules.
4. Iteration: Repeat steps 2 and 3 until the gradient tolerance is met or the iteration budget is exhausted; report which stopping condition was reached.

Try moving points and adjusting the line in Explained Visually’s least-squares demonstration. Compare the residual squares as the slope and intercept change; their sum differs from the mean-squared-error objective above only by the constant number of observations.

Exact solution and a reproducible update

This note concerns the optimization calculation; the assumptions and interpretation of the model belong to Linear Regression. With $r_i=mx_i+b-y_i$, the chain rule gives $\partial r_i^2/\partial m=2r_ix_i$ and $\partial r_i^2/\partial b=2r_i$, explaining the signs and factor $2$ above. Because of $1/n$, $E$ is mean squared error, not the residual sum of squares. Scaling a loss preserves its minimizer but scales its gradient and changes a suitable learning rate.

Use the three observations $(1,2),(2,5),(3,3)$. Their sum of squared errors is exactly the quadratic from the gradient note:

$$S=3E=14m^2+12mb+3b^2-42m-20b+38.$$

Here $\sum x_i=6$, $\sum y_i=10$, $\sum x_i^2=14$, and $\sum x_iy_i=21$. Solving $28m+12b-42=0$ and $12m+6b-20=0$ gives $m=1/2$, $b=7/3$. The residuals $y_i-(mx_i+b)$ are $-5/6,5/3,-5/6$, so $S=25/6$ and $E=25/18$.

At $(m,b)=(0,0)$, $\nabla E=(-14,-20/3)$. A simultaneous update with $\alpha=0.05$ gives $(7/10,1/3)$ and lowers $E$ from $38/3$ to $1789/450\approx3.975556$. Repeat by computing both gradient sums before assigning either parameter.

Collect the parameters in $\theta=(m,b)^T$ and the observations in $y=(y_1,\ldots,y_n)^T$. Let row $i$ of the design matrix $X$ be $(x_i,1)$, so entry $i$ of $X\theta$ is the prediction $mx_i+b$. Then $E=\|X\theta-y\|_2^2/n$, where the squared Euclidean norm sums the squared residuals, and the Hessian is $H=2X^TX/n$. For every $v$, $v^THv=2\|Xv\|_2^2/n\ge0$, proving convexity. The solution is unique only when the columns of $X$ are linearly independent (full column rank); for slope plus intercept this requires at least two distinct $x_i$. If all $x_i=c$, only $mc+b$ is identifiable and many parameter pairs fit equally well.

The step-size bound follows from the error dynamics. Here $H$ is symmetric positive definite and $\theta_*$ is the unique minimizer. For $e_k=\theta_k-\theta_*$, the quadratic gradient is $He_k$, hence

$$e_{k+1}=(I-\alpha H)e_k.$$

Along an eigenvector of $H$ with eigenvalue $\lambda>0$, the error component is multiplied by $1-\alpha\lambda$. Convergence from every starting point requires $|1-\alpha\lambda|<1$ for every eigenvalue, giving $0<\alpha<2/\lambda_{\max}(H)$. At the upper boundary, the largest-eigenvalue component oscillates instead of shrinking. Convexity identifies global minima; it does not make every step size converge.

For this dataset, $\lambda_{\max}(H)=(17+\sqrt{265})/3\approx11.092940$, so fixed-step descent converges for $0<\alpha<2/\lambda_{\max}\approx0.180295$. Feature scaling changes this bound. Stop with a gradient-norm tolerance and an iteration cap, and compare with the exact solution; unchanged loss alone can mean numerical stagnation. For small dense problems, QR or SVD least-squares solvers are often preferable to hand-iterating or explicitly inverting $X^TX$.

My reading · Opened notes are remembered in this browser.