Geometry question resolved + debriefing

First, I should note that the margin question came up in my work with Corinna Cortes and Mehryar Mohri; see our ALT'06 and (to appear) COLT'07 papers.

Next, a shameful admission: I seem to have forgotten how logical contrapositives work. As Avrim reminds me, the perceptron algorithm will terminate in O(1/gamma^2) steps if the data are separable by a margin of at least gamma. Let me quote Avrim:

what you show is that any separator must have w_n that is exponential in w_1, and that furthermore, flipping the sign ofw_1 makes the separator inconsistent. That implies that for any consistent separator, there is an exponentially small change in its angle that makes it inconsistent, which means it has an exponentially small margin.

Finally, a bit of philosophy of math. One should resist the temptation to run numerical simulations, taking the time to think things through with pen and paper first.