Problem $2$: Sub$-$gradient Method

Consider a least squares problem with $l^1$ regularization:

$mi{n}_x[f(x)=\frac{1}{2}||Ax-b|{|}_2^2+||x|{|}_1]$

This problem is often called LASSO $($least absolute shrinkage and selection operator$)$ and is known to induce $\{$lem sparse$\}$ solutions with few

nonzero elements in $x,$ which can have advantages in terms of computation and interpretability. This problem is nonsmooth due to the

regularization term. It is also not strongly convex when A has more columns than rows. We $($i$.$e$.,$ you$)$ will solve this problem using several

different algorithms in this class. We start with what we have seen thus far: the subgradient method.

The dataset represented in the matrices provided in the numpy binary files A$.$npy and b$.$npy are from a diabetes dataset $($scikit$-$

learn.org$/$stable$/$modules$/$generated$/$sklearn$.$datasets.load$\_$diabetes.html$)$ with $10$ features that has been corrupted with an additional $90$ noisy

features. Thus a sparse solution should be very effective. Below you will find some skeleton code to help with loading the data, running the

algorithm and plotting the results. Don't use stock optimization code, you should develop the core part of this assignment yourself.

Minimize $f(x)$ using ${10}^4$ iterations of the subgradient method starting with $t=0$ and $x_0=0.$

Part $($A$)$

Use a decreasing step size of ${}_t=\frac{c}{t}$ with values for $c$ that $($roughly$)$ optimize the empirical performance. Separately record the $($unsquared$)$

error $||A{x}_t-b||$ and the regularization term $||x|{|}_1.$

Part $($B$)$

Now use a more slowly decreasing step size of ${}_t=\frac{c}{\sqrt[\phantom{2}]{t+1}}$ with values for $c$ that $($roughly$)$ optimize the empirical performance. Separately

record the $($unsquared$)$ error $||A{x}_t-b||$ and the regularization term $||x|{|}_1.$

Part $($C$)$

Now try to find the best fixed step size. Plot the results and compare to the decreasing step size you see above.