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$ 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$ 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).$$ Additionally, in a recent tour de force, Kupavskii has given a polynomial bound on the VC-dimension of $k$-vertex polytopes: https://link.springer.com/article/10.1007/s00493-020-4475-4

  • $\begingroup$ The upper bound for the intersection of halfspaces is well known and predates the work by Mustafa etal. $\endgroup$ Jul 13 at 15:59
  • $\begingroup$ Indeed. It's the lower bound that was non-trivial. And the k-vertex polytope question was open for 30 years. $\endgroup$
    – Aryeh
    Jul 13 at 17:02

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.