# Lower bounds for SRM?

This question is about structural risk minimization and model selection. Let $$H_n$$ be the collection of all binary classifiers on some fixed set with an $$n$$-bit description length in some fixed encoding. The learner receives a sample of $$m$$ iid points drawn from an unknown distribution and labeled correctly by some $$h^*\in H:=\bigcup_{n\ge1}H_n$$. Consider the Occam learner, whose strategy is to choose a consistent $$\hat h\in H$$ with the smallest description length $$|\hat h|$$. It is easy to show (see Question 2 here https://www.cs.bgu.ac.il/~inabd161/wiki.files/exercise3.pdf ) that with probability at least $$1-\delta$$, the generalization error of $$\hat h$$ is at most $$\frac{|\hat h|\log 4+\log(1/\delta)}{m} \le \frac{|h^*|\log 4+\log(1/\delta)}{m}$$ (because by construction, $$|\hat h|\le|h^*|$$). It's obvious from the no-free-lunch theorem that no learner can achieve a risk rate independent of $$|h^*|$$. It's less obvious -- but seems plausible -- that no learner can achieve a risk rate $$o(|h^*|/m)$$ uniformly over all distributions. Is this sort of thing known? To rule out degenerate cases, assume that the VC-dim of $$H_n$$ is $$\Theta(n)$$.