$1.(40$ points$)$ The weight decay regularizer is also called L$2$ regularizer, since $$wT $$w is the square

of the $2-$norm of the weight vector $$w$2=$

qPd

i$=0$ w$2$

i $.$ Another common regularizer is called

L$1$ regularizer, since $1-$norm $($w$1=$

Pd

i$=0|$wi$|)$ is used as the regularizer.

Below are the definitions of the two regularizations$1$:

$$ L$1$ regularization: Eaug$($w$)=$ Ein$($w$)+$ $$w$1$

$$ L$2$ regularization: Eaug$($w$)=$ Ein$($w$)+$ $$wT $$w

$($a$)(10$ points out of $40$ points$)$ Answer LFD Problem $4\mathrm{.}8.$

$($b$)(10$ points out of $40$ points$)$ Similar to Problem $4\mathrm{.}8,$ derive the update rule of gradient

descent for minimizing the augmented error with L$1$ regularizer.

Note that the gradient of $1-$norm is not well$-$defined at $0.$ To address this issue, we can

utilize the subgradient idea defined as follows:

$$

$$wi

$$w$1=$

$$

$$

$+1$ if wi $>0$

any value in $[1,1]$ if wi $=0$

$1$ if wi $<0$

$1$When applying these regulerizations to linear regression, they are called Ridge Regression $($L$2$ regularizer$)$ and

Lasso Regression $($L$1$ regularizer$)$ respectively.

$1$

To simplify the discussion, we let $$

$$wi

$$w$1=0$ when wi $=0.$ Please write down the

update rule of gradient descent for L$1$ regularization. $($You can define a sign$()$ function

that returns $+1,0,1$ when the input is positive, zero, negative$).$

Truncated gradient $($for part $($c$))$: In Lasso regression $($linear regression with L$1$ regularization$),$

one nice property is that it tends to learn a weight vector with many $0$s$.$

However, if we perform gradient descent on the augmented error with L$1$ regularization,

it won$$t lead to this nice property partly due to the not$-$well$-$defined behavior of

subgradient. In this homework, you will implement truncated gradient $[1],$ an approach

trying to maintain the nice property of L$1$ regularizations, as described below.

Let $$w$($t $+1)$w$($t$)$ $$Ein$($w$($t$))$ be the update rule of gradient descent without

regularization. The update rule for L$1$ regularization that you derived should be in the

form of

$$w$($t $+1)$w$($t $+1)+$ additional term

The additional term represents the effect of L$1$ regularization compared with no regularization.

Truncated gradient works as follows: At each step t$,$ you first perform the

update and obtain $$w$($t $+1).$ Then for each dimension i$,$ if wi$($t $+1)$ and w$$i$($t $+1)$ have

different signs and when w$$i$($t$+1)=0,$ we set the update wi$($t$+1)$ to $0($i$.$e$.,$ we truncate

the update if the additional term makes the new weight change signs$).2$

$($c$)(20$ points out of $40$ points$)$ Update your implementation of logistic regression in HW$2$

to include the L$1$ and L$2$ regularizers $($use truncated gradient for L$1$ regularizer and

regular gradient descent for L$2$ regularizers$).$ Conduct the following experiment and

include the results in your report. Also submit the updated python implementation

$($feel free to update the function headers and$/$or define new functions$).$

You will work with digits dataset, classifying whether a digit belongs to $\{1,6,9\}($labeled

as $1)$ or $\{0,7,8\}($labeled as $+1).$ Please download the pre$-$processed data $($check

the label format and make sure you are working with the $+1/1$ labels$)$ on Canvas.

Examine different $=0,0\mathrm{.}0001,0\mathrm{.}001,0\mathrm{.}005,0\mathrm{.}01,0\mathrm{.}05,0\mathrm{.}1$ for both L$1$ and L$2$ regularizations.

Train your models on the training set. For each trained model, report $(1)$ the

classification error on the test set and $(2)$ the number of $0$s in your learned weight vector.

Describe your observations and the property of the L$1$ regularizer $($when coupled

with truncated gradient$).$

For the other parameters, please use the following. Normalize the features. Set learning

rate $=0\mathrm{.}01.$ The maximum number of iterations is $104.$ Terminate learning if the

magnitude of every element of the gradient $($of Ein$)$ is less than $106.$ When calculating

classification error, classify the data using a cutoff probability of $0\mathrm{.}5.$