<p>It has been recently shown by Csikos, Kupavskii, Mustafa
in &quot;Optimal Bounds on the VC-dimension&quot; that the VC dimension of <span class="math-container">$k$</span>-fold unions (or intersections or XORs) of half-spaces in <span class="math-container">$R^d$</span> behaves as
<span class="math-container">$$ \Theta(dk\log k),$$</span>
<a href="https://jmlr.org/papers/v20/18-719.html" rel="nofollow noreferrer">https://jmlr.org/papers/v20/18-719.html</a></p>
<p>Additionally, in a recent tour de force, Kupavskii has given a polynomial bound on the VC-dimension of <span class="math-container">$k$</span>-vertex polytopes:
<a href="https://link.springer.com/article/10.1007/s00493-020-4475-4" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00493-020-4475-4</a></p>

CC BY-SA 4.0
2021-07-13T15:59:25.277Z
The upper bound for the intersection of halfspaces is well known and predates the work by Mustafa etal.
Sariel Har-Peled
CC BY-SA 4.0
2021-07-13T17:02:46.770Z
Indeed. It's the lower bound that was non-trivial. And the k-vertex polytope question was open for 30 years.
Aryeh
CC BY-SA 4.0
2019-03-06T10:00:03.580Z
2021-12-22T16:38:37.203Z
2021-12-22T16:38:37.203Z
Aryeh
<p>Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$</p>

<p>for $i=1,...,n$, where $x \in \mathbb{R}^d$.</p>

<p>Then define the classifier</p>

<p>$$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$</p>

<p>which represents the intersection of $n$ linear functions and hence a convex polytope in $\mathbb{R}^d$ with $n$ facets.</p>

<p>What is the VC dimension of the family of all $g$ of this form?</p>

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

CC BY-SA 3.0
2013-05-02T14:13:48.187Z
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?
Jeffε
CC BY-SA 3.0
2013-05-02T15:05:13.390Z
I mean that $X$ is a convex polyhedron in dimension $n$ formed by the intersection of $n$ half-spaces.
user693
CC BY-SA 3.0
2013-05-02T16:00:48.073Z
And what is $R$?
Jeffε
CC BY-SA 3.0
2013-05-02T18:55:47.650Z
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: http://arxiv.org/pdf/0907.5223v2.pdf (the VC-dimension is infinite in $n=3$ and at most $3$ in $n=2$)
Sasho Nikolov
CC BY-SA 3.0
2013-05-02T19:56:29.207Z
Thanks for the reference. Let me reformulate the question.
user693
CC BY-SA 3.0
2013-05-02T20:15:35.920Z
I have found in [Haussler, Welzl - Epsilon nets and simplex range queries] that for a polytope of dimension $d$ with $n$ facets, the VC dimension is upper bounded by $2 (d+1) n \text{log}_2( (d+1)n )$. I do not know if a better bound is known.
user693
CC BY-SA 3.0
2013-05-02T20:48:47.823Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-05-02T21:06:41.067Z
Thanks again. I meant the VC dimension of $g$. I am brand new to the concept of VC dimension.
user693
CC BY-SA 3.0
2013-05-12T00:31:45.017Z
Well, $d*n$ is an easy lower bound. I suspect this is the correct bound, but proving it is going to be not easy.
Sariel Har-Peled
<cg.comp-geom><machine-learning><lg.learning><vc-dimension><high-dimensional-geometry>
VC dimension of intersection of half-spaces
user693
# VC dimension of intersection of half-spaces

(Asked by: username_0 on 2013-05-02)

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

**Tags:** cg.comp-geom, machine-learning, lg.learning, vc-dimension, high-dimensional-geometry

> **Comments:**
> **username_1**: 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?  
> **username_0**: I mean that $X$ is a convex polyhedron in dimension $n$ formed by the intersection of $n$ half-spaces.  
> **username_1**: And what is $R$?  
> **username_2**: 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: http://arxiv.org/pdf/0907.5223v2.pdf (the VC-dimension is infinite in $n=3$ and at most $3$ in $n=2$)  
> **username_0**: Thanks for the reference. Let me reformulate the question.  
> **username_0**: I have found in [Haussler, Welzl - Epsilon nets and simplex range queries] that for a polytope of dimension $d$ with $n$ facets, the VC dimension is upper bounded by $2 (d+1) n \text{log}_2( (d+1)n )$. I do not know if a better bound is known.  
> **username_2**: 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.  
> **username_0**: Thanks again. I meant the VC dimension of $g$. I am brand new to the concept of VC dimension.  
> **username_3**: Well, $d*n$ is an easy lower bound. I suspect this is the correct bound, but proving it is going to be not easy.  

---

## 1 answers

### Answer by username_4 on 2019-03-06. Score: 3

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>

> **Comments:**
> **username_3**: The upper bound for the intersection of halfspaces is well known and predates the work by Mustafa etal.  
> **username_4**: Indeed. It's the lower bound that was non-trivial. And the k-vertex polytope question was open for 30 years.  

---

