$[6$ pts$]$ Suppose S$=\{($x$\_($i$),$y$\_($i$))\}\_($i$)=1^($n$)$subR$^($d$)\backslash$times $\{-1,+1\}$ is a linearly separable training dataset. We saw

in that there exists a w$^(**)$inR$^($d$)$ such that y$\_($i$)($:w$^(**),$x$\_($i$)$:$)>1$ for all iin$[$n$].$ Recall that the Perceptron

algorithm outputs a hyperplane that separates the positive and negative examples $($i$.$e$.,$ y$\_($i$)($:w$,$x$\_($i$)$:$)>0,$

for all iin$[$n$].$

$($a$)$ Devise a new algorithm called MARGIN$-$PERCEPTRON that outputs a widehat$($w$)$ that separates the positive

and negative examples by a margin, that is$,$ y$\_($i$)($:$($widehat$($w$)),$x$\_($i$)$:$)>=1$ for all iin$[$n$].$

$($b$)$ Suppose, as in class, that R$$max$\_($i$)||$x$||\_(2)$ and B$$min$\{(||$w$||\_(2))$:$\}$ : for all $\{$:y$\_($i$)($:w$,$x$\_($i$)$:$)>=1\}.$ Show using

the technique we used in class to show that MARGIN$-$PERCEPTRON in at most B$^(2)($R$^(2)+2)$ steps.Suppose we modify the Perceptron algorithm as follows: In the update step, instead of performing w$($t$+1)=$ w$($t$)+$ yixi, whenever we make a mistake, we instead perform w$($t$+1)=$ w$($t$)+\backslash$eta yixi, for some $\backslash$eta $>0$; $\backslash$eta is sometimes referred to as the learning rate or the step size. Show that this modified Perceptron will perform the same number of iterations as the original Perceptron we studied in class, and that it will converge to a vector that points in the same direction as the output of the vanilla Perceptron. Hint: What can you say about the relationship between the signs of $$w$,$ x$$ and $\backslash$eta w$,$ x$?$