All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-S5-T2.2
Paper Title Quantization of Random Distributions under KL Divergence
Authors Aviv Adler, Jennifer Tang, Yury Polyanskiy, Massachusetts Institute of Technology, United States
Session D6-S5-T2: Rate-Distortion Theory II
Chaired Session: Monday, 19 July, 23:20 - 23:40
Engagement Session: Monday, 19 July, 23:40 - 00:00
Abstract Consider the problem of representing a distribution pi on a large alphabet of size k up to fidelity epsilon in Kullback-Leibler (KL) divergence. Heuristically, arguing as for quadratic loss in high dimension, one expects that about (k/ 2) log (1/ epsilon) bits would be required. We show this intuition is correct by proving explicit non-asymptotic bounds for the minimal average distortion when pi is randomly sampled from a symmetric Dirichlet prior on the simplex. Our method is to reduce the single-sample problem to the traditional setting of iid samples, but for a non standard rate distortion question with the novel distortion measure d(x,y) = x log(x/y), which we call divergence distortion. Practically, our results advocate using a x maps to x^{2/3} compander (for small x) followed by a uniform scalar quantizer for storing large-alphabet distributions.