Mistake-bounded online learning with operation caps

Jesse Geneson, Meien Li, Linus Tang
9/4/2025
cs.LGcs.CCcs.DM

No confident code implementation found for this paper.

Abstract

We investigate the mistake-bound model of online learning with caps on the number of arithmetic operations per round. We prove general bounds on the minimum number of arithmetic operations per round that are necessary to learn an arbitrary family of functions with finitely many mistakes. We solve a problem on agnostic mistake-bounded online learning with bandit feedback from (Filmus et al, 2024) and (Geneson \& Tang, 2024). We also extend this result to the setting of operation caps.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Bounds on the price of feedback for mistake-bounded online learning

82% match2024

Optimal Mistake Bounds for Transductive Online Learning

82% match2025

Multiclass Transductive Online Learning

82% match2024

On Computable Online Learning

82% match2023

On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective

80% match2024

A Trichotomy for Transductive Online Learning

79% match2026

Cite this paper

@article{geneson2025mistakebounded,
  title  = {Mistake-bounded online learning with operation caps},
  author = {Jesse Geneson and Meien Li and Linus Tang},
  year   = {2025},
  eprint = {2509.03892},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2509.03892v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2509.03892.svg)](https://codeofpaper.com/paper/2509.03892)

Discussion