Online Classification on a Budget

Online algorithms for classification often require vast amounts of memory andcomputation 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 support vectormachine (SVM) although the latter, being a batch algorithm, accesses each training example multiple times.