2010/02/03 by Peter Grünwald, Grünwald, Peter, Wojciech Kotłowski +1 · 1 citation
Computer Science · Mathematics · #Advanced Data Storage Technologies #Algorithms and Data Compression #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Statistics Theory (math.ST) #cs.IT #cs.LG #math.IT #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1002.0757
arxiv created 2010/02/03 · openalex publication_date 2010/02/03 · arxiv updated 2010/02/26 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We analyse the prequential plug-in codes relative to one-parameter exponential families M. We show that if data are sampled i.i.d. from some distribution outside M, then the redundancy of any plug-in prequential code grows at rate larger than 1/2 ln(n) in the worst case. This means that plug-in codes, such as the Rissanen-Dawid ML code, may behave inferior to other important universal codes such as the 2-part MDL, Shtarkov and Bayes codes, for which the redundancy is always 1/2 ln(n) + O(1). However, we also show that a slight modification of the ML plug-in code, "almost" in the model, does achieve the optimal redundancy even if the the true distribution is outside M.