Relationship between MDL and "difficulty of learning from data"

Question

While trying to make sense of MDL and stochastic complexity, I found this previous question: Measures of model complexity, in which Yaroslav Bulatov defines model complexity as "how hard it is to learn from limited data."

It is not clear to me how Minimal Description Length (MDL) measures this. What I am looking for is some sort of probability inequality (analagous to the VC upper bound) which relates the "code length" of a model with its worst case behavior on fitting data generated by itself. If such a concrete result cannot be found in the literature, even an empirical example would be enlightening.

Answer 1

The worst case of code length of a code induced by a probability density is just the negative log of the most unlikely event, since $L_p(x) = -\log p(x)$.

I am currently working through Peter Grünwald's book 'The MDL principle'. He defines the complexity of a model class as the log of the sum of probabilities it can assign to data.

Thus, the more different datasets a model can fit, the more complex it is.

$x^n$ here is a complete data set. $X^n$ is the set of all possible data sets of length $n$. This might seem confusing, but it is done this way wo allow non-iid data.

The formal definition goes as follows: $$COMP(\mathcal{M}) := \log \sum_{x^n \in X^n} p_{x^n}(x^n)$$

where $p_{x^n}$ is the optimal $p \in \mathcal{M}$ with regard to $x^n$.

Answer 2

MDL for model selection seems to mean "choose model with lowest parametric complexity". Since parametric complexity is equal to worst case excess code length when you don't know the distribution, I bet it also gives you the number of observations needed to get close to true member of M in KL-divergence. Parametric complexity is a function of number of observations n and is given as COMP in bayer's answer.

Chapter 14 and chapter 7 of Grunwald's book give more details