What is the Rademacher complexity of continuous functions from $[0,1]$ to $[0,1]$?

63 Views Asked by At

Recall that the RC is defined as

$$\mathfrak{R}_m(\mathcal{G}) := \mathbb{E}_{S\sim \mathcal{D}^m}[\hat{\mathfrak{R}}_S(\mathcal{G})]$$

where

$$\hat{\mathfrak{R}}_S(\mathcal{G}) := \mathbb{E}_{\sigma} [\sup_{g\in \mathcal{G}} \frac1m \sum_{i=1}^m \sigma_i g(x_i)]$$

is the empirical Rademacher complexity. Here $\mathcal{G}$ is a family of functions from $Z$ to $[a,b]\subseteq \mathbb{R}$, $S = (x_1,...x_m) \subset Z$ is a sample distributed according to a law $\mathcal{D}$ and $\sigma_i$ are independent uniform RV's with values in $\{-1,1\}$. On wikipedia there are examples where it is calculated for certain sets but in my notes I have an example where $\mathcal{G} = C([0,1]\rightarrow [0,1])$ are the continuous functions from $[0,1]$ to $[0,1]$. $S$ is a sample where $x_i\neq x_j$ for all $i\neq j \in [m]$. It is claimed without further explanation that $\hat{\mathfrak{R}}_S(\mathcal{G})=1$. I don't understand why this is true (if it is true). Take for example $m=1$, that is we pick a point randomly in $[0,1]$. Then

$$\hat{\mathfrak{R}}_S(\mathcal{G})= \mathbb{E}_{\sigma}[\sup_{g\in C[0,1]} \sigma g(x)]$$ Since g maps to $[0,1]$ we can pick any point in $[0,1]$ as $g(x)$ and by the linearity of $\mathbb{E}$ we would have $$const. \cdot \mathbb{E}_{\sigma}[\sigma]= 0$$ Where am I wrong? And how does one determine $\mathbb{R}$ for general $m$?