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.


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.