1
$\begingroup$

How do I prove that the Perceptron bound for mistakes is tight? I need to prove that for any amount of given data points, the total amount of updates (mistakes) that the algorithm will make is $\frac{1}{\gamma ^2}$, where $\gamma$ is the margin. I know that I'll have to make it such that for a given $m$ number of data points, I'll make it such that $\gamma = \frac{1}{\sqrt{m}}$, but I'm not really sure how to continue and would appreciate a hint in the right direction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.