Quantization of random distributions under KL divergence

Consider the problem of representing a distribution π on a large alphabet of size k up to fidelity ε in Kullback-Leibler (KL) divergence. Heuristically, arguing as for quadratic loss in high dimension, one expects that about (k/2)log(1/ε) bits would be required. We show this intuition is correct by proving explicit non-asymptotic bounds for the minimal average distortion when π 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)=xlog(x/y), which we call divergence distortion. Practically, our results advocate using a x↦x2/3 compander (for small x) followed by a uniform scalar quantizer for storing large-alphabet distributions.