Lune

AAAI2024Top-tier venue

Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound

Yun Liao, Junfan Li, Shizhong Liao, Qinghua Hu, Jianwu Dang

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Regret Bounds for Online Kernel Selection in Continuous Kernel SpaceXiao Zhang, Shizhong Liao, Jun Xu, Ji-Rong WenAAAI 2021 · 3 citations
  2. On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial NoiseJie ShenICML 2021 · 15 citations
  3. Exploiting the Surrogate Gap in Online Multiclass ClassificationDirk van der HoevenNeurIPS 2020 · 12 citations
  4. Improved Kernel Alignment Regret Bound for Online Kernel LearningJunfan Li, Shizhong LiaoAAAI 2023 · 3 citations
  5. Fast Co-Training under Weak Dependence via Stream-Based Active LearningIlias Diakonikolas, Mingchen Ma, Lisheng Ren, Christos TzamosICML 2024 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines