The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement

Steve Hanneke
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:2308-2359, 2024.

Abstract

This article presents a number of elementary observations and relations concerning commonly-studied combinatorial dimensions from the learning theory literature on classification and reinforcement learning: namely, the star number, eluder dimension, VC dimension, Littlestone dimension, threshold dimension, and cardinality of the class. One theme of the work is understanding how these dimensions may be re-expressed as natural dimensions of the convexity space of version spaces. Specifically, we find that the star number is precisely the VC dimension of version spaces (and of their disagreement regions), whereas the eluder dimension is precisely the threshold dimension of version spaces (and of their disagreement regions). We are also interested in understanding direct relations among these dimensions. For instance, we show that there is no infinite concept class with both finite Littlestone dimension and finite star number. Moreover, any infinite concept class must have infinite eluder dimension. In both cases, we also provide quantitative relations to the cardinality of the class. For the latter result, we also show an analogous relation for real-valued functions, where the cardinality of the class is replaced by the $L_\infty$ covering number. As another relation between star numbers and VC dimension, we provide a simple, precise, and general characterization of the VC dimension of the minimal intersection-closed class containing a given concept class: namely, the 1-centered star number of the original class. Moreover, we generalize this result to provide a unifying approach to the design of certain sample compression schemes, along with a simple combinatorial dimension characterizing its compression size: the minimum star number. We also discuss a number of implications of many of these observations. Though the proofs of the above observations are actually all incredibly simple, it is interesting that such fundamental relations among these well-known quantities appear to have heretofore gone unnoticed in the literature.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-hanneke24a, title = {The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement}, author = {Hanneke, Steve}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {2308--2359}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/hanneke24a/hanneke24a.pdf}, url = {https://proceedings.mlr.press/v247/hanneke24a.html}, abstract = {This article presents a number of elementary observations and relations concerning commonly-studied combinatorial dimensions from the learning theory literature on classification and reinforcement learning: namely, the star number, eluder dimension, VC dimension, Littlestone dimension, threshold dimension, and cardinality of the class. One theme of the work is understanding how these dimensions may be re-expressed as natural dimensions of the convexity space of version spaces. Specifically, we find that the star number is precisely the VC dimension of version spaces (and of their disagreement regions), whereas the eluder dimension is precisely the threshold dimension of version spaces (and of their disagreement regions). We are also interested in understanding direct relations among these dimensions. For instance, we show that there is no infinite concept class with both finite Littlestone dimension and finite star number. Moreover, any infinite concept class must have infinite eluder dimension. In both cases, we also provide quantitative relations to the cardinality of the class. For the latter result, we also show an analogous relation for real-valued functions, where the cardinality of the class is replaced by the $L_\infty$ covering number. As another relation between star numbers and VC dimension, we provide a simple, precise, and general characterization of the VC dimension of the minimal intersection-closed class containing a given concept class: namely, the 1-centered star number of the original class. Moreover, we generalize this result to provide a unifying approach to the design of certain sample compression schemes, along with a simple combinatorial dimension characterizing its compression size: the minimum star number. We also discuss a number of implications of many of these observations. Though the proofs of the above observations are actually all incredibly simple, it is interesting that such fundamental relations among these well-known quantities appear to have heretofore gone unnoticed in the literature.} }
Endnote
%0 Conference Paper %T The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement %A Steve Hanneke %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-hanneke24a %I PMLR %P 2308--2359 %U https://proceedings.mlr.press/v247/hanneke24a.html %V 247 %X This article presents a number of elementary observations and relations concerning commonly-studied combinatorial dimensions from the learning theory literature on classification and reinforcement learning: namely, the star number, eluder dimension, VC dimension, Littlestone dimension, threshold dimension, and cardinality of the class. One theme of the work is understanding how these dimensions may be re-expressed as natural dimensions of the convexity space of version spaces. Specifically, we find that the star number is precisely the VC dimension of version spaces (and of their disagreement regions), whereas the eluder dimension is precisely the threshold dimension of version spaces (and of their disagreement regions). We are also interested in understanding direct relations among these dimensions. For instance, we show that there is no infinite concept class with both finite Littlestone dimension and finite star number. Moreover, any infinite concept class must have infinite eluder dimension. In both cases, we also provide quantitative relations to the cardinality of the class. For the latter result, we also show an analogous relation for real-valued functions, where the cardinality of the class is replaced by the $L_\infty$ covering number. As another relation between star numbers and VC dimension, we provide a simple, precise, and general characterization of the VC dimension of the minimal intersection-closed class containing a given concept class: namely, the 1-centered star number of the original class. Moreover, we generalize this result to provide a unifying approach to the design of certain sample compression schemes, along with a simple combinatorial dimension characterizing its compression size: the minimum star number. We also discuss a number of implications of many of these observations. Though the proofs of the above observations are actually all incredibly simple, it is interesting that such fundamental relations among these well-known quantities appear to have heretofore gone unnoticed in the literature.
APA
Hanneke, S.. (2024). The Star Number and Eluder Dimension: Elementary Observations About the Dimensions of Disagreement. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:2308-2359 Available from https://proceedings.mlr.press/v247/hanneke24a.html.

Related Material