Rademacher Complexity of the Composition with an Indicator

Question

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.

Answer 1

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.