7
$\begingroup$

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 ).$

Improve this question
$\endgroup$
9
  • 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ε
    Commented May 2, 2013 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
    Commented May 2, 2013 at 15:05
  • 1
    $\begingroup$ And what is $R$? $\endgroup$
    – Jeffε
    Commented May 2, 2013 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
    Commented May 2, 2013 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
    Commented May 2, 2013 at 20:48

1 Answer 1

Reset to default
3
$\begingroup$

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),$$ https://jmlr.org/papers/v20/18-719.html

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ The upper bound for the intersection of halfspaces is well known and predates the work by Mustafa etal. $\endgroup$
    – Sariel Har-Peled
    Commented Jul 13, 2021 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
    Commented Jul 13, 2021 at 17:02

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.