  In this paper, we study the mistake bound of online kernel learning on a
budget. We propose a new budgeted online kernel learning model, called
Ahpatron, which significantly improves the mistake bound of previous work and
resolves the open problem posed by Dekel, Shalev-Shwartz, and Singer (2005). We
first present an aggressive variant of Perceptron, named AVP, a model without
budget, which uses an active updating rule. Then we design a new budget
maintenance mechanism, which removes a half of examples,and projects the
removed examples onto a hypothesis space spanned by the remaining examples.
Ahpatron adopts the above mechanism to approximate AVP. Theoretical analyses
prove that Ahpatron has tighter mistake bounds, and experimental results show
that Ahpatron outperforms the state-of-the-art algorithms on the same or a
smaller budget.
