What is the Rademacher complexity of kernelbased hypotheses with offset?

Question

Let $\mathcal{H}=\{ x\rightarrow \langle \mathbf{w},\Phi(x)\rangle+b : \| \mathbf{w}\|_{\mathbb{H}} \le \Lambda, b\in \mathbb{R}\}$ be a function family, where $\Phi$ is a feature mapping, and $\mathbb{H}$ denotes the feature space, i.e., Hilber space.

How can we bound the Rademacher complexity of $\mathcal{H}$?

---

I know that when $b=0$, the Rademacher complexity of $\mathcal{H}$ is bounded by $\sqrt{\frac{r^2\Lambda^2}{m}}$, where $K(x,x) \le r^2$ and $m$ is the number of samples. But when the offset $b$ exists, how can we bound this Rademacher complexity?

Answer 1

Lemma: Let $H$ be a hypothesis class with Rademacher complexity $R(H)$. Define $H_b = \{ x \mapsto h(x) + b : h \in H, b \in \mathbb{R}\}$. Then $R(H_b) = R(H)$.

Proof: Fix any set $x_1, \dots, x_m$. \begin{align*} R(H_b) &= \frac1m \mathbb{E}_\sigma[\sup_{h \in H_b} \sum_{i=1}^m \sigma_i h(x_i)] \\ &= \frac1m \mathbb{E}_\sigma[\sup_{h \in H, b} \sum_{i=1}^m \sigma_i h(x_i) + b\sigma_i] \\ &= R(H) \end{align*}

using the fact that $\mathbb{E} \sigma_i = 0$. Taking expectations over the set $x_1, \dots, x_m$, we conclude.