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

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

## 1 Answer

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