2
$\begingroup$

In pg. 64-65 of "Foundations of Machine Leaning (2nd Ed.)" by Mohri et al. there is a discussion about structural risk minimization.

The hypothesis class $\mathcal H$ is decomposed into a union of hypothesis classes $\mathcal H=\cup_{k\geq 1}\mathcal H_k$. The bound at the start of page 65 says that for all $h\in\mathcal H_k$, with probability $\geq 1-\delta$ over an iid sample of $m$ elements $S$, $$ R(h)\leq\hat R_S(h)+\mathfrak R_m(\mathcal H_k)+\sqrt{\frac{\log k}{m}}+\sqrt{\frac{\log 2/\delta}{2m}} $$ where $R$ denotes risk (expected 0-1 loss), $\hat R_S(h)$ denotes empirical risk, and $\mathfrak R_m$ is the Rademacher complexity.

I am confused why there is a dependence on $k$ in the bound. As per the discussions in the textbook, we do not even assume the $\mathcal H_k$ are nested. Hence to me, the value of $k$ is totally arbitrary and serves only as an index; I can for example permute all the $\mathcal H_k$ around arbitrarily and hence reindex the $k$ arbitrarily. This doesn't seem right, so clearly I must be missing something about what $k$ means.

$\endgroup$

1 Answer 1

2
$\begingroup$

You (slightly) misquoted the learning bound on page 65 : the actual bound is given by (emphasis mine)

$$R(h)\leq\hat R_S(h)+\mathfrak R_m(\mathcal H_{\color{red}{k(h)}})+\sqrt{\frac{\log \color{red}{k}}{m}}+\sqrt{\frac{\log 2/\delta}{2m}} $$

The crucial thing that this notation highlights is that $k$ depends on the hypothesis $h$. More specifically, the author defines $k(h)$ as follows

For any $h\in\mathcal H$, we will denote by $\mathcal H_{k(h)} $ the least complex hypothesis set among the $\mathcal H_k$s which contain $h$.

The idea is that, although the hypotheses sets $\mathcal H_k$ may not be nested, the indices $k$ are a measure of complexity for each $\mathcal H_k$, hence picking a more complex hypothesis will hurt the generalization error accordingly. Figure 4.4 in the book and following discussion should make it clearer.

$\endgroup$

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.