$[4$ points$].$ Coordinate Descent for Linear Regression. We would like to solve

the following linear regression problem

minimize

M$$

i$=1$

$($y$($i$)$ wT x$($i$))2,(2)$

where w in RN $1$ and x$($i$)$ in RN $1$ using coordinate descent.

a$)[2$ points$].$ In the current iteration, wk is selected for update. Please prove

the following update rule:

wk $$

$$M

i$=1$ x$($i$)$

k $($y$($i$)$N

j$=1,$j$6=$k wj x$($i$)$

j $)$

$$M

i$=1($x$($i$)$

k $)2,$k in $\{1,2,...,$ N $\}(3)$

b$)[2$ points$].$ Prove that the following update rule for wk is equivalent to

Eq$.(3).$

wold

k $$ wk$,(4)$

wk $$

$$M

i$=1$ x$($i$)$

k $$ r$($i$)$

$$M

i$=1($x$($i$)$

k $)2+$ wold

k $,(5)$

r$($i$)$ r$($i$)+($wold

k $$ wk$)$x$($i$)$

k $$i in $\{1,2,...$ M $\}.(6)$

where r$($i$)$ is the residual

r$($i$)=$ y$($i$)$

N$$

j$=1$

wj x$($i$)$

j $.(7)$

Compare the two update rules. Which one is better and why?