How to deal with concept classes with exponential value of VC dimension

Let $C$ be a concept class with VC dimension $d$ exponential to the input size (i.e number of variables represented in each concept $c\in C$). I am looking for papers/resources/suggestions of how computational learning community handle the learnability of $C$.

One thing I am thinking about is investigating the learnability of $C$ in active learning. Hoping that I will end up with less number of examples required.

However, I prefer to stick with the passive learning for now and wondered what else I can do for this poor $C$? As I am new to the field, I also wish to have some examples of concept classes with exponential VC dimension.

• You need your number of samples to scale linearly with VC dimension or you cannot even do supervised learning. This is a lower bound, see: cis.upenn.edu/~mkearns/papers/lower.ps Mar 10, 2014 at 18:23
• Its also confusing what you are asking for... Suppose each $c \in C$ can be described with d bits. Then trivially, $|C| \leq 2^d$, and hence $VCDIM(C) \leq d$ -- so the VC-Dimension of a class is never more than linear in the description length of one of the concepts in the class. I guess you must mean something different by "number of variables represented in each concept c", but I'm not sure what. Mar 11, 2014 at 21:36

One approach would be to stratify your concept class by VC-complexity. For example, suppose that $$C$$ is the set of all functions $$f:\{0,1\}^n\to\{0,1\}$$; its VC-dim is $$2^n$$. However, you can decompose $$C$$ in any number of ways. Say, $$C_k$$ is the collection of all functions whose (minimal) binary tree has depth $$k$$ or less. Or, $$C_k$$ is the set of all functions whose Fourier expansion puts no weight on XORs of more than $$k$$ bits. Then $$C_1\subset C_2 \subset \ldots \subset C_n$$, and selecting the appropriate $$C_k$$ is the problem of model selection. Machine learning theory offers a principled way of doings this via Structural Risk Minimization; here is a good start: Link