The PAC-learning scenario doesn't have any parameter that goes to infinity, so I'm not sure why you dismiss "fixed" overheads :-)

Once you've chosen them, they're fixed, and don't run off to infinity.

This definition-only-up-to-a-constant is one of the weaknesses of minimum description length. (The other is its uncomputability. Shalizi somewhere else remarks that in discussions of algorithmic complexity, it is traditional to solemnly take out Kolmogorov complexity, exhibit its theoretical properties, remark on its uncomputability, and put it awa... (read more)