Universal convergence bound for MDL predictions of Bernoulli sequences

Let θ0\theta_0 be the true Bernoulli parameter, let θx\theta^x denote the MDL prediction based on the observed sequence, let K(θ0)K(\theta_0) be the prefix Kolmogorov complexity of θ0\theta_0, and let Δ(k)\Delta(k) denote the relevant complexity difference. Universal convergence bound. The cumulative expected squared prediction error should satisfy

nE(θ0θx)2×K(θ0)+k2Δ(k).\sum_n {\mathbf E} (\theta_0-\theta^x)^2\stackrel\times\leq K(\theta_0)+ \sum_k 2^{-\Delta(k)}.

This would strengthen the preceding upper-bound theorem in the universal setting, where the complexity is prefix Kolmogorov complexity, and would imply the paper's earlier convergence result up to a constant. The source does not establish the bound.

Sources & referencesView supporting material

Primary source

Jan Poland and Marcus Hutter, “On the Convergence Speed of MDL Predictions for Bernoulli Sequences”, arXiv:cs/0407039 (2004).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.