Online classification on a budget

Online algorithms for classification often require vast amounts of mem-ory and computation time when employed in conjunction with kernel functions. In this paper we describe and analyze a simple approach for an on-the-fly reduction of the number of past examples used for prediction. Experiments performed with real datasets show that using the proposed algorithmic approach with a single epoch is competitive with the sup-port vector machine (SVM) although the latter, being a batch algorithm, accesses each training example multiple times.