Adaptive compression against a countable alphabet

Abstract : This paper sheds light on universal coding with respect to classes of memoryless sources over a countable alphabet defined by an envelope function with finite and non-decreasing hazard rate. We prove that the auto-censuring (AC) code introduced by Bontemps (2011) is adaptive with respect to the collection of such classes. The analysis builds on the tight characterization of universal redundancy rate in terms of metric entropy by Haussler and Opper (1997) and on a careful analysis of the performance of the AC-coding algorithm. The latter relies on non-asymptotic bounds for maxima of samples from discrete distributions with finite and non-decreasing hazard rate.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01197243
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:55:06 PM
Last modification on : Friday, January 10, 2020 - 9:08:59 PM
Long-term archiving on: Tuesday, December 29, 2015 - 12:35:59 AM

File

dmAQ0117.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01197243, version 1

Citation

Dominique Bontemps, Stephane Boucheron, Elisabeth Gassiat. Adaptive compression against a countable alphabet. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.201-218. ⟨hal-01197243⟩

Share

Metrics

Record views

552

Files downloads

417