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

n

i$=1($R d $\backslash$times $\{0,1\})$ n $,$ show that there exists a polynomial r S $($x$)$ : R d $->$ R such that

h OF $($x$)=1$ if and only if r S $($x$)>=0.$ That is$,$ even if you restrict yourself to learning only $($thresholded$)$

polynomials that describe the training data, you may end up overfitting. The other message of this

exercise is that inductive bias alone is not sufficient to avoid overfitting