# Mistake-bounded online learning with operation caps

arXiv: https://arxiv.org/abs/2509.03892 · HTML: https://mlsanity.com/paper/2509.03892/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 4 Sep 2025.

## Builds on (most cited first, 13 of 13)

- [A Theory of Learning with Autoregressive Chain of Thought](https://mlsanity.com/paper/2503.07932/) (2025)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [A note on the price of bandit feedback for mistake-bounded online learning](https://mlsanity.com/paper/2101.06891/) (2021)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning](https://mlsanity.com/paper/2209.01366/) (2022)
- [Online Learning of Smooth Functions](https://mlsanity.com/paper/2301.01434/) (2023)
- [Bounds on the price of feedback for mistake-bounded online learning](https://mlsanity.com/paper/2401.05794/) (2024)
- [RAIN: Reinforcement Algorithms for Improving Numerical Weather and Climate Models](https://mlsanity.com/paper/2408.16118/) (2024)
- [Improved Online Learning Algorithms for CTR Prediction in Ad Auctions](https://mlsanity.com/paper/2403.00845/) (2024)
- [Incremental Online Learning of Randomized Neural Network with Forward Regularization](https://mlsanity.com/paper/2412.13096/) (2024)

## Built on by (most cited first, 3 of 3)

- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Online learning of smooth functions on ℝ](https://mlsanity.com/paper/2604.03525/) (2026)

## Abstract (arXiv)

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.