The strengthened universal MDL convergence bound

Let KK be prefix Kolmogorov complexity, let ϑ0\boldsymbol{\vartheta}_0 be the true parameter, and let Δ(k)\Delta(k) denote the complexity difference used in the MDL setup. Strengthened universal convergence conjecture. Under the same conditions as the preceding upper-bound theorem,

nE(ϑ0ϑx)2×K(ϑ0)+k2Δ(k).\sum_n \mathbf{E}(\boldsymbol{\vartheta}_0-\boldsymbol{\vartheta}^x)^2\stackrel{\times}{\leq} K(\boldsymbol{\vartheta}_0)+\sum_k2^{-\Delta(k)}.

The conjectured strengthening would make the universal setup useful despite the divergence of k2K(k)K(k)\sum_k2^{-K(k)}\sqrt{K(k)}, and would imply the paper's earlier convergence result up to a multiplicative constant. The supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Jan Poland and Marcus Hutter, “MDL Convergence Speed for Bernoulli Sequences”, arXiv:math/0602505 (2006).

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.