@inproceedings{eb60eece0987400ba8d036b5d615ed8e,

title = "Universal Compression, List Decoding, and Logarithmic Loss",

abstract = "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.",

author = "Yanina Shkel and Maxim Raginsky and Sergio Verdu",

year = "2018",

month = aug,

day = "15",

doi = "10.1109/ISIT.2018.8437892",

language = "English (US)",

isbn = "9781538647806",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "206--210",

booktitle = "2018 IEEE International Symposium on Information Theory, ISIT 2018",

address = "United States",

note = "2018 IEEE International Symposium on Information Theory, ISIT 2018 ; Conference date: 17-06-2018 Through 22-06-2018",

}