Exercise $3($Data Separation$)$ Assume we have $n$ data points $x_{i}in{R}^d,$ with label $y_{i}in\{-1,1\}.$ We are searching for an hyper$-$plane defined by its normal $,$ which separates the points according to their label. Ideally, we would like t

$$

$$

$$

$$ o have

${}^T{x}_i-1=>y_i=-1,$ and $,{}^T{x}_{i}1=>y_i=1.$

Unfortunately, this condition is rarely met with real$-$life problems. Instead, we solve an optimization problem which minimizes the gap between the hyper$-$plane and the miss$-$classified points. To do so$,$ we will use a specific loss function

$L(,x_i,y_i)=$max$\{0$;$1-y_i({}^T{x}_i)\},$

$1$

which is equal to $0$ when the point $x_i$ is well$-$classified $($the sign of ${}^T{x}_i$ and $y_i$ is the same$),$ but is strictly positive when the sign of ${}^T{x}_i$ and $y_i$ is different. To improve the performances, instead of minimizing the loss function alone, we also use a quadratic regularizer as follow,

$mi{n}_{}\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{}}}L(,x_i,y_i)+\frac{}{2}|||{|}_2^2,$

where $$ is the regularization parameter.

Consider the following quadratic optimization problem $(1$ is a vector full of ones$),$

$,mi{n}_{,z}\frac{1}{n}{1}^{T}z+\frac{1}{2}|||{|}_2^2$

$s.t.z_{i}1-y_i({}^T{x}_i),$AAi$=1$dotsn

$,z0$

Explain why problem $($Sep$.2)$ solves problem $($Sep$.1).$

$2.$ Compute the dual of $($Sep$.2),$ and try to reduce the number of variables. Use the notations ${}_i$ and $$ for the dual variables.