Exercises — Linear regression — normal equation, gradient descent derivation

With the bias column there are $3+1=4$ columns.

• $\mathbf{X}$ is $5\times 4$ (rows $=$ points, columns $=$ features$+$bias).
• ${\mathbf{X}}^T$ is $4\times 5$, so ${\mathbf{X}}^T\mathbf{X}$ is $(4\times 5)(5\times 4)=4\times 4$.
• ${\mathbf{X}}^T\mathbf{y}$ is $(4\times 5)(5\times 1)=4\times 1$.
• $\mathbf{w}$ solves a $4\times 4$ system so it is $4\times 1$.

Sanity check: the number of unknowns in $\mathbf{w}$ ($=4$) always equals the number of columns of $\mathbf{X}$.

(b). (a) is absolute error — kinks make its derivative undefined at $0$, so calculus is harder. (c) is not squared, so errors above and below the line cancel; you could have huge errors summing to zero. Squaring in (b) makes every error positive and gives a smooth bowl to slide down.

$\mathbf{X}=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\end{array}\right],\mathbf{y}=\left[\begin{array}{c}1\\ 3\\ 3\end{array}\right]$ Top-left of ${\mathbf{X}}^T\mathbf{X}$ counts the points: $1+1+1=3$. Off-diagonal is $\sum x_i=0+1+2=3$. Bottom-right is $\sum x_i^2=0+1+4=5$. ${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 3\\ 3& 5\end{array}\right]$ ${\mathbf{X}}^T\mathbf{y}$: first entry $\sum y_i=1+3+3=7$; second $\sum x_i{y}_i=0\cdot 1+1\cdot 3+2\cdot 3=9$. ${\mathbf{X}}^T\mathbf{y}=\left[\begin{array}{c}7\\ 9\end{array}\right]$

Determinant: $3\cdot 5-3\cdot 3=15-9=6$. $({\mathbf{X}}^T\mathbf{X}{)}^{-1}=\frac{1}{6}\left[\begin{array}{cc}5& -3\\ -3& 3\end{array}\right]$ ${\mathbf{w}}^{\ast }=\frac{1}{6}\left[\begin{array}{cc}5& -3\\ -3& 3\end{array}\right]\left[\begin{array}{c}7\\ 9\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}35-27\\ -21+27\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}8\\ 6\end{array}\right]=\left[\begin{array}{c}1.333\\ 1\end{array}\right]$ So $b=\frac{4}{3}\approx 1.333$, $w=1$. Line: $\hat{y}=x+1.333$.

Check by eye: at $x=1$ it predicts $2.333$ (true $3$), at $x=2$ predicts $3.333$ (true $3$) — errors balanced, as least squares demands.

Predictions with ${\mathbf{w}}_0$ are all $0$, so error $\mathbf{X}{\mathbf{w}}_0-\mathbf{y}=[-1,-3,-3{]}^T$. Gradient $\nabla J=\frac{1}{3}{\mathbf{X}}^T(\mathbf{X}{\mathbf{w}}_0-\mathbf{y})$:

• first entry $\frac{1}{3}(-1-3-3)=\frac{-7}{3}=-2.333$
• second entry $\frac{1}{3}(0\cdot (-1)+1\cdot (-3)+2\cdot (-3))=\frac{-9}{3}=-3$ ${\mathbf{w}}_1=\left[\begin{array}{c}0\\ 0\end{array}\right]-0.1\left[\begin{array}{c}-2.333\\ -3\end{array}\right]=\left[\begin{array}{c}0.2333\\ 0.3\end{array}\right]$

