VC dimension of a certain derived class of binary functions

Question

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$

Answer 1

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{equation} \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} \end{equation}

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