2
$\begingroup$

Let $G$ be a family of functions mapping from $Z$ to $[a, b]$ and $S=\left(z_{1}, \ldots, z_{m}\right)$ a fixed sample of size $m$ with elements in $Z$ . Then, the empirical Rademacher complexity of $G$ with respect to the sample $S$ is defined as : $$ \widehat{\Re}_{S}(G)=\underset{\boldsymbol{\sigma}}{\mathrm{E}}\left[\sup _{g \in G} \frac{1}{m} \sum_{i=1}^{m} \sigma_{i} g\left(z_{i}\right)\right] \text { . } $$ where $\boldsymbol{\sigma}=\left(\sigma_{1}, \ldots, \sigma_{m}\right)^{\top},$ with $\sigma_{i} s$ independent uniform random variables taking values in ${-1,+1}.

Empirical Rademacher complexity is commonly used in bounding the generalization error. From definition of empirical Rademacher complexity I found that it is data-dependent and irrelevant to the training algorithm - it depends on the complexity of hypotheses set.

My concern is that: we will usually get a fixed function by a training algorithm on a training set, and we can give the generalization error regarding this function directly by Hoeffding's inequality. Why we need to calculate Rademacher complexity for a generalization error bound which involves a hypotheses set?

$\endgroup$

1 Answer 1

3
$\begingroup$

We will usually get a fixed function by a training algorithm on a training set, and we can give the generalization error regarding this function directly by Hoeffding's inequality.

Nope! The function is special because you used the data to pick it, i.e. it's correlated. By this same reasoning, you could draw samples uniformly from $[0,1]$, then take that set of samples and argue by Hoeffding's that any future draw from $U[0,1]$ is likely to be in this finite set (after all, every one of the initial samples was!).

So we need to bound the probability of the learning process outputting a bad hypothesis, or in other words, treat the hypothesis as a random variable. The straightforward approach is to take a small set of hypotheses as our class, use Hoeffding on all of them, then take a union bound. This gives a high probability that all the hypotheses have empirical loss close to to true expected loss on the sample. Therefore, no matter what the training algorithm is, the hypothesis it outputs will have expected loss close to empirical loss.

VC-dimension and Rademacher complexity are just improvements on this straightforward approach.

$\endgroup$
2
  • $\begingroup$ I guess by "treat the hypothesis as a random variable" you mean we treat the training set as a random set sampling from related data distribution. As a result, the empirical error is a random variable, and the expectation of empirical error over the data distribution is a constant. Do I understand this correctly? $\endgroup$
    – lee
    Commented Oct 2, 2019 at 8:06
  • $\begingroup$ Yes. The training set is sampled i.i.d. from a distribution, otherwise the Rademacher complexity setup doesn't really make sense. $\endgroup$
    – usul
    Commented Oct 2, 2019 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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