<p>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 <span class="math-container">$\Omega$</span> be a finite set, <span class="math-container">$|\Omega|=N$</span>, and let <span class="math-container">$F=[-a,a]^\Omega$</span> be the set of all functions from <span class="math-container">$\Omega$</span> to <span class="math-container">$[-a,a]$</span>.
When <span class="math-container">$N\gg n$</span>, the Rademacher complexity (either empirical or expected) of <span class="math-container">$F$</span> will be <span class="math-container">$\Theta(a)$</span>. Let <span class="math-container">$F'$</span> be <span class="math-container">$F$</span> composed with the sign function; now <span class="math-container">$F'=\{-1,1\}^\Omega$</span> and its Rademacher complexity in this regime is <span class="math-container">$\Theta(1)$</span>. Since <span class="math-container">$a&gt;0$</span> can be taken arbitrarily small, this shows that the multiplicative gap can be arbitrarily large.</p>

CC BY-SA 4.0
2020-09-26T18:56:16.923Z
2020-09-26T18:56:16.923Z
Aryeh
<p>Consider the statistical learning setting where you have an arbitrary hypothesis space <span class="math-container">$\mathcal{H}$</span>, a data space <span class="math-container">$\mathcal{Z}$</span>, and a bounded loss function <span class="math-container">$\ell: \mathcal{H}\times \mathcal{Z} \rightarrow [0,1]$</span>. Further, for <span class="math-container">$c\in(0,1)$</span>, let <span class="math-container">$\mathcal{F}_c$</span> be the function class defined by
<span class="math-container">\begin{align}
\mathcal{F}_c := \{ z \mapsto  \mathbb{I}\{\ell(h,z) \leq c\}: h \in \mathcal{H}\}. 
\end{align}</span>
<strong>Question.</strong> Is it in any way possible to relate the Rademacher complexity of the function class <span class="math-container">$\mathcal{F}_c$</span>, to that of <span class="math-container">$\ell \circ \mathcal{H}:= \{z\mapsto \ell(h,z): h \in \mathcal{H}\}$</span>?
My goal is to show that when the complexity of the latter class is small, so is the complexity of the former.</p>
<p><strong>Rademacher Complexity.</strong> The Rademacher complexity of a function class <span class="math-container">$\mathcal{F}$</span> is defined as
<span class="math-container">\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}</span>
where <span class="math-container">$(\sigma_i,z_i)$</span> are i.i.d. random variables with <span class="math-container">$(\sigma_i)$</span> having a Rademacher distribution.</p>
<p><strong>Failed Attempt.</strong> 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 <span class="math-container">$\mathcal{F}_c$</span> since we compose with an indicator function.</p>

<complexity-classes><machine-learning>
Rademacher Complexity of the Composition with an Indicator
user6952886
# Rademacher Complexity of the Composition with an Indicator

(Asked by: username_0 on 2020-09-26)

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.

**Tags:** complexity-classes, machine-learning


---

## 1 answers

### Answer by username_1 on 2020-09-26. Score: 3 | Accepted answer

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.


---

