mlsanityData to 14 Oct 2026

Mistake-bounded online learning with operation caps

arXiv 2509.03892 ↗First posted 4 Sep 2025cs.LG cs.CC cs.DMcited by 3

Not on the map. Why?

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.

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

13 of 37 references.

References · 13

  1. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 23
  2. 2023Optimal Prediction Using Expert Advice and Randomized Littlestone Dimensioncited by 18
  3. 2023A Trichotomy for Transductive Online Learningcited by 14
  4. 2021A note on the price of bandit feedback for mistake-bounded online learningcited by 9
  5. 2024Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffscited by 9
  6. 2024Multiclass Transductive Online Learningcited by 8
  7. 2025Online Learning of Neural Networkscited by 5
  8. 2022Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learningcited by 4
  9. 2023Online Learning of Smooth Functionscited by 4
  10. 2024Bounds on the price of feedback for mistake-bounded online learningcited by 4
  11. 2024RAIN: Reinforcement Algorithms for Improving Numerical Weather and Climate Modelscited by 3
  12. 2024Improved Online Learning Algorithms for CTR Prediction in Ad Auctionscited by 2
1 more
  1. 2024Incremental Online Learning of Randomized Neural Network with Forward Regularizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-Endcited by 5
  2. 2026Online Realizable Regression and Applications for ReLU Networkscited by 1
  3. 2026Online learning of smooth functions on ℝcited by 0