3
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Jul 22, 2014 at 2:56

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • $\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
    Commented Jul 22, 2014 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$ Commented Jul 22, 2014 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$ Commented Jul 23, 2014 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
    Commented Jul 23, 2014 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
    Commented Jul 23, 2014 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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