The power of absolute discounting: all-dimensional distribution estimation
Categorical models are a natural fit for many problems. When learning the distribution of categories 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 a constant from observed categories, which it then redistributes among the unobserved. It outperforms classical estimators empirically, and has been used extensively in natural language modeling. In this paper, we rigorously explain the prowess of this estimator using less pessimistic notions. We show that (1) absolute discounting recovers 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 distributions as the cornerstone of these results. We validate the theory via synthetic data and an application to the Global Terrorism Database.
SUMMARY: The paper discusses methods for estimating categorical distributions, in particular a method called "absolute discounting". The paper gives bounds for the KL-risk of absolute discounting, and discusses properties such as minimax rate-optimality, adaptivity, and its relation to the Good–Turing estimator.
CLARITY: The paper is presented in reasonably clear language, and is well-structured.
NOVELTY: The contributions of the paper seem good, but perhaps rather incremental, and not ground-breakingly novel. The paper advocates for the use of absolute discounting, and gives good arguments in favor, including theoretical properties and some experimental results. But the technique as such isn't especially novel, and more general versions of it exist that aren't referenced. The literature review might not be thorough enough: for example, there are many relevant techniques in Chen & Goodman's comprehensive and widely-cited report (1996, 1998) that aren't mentioned or compared to. The paper does cite this report, but could perhaps engage with it better.
Also, the paper does not give any insight on its relation to clearly relevant Bayesian techniques (e.g. Pitman-Yor processes and CRPs) that are similar to (and perhaps more general than) the form absolute discounting presented in this paper. These other techniques probably deserve a theoretical and/or experimental comparison. At the very least they could be mentioned, and it would be helpful to have their relationship to "absolute discounting" clarified.
SCORE:
Overall, I enjoyed reading the paper, and I hope the authors will feel encouraged to continue and improve their work. The main contributions seem useful, but I have a feeling that their relevance to other techniques and existing research isn't clarified enough in this version of the paper.
A few minor suggestions for improvements to the paper follow below.
SECTION 8 (Experiments):
Some questions.
Q1: Is 500 Monte-Carlo iterations enough?
Q2: If the discount value is set based on the data, is that cheating by using the data twice?
LANGUAGE:
Some of the phrasing might be a bit overconfident, e.g.:
  Line 1: "Categorical models are the natural fit..." -> "Categorical models are a natural fit..."?
  Line 48: "[we report on some experiments], which showcases perfectly the all-dimensional learning power of absolute discounting" (really, "perfectly"?)
  Line 291: "This perfectly captures the importance of using structure [...]"
NOTATION:
Totally minor, but perhaps worth mentioning as it occurs a lot: "Good-Turing" should be written with an en-dash ("–" in Unicode, "--" in LaTeX), and not with a hyphen ("-" in Unicode, "-" in LaTeX).
BIBLIOGRAPHY:
In the bibliography, "Good–Turing" is often written in lowercase ("good-turing"), perhaps as a result of forgetting the curly brace protections in the BibTeX source file. (Correct syntax: "{G}ood--{T}uring".)
The final reference (Zip35, Line 364) seems incomplete: only author, title and year are mentioned, no information is given where or how the paper was published.