The normal equation is ${\mathbf{X}}^T\mathbf{X}{\mathbf{w}}^{\ast }={\mathbf{X}}^T\mathbf{y}$. Rearrange: ${\mathbf{X}}^T\mathbf{y}-{\mathbf{X}}^T\mathbf{X}{\mathbf{w}}^{\ast }=0\Rightarrow {\mathbf{X}}^T(\mathbf{y}-\mathbf{X}{\mathbf{w}}^{\ast })=0\Rightarrow {\mathbf{X}}^T\mathbf{r}=0.$ Meaning (see figure): $\mathbf{X}{\mathbf{w}}^{\ast }$ is the shadow (projection) of $\mathbf{y}$ onto the flat plane spanned by $\mathbf{X}$'s columns. The leftover $\mathbf{r}$ points straight out of that plane — the shortest possible leftover. Any other $\mathbf{w}$ leaves a longer residual.

Column 3 $=2\times$ column 2, so the columns are linearly dependent. Then ${\mathbf{X}}^T\mathbf{X}$ is singular (determinant $0$) and $({\mathbf{X}}^T\mathbf{X}{)}^{-1}$ does not exist — the normal equation has infinitely many solutions. Geometrically the "plane" the columns span collapses to a lower dimension, so $\mathbf{y}$'s projection is well-defined but the coordinates $\mathbf{w}$ that reach it are not unique. This is multicollinearity. Fixes: drop a redundant feature, or add Ridge which replaces ${\mathbf{X}}^T\mathbf{X}$ with ${\mathbf{X}}^T\mathbf{X}+\lambda I$ (always invertible for $\lambda >0$), or use the Matrix Pseudoinverse which picks the minimum-norm solution.

The second derivative (Hessian) of $J$ is $\frac{1}{n}{\mathbf{X}}^T\mathbf{X}$. For any nonzero direction $\mathbf{v}$, ${\mathbf{v}}^T{\mathbf{X}}^T\mathbf{Xv}=\Vert \mathbf{Xv}{\Vert }^2\ge 0$, and it is $>0$ when the columns are independent. A matrix with all positive curvatures is positive definite, so $J$ is strictly convex — a single bowl. Every downhill path reaches the same bottom, which is why gradient descent cannot get stuck in a fake local minimum here.

$\mathbf{X}=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right]$, $\mathbf{y}=[2,2,4{]}^T$. ${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right]$, det $=42-36=6$. ${\mathbf{X}}^T\mathbf{y}$: $\sum y_i=8$; $\sum x_i{y}_i=2+4+12=18$. ${\mathbf{w}}^{\ast }=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]\left[\begin{array}{c}8\\ 18\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}112-108\\ -48+54\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}4\\ 6\end{array}\right]=\left[\begin{array}{c}0.667\\ 1\end{array}\right]$ So $b=\frac{2}{3},w=1$. (ii) Because $J$ is strictly convex (L3.3) and ${\mathbf{X}}^T\mathbf{X}$ is invertible, gradient descent with small enough $\alpha$ converges to the same unique minimum $[0.667,1{]}^T$. The two methods must agree — they solve the same equation, one in a jump, one by walking.

The curvature in each direction is set by that feature's $\sum x^2$. With ranges $1$ vs $10,000$ the bowl is a long thin canyon: steep across the small feature, nearly flat along the big one. A single learning rate $\alpha$ must be tiny enough not to overshoot the steep wall — so it barely moves along the flat floor. Result: zig-zagging, glacial convergence. Scaling (e.g. subtract mean, divide by std) makes all $\sum x^2$ comparable, turning the canyon into a round bowl where one $\alpha$ works in every direction. The normal equation is immune (no $\alpha$), which is one reason it's convenient for small $d$.

Take the gradient and set to zero. The extra term contributes $\lambda \mathbf{w}$: $\frac{1}{n}{\mathbf{X}}^T(\mathbf{Xw}-\mathbf{y})+\lambda \mathbf{w}=0.$ Multiply through by $n$ and group $\mathbf{w}$: $({\mathbf{X}}^T\mathbf{X}+n\lambda I)\mathbf{w}={\mathbf{X}}^T\mathbf{y}\Rightarrow {\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}+n\lambda I{)}^{-1}{\mathbf{X}}^T\mathbf{y}.$ Since ${\mathbf{X}}^T\mathbf{X}$ has eigenvalues $\ge 0$, adding $n\lambda I$ ($\lambda >0$) shifts every eigenvalue up by $n\lambda >0$ — none can be zero, so the matrix is invertible even under the multicollinearity of L3.2. See Regularization (Ridge, Lasso).

