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 – Lev Reyzin Mar 10 '14 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. – Aaron Roth Mar 11 '14 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: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=705570&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel4%2F18%2F15247%2F00705570.pdf%3Farnumber%3D705570