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

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

$$ \begin{split} R_n(F) &:= \mathbb E_{\sigma_1,\ldots,\sigma_n}\left[\sup_{f \in F}\sum_{i=1}^n \sigma_i f(x_i)\right]\\ R_n(H) &:= \mathbb E_{\sigma_1,\ldots,\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_{\mathrm{lin}}$, a function class on $\mathbb R^d$ defined by $$ F_{\mathrm{lin}} := \{x \mapsto x^\top w + b \mid b \in \mathbb R, \,w \in \mathbb R^d\}. $$

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

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

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

$$ \begin{split} R_n &:= \mathbb E_{\sigma_1,\ldots,\sigma_n}\left[\sup_{f \in F}\sum_{i=1}^n \sigma_i f(x_i)\right]\\ \widetilde R_n &:= \mathbb E_{\sigma_1,\ldots,\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$ (resp. $\widetilde R_n$) is nothing but the Rademacher complexity of $F$ (resp. $H$).

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

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

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

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

$$ \begin{split} R_n(F) &:= \mathbb E_{\sigma_1,\ldots,\sigma_n}\left[\sup_{f \in F}\sum_{i=1}^n \sigma_i f(x_i)\right]\\ R_n(H) &:= \mathbb E_{\sigma_1,\ldots,\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_{\mathrm{lin}}$, a function class on $\mathbb R^d$ defined by $$ F_{\mathrm{lin}} := \{x \mapsto x^\top w + b \mid b \in \mathbb R, \,w \in \mathbb R^d\}. $$

Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$. Fix $\alpha \in \mathbb R$ and $\beta > 0$, and define a 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} $$

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

$$ \begin{split} R_n &:= \mathbb E_{\sigma_1,\ldots,\sigma_n}\left[\sup_{f \in F}\sum_{i=1}^n \sigma_i f(x_i)\right]\\ \widetilde R_n &:= \mathbb E_{\sigma_1,\ldots,\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$ (resp. $\widetilde R_n$) is nothing but the Rademacher complexity of $F$ (resp. $H$).

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

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

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

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

$$ \begin{split} R_n &:= \mathbb E_{\sigma_1,\ldots,\sigma_n}\left[\sup_{f \in F}\sum_{i=1}^n \sigma_i f(x_i)\right]\\ \widetilde R_n &:= \mathbb E_{\sigma_1,\ldots,\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$ (resp. $\widetilde R_n$) is nothing but the Rademacher complexity of $F$ (resp. $H$).

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

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