Is there any reference resource gathering models with known VC dimension? I am looking for an exhaustive list of models with their VC dimension (and ideally the associated proof or a pointer to it).

It would be in the same spirit as the Complexity Zoo, which gathers most of the known complexity classes, or the textbook Computers and Intractability, which catalogues many NP-Complete problems.

  • $\begingroup$ Just a funny side note, it sounded to me on first read like you wanted "resource-gathering models". Suggest a change of title to maybe something like "Resources listing known VC Dimensions?" $\endgroup$ – usul Jul 22 '14 at 2:56

Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded depth/fanin (Lemma 8.6 in Bartlett and Anthony, Neural Network Nearning) or the VC-dim of a neural network with a certain number of nodes (Thm. 3.6 in Kearns & Vazirani, An Introduction to Computational Learning Theory.

  • $\begingroup$ The reason we have a complexity zoo is that we don't have good structural characterizations of NP-hard problems. The situation with VC-dimension is "better", hence no zoo. $\endgroup$ – Aryeh Jul 22 '14 at 20:15
  • $\begingroup$ Thanks, yes sure there might be some results that apply to a set of models, but I think a zoo would still be useful :) $\endgroup$ – Franck Dernoncourt Jul 22 '14 at 21:09
  • $\begingroup$ @Aryeh I am curious, Can you elaborate more on what you mean by structural characterizations of NP-hard problems? How is such characterization is related to the P vs NP problem? $\endgroup$ – Mohammad Al-Turkistany Jul 23 '14 at 2:51
  • $\begingroup$ I'll illustrate by an example. 3 Term DNFs and 3-CNFs over the same literals have roughly the same VC dimension. However, deciding whether a given labeled sample admits a consistent 3-CNF is in polytime, while the decision problem for 3 Term DNF is NP-hard. $\endgroup$ – Aryeh Jul 23 '14 at 3:03
  • $\begingroup$ The point is that for discrete concept classes, VC upper bounds largely amount to cardinality estimates (lower bounds often involve more work, as they tend to actually construct a shattered set). But of course, cardinality is far too crude an indicator of computational hardness. $\endgroup$ – Aryeh Jul 23 '14 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.