# VC dimension of a certain derived class of binary functions

Let $$X$$ be a measurable space and let $$P$$ be a probability distribution on $$X \times \{\pm 1\}$$. Let $$F$$ be a function class on $$X$$, i.e., a collection of (measurable) functions from $$X$$ to $$\mathbb R$$. Fix $$\alpha \in \mathbb R$$ and $$\beta > 0$$, and cobsider a derived function class on $$H := \{\ell_f \mid f \in F\}$$ on $$X \times \{\pm 1\}$$, where for each $$f \in F$$, the new function $$\ell_f:X \times \{\pm 1\} \to \{0,1\}$$ is defined by $$\ell_f(x,y) = \begin{cases} 1,&\mbox{ if }|yf(x)-\alpha| \ge \beta,\\ 0,&\mbox{ otherwise.} \end{cases}$$

Question. What is the a good upper-bound on VC-dimension of $$H$$ in terms of some complexity measure associated with $$F$$ (e.g., Rademacher complexity of $$F$$, VC-dimension of $$\mathrm{subgraph}(F) := \{A_f \mid f \in F\}$$, where $$A_f := \{x \in X \mid f(x) \le 0\}$$, etc.) ?

I'm particularly interested in the case where $$X=$$ euclidean $$\mathbb R^d$$ (or unit-sphere in $$\mathbb R^d$$) and $$F$$ is the collection of functions $$f:\mathbb R^d \to \mathbb R$$ of the form $$f(x) \equiv x^\top w + c$$, for some $$b \in \mathbb R$$ and unit vector $$w \in \mathbb R^d$$.

Related: Rademacher complexity of function class $\{(x,y) \mapsto 1[|yf(x)-\alpha| \ge \beta]$ in terms of $\alpha$, $\beta$, and Rademacher complexity of $F$

Consider the "loss function" $$\ell_t:\mathbb R^2 \to \{0,1\}$$ defined by $$\phi_t(y,y') := 1_{yy' \le t}$$, and let consider the function class on $$X \times \{\pm 1\}$$ given by $$S_t(F):= \ell_t \circ (Id,F) = \{(x,y) \mapsto \ell_t(y,f(x)) \mid f \in F\}.$$

Since $$|yf(x)-\alpha| \ge \beta$$ iff $$yf(x)\le \alpha-\beta$$ or $$-yf(x) \le -\alpha-\beta$$, it is clear that

$$H = S_{\alpha-\beta}(F) \lor S_{-\alpha-\beta}(-F),$$

where where $$-F := \{-f \mid f \in F\}$$. and $$A \widetilde{\cup} B := \{a \lor b \mid a \in A,\, b \in B\}$$.

Thus, thanks to van der Vaart and Wellner, Lemma 2.6.17, we deduce that

$$$$\begin{split} \mathrm{VCdim}(H) &\le \mathrm{VCdim}(S_{\alpha-\beta}(F)) + \mathrm{VCdim}(S_{-\alpha-\beta}(-F))\\ &= \mathrm{VCdim}(S_{\alpha-\beta}(F)) + \mathrm{VCdim}(S_{\alpha+\beta}(F))\\ &\le 2\cdot \mathrm{VCdim}(S_{\alpha-\beta}(F)). \end{split} \tag{1}$$$$

Finally, because for $$t \in \mathbb R$$, the loss function $$\ell_t$$ is monotone in the second (in fact, in both!) arguments, we know that $$\mathrm{VCdim}(S_t(F)) \le \mathrm{SG}(F)$$, where $$\mathrm{SG}(F) := \{\{x \in X \mid f(x) \le 0\} \mid f \in F\}$$ is the subgraph of $$F$$. Combining with (1) then gives

$$\mathrm{VCdim}(H) \le 2\cdot\mathrm{VCdim}(\mathrm{SG}(F)),$$

In particular, we deduce that for the half-space function class $$F_{\mathrm{lin}}$$ on $$\mathbb R^d$$, then

$$\mathrm{VCdim}(H_{\alpha-\beta}(F_{\mathrm{lin}})) \le 2\cdot \mathrm{VCdim}(\mathrm{SG}(F_{\mathrm{lin}})) = 2d.$$

• It is not true in general that $VC(A\vee B)\leq VC(A)+VC(B)$. The cited result in van der Vaart and Wellner proves that the VC-density of $A\vee B$ is at most the sum of the VC-densities of $A$ and $B$ (which then implies $VC(A\vee B)$ is finite whenever $VC(A)$ and $VC(B)$ are). From the proof of this one can obtain (e.g.) $VC(A\vee B)< 10\max\{VC(A),VC(B)\}$. Commented Jan 8 at 21:25
• Thanks for the input. OK, that's quite subtle. I'll take a look at the precise statement of the cited result asap. In any case, using what you're saying would give $\mathrm{VC}(H) \le Cd = O(d)$, with $C=10$. This is still sufficient for my purposes. Will come back to this asap. Commented Jan 8 at 22:31