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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.