<p>The answer depends on whether you want a bound for a single, <em>fixed</em> <span class="math-container">$Q\subseteq M$</span> or <em>uniformly</em> over all such <span class="math-container">$Q$</span>. For a single, fixed <span class="math-container">$Q$</span>, the Chernoff-Hoeffding bound is essentially the best you can do (see also empirical Bernstein's inequality for "fast rates").</p>

<p>If you want the bound to hold simultaneously for all <span class="math-container">$Q\subseteq M$</span>, you need apply the union bound, which amounts to multiplying the deviation probability by <span class="math-container">$2^{|M|}$</span> (or the sample complexity by <span class="math-container">$|M|\log 2$</span>).</p>

<p>You have nothing to gain here by using Rademacher complexities. The latter are useful at capturing the combinatorial properties of VC classes, and are sharper than naive union bounds (though Massart's lemma of course has a union bound inside). In your case, the VC structure is very simple -- it's all subsets -- and so you might as well just use the simple union bound.</p>

CC BY-SA 4.0
2018-11-17T18:47:57.370Z
2018-11-17T18:47:57.370Z
Aryeh
<p>Let <span class="math-container">$M$</span> be <em>finite</em> set with <span class="math-container">$n$</span> distinct elements. I want to probalistically  approximate the relative counts <span class="math-container">$\frac{|P(Q)|}{|M|}$</span> of <span class="math-container">$Q \subseteq M$</span>, where <span class="math-container">$P(Q) = |P \cap M|$</span>. </p>

<p>An upper-bound for the number of samples need to get an (additive) <span class="math-container">$\varepsilon$</span>-approximation can be derrived using the Hoeffding bound. </p>

<p>I am interested in achieving (empirical) better bounds using <em>empirical Rademacher averages</em>. My idea is to adaptability sample from <span class="math-container">$M$</span>, to fulfill
    <span class="math-container">\begin{equation}
  \sup_{f \in \mathcal{F}}\,| L_{\mathcal{D}}(f) - L_{S}(f) | \leq 2\cdot\mathcal{R}_{\mathcal{F}}(S) + 3 \sqrt{\frac{ \log (2/\delta)}{2m}} \leq \epsilon,
 \end{equation}</span> 
where
<span class="math-container">\begin{equation*}
 \mathcal{F} = \{ \mathbf{1}_{Q} \mid Q \subseteq M \}, 
\end{equation*}</span>
and <span class="math-container">$\mathbf{1}_{Q}$</span> equals <span class="math-container">$1$</span> if the current sample is in <span class="math-container">$Q$</span>, and otherwise <span class="math-container">$0$</span>.
It follows that 
<span class="math-container">\begin{equation*}
 L_{\mathcal{D}}(\mathbf{1}_{Q}) =  \frac{|P(Q)|}{|M|}.
\end{equation*}</span></p>

<p>Can one achieve better bounds using this approaches, e.g., by using Massart's Lemma to approximate <span class="math-container">$\mathcal{R}_{\mathcal{F}}(S)$</span>?</p>

<machine-learning><pr.probability><lg.learning><epsilon-nets>
Empirical Rademacher averages versus Hoeffdings bound
Christopher
# Empirical Rademacher averages versus Hoeffdings bound

(Asked by: username_0 on 2018-11-16)

Let $M$ be *finite* set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$.

An upper-bound for the number of samples need to get an (additive) $\varepsilon$-approximation can be derrived using the Hoeffding bound.

I am interested in achieving (empirical) better bounds using *empirical Rademacher averages*. My idea is to adaptability sample from $M$, to fulfill
\begin{equation}
\sup\_{f \in \mathcal{F}}\,| L\_{\mathcal{D}}(f) - L\_{S}(f) | \leq 2\cdot\mathcal{R}\_{\mathcal{F}}(S) + 3 \sqrt{\frac{ \log (2/\delta)}{2m}} \leq \epsilon,
\end{equation}
where
\begin{equation\*}
\mathcal{F} = \{ \mathbf{1}\_{Q} \mid Q \subseteq M \},
\end{equation\*}
and $\mathbf{1}\_{Q}$ equals $1$ if the current sample is in $Q$, and otherwise $0$.
It follows that
\begin{equation\*}
L\_{\mathcal{D}}(\mathbf{1}\_{Q}) = \frac{|P(Q)|}{|M|}.
\end{equation\*}

Can one achieve better bounds using this approaches, e.g., by using Massart's Lemma to approximate $\mathcal{R}\_{\mathcal{F}}(S)$?

**Tags:** machine-learning, pr.probability, lg.learning, epsilon-nets

---

## 1 answers

### Answer by username_1 on 2018-11-17. Score: 2 | Accepted answer

The answer depends on whether you want a bound for a single, *fixed* $Q\subseteq M$ or *uniformly* over all such $Q$. For a single, fixed $Q$, the Chernoff-Hoeffding bound is essentially the best you can do (see also empirical Bernstein's inequality for "fast rates").

If you want the bound to hold simultaneously for all $Q\subseteq M$, you need apply the union bound, which amounts to multiplying the deviation probability by $2^{|M|}$ (or the sample complexity by $|M|\log 2$).

You have nothing to gain here by using Rademacher complexities. The latter are useful at capturing the combinatorial properties of VC classes, and are sharper than naive union bounds (though Massart's lemma of course has a union bound inside). In your case, the VC structure is very simple -- it's all subsets -- and so you might as well just use the simple union bound.


---

