Near-tight closure bounds for Littlestone and threshold dimensions
This work addresses a theoretical question in learning theory, providing near-optimal closure bounds for dimensions used in online learning and classification, which is incremental but resolves an open problem.
The paper tackles the problem of bounding the Littlestone and threshold dimensions of binary hypothesis classes under arbitrary aggregation rules, establishing nearly tight upper bounds that improve exponentially over previous results.
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ of Boolean functions with bounded Littlestone (respectively, threshold) dimension, we establish an upper bound on the Littlestone (respectively, threshold) dimension of the class defined by applying an arbitrary binary aggregation rule to $\mathcal{H}_1, \ldots, \mathcal{H}_k$. We also show that our upper bounds are nearly tight. Our upper bounds give an exponential (in $k$) improvement upon analogous bounds shown by Alon et al. (COLT 2020), thus answering a question posed by their work.