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 the intersection of $n$ linear functions and hence a convex polytope in $\mathbb{R}^d$ with $n$ facets.

What is the VC dimension of the family of all $g$ of this form?

I found that an upper bound is $2 (d+1) n \text{log}_2( (d+1)n ).$

  • 1
    $\begingroup$ VC dimension is normally defined for range spaces — pairs $(X, R)$ where $X$ is a set of points and $R\subseteq 2^X$ is a set of subsets of $X$ called ranges. (Range spaces are also called set systems.) I assume you want $X$ to be a convex polyhedron, but what are your ranges? Or is $X=\mathbb{R}^n$ and $R$ the set of convex polyhedra? $\endgroup$ – Jeffε May 2 '13 at 14:13
  • $\begingroup$ I mean that $X$ is a convex polyhedron in dimension $n$ formed by the intersection of $n$ half-spaces. $\endgroup$ – user693 May 2 '13 at 15:05
  • 1
    $\begingroup$ And what is $R$? $\endgroup$ – Jeffε May 2 '13 at 16:00
  • 3
    $\begingroup$ on the off chance that you got confused and meant to say that $X$ is $\mathbb{R}^n$ and $R$ is all translates of a convex polytope, does this answer your question: arxiv.org/pdf/0907.5223v2.pdf (the VC-dimension is infinite in $n=3$ and at most $3$ in $n=2$) $\endgroup$ – Sasho Nikolov May 2 '13 at 18:55
  • 2
    $\begingroup$ so you actually mean the range space of all convex polytopes, taken as subsets of $\mathbb{R}^n$. you should understand that the VC dimension of "a polytope" is 0, because it's a single set! you need some family of sets here. $\endgroup$ – Sasho Nikolov May 2 '13 at 20:48

It has been recently shown by Csikos, Kupavskii, Mustafa in "Optimal Bounds on the VC-dimension" that the VC dimension of $k$-fold unions (or intersections or XORs) of half-spaces in $R^d$ behaves as $$ \Theta(dk\log k).$$

| cite | improve this answer | |

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.