8.11 On-line to batch | kernel Perceptron margin bound. In this problem, we give a margin-based generalization guarantee for the kernel Perceptron algorithm. Let h1; : : : ; hT be the sequence of hypotheses generated by the kernel Perceptron algorithm and let bh be dened as in exercise 8.10. Finally, let L denote the zero-one loss. We now wish to more precisely bound the generalization error of bh in this setting.

(a) First, show that XT i=1 L(hi(xi); yi)  inf h2H:khk1 XT i=1 max



0; 1 ????

yih(xi)





+

1



sX i2I K(xi; xi);

where I is the set of indices where the kernel Perceptron makes an update and where  and  are dened as in theorem 8.12.

(b) Now, use the result of exercise 8.10 to derive a generalization guarantee for bh in the case of kernel Perceptron, which states that for any 0 <   1, the following holds with probability at least 1 ???? :

R(bh)  inf h2H:khk1 bR S;(h) +

1

T sX i2I K(xi; xi) + 6 r

1 T

log 2(T + 1)



;

where bR S;(h) = 1 T

PT i=1 max

????

0; 1 ???? yih(xi)



. Compare this result with the margin bounds for kernel-based hypotheses given by corollary 6.13.