# Upper bound on risk in structural risk minimization

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.

$$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.