Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

VC-dimension (after Vapnik and Chervonenkis) is a measure of the power of a set of shapes (ranges) to realize subsets of points. VC-dimension is a vital analysis tool in the fields of machine learning and computational geometry.

37
votes
3answers
1k views

Parameterized complexity of Hitting Set in finite VC-dimension

I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
15
votes
1answer
449 views

VC dimension of polynomials over tropical semirings?

As in this question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ problem for tropical $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the ...
14
votes
0answers
340 views

Applications of fat shattering dimension in computational geometry

The fat shattering dimension generalizes the notion of VC-dimension to handle function classes where the range is $(0,1)$, instead of $\{0,1\}$. Fat shattering dimension plays the same role as VC-...
12
votes
2answers
502 views

Estimating VC-Dimension

What is known about the following problem? Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-...
10
votes
3answers
876 views

Resource / book for recent advances in statistical learning theory

I'm quite familiar with the theory behind VC-Dimension, but I'm now looking at the recent (last 10 years) advances in statistical learning theory: (local) Rademacher averages, Massart's Finite Class ...
9
votes
2answers
2k views

VC-dimension of spheres in 3 dimension

I am searching for the VC-dimension of the following set system. Universe $U=\{p_1,p_2,\ldots,p_m\}$ such that $U\subseteq \mathbb{R}^3$. In the set system $\mathcal{R}$ each set $S\in \mathcal{R}$ ...
8
votes
1answer
306 views

How intrinsic is the $d^d$ term in the running time for constructing $\varepsilon$-nets in range spaces of VC-dimension d?

An $\varepsilon$-net for a range space $(X,\mathcal{R})$ is a subset $N$ of $X$ such that $N\cap R$ is nonempty for all $R\in \mathcal{R}$ such that $|X\cap R| \ge \varepsilon |X|$. Given a range ...
8
votes
1answer
378 views

VC Dimension generalized to discrete, non-binary, unordered domains?

VC dimension is a measure of the complexity of classes of functions $f:X\rightarrow \{0,1\}$ that is closely tied to sample complexity. Fat shattering dimension is a generalization suited to richer ...
8
votes
1answer
326 views

VC-dimension of Cylinders within a Cylinder

I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows: $X$ is the cylinder $\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\}$ The ranges in $\mathcal{R}$ are formed by ...
7
votes
2answers
3k views

VC dimension of polynomials (in one variable) of degree d

Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$. I am searching for ideas that can prove the ...
7
votes
1answer
349 views

What is the VC Dimension of the $k-$Junta class

A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension ...
7
votes
2answers
256 views

The complexity of recognizing optimal set systems for the V-C dimension

The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\...
6
votes
4answers
535 views

Small $\epsilon$-nets for points and half-planes without VC dimension

I have recently learned the proof of Haussler and Welzl of the following theorem. Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ ...
6
votes
2answers
261 views

Proper PAC learning VC dimension bounds

It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\...
6
votes
1answer
91 views

