CONF orabona:ICML08:2008/IDIAP The Projectron: a Bounded Kernel-Based Perceptron Orabona, Francesco Keshet, Joseph Caputo, Barbara EXTERNAL https://publications.idiap.ch/attachments/papers/2008/orabona-ICML08-2008.pdf PUBLIC https://publications.idiap.ch/index.php/publications/showcite/orabona:rr08-30 Related documents Int. Conf. on Machine Learning 2008 IDIAP-RR 08-30 We present a discriminative online algorithm with a bounded memory growth, which is based on the kernel-based Perceptron. Generally, the required memory of the kernel-based Perceptron for storing the online hypothesis is not bounded. Previous work has been focused on discarding part of the instances in order to keep the memory bounded. In the proposed algorithm the instances are not discarded, but projected onto the space spanned by the previous online hypothesis. We derive a relative mistake bound and compare our algorithm both analytically and empirically to the state-of-the-art Forgetron algorithm (Dekel et al, 2007). The first variant of our algorithm, called Projectron, outperforms the Forgetron. The second variant, called Projectron++, outperforms even the Perceptron. REPORT orabona:rr08-30/IDIAP The Projectron: a Bounded Kernel-Based Perceptron Orabona, Francesco Keshet, Joseph Caputo, Barbara EXTERNAL https://publications.idiap.ch/attachments/reports/2008/orabona-idiap-rr-08-30.pdf PUBLIC Idiap-RR-30-2008 2008 IDIAP To appear in Proceedings of the 25th International Conference on Machine Learning (ICML 2008) We present a discriminative online algorithm with a bounded memory growth, which is based on the kernel-based Perceptron. Generally, the required memory of the kernel-based Perceptron for storing the online hypothesis is not bounded. Previous work has been focused on discarding part of the instances in order to keep the memory bounded. In the proposed algorithm the instances are not discarded, but projected onto the space spanned by the previous online hypothesis. We derive a relative mistake bound and compare our algorithm both analytically and empirically to the state-of-the-art Forgetron algorithm (Dekel et al, 2007). The first variant of our algorithm, called Projectron, outperforms the Forgetron. The second variant, called Projectron++, outperforms even the Perceptron.