[alextp]

Regarding the perceptron, most modern texts also have a regret analysis for the perceptron, which coupled with an online-to-batch conversion tells you how well do you expect a perceptron to perform on unseen data after a single pass, and it's usually a very good estimate (the answer is on average about as well as it did on the examples in the training data).

[syllogism]

This isn't often discussed in my field (NLP) -- thanks!

We usually use averaged perceptron though, which seems like it would make this hard to analyse.

[alextp]

The averaged perceptron is the one to which the proof applies :-)