---

Why gradient descent works

---

Normal Equations

Let there be a design matrix $XX$ such that it contains training samples in each row, with features in each column

This is also known as the Design Matrix

And similarly, there is a vector y such that it contains all the training sample outputs

$$y=\left(\begin{array}{c}{y}^{(1)}\\ y^{(2)}\\ y^{(3)}\\ \mathrm{.}\mathrm{.}\\ y^{(i)}\end{array}\right)y\; =\; \backslash begin\{pmatrix\}\; y^\{(1)\}\; \backslash \backslash \; y^\{(2)\}\; \backslash \backslash \; y^\{(3)\}\; \backslash \backslash \; ..\; \backslash \backslash \; y^\{(i)\}\; \backslash end\{pmatrix\}$$

Therefore, we can write the differences vector as $$X\theta -yX\backslash theta\; -\; y$$
To write Error function $J(\theta )J(\backslash theta)$ in this form we can write it as -

$$J(\theta )=\frac{1}{2}(X\theta -y)(X\theta -y{)}^{T}J(\backslash theta)\; =\; \backslash frac\{1\}\{2\}\; (X\backslash theta\; -\; y)\; (X\backslash theta\; -\; y)^T$$


And then to find the minima, we can take the matrix derivative of this like so

$${\mathrm{\nabla }}_{\theta }J=0\backslash nabla\_\backslash theta\; J\; =\; 0$$

and by opening up the factors and applying derivative, we get this -

$$X^{T}X\theta -X^{T}y=0X^T\; X\; \backslash theta\; -\; X^T\; y\; =\; 0$$


If $X^{T}XX^T\; X$ is invertible,

$$\theta =(X^{T}X{)}^{-1}{X}^{T}y\backslash theta\; =\; (X^T\; X)^\{-1\}\; X^T\; y$$

---

Why minimize J?

In order to arrive at this conclusion, we just need to have a pretty reasonable assumption of Error function for each input , ie, $y^{(i)}-h^{(i)}y^\{(i)\}\; -\; h^\{(i)\}$ to be random and IID (Independent and Identically distributed)

Which means that it will be normally distributed like so - $$p(ϵ)=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{({ϵ}^{(i)}{)}^2}{2{\sigma }^2})p\; (\backslash epsilon)\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\}\; \backslash sigma\}\; exp(-\; \backslash frac\{(\backslash epsilon^\{(i)\})^2\}\{2\; \backslash sigma^2\})$$

Therefore from the relation,

$$y^{(i)}-{\theta }^T{x}^{(i)}={ϵ}^{(i)}y^\{(i)\}\; -\; \backslash theta^T\; x^\{(i)\}\; =\; \backslash epsilon^\{(i)\}$$

this probability density function becomes

$$p(ϵ)=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})p\; (\backslash epsilon)\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\}\; \backslash sigma\}\; exp(-\; \backslash frac\{(y^\{(i)\}\; -\; \backslash theta^T\; x^\{(i)\})^2\}\{2\; \backslash sigma^2\})$$

At the maximum value of this probability function, exponential is 1, which means that error is zero and target variable is exactly equal to the hypothesis.

Therefore, we need to choose ${\theta }^T\backslash theta^T$ such that this function is maximized. This function is called Likelihood function $L(\theta )=L(\backslash theta)\; =$. Now, since ${ϵ}^{(i)}\backslash epsilon^\{(i)\}$ are IID, the probabilities of each training sample can be multiplied to get total likelihood

$$L(\theta )=\prod _{i=1}^n\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})L(\backslash theta)\; =\; \backslash prod\_\{i\; =\; 1\}^\{n\}\; \backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\}\; \backslash sigma\}\; exp(-\; \backslash frac\{(y^\{(i)\}\; -\; \backslash theta^T\; x^\{(i)\})^2\}\{2\; \backslash sigma^2\})$$

since any strictly increasing function of L, would be at its maximum when the best parameters are chosen, we can maximize $log(L)log\; (L)$ as well to convert the multiplying factors into simply a sum

$$log(L(\theta ))=\sum _{i}log(\frac{1}{\sqrt{2\pi }\sigma })-\frac{1}{2}\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{{\sigma }^2}log(L(\backslash theta))\; =\; \backslash sum\_i\; log(\backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\}\; \backslash sigma\})\; -\; \backslash frac\{1\}\{2\}\; \backslash frac\{(y^\{(i)\}\; -\; \backslash theta^T\; x^\{(i)\})^2\}\{\backslash sigma^2\}$$
Summing the $log(\frac{1}{\sqrt{2\pi }\sigma })log(\backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\}\backslash sigma\})$ terms over all samples,

$$n\cdot log(\frac{1}{\sqrt{2\pi }\sigma })-\frac{1}{{\sigma }^2}\sum _i\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2}n\; \backslash cdot\; log(\backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\}\; \backslash sigma\})\; -\; \backslash frac\{1\}\{\backslash sigma^2\}\; \backslash sum\_i\; \backslash frac\{(y^\{(i)\}\; -\; \backslash theta^T\; x^\{(i)\})^2\}\{2\}$$

Maximizing the log(L) thus would require minimizing the second term, which is nothing but $J(\theta )J(\backslash theta)$,

$$\text{QED}\backslash text\{QED\}$$