Normal equation is out: forming and inverting ${\mathbf{X}}^T\mathbf{X}$ ($50,000\times 50,000$) costs $O(d^3)\approx 1.25\times 10^{14}$ operations plus $2.5\times 10^9$ entries of memory — infeasible, and it can't ingest a live stream. Full batch GD touches all $2,000,000$ rows per step — expensive per iteration. The right choice is mini-batch / SGD: each step uses a small batch (e.g. 256 rows), cost $O(bd)$ per step, and it naturally consumes the stream in real time. Trade-off: noisier steps, so use a decaying $\alpha$. This is exactly the setting behind Kalman Filtering and online estimators, and mini-batch GD is the workhorse of Neural Networks for the same scaling reason.

$\mathbf{X}=\left[\begin{array}{cc}1& 1\\ 1& 2\\ 1& 3\end{array}\right]$, $\mathbf{y}=[1,2,2{]}^T$. ${\mathbf{X}}^T\mathbf{X}=\left[\begin{array}{cc}3& 6\\ 6& 14\end{array}\right]$ (det $6$). ${\mathbf{X}}^T\mathbf{y}$: $\sum y=5$, $\sum x_i{y}_i=1+4+6=11$. ${\mathbf{w}}^{\ast }=\frac{1}{6}\left[\begin{array}{cc}14& -6\\ -6& 3\end{array}\right]\left[\begin{array}{c}5\\ 11\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}70-66\\ -30+33\end{array}\right]=\frac{1}{6}\left[\begin{array}{c}4\\ 3\end{array}\right]=\left[\begin{array}{c}0.667\\ 0.5\end{array}\right]$ (ii) Predictions $\hat{y}=0.5x+0.667$: at $x=1,2,3$ give $1.167,1.667,2.167$. Residuals $\mathbf{r}=\mathbf{y}-\hat{\mathbf{y}}=[-0.167,0.333,-0.167{]}^T$. $\Vert \mathbf{r}{\Vert }^2=0.0278+0.1111+0.0278=0.1667$. Cost $J=\frac{1}{2\cdot 3}(0.1667)=0.02778$. (iii) ${\mathbf{X}}^T\mathbf{r}$: first entry $-0.167+0.333-0.167=0$; second $-0.167+0.667-0.5=0$. ✓ Residual is orthogonal to both columns, confirming the projection picture.

Convergence needs the contraction factor's magnitude $<1$: $\left|1-\frac{\alpha }{n}\sum x_i^2\right|<1\Rightarrow 0<\frac{\alpha }{3}(14)<2\Rightarrow \alpha <\frac{6}{14}=\mathrm{0.4286.}$ Above this, $\alpha \approx 0.4286$ oscillates without shrinking, and $\alpha >0.4286$ diverges — each step overshoots further than the last. The safe rule: $\alpha <\frac{2n}{\sum x_i^2}$ (in general, $\alpha <2/{\lambda }_{\max }$ of the Hessian).

The normal equation solution is ::: ${\mathbf{w}}^{\ast }=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$ Gradient descent diverges when $\alpha$ exceeds ::: $2/{\lambda }_{\max }$ of the Hessian $\frac{1}{n}{\mathbf{X}}^T\mathbf{X}$ Ridge stays invertible because it adds ::: $n\lambda I$, lifting every eigenvalue above zero At the optimum the residual is ::: orthogonal to every column of $\mathbf{X}$ (${\mathbf{X}}^T\mathbf{r}=0$)