Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound
Abstract
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 an open problem related to upper bounds of hypothesis space constraints. 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.
Cite
Text
Liao et al. "Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I12.29284Markdown
[Liao et al. "Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/liao2024aaai-ahpatron/) doi:10.1609/AAAI.V38I12.29284BibTeX
@inproceedings{liao2024aaai-ahpatron,
title = {{Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound}},
author = {Liao, Yun and Li, Junfan and Liao, Shizhong and Hu, Qinghua and Dang, Jianwu},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {13782-13789},
doi = {10.1609/AAAI.V38I12.29284},
url = {https://mlanthology.org/aaai/2024/liao2024aaai-ahpatron/}
}