Universal Compression, List Decoding, and Logarithmic Loss

Yanina Shkel, Maxim Raginsky, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Universal lossy source coding under the logarithmic loss (log-loss) criterion is studied. Bounds on the rate-redundancy of variable-length universal codes with respect to a family of distributions are derived. These bounds correspond to previously derived bounds on distortion-redundancy of fixed-length coding. The asymptotic behavior of the resulting optimization problem is studied for a family of i.i.d. sources with a finite alphabet size. As is the case with distortion-redundancy, rate-redundancy of memoryless sources is lower bounded by frac k 2log n, where n is the blocklength and k is the number of degrees of freedom in the parameter space. The impact of the distortion constraint is on the constant term: higher allowed distortion effectively reduces the volume of the parameter uncertainty set. In view of previously established connections between lossy variable-length coding under log-loss and compression with list decoding, the bounds derived in this work also apply to variable-length coding with list decoding.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781538647806
StatePublished - Aug 15 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2018 IEEE International Symposium on Information Theory, ISIT 2018
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Universal Compression, List Decoding, and Logarithmic Loss'. Together they form a unique fingerprint.

Cite this