Mistake-bounded online learning with operation caps
This work addresses computational efficiency in online learning for researchers in theoretical machine learning, but appears incremental as it extends existing results to operation caps.
The paper tackles the problem of mistake-bounded online learning with caps on arithmetic operations per round, proving general bounds on the minimum operations needed to learn arbitrary function families with finitely many mistakes, and solves a specific problem from prior work on agnostic learning with bandit feedback.
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.