ERRATUM

We apologize for an experimental bug in the paper "Online (and Offline) On an Even Tighter Budget", AISTATS 2005. For the noisy USPS dataset only (with 10% flipped labels) we made a mistake. We randomly shuffled the data and then flipped the labels of the first 10% of the data, which for SVMs is fine because the ordering of the data is irrelevant. However, for the online methods this meant they saw the noisy data first, and the clean data last. This explains why the Perceptron has so much fewer SVs than the SVM. However, all the conclusions of the paper still stand as the other noisy datasets do not have this flaw.