Universal convergence bound for MDL predictions of Bernoulli sequences
Universal convergence bound for MDL predictions of Bernoulli sequences
Let be the true Bernoulli parameter, let denote the MDL prediction based on the observed sequence, let be the prefix Kolmogorov complexity of , and let denote the relevant complexity difference. Universal convergence bound. The cumulative expected squared prediction error should satisfy
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.