Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \rightarrow [0,1]$. Further, for $c\in(0,1)$, let $\mathcal{F}_c$ be the function class defined by \begin{align} \mathcal{F}_c := \{ z \mapsto \mathbb{I}\{\ell(h,z) \leq c\}: h \in \mathcal{H}\}. \end{align} Question. Is it in any way possible to relate the Rademacher complexity of the function class $\mathcal{F}_c$, to that of $\ell \circ \mathcal{H}:= \{z\mapsto \ell(h,z): h \in \mathcal{H}\}$? My goal is to show that when the complexity of the latter class is small, so is the complexity of the former.

Rademacher Complexity. The Rademacher complexity of a function class $\mathcal{F}$ is defined as \begin{align} \mathfrak{R}_n(\mathcal{F}) := \mathbb{E}\left[\sup_{f\in \mathcal{F}}\frac{1}{n} \sum_{i=1}^n \sigma_i f(z_i)\right], \quad n \in \mathbb{N}, \end{align} where $(\sigma_i,z_i)$ are i.i.d. random variables with $(\sigma_i)$ having a Rademacher distribution.

Failed Attempt. There are results on the Rademacher complexity of the composition of functions, but these typically rely on some Lipschitzness properties, which do not hold for our function class $\mathcal{F}_c$ since we compose with an indicator function.


In general, composing a threshold function with a function class can arbitrarily increase the Rademacher complexity (so the answer to your question is negative). Let $\Omega$ be a finite set, $|\Omega|=N$, and let $F=[-a,a]^\Omega$ be the set of all functions from $\Omega$ to $[-a,a]$. When $N\gg n$, the Rademacher complexity (either empirical or expected) of $F$ will be $\Theta(a)$. Let $F'$ be $F$ composed with the sign function; now $F'=\{-1,1\}^\Omega$ and its Rademacher complexity in this regime is $\Theta(1)$. Since $a>0$ can be taken arbitrarily small, this shows that the multiplicative gap can be arbitrarily large.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.