Optimal mistake bounds achieved for online learning with randomization
Optimal Randomized Proper Online Learning
Machine Learning
Summary
When computers learn from data step-by-step without knowing the future, they sometimes make mistakes. This paper shows how to minimize those mistakes to the best possible level for a certain type of learning that picks solutions only from a fixed set and uses random choices. The authors improved the known math to show fewer mistakes happen as the number of learning steps grows. This helps understand the limits of such learning methods in the worst cases.
What this means in practice
- •For machine learning engineers: Design online learning systems that minimize prediction errors over time optimally when using randomized proper methods.
- •For automated decision system developers: Set theoretical performance limits for adaptive algorithms in environments where decisions must be made sequentially and with restricted hypotheses.
A theory result. No direct application yet.
Authors
Zachary Chase, Idan Mehalel
Abstract
We prove that the optimal expected mistake bound of online learning a function class $\mathcal{H}$ by a randomized proper learning algorithm is $O(\mathtt{L}(\mathcal{H}) \log T)$, where $\mathtt{L}(\mathcal{H})$ is the Littlestone dimension of $\mathcal{H}$ and $T$ is the time horizon. Our result improves upon the previously best known bound of $O(\mathtt{L}(\mathcal{H}) \log^6 T)$ given by Daskalakis and Golowich (STOC 2022), and is optimal up to a universal constant for worst-case classes.