<p>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, <em>Neural Network Nearning</em>) or the VC-dim of a neural network with a certain number of nodes (Thm. 3.6 in Kearns &amp; Vazirani,  <em>An Introduction to Computational Learning Theory</em>.</p>

CC BY-SA 3.0
2014-07-22T20:15:39.837Z
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.
Aryeh
CC BY-SA 3.0
2014-07-22T21:09:00.123Z
Thanks, yes sure there might be some results that apply to a set of models, but I think a zoo would still be useful :)
Franck Dernoncourt
CC BY-SA 3.0
2014-07-23T02:51:20.353Z
@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?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-07-23T03:03:59.140Z
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.
Aryeh
CC BY-SA 3.0
2014-07-23T03:06:21.900Z
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.
Aryeh
CC BY-SA 3.0
2014-07-22T20:12:54.197Z
2014-07-22T20:12:54.197Z
Aryeh
<p>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).</p>

<p>It would be in the same spirit as the <a href="https://complexityzoo.uwaterloo.ca" rel="nofollow">Complexity Zoo</a>, which gathers most of the known complexity classes, or the textbook <a href="http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness" rel="nofollow">Computers and Intractability</a>, which catalogues many NP-Complete problems.</p>

CC BY-SA 3.0
2014-07-22T02:56:40.153Z
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?"
usul
<reference-request><lg.learning><vc-dimension>
Resource listing models with known VC dimension
Franck Dernoncourt
# Resource listing models with known VC dimension

(Asked by: username_0 on 2014-07-21)

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](https://complexityzoo.uwaterloo.ca), which gathers most of the known complexity classes, or the textbook [Computers and Intractability](http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness), which catalogues many NP-Complete problems.

**Tags:** reference-request, lg.learning, vc-dimension
> **Comments:**
> **username_1**: 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?"  

---

## 1 answers

### Answer by username_2 on 2014-07-22. Score: 5

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*.

> **Comments:**
> **username_2**: 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.  
> **username_0**: Thanks, yes sure there might be some results that apply to a set of models, but I think a zoo would still be useful :)  
> **username_3**: @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?  
> **username_2**: 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.  
> **username_2**: 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.  

---