Hidden constant in eps-sample size computation

Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ O\left(\frac{1}{\varepsilon^2}\left(d+\log\frac{1}{\...
5
votes
1answer
286 views

Do combinatorial discrepancy upper bounds lead to smaller $epsilon$-nets (as with $epsilon$-samples)?

An $\epsilon$-sample (or $\epsilon$-approximation) of a family of subsets $\mathcal{S}$ of a ground set $X$ is a subset $P \subseteq X$ which preserves relative sizes of sets up to $\epsilon$. I.e., ...
5
votes
1answer
241 views

VC-Dimension and sample complexity dependent on size of subsets

I have a range space $(X,R)$, were $R$ is a collection of subsets of $R$ and I have an upper bound $d$ to the VC-dimension of $(X,R)$. Suppose for simplicity that $X$ is finite. Given $\delta\in(0,1)$ ...
4
votes
1answer
126 views

Tight VC bound for agnostic learning

The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound? Theorem. Let $\...
3
votes
1answer
263 views

Resource listing models with known VC dimension

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). ...
3
votes
2answers
155 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
3
votes
1answer
106 views

Rademacher complexity for piecewise-linear convex function

Consider a function family $$\ell(x)=\max_{1\leq k\leq K} a_k^\top x + b_k,$$ where $a_k,b_k \in \mathbb{R}^d$ are bounded in the sense of some norm and $K\geq 2$. What is the best upper bound on the ...
3
votes
1answer
161 views

PAC-learning bound with epsilon-cover of hypothesis class

In this video at 43:00, a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted: $$\epsilon^2 < \frac{\log{|H_\epsilon|} + \log{1/\delta}}{2m}$$ ...
3
votes
1answer
116 views

Tighter Probability Bounds

Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
2
votes
1answer
80 views

Other Uniform Bound

In theoretical machine learning, VC-dimension (VCD) and Rademacher average (RA) are two frequently used uniform bounds, providing better sample complexity than bounds such as Chernoff bound and ...
2
votes
1answer
112 views

Characterizing the exponential savings in active learning

Let $H$ be a hypothesis class with VC dimension $d$. In supervised learning, we need almost $O(\frac{d}{\epsilon})$ random labelled examples to return a hypothesis within $\epsilon$ from the target (...
2
votes
1answer
265 views

Are there closed-form expressions providing the VC-dimension for the multi-class case for different classifiers?

So far, I've only encountered the VC-dim for binary classifiers. I'm interested to learn how this notion can be extended to the multi-class case. Are there expressions that provide bounds on the out-...
2
votes
1answer
205 views

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 ...
2
votes
0answers
187 views

Expected probability of error in Vapnik's book

In Vapnik's book "Statistical Learning Theory", Theorem 10.5 states that - for a Support Vector Machine - the expected probability of error (of the optimal hyperplane) is upper bounded by $1/(l+1)$ ...
2
votes
0answers
81 views

(eps,delta)-approx with VC-Dimension 1?

I have a domain $X$ and a set system $R$ on $X$, such that the sets in $R$ are one included in the other, that is, for any $A,B\in R$, either $A\subseteq B$ or $B\subseteq A$. The sets are not all ...
2
votes
0answers
682 views

VC dimension of intersection of half-spaces

Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$ for $i=1,...,n$, where $x \in \mathbb{R}^d$. Then define the classifier $$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$ which represents ...
2
votes
0answers
313 views

VC dimension for ellipsoidal classifiers

What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as $$ g( x, (P_1,p_2,p_3), ) := \text{sgn} \left( x^\...
1
vote
1answer
147 views

What is the VC dimension of Turing machines with specified maximum size?

Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine. I chose Turing machines in the question to make the question concrete, but I'm also more ...
1
vote
0answers
119 views

How to find the shattering set size without visualising the target function behaviour?

My aim is to prove a vc-dimension $d$ for different problems. All the problems I have do not have visualised target function (or concept) . I know this is unnecessarily. But this unlike most of the ...
1
vote
0answers
141 views

Hitting sets for sets of VC dimension d

Let $S$ be a collection of sets of binary vectors (in $\{0,1\}^m$) $S_1, S_2, \dotsc, S_t$ (say $t = O(m^d)$) each of VC dimension $d$. What can be said about the size of a hitting set $S_\text{hit}$ ...
1
vote
0answers
175 views

Rademacher Averages, VC shatter coefficient, and eps-approximations

I am learning about Rademacher averages and their relation to VC-dimension for a project I am working on, but I am not sure I got everything right, so I will recap what I understood below and I would ...
0
votes
1answer
301 views

Bounding Rademacher Averages, with and without chaining

One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma: $$ R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n} $$ where $\|\cdot\|$...
0
votes
0answers
52 views

Different estimators for uniform convergence of means/averages to expectations

In uniform converge results of means or averages to their expectations (think of the typical results involving VC-dimension, covering numbers, Pseudo-dimension, fat shattering dimension, ...) , the ...
-2
votes
1answer
95 views

VC dimension in data mining

Can someone please explain to me (with normal language) - how is VC dimension related to data mining (frequent itemset mining - PAC learning). (incl. how we define range space as it's written in ...