Research
Optimal Randomized Proper Online Learning
arXiv:2609.21445v1 Announce Type: new Abstract: We prove that the optimal expected mistake bound of online learning a function class H by a randomized proper learning algorithm is O(mathtt{L}(H) log T
arXiv:2609.21445v1 Announce Type: new Abstract: We prove that the optimal expected mistake bound of online learning a function class H by a randomized proper learning algorithm is O(mathtt{L}(H) log T), where mathtt{L}(H) is the Littlestone dimension of H and T is the time horizon. Our result improves upon the previously best known bound of O(mathtt{L}(H) log^6 T) given by Daskalakis and Golowich (STOC 2022), and is optimal up to a universal constant for worst-case classes.
Source: arXiv cs.LG | 2026-09-21