研究在线学习中每轮操作受限时的错误上限，给出理论下界。
Mistake-bounded online learning with operation caps
- 在每轮操作数受限条件下分析在线学习的错误边界。
- 证明任意有限错误函数族所需最小操作数的通用下界。
- 解决带偏差反馈的在线学习难题，适用于资源受限场景。
我们研究了在每轮算术操作次数受限条件下的在线学习错误边界模型。证明了对于任意具有有限错误的函数族，学习所需的最小每轮算术操作数的通用下界。解决了Filmus等（2024）和Geneson & Tang（2024）提出的关于带偏差反馈的泛化错误边界在线学习问题。同时将该结果扩展至操作数受限的设定。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。