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

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.