Suppose S $=\{($x i $,$ y i $)\}$ n

i$=1$ R d $\backslash$times $\{1,+1\}$ is a linearly separable training dataset. We saw

in that there exists a w $$ in R d such that y i $$w $,$ x i $>1$ for all i in $[$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 i in $[$n$]).$

$($a$)$ Devise a new algorithm called Margin$-$Perceptron that outputs a $$w that separates the positive

and negative examples by a margin, that is$,$ y i $$w$,$ x i $>=1$ for all i in $[$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.