0
$\begingroup$

Consider a fixed set of vectors $\{x_i\}_{i\in[n]}$ in $\mathbb R^d$ and closed polyhedral cone $C = \{w \in \mathbb R^d : w^\top x_i \geq 0, \forall i \in [n]\}$ with full dimension i.e. $C$ contains a set of $d$ independent vectors. For each $w\in C$, the corresponding labeling hypothesis is given by $h_w(x) = {1}[w^\top x\geq 0]$ where $1[\cdot]$ is an indicator function which outputs 1 if its argument evaluates to true and 0 otherwise. What is the VC dimension of $C$ and how would one go about proving it?

P.S. I am aware of this answer where the author @domotorp suggest that VC should be $d-1$ for any full dimensional cone but their suggestion of replacing set of $e_i$'s by any set of vector(or even any set of $d$ independent vectors) whose negation is in the cone does not seem to work. More concretely, it is not clear if we choose to shatter a set of independent points $\{v_i\}|_{i\in[d]}$ such that $\forall i \in [d], -v_i \in C$, what are the hypotheses in $C$ that should produce a label vector $l$ for all $l \in \{0,1\}^d\backslash\{0^d, 1^d\}$? It seems like some sort of Seperating hyperplane theorem and Radon theorem for cone may help but how exactly is not very clear to me.

$\endgroup$
4
  • $\begingroup$ I agree that the cited answer by @domotorp is quite hard to read. But why can't you take an affine transformation that converts any independent $x_1\ldots,x_d$ to $e_1,\ldots,e_d$ to get an orthant? Now it seems to me that the VC-dim will be even $d$, I don't get why the other answer claims only $d-1$. $\endgroup$
    – domotorp
    Commented Apr 13 at 4:42
  • $\begingroup$ I think the issue is that the cone $C$ can be restricted/pointed and need not contain all hypotheses that would shatter the d independent points. For example, in 2D, we can clearly see that no two points can be shattered by a pointed full dimensional cone - example. So, the VC of that 2D cone seems to align with $VC = d-1 = 1$. $\endgroup$
    – Neophyte
    Commented Apr 15 at 16:30
  • $\begingroup$ In general, if we take a set of $d$ independent vectors and apply an affine transformation to transform them into $e_1,\cdots, e_d$, it need not be the case that the hypothesis that realize the labeling vector $l \in \{-1,1\}^d$ lie in $C$ itself. For $\mathbb R^d$ cone, this was trivial but need not be the same for a non-trivial full dimensional polyhedral cones like pointed ones. $\endgroup$
    – Neophyte
    Commented Apr 15 at 16:36
  • $\begingroup$ I'm again getting a bit lost with the definitions. I think it would be best if someone else answered your question. $\endgroup$
    – domotorp
    Commented Apr 16 at 6:32

0

You must log in to answer this question.

Browse other questions tagged .