Gradient Descent for Linear Regression

Consider applying gradient descent to an 1D linear regression model. The model $f[x,\varphi ]$ maps a scalar input $x$ to a scalar output $y$ and has parameter $\varphi =[{\varphi }_0,{\varphi }_1{]}^T$, which represents the $y$-intercept and the slope:

$$\begin{array}{rl}y& =f[x,\varphi ]\\ & ={\varphi }_0+{\varphi }_{1}x\end{array}$$

Given a dataset $\{x_i,y_i\}$ containing $I$ input/output pairs, we choose the least squares loss function:

$$\begin{array}{rl}L[\varphi ]=\sum _{i=1}^I{\ell }_i& =\sum _{i=1}^I(f[x_i,\varphi ]-y_i{)}^2\\ & =\sum _{i=1}^I({\varphi }_0+{\varphi }_1{x}_i-y_i{)}^2\end{array}$$

where the term ${\ell }_i=({\varphi }_0+{\varphi }_1{x}_i-y_i{)}^2$ is the individual contribution to loss from the $i$-th training example.

The derivative of the loss function with respect to the parameters can be decomposed into the sum of the derivates of the individual contributions:

$$\frac{\partial L}{\partial \varphi }=\frac{\partial }{\partial \varphi }\sum _{i=1}^I{\ell }_i=\sum _{i=1}^I\frac{\partial {\ell }_i}{\partial \varphi }$$

where these are given by:

$$\frac{\partial {\ell }_i}{\partial \varphi }=\left[\begin{array}{c}\frac{\partial {\ell }_i}{\partial {\varphi }_0}\\ \frac{\partial {\ell }_i}{\partial {\varphi }_1}\end{array}\right]=\left[\begin{array}{c}2({\varphi }_0+{\varphi }_1{x}_i-y_i)\\ 2x_i({\varphi }_0+{\varphi }_1{x}_i-y_i)\end{array}\right]$$

The figure below shows the progression of this algorithm as we iteratively compute the derivatives according to the equations above and update them. In this case, we have used a line search procedure to find the value of $\alpha$ that decreases the loss the most at each iteration.