# VC dimension of cone-restricted linear classifiers

Let $\mathcal{C}$ be a pointed, salient cone in $\mathbb{R}^d$. We may also assume that $\mathcal{C}$ is full-dimensional. Consider the set of binary classifiers $$\mathcal{H} = \{\boldsymbol{x}\mapsto\boldsymbol{1}\hspace{-0.9ex}\mathrm{1}(\boldsymbol{h}^\mathsf{T}\boldsymbol{x}\ge 0)\mid \boldsymbol{h} \in \mathcal{C} \}.$$ Is there any bound known for the VC-dimension of $\mathcal{H}$ that depends on $\mathcal{C}$ and can be significantly better than the VC-dimension of the set of all (linear) classifiers in $\mathbb{R}^d$ (i.e., $d$)?

Edit: Above, $\boldsymbol{1}\hspace{-0.9ex}\mathrm{1}(\cdot)$ denotes the binary indicator function. So a more explicit definition of $\mathcal{H}$ is the set of functions $$f_\boldsymbol{h}(\boldsymbol{x})=\begin{cases} 0 & \text{if }\boldsymbol{h}^\mathsf{T}\boldsymbol{x}<0 \\ 1 & \text{if }\boldsymbol{h}^\mathsf{T}\boldsymbol{x}\ge0\end{cases},$$ parametrized by $\boldsymbol{h}\in \mathcal{C}$.

• I'm sorry but I don't understand your notation. What is $\mathcal H$? Aug 30, 2016 at 20:35
• @domotorp I have explained the notation in added edit line. I hope the definition of $\mathcal{H}$ is clear now.
– S.B.
Aug 30, 2016 at 21:09
• Thx, now it's clear. I just wonder why you use functions instead of sets, so I would define $S_h=\{x \mid h^Tx\ge 0\}$. Aug 31, 2016 at 4:04
• Also, being pointed or salient doesn't change much, at most a factor of two. Aug 31, 2016 at 4:07
• And there's one more thing missing - what are (linear) classifiers? Aug 31, 2016 at 4:09

No, I claim that the set of $d$ unit vectors, $e_1=(1,0,\ldots,0)$, $e_2=(0,1,0,\ldots,0)$, $\ldots,$ $e_d=(0,\ldots,0,1)$, along the axes can be shattered, except that for every $\mathcal H$ either the empty set, or all $d$ of the won't be in any $h\in \mathcal H$, so the VC-dimension is $d-1$. (For similar reasons, it cannot be $d$ for any point set.)
Indeed, if $\mathcal H$ is the opposite of the cone spanned by the above $d$ vectors, i.e., the all-negative hyperoctant, and $h_I=-\sum_{i\in I} e_i$, then $f_h(e_i)=0$ if and only if $i\in I$.
• Is this independent of the cone $\mathcal{C}$ (i.e., the domain where $\boldsymbol{h}$ lives in)?
• Yes, it works the same for any full-dimensional cone, you just have to replace the $e_i$ with other vectors whose negation is in the cone. Sep 1, 2016 at 5:27