8.1 Perceptron lower bound. Let S be a labeled sample of m points in RN with xi = ((????1)i; : : : ; (????1)i; (????1)i+1

| {z }

i rst components

; 0; : : : ; 0) and yi = (????1)i+1: (8.30)

Show that the Perceptron algorithm makes (2N) updates before nding a separating hyperplane, regardless of the order in which it receives the points.