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

• 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? May 2, 2013 at 14:13
• I mean that $X$ is a convex polyhedron in dimension $n$ formed by the intersection of $n$ half-spaces. May 2, 2013 at 15:05
• And what is $R$? May 2, 2013 at 16:00
• 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$) May 2, 2013 at 18:55
• 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. May 2, 2013 at 20:48

## 1 Answer

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

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