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

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 consider the derived function class $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} $$

Let $\sigma_1,\dotsc,\sigma_n$ be an iid sequence of Rademacher $\pm 1$ random variables, independent of the $x_i$'s and $y_i$'s, and define

$$ \begin{split} R_n(F) &:= \mathbb E_{\sigma_1,\dotsc,\sigma_n}\left[\sup_{f \in F}\sum_{i=1}^n \sigma_i f(x_i)\right]\\ R_n(H) &:= \mathbb E_{\sigma_1,\dotsc,\sigma_n}\left[\sup_{h \in H}\sum_{i=1}^n \sigma_i h(x_i,y_i)\right]. \end{split} $$ Note that $R_n(F)$ (resp. $R_n(H)$) is nothing but the Rademacher complexity of $F$ (resp. $H$).

Question. What is a good upper-bound for $\mathbb E\ R_n(H)$ in terms of $\mathbb E\,R_n(F)$, $\alpha$, and $\beta$ ?

I'm particularly interested in the case where $F := F_{\text{lin}}$, the function class on $\mathbb R^d$ defined by $$ F_{\text{lin}} := \{x \mapsto x^\top w + b \mid b \in \mathbb R, \,w \in \mathbb R^d\}. $$

Answer 1

The following VC dimension bound was established in this answer to VC dimension of a certain derived class of binary functions, $$ \operatorname{VCdim}(H) \le 2\cdot \operatorname{VCdim}(\operatorname{SG}(F)), $$ where $\operatorname{SG}(F) := \{\{x \in X \mid f(x) \le 0\} \mid f \in F\}$ is the subgraph of $F$.

On the other hand, it's well-known that Rademacher complexity can be bounded via VC dimension like so. $$ \mathbb E\, R_n(H) \lesssim\sqrt{\dfrac{\operatorname{VCdim}(H)}{n}}. $$

We conclude that $$ \mathbb E\,R_n(H) \lesssim \sqrt{\frac{\operatorname{VCdim}(\operatorname{SG}(F))}{n}}. $$

In particular, because $\operatorname{VCdim}(\operatorname{SG}(F_{\text{lin}})) = d$, we conclude that

$$ \mathbb E\,\widetilde R_n(F_{\text{lin}}) \lesssim \sqrt{\frac{d}{n}}. $$