Competitive Distribution Estimation: Why is Good-Turing Good
Estimating distributions over large alphabets is a fundamental machine-learning tenet. Yet no method is known to estimate all distributions well. For example, add-constant estimators are nearly min-max optimal but often perform poorly in practice, and practical estimators such as absolute discounting, Jelinek-Mercer, and Good-Turing are not known to be near optimal for essentially any distribution.
The paper gives justification for the widespread use of the Good-Turing estimator for discrete distribution estimation through minimax regret analysis with two comparator classes. The paper obtains competitive regret bounds that lead to a more accurate characterization of the performance of the the Good-Turing estimators and in some cases is much better than the best known risk bounds. The comparator classes considered are estimators with knowledge of the distribution up to permutation, and estimators with full knowledge of the distribution, but with the constraint that the must assign the same probability mass to symbols appearing with the same frequencies. While I like the exposition in the paper, I think there are several nice results in the appendix that should be highlighted that also clear up some confusions in the paper. For example, the fact that the optimal natural estimator can be explicitly computed and its risk can be bounded is very useful. First, it means that we actually obtain an "instance-specific" risk bound for the Good-Turing estimator by combining Lemma 10 with Theorem 2. It would be nice to give examples of this bound being much tighter than the best log(k/n) bound on the minimax risk.Major comments: 1. In Figure 1, what is the estimator designed with prior knowledge of the partition? Is the red line a theoretical curve or an empirical one? Is there any analysis for the case where the partition is known? Roughly, my question is whether that red curve actually lower bounds the minimax risk here. I know you are using the lower bound r_n(\Delta_k) \ge r_n(P), but I am not sure how you are calculating the min_q in the definition of r_n(P). It is not sufficient to use an upper bound (i.e. a sub-optimal estimator) if the claim is that the red curve lower bounds the r_n(\Delta_k).I think this is answered in the proof of Lemma 4 in the appendix but it should be made clear in the main paper.2. In the experiments it would be helpful to make it clear what things are known to the estimators and what aren't. I believe the quantity S(t) is not known to fully data-driven estimators and only to the comparator in the natural class. Is that correct? 3. More generally, I noticed that some notation is defined only in the appendix and not in the main paper and vice versa. It would be nicer and aid readability if all of the notation was in the main paper (and maybe even remind the reader from time to time).Minor comments: 1. In the abstract you use k and n but those variables have not been defined yet.2. "The distributions resulting in r_n(\Delta_k)." I think you mean to say the distributions achieving the max in the definition. 3. The claim that "which in turn is better than the performance of any data-driven estimator designed without prior information" is technically not true for the second comparator since in theory there could be an estimator which does not assign the same estimate to symbols with the same frequency. I do believe the prior information makes the problem easier but technically there could be a better estimator that does not obey this constraint. 4. Some typos in the first paragraph of section 2.3. Sentence beginning with "for example..." is not technically a sentence. No space after period. 5. Typo line 227. 6. n(x) undefined in the main text. I think it is the number of times symbol x appeared in the sample.