Research map / Bandits and online learning / Online convex optimization and games

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

AAAI 2024 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 4 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Ahpatron, a budgeted online kernel learner that approximates an aggressive Perceptron (AVP) by halving the active set and projecting removed examples onto the remaining ones, achieving a tighter deterministic mistake bound and resolving an open problem on the hypothesis-space constraint U.

Problem

Online kernel learning under a fixed memory budget B suffers worse mistake bounds than unbudgeted methods, and existing budgeted bounds either are only expected, depend poorly on B, or carry an unresolved ln^{-1/2}(B+1) factor in the hypothesis-space constraint U.

Approach

Combines an aggressive Perceptron variant (AVP) that updates on low-confidence margins (y f(x) < 1 - epsilon) with a budget mechanism that removes half of the active set and projects the removed examples' contribution onto the span of the kept examples, yielding a deterministic mistake bound L_T(f)+O(U L_T(f)/sqrt(B)).

Key results

• On phishing (sigma=1), Ahpatron achieves AMR 7.27% with budget 400 versus Projectron++ 7.42% with budget 571; on SUSY it reaches 23.66% vs POMDR 25.36% at the same budget 400.
• Theory: Ahpatron's deterministic bound is L_T(f)+O(U L_T(f)/sqrt(B)), improving on Forgetron (4L_T(f)+2||f||^2) and resolving the open problem by setting U=sqrt(B)/4 without the ln factor.
• Ahpatron with budget 3000 on SUSY achieves 21.97% AMR vs Projectron++ 22.05% at budget 4898, with much lower running time (38.20 s vs 1330.83 s).

Measured effects reported in the paper

Surprising findings

• Projectron++ attains lower AMR than Ahpatron on ijcnn1 and a9a at the same or larger budget, which the authors attribute to its very large budget.
• Reported |N_T| values are large (e.g., 129497 on cod-rna), so the negative correction term is substantial in practice.

Limitations

• The explicit trade-off between mistake bound and budget is left for future work.
• Ahpatron can use a larger budget than Projectron++ and still lose on some datasets (e.g., ijcnn1, a9a), so it does not uniformly dominate baselines.
• Parameters such as epsilon are chosen in hindsight from a grid, and experiments are implemented in R on a single laptop CPU.

Experimental setup

Datasets: phishing a9a w8a SUSY ijcnn1 cod-rna

Benchmarks: phishing SUSY ijcnn1 cod-rna w8a a9a

Metrics: average mistake rate (%) running time (s) budget size

Baselines: Projectron Projectron++ FOGD BOGD++ NOGD POMDR

Builds on: Perceptron Forgetron RBP POMDR ALMA

Closest papers by meaning

• Online Learning of Neural Networks (NeurIPS 2025 · similarity 0.83)
• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.82)
• Optimal Mistake Bounds for Transductive Online Learning (NeurIPS 2025 · similarity 0.82)
• Joker: Joint Optimization Framework for Lightweight Kernel Machines (ICML 2025 · similarity 0.82)
• Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.81)
• Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.81)