0
$\begingroup$

Disclaimer: I'm not very familiar with the concept of VC dimensions and how to manipulate such objects. I'd be grateful if expects on the subject (learning theory, probability), could kindly proof check a small computation I've done below (or provide a simple alternative derivation, using classical arguments). Thanks in advance.


Let $X$ be a measurable space and let $F$ be a collection of measurable functions $f: X \to \mathbb R$ such that the VC-dimension the collection of subsets of $X$ given by $sg(F) := \{S(f) \text{ s.t } f \in F\}$ is $d$, where $$ S(f) := \{x \in X \text{ s.t }f(x) \le 0\}. $$ Let $\alpha,\beta \in \mathbb R$ with $\beta \ge 0$ an define a collection $H$ of subsets of $X \times \{\pm 1\}$ given by $$ H := \{T(f) \mid f \in F\},\text{ where } T(f) := \{(x,y) \in X \times \{\pm 1\} \text{ s.t } |yf(x)-\alpha| \ge \beta\}. $$

NB.: We also assume that $F$ is closed under affine transformations of the form $f \mapsto \pm f + c$, with $c \in \mathbb R$.

Question. Is it true that $VCdim(H) \le Cd$, for some absolute constant $C$ (not depending on parameters of the problem) ?


My attempt

It is clear that $|yf(x)-\alpha| \ge \beta$ iff $yf(x) \le \alpha-\beta$ or $-yf(x) \le -\alpha-\beta$, and so $T(f) = S_{\alpha-\beta}(f) \cup S_{-\alpha-\beta}(-f)$, where $$ S_t(f) := \{x \in X \mid yf(x) \le t\}. $$

We deduce the definition of $H$ that \begin{equation*} \begin{split} H &= \{S_{\alpha-\beta}(f) \cup S_{-\alpha-\beta}(f) \text{ s.t. }f \in F\}\\ &\subseteq \{A \cup B \text{ s.t } A \in S_{\alpha-\beta}(F),\, B \in S_{-\alpha-\beta}(-F)\}, \end{split} \tag{1} \end{equation*} where $S_t(F) := \{S_t(f) \text{ s.t } f \in F\}$, $-F:=\{-f \text{ s.t } f \in F\}$. Invoking Lemma 2.6.17 of van der Vaart and Wellner's Weak convergence and empirocal processes book, we deduce from (1) that $$ \begin{split} VCdim(H) &\le VCdim(S_{\alpha-\beta}(F))+ VCdim(S_{-\alpha-\beta}(-F))\\ &\le 4\cdot VCdim(sg(F))\\ &\le 4d \end{split} $$ where we have used the fact that for any $t \in \mathbb R$, both $S_t(F)$ and $S_t(-F)$ have the same VC dimension at most twice that of $sg(F)$, i.e., at most $2d$. See equation (3) of this CS Theory post (note that $S_t(F)$ is called $H$ in that post).

Thus, if my computations above are correct, then the bound in the question hold with $C=4$.

Question. Does my argument seem correct ?

Thanks in advance!

$\endgroup$
2

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.