Near-tight Closure Bounds for the Littlestone and Threshold Dimensions

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:686-696, 2021.

Abstract

We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ of binary 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 an open question posed by their work.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-ghazi21a, title = {Near-tight Closure Bounds for the {L}ittlestone and Threshold Dimensions}, author = {Ghazi, Badih and Golowich, Noah and Kumar, Ravi and Manurangsi, Pasin}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {686--696}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/ghazi21a/ghazi21a.pdf}, url = {https://proceedings.mlr.press/v132/ghazi21a.html}, abstract = {We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ of binary 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 an open question posed by their work.} }
Endnote
%0 Conference Paper %T Near-tight Closure Bounds for the Littlestone and Threshold Dimensions %A Badih Ghazi %A Noah Golowich %A Ravi Kumar %A Pasin Manurangsi %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-ghazi21a %I PMLR %P 686--696 %U https://proceedings.mlr.press/v132/ghazi21a.html %V 132 %X We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes $\mathcal{H}_1, \ldots, \mathcal{H}_k$ of binary 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 an open question posed by their work.
APA
Ghazi, B., Golowich, N., Kumar, R. & Manurangsi, P.. (2021). Near-tight Closure Bounds for the Littlestone and Threshold Dimensions. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:686-696 Available from https://proceedings.mlr.press/v132/ghazi21a.html.

Related Material