The power of absolute discounting: all-dimensional distribution estimation

Categorical models are a natural fit for many problems. When learning the distribution ofcategories from samples, high-dimensionality may dilute the data. Minimax optimality is too pessimistic to remedy this issue. A serendipitously discovered estimator, absolute discounting, corrects empirical frequencies by subtracting aconstant from observed categories, which it then redistributes among the unobserved. It outperforms classical estimators empirically, and has been used extensively innatural language modeling. In this paper, we rigorously explain the prowess of this estimator using less pessimistic notions. We show that (1) absolute discountingrecovers classical minimax KL-risk rates, (2) it is adaptive to an effective dimension rather than the true dimension, (3) it is strongly related to the Good-Turing estimator and inherits its competitive properties. We use powerlaw distributionsas the cornerstone of these results.