Pith. sign in

REVIEW 1 major objections 4 minor 2 cited by

Besting Good--Turing: Optimality of Non-Parametric Maximum Likelihood for Distribution Estimation

T0 review · 1 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A parameter-free empirical-Bayes estimator attains optimal worst-case excess KL risk up to logarithmic factors, while the Good–Turing estimator is strictly suboptimal in the same competitive framework.

desk verdict NPMLE settles the Orlitsky–Suresh competition for distribution estimation, but the main theorem leans on an external density-estimation rate the paper neither proves nor fully verifies. read the letter →

arxiv 2509.07355 v1 pith:U2MBJSMR submitted 2025-09-09 math.ST cs.ITmath.ITstat.MEstat.TH

Yanjun Han , Jonathan Niles-Weed , Yandi Shen , Yihong Wu This is my paper · ORCID
classification math.STcs.ITmath.ITstat.MEstat.TH MSC 62C1262C2062G05
keywords distributionestimationGood–Turingestimatornon-parametricmaximumlikelihoodempiricalBayescompetitiveoptimalityregretpermutation-invariantoraclePoissonsampling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that combining Robbins's empirical Bayes with Kiefer–Wolfowitz non-parametric maximum likelihood yields a distribution estimator whose worst-case excess KL risk over the best permutation-invariant oracle is the smaller of $n^{-2/3}$ and $k/n$, up to logarithmic factors—the optimal rate in the Orlitsky–Suresh competitive framework. The estimator needs no hand-tuned smoothing: it learns a prior from the data and converts it into probability estimates through the Poisson posterior mean, with only a flexible regularization for unseen symbols. The paper also claims that the classic Good–Turing estimator, even in the common modified form that switches to empirical frequencies for high counts, has regret at least $c/\sqrt{n \log n}$ for alphabet sizes between $\sqrt{n}$ and $n^C$, so it cannot be competitive-optimal. If correct, this settles a question left open by earlier analyses and gives a concrete theoretical and empirical reason to prefer the NPMLE-based method over Good–Turing.

What carries the argument

The carrying object is Robbins's Bayes rule for Poisson mixtures: $\theta_G(y) = \frac{(y+1) f_G(y+1)}{f_G(y)}$, the posterior mean of the Poisson rate theta given that a draw equals y. The NPMLE maximizes the likelihood $\sum \log f_G(N_i)$ over all priors on $R_+$, turning the observed counts into an estimated Bayes rule; the term $\tau \mathbf{1}\{N_i = 0\}$ prevents zero-count symbols from receiving exponentially small estimates. The proof's workhorse is a two-term regret decomposition: term (I) measures closeness of this estimated Bayes rule to the separable oracle, and term (II) is a mean-field comparison, proved via approximate independence of noisy permutation mixtures, showing the permutation-invariant oracle is

What would settle it

Compute the NPMLE on a worst-case instance such as $k n^{1/3}$ atoms each of probability about $1/k$ under Poisson sampling, and measure the squared Hellinger distance between $f_{\hat{G}}$ and $f_{G_k}$; if the distance is not of order $(n^{1/3}/k) \mathrm{polylog}(k)$, Theorem 1.1's proof collapses. Alternatively, run modified Good–Turing on the paper's hard construction with $k = \sqrt{n}$ and $y_0 = C \sqrt{n \log n}$: the paper predicts regret at least $c/\sqrt{n \log n}$, which can be checked in simulation.

Watch

Extended reading notes

Core claim

The central claim is that the NPMLE-based estimator, defined by $\hat{p}_i$ proportional to $(\theta_{\hat{G}}(N_i) + \tau \mathbf{1}\{N_i = 0\})/n$ with $\tau = k^{-C_0}$ for any $C_0 \ge 1$, has regret at most $C\left( (n^{-2/3} \wedge k/n) \log^{14}(nk) \right)$. With the matching lower bound quoted from Orlitsky–Suresh, this establishes competitive optimality up to logarithmic factors. The proof decomposes the regret into two parts: first controlling how well the empirical-Bayes rule approximates a weaker 'separable oracle' using the NPMLE's Poisson-mixture density estimation rate, and then showing that the separable oracle is itself within eO($n^{-2/3} \wedge k/n$) of the permutation-invariant oracle. A second theorem constructs hard distrib

Load-bearing premise

The whole regret rate rests on an imported guarantee—taken from the authors' earlier paper, not reproved here—that the NPMLE's fitted Poisson-mixture density approximates the true empirical mixture with squared Hellinger error of order $(n^{1/3}/k) \mathrm{polylog}(k)$; if this density-estimation rate is even slightly slower, the main theorem's rate breaks.

Editorial extensions

If this is right

  • If the theorem is right, the NPMLE-based rule is shown to achieve the eO(n^{-2/3}) instance-wise regret rate, matching the known lower bound up to logarithmic factors with no tuning beyond setting tau = k^{-C0} for C0 >= 1.
  • The Good–Turing estimator, even in the practitioner's modified form that falls back to empirical frequencies for high counts, is strictly suboptimal in the Orlitsky–Suresh framework for alphabet sizes in [sqrt(n), n^C].
  • The profile maximum likelihood estimator inherits a near-optimal regret bound as a corollary, because the NPMLE is a convex relaxation of PML and the same density-estimation guarantee applies.
  • On synthetic distributions and real text and census data, the NPMLE consistently outperforms Good–Turing and fixed-prior Bayes rules in KL risk; an out-of-sample Bayes rule pretrained on Hamlet even beats the in-sample NPMLE on most other Shakespeare plays.
  • The separation between the two estimators is not merely asymptotic: the paper's simulations and data experiments show the gap appears at moderate sample sizes and persists across heavy-tailed, uniform, step, Zipf, and Dirichlet-structured distributions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same two-term architecture—regret against a separable oracle plus a mean-field comparison—likely transfers to other compound decision problems; the paper's Gaussian warm-up already shows a linear-in-mu mean-field bound, so a testable extension is whether the Poisson machinery carries over to multinomial sampling.
  • A truly dimension-free optimal-rate regret bound for infinite alphabets is an open problem the paper flags; if the imported NPMLE density-estimation rate can be strengthened to remove the k-dependence in the logarithmic factors, the same proof would close it.
  • The empirical success of the pretrained Shakespeare Bayes rule suggests the learned prior captures corpus-specific structure; a natural testable extension is whether a prior pretrained on a large corpus improves n-gram smoothing, a direction the paper itself lists.
  • Because the regularization parameter tau is flexible, an interesting finite-sample extension would be a fully data-dependent tau—for instance one tied to the number of unseen symbols—that preserves the regret bound while improving practical performance on small samples.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper proposes a parameter-free estimator for discrete distribution estimation under Poisson sampling, obtained by combining Robbins's empirical Bayes with Kiefer-Wolfowitz NPMLE. The estimator learns a prior from the data and converts it into probability estimates. The main theoretical result (Theorem 1.1) bounds the worst-case regret relative to the permutation-invariant (PI) oracle by C((n^{-2/3} ∧ k/n) log^{14}(nk)), matching up to logarithmic factors the lower bound from Orlitsky and Suresh [OS15]. Theorem 1.2 shows that a modified Good--Turing estimator has regret at least c/√(n log n) for k ∈ [√n, n^C], establishing a separation. The proof decomposes the regret into two parts: the NPMLE's closeness to a separable oracle, and the gap between the separable and PI oracles. The latter is controlled via a mean-field approximation for Poisson permutation mixtures, with a Gaussian analogue presented as a warm-up. The paper also contains extensive experiments on synthetic and real data, and appendices on the unregularized NPMLE and connections to profile maximum likelihood.

Significance. If the main theorem holds, this is a significant contribution to competitive distribution estimation: it establishes the first optimal (up to logarithmic factors) instance-wise regret for a practical, parameter-free estimator in the Orlitsky--Suresh framework, and contrasts it with the suboptimality of Good--Turing. The proof is detailed, with explicit constants and conditioning events, and the paper is transparent about its limitations (Poisson sampling, dimension-dependent logarithmic factors, and the necessity of regularization for unseen symbols). The mean-field bounds for Gaussian and Poisson compound decision problems are of independent interest. The paper also credits prior work and clearly separates imported results from new ones. The main concern is a missing verification of a hypothesis in an imported NPMLE density-estimation lemma, which is load-bearing for the claimed optimal rate.

major comments (1)
  1. [Section 2.1, Lemma 2.7] The proof of Theorem 2.1 applies Lemma 2.7 with p=1 to obtain ε^2 ≍ 1 ∧ (n^{1/3} log^8 k/k) and δ=exp(-Ω(n^{1/3} log k)), and then feeds this into Theorem 2.2. However, Lemma 2.7 is stated only under the hypothesis m_p(G_k)^{1/p} ≤ k^{10}. For p=1, m_1(G_k)=n/k, so the condition is k ≥ n^{1/11}. The paper never verifies this condition, and for k < n^{1/11} the lemma is inapplicable. This is exactly the regime where the claimed bound is k/n, so the main theorem is unproved there. A trivial ε=2 bound (or a short minimax argument giving Reg ≤ C k/n) would fill the gap, but no such argument is supplied. Since the n^{-2/3} exponent is the square of the imported Hellinger rate, a polynomial slowdown in Lemma 2.7 would break Theorem 1.1. This is a load-bearing omission in the proof of the main theorem.
minor comments (4)
  1. [Section 2.1, Lemma 2.7] For k=1, the lemma involves log k=0 and the tail exponent becomes degenerate (division by zero). Theorem 1.1 is trivial for k=1, but the proof should explicitly exclude or handle this case.
  2. [Section 5.1] The statement 'without loss of generality we assume that m := n/(y0+y⋆) is an integer' is not actually WLOG. The argument should either define m via floor/ceil and track rounding errors, or restrict to n such that m is integral. As written, the proof covers only a subset of n.
  3. [Section 1.3 / Appendix E.1] The surname experiment is labeled '2010 Census' in Fig. 3f and the main text, but Appendix E.1 and E.2 refer to the '2000 census surname dataset'. The census year should be made consistent.
  4. [Appendix A] There is a duplicated word: 'for for any permutation' in the paragraph after (63).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the regret bound is derived from independent external density-estimation and permutation-mixture theorems, not from the regret claim itself.

full rationale

The main regret bound (Theorem 1.1/2.1) is obtained by plugging a Hellinger density-estimation guarantee for the Poisson NPMLE into a general regret reduction (Theorem 2.2). The density-estimation guarantee, Lemma 2.7, is quoted as Proposition 27 of [SW22] and is a separate, parameter-free statement about the NPMLE's Poisson mixture density error under an explicit moment condition; its conclusion is about squared Hellinger distance, not about KL regret against the PI oracle. It is load-bearing, and it is a self-citation (Shen and Wu are authors of both works), but under the review rules this does not constitute circularity because the cited result has its own stated assumptions, is not defined in terms of the target regret, and is not fitted to any data or to the PI benchmark. Similarly, the mean-field comparison between the PI and separable oracles (Theorem 1.3 / Theorem 4.3) uses the permutation-mixture KL bound of [HNW24], which is again an external theorem with independent content, used as machinery. The lower bound is taken from [OS15], external to this paper, and the regularization parameters tau = k^{-C0} and rho = c(nk)^{-5} are not optimized against the regret; they are chosen within stated ranges and the proof shows the bound holds for any such choice. No fitted quantity is renamed as a prediction, no target quantity is defined in terms of the estimator, and no uniqueness claim is imported from the authors' prior work to force the choice of NPMLE. The only mild caveat is that the paper relies on the authors' earlier density-estimation rate for the central exponent, so the truth of Theorem 1.1 is conditional on that external result; but that is a correctness/robustness concern, not a circularity. Accordingly no circular step is identified and the score is 0.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

Everything the regret bound rests on that is not proved in this manuscript: the NPMLE's Hellinger rate (from SW22), the permutation-mixture KL bound (from HNW24), the Poissonization step, and standard compound-decision identities. The free parameters are the two regularizers required by the theorems (not data-fitted) plus the empirical census threshold. No new physical or structural entities are posited, so invented_entities is empty.

free parameters (3)
  • tau: unseen-symbol regularization in (4) = k^{-C0}, C0 >= 1 (theory); 0 (experiments)
    Theorem 1.1 requires tau = k^{-C0} to control the regret for unseen symbols; Appendix C shows tau = 0 can give constant worst-case regret. Since the bound is uniform over C0 >= 1, it is a form-fixed parameter rather than data-fitted, but the reported experiments use tau = 0, outside the theorem's scope.
  • rho: regularization floor in smoothed Bayes rule (20) = c (nk)^{-5}
    Hand-set with a small constant c; used in Theorem 2.2 and Lemma 3.3. For the NPMLE it is inactive when N_i <= 2n (Section 2.1), so its numeric value has little effect on the stated bound.
  • Conditional-NPMLE count threshold (census surnames) = tau = 20000 counts
    Appendix E.2 uses this threshold so the Frank-Wolfe gradient polynomial (degree N_max) stays numerically stable; an empirical choice not covered by Theorem 1.1 and used only in the 2010 Census experiment.
assumptions (6)
  • domain assumption NPMLE Hellinger-rate bound: P(H(f_Ĝ, f_Gk) >= t epsilon_k) <= 2 exp(-t^2 log^2 k / 8), with epsilon_k from Lemma 2.7
    Imported from [SW22, Prop. 27]; converts NPMLE density error into the regret bound (Theorem 2.2). Not reproved; the paper's eO(n^{-2/3}) rate is directly proportional to this bound.
  • domain assumption Permutation-mixture KL/chi^2 bound: D_KL(P_Z || product of P_Zi) = O(m log n) after clustering, via [HNW24, Thm 1.2]
    Used in Sections 4.1.1 and 4.2.1 to control the mean-field gap via chi^2-diameter per cluster; the unbounded-diameter generalization is sketched but relies on the cited theorem.
  • domain assumption Poisson sampling model: N_i ~ Poi(n p_i) independently
    The entire theoretical framework conditions on Poissonized sample size (Section 1.1); the fixed-n multinomial extension is left open in Section 1.4.
  • standard math Fundamental theorem of compound estimation (Eq. 14)
    From Zhang (2003); equates empirical averages over symbols with expectations under the empirical prior G_k.
  • standard math PI oracle equals posterior mean under uniform random relabeling (Eq. 9/11)
    Derived in Appendix A following Robbins (1951) and Greenshtein-Ritov (2009).
  • standard math NPMLE first-order optimality condition (68) and O(sqrt(n)) support size
    Classical NPMLE facts from Lindsay (1983, 1995) and Polyanskiy-Wu (2020), used in Section 2.1 and Appendix B.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Besting Good--Turing: Optimality of Non-Parametric Maximum Likelihood for Distribution Estimation." pith.science (2026). https://pith.science/paper/U2MBJSMR

@misc{pith2026250907355,
  author       = {Pith},
  title        = {Pith review of: Besting Good--Turing: Optimality of Non-Parametric Maximum Likelihood for Distribution Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U2MBJSMR}},
  note         = {Machine review of arXiv:2509.07355}
}
read the original abstract

When faced with a small sample from a large universe of possible outcomes, scientists often turn to the venerable Good--Turing estimator. Despite its pedigree, however, this estimator comes with considerable drawbacks, such as the need to hand-tune smoothing parameters and the lack of a precise optimality guarantee. We introduce a parameter-free estimator that bests Good--Turing in both theory and practice. Our method marries two classic ideas, namely Robbins's empirical Bayes and Kiefer--Wolfowitz non-parametric maximum likelihood estimation (NPMLE), to learn an implicit prior from data and then convert it into probability estimates. We prove that the resulting estimator attains the optimal instance-wise risk up to logarithmic factors in the competitive framework of Orlitsky and Suresh, and that the Good--Turing estimator is strictly suboptimal in the same framework. Our simulations on synthetic data and experiments with English corpora and U.S. Census data show that our estimator consistently outperforms both the Good--Turing estimator and explicit Bayes procedures.

Figures

Figures reproduced from arXiv: 2509.07355 by the authors.

Figure 1
Figure 1. KL risk and regret of various estimators and oracles for heavy-tailed distribution [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. KL regret over the separable oracle for various distributions over [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. KL regret of NPMLE and modified Good-Turing on real data experiments. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Out of sample experiment on the Shakespearean canon (sampling ratio 20%). The [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Smoothing effect of distribution estimators. Data are drawn from the Zipf distribution [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: The gradient function θ 7→ DGb(θ) (blue curve) in Example B.1 for m = 3. Example B.2. Suppose the data is such that each symbol either appears 0 times or once, so Ni = 0 or 1, but not all 0 or all 1. From the basic properties summarized in Section B.1, we know that NPM…
Figure 7
Figure 7. Figure 7: The gradient function θ 7→ DGb(θ) in Example B.2 with q = 0.3. Remark B.3. As mentioned in the Introduction, it is well-known that the original Good–Turing estimator pb GT i ∝ (Ni + 1)ΦNi+1 ΦNi , (73) 56 [PITH_FULL_IMAGE:figures/full_fig_p056_7.png]
Figure 8
Figure 8. Figure 8: KL risk and regret (over the separable oracle) for various distributions over [PITH_FULL_IMAGE:figures/full_fig_p065_8.png]
Figure 9
Figure 9. Figure 9: KL risk and regret (over the separable oracle) for various distributions over [PITH_FULL_IMAGE:figures/full_fig_p066_9.png]
Figure 10
Figure 10. Figure 10: Smoothing effect of estimators. Estimated probabilities [PITH_FULL_IMAGE:figures/full_fig_p067_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Universal priors: solving empirical Bayes via Bayesian inference and pretraining

    stat.ML 2026-02 conditional novelty 8.0 of 10

    A simple random prior-on-prior lets pretrained transformers achieve near-optimal empirical Bayes regret uniformly over all test priors, and length generalization matches α-posterior inference.

  2. Elementary Symmetric Polynomial Inequalities for Centered Vectors and Matrices

    math.CO 2026-07 accept novelty 6.0 of 10

    Centered complex vectors and doubly centered matrices obey ESP magnitude bounds of order binom(n,k)^{1/2} and B^k binom(n,k), improving permanent and de Finetti estimates.

Reference graph

Works this paper leans on

53 extracted references · 48 canonical work pages · cited by 2 Pith papers

  1. [1]

    A unified maximum likelihood approach for estimating symmetric properties of discrete distributions

    Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. A unified maximum likelihood approach for estimating symmetric properties of discrete distributions. In International Conference on Machine Learning , pages 11--21. PMLR, 2017

    work page 2017

  2. [2]

    Optimal probability estimation with applications to prediction and classification

    Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Optimal probability estimation with applications to prediction and classification. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory , volume 30 of Proceedings of Machine Learning Research , pages 764--796, Princeton...

    work page 2013

  3. [3]

    Chen and Joshua Goodman

    Stanley F. Chen and Joshua Goodman. An empirical study of smoothing techniques for language modeling. Computer Speech & Language , 13(4):359--394, 1999

    work page 1999

  4. [4]

    Elements of Information Theory

    Thomas M Cover and Joy A Thomas. Elements of Information Theory . John Wiley & Sons, 2012

    work page 2012

  5. [5]

    Two modeling strategies for empirical B ayes estimation

    Bradley Efron. Two modeling strategies for empirical B ayes estimation. Statist. Sci. , 29(2):285--301, 2014

    work page 2014

  6. [6]

    R. A. Fisher, A. Steven Corbet, and C. B. Williams. The relation between the number of species and the number of individuals in a random sample of an animal population. Journal of Animal Ecology , 12(1):42--58, 1943

    work page 1943

  7. [7]

    Theory of optimal experiments

    Valerii Vadimovich Fedorov. Theory of optimal experiments . Academic Press, 1972

    work page 1972

  8. [8]

    Towards competitive n-gram smoothing

    Moein Falahatgar, Mesrob Ohannessian, Alon Orlitsky, and Venkatadheeraj Pichapati. Towards competitive n-gram smoothing. In International Conference on Artificial Intelligence and Statistics , pages 4206--4215. PMLR, 2020

    work page 2020

Show all 53 references
  1. [9]

    An algorithm for quadratic programming

    Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly , 3(1-2):95--110, 1956

    1956

  2. [10]

    I. J. Good. The population frequencies of species and the estimation of population parameters. Biometrika , 40(3/4):237--264, 1953

    1953

  3. [11]

    Asymptotic efficiency of simple decisions for the compound decision problem

    Eitan Greenshtein and Ya'acov Ritov. Asymptotic efficiency of simple decisions for the compound decision problem. Lecture Notes-Monograph Series , pages 266--275, 2009

    2009

  4. [12]

    P. J. Green and B. W. Silverman. Nonparametric regression and generalized linear models , volume 58 of Monographs on Statistics and Applied Probability . Chapman & Hall, London, 1994. A roughness penalty approach

    1994

  5. [13]

    Gale and Geoffrey Sampson

    William A. Gale and Geoffrey Sampson. Good- T uring frequency estimation without tears. Journal of Quantitative Linguistics , 2(3):217--237, 1995

    1995

  6. [14]

    Approximate independence of permutation mixtures

    Yanjun Han and Jonathan Niles-Weed. Approximate independence of permutation mixtures. arXiv preprint arXiv:2408.09341 , 2024

    2024

  7. [15]

    The broad optimality of profile maximum likelihood

    Yi Hao and Alon Orlitsky. The broad optimality of profile maximum likelihood. Advances in Neural Information Processing Systems , 32, 2019

    2019

  8. [16]

    Asymptotic solutions of the compound decision problem for two completely specified distributions

    James F Hannan and Herbert Robbins. Asymptotic solutions of the compound decision problem for two completely specified distributions. The Annals of Mathematical Statistics , pages 37--51, 1955

    1955

  9. [17]

    On the competitive analysis and high accuracy optimality of profile maximum likelihood

    Yanjun Han and Kirankumar Shiragur. On the competitive analysis and high accuracy optimality of profile maximum likelihood. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1317--1336. SIAM, 2021

    2021

  10. [18]

    Revisiting F rank- W olfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting F rank- W olfe: Projection-free sparse convex optimization. In International conference on machine learning , pages 427--435, 2013

    2013

  11. [19]

    Daniel Jurafsky and James H. Martin. Speech and Language Processing . Prentice-Hall, Inc., USA, 2nd edition, 2009

    2009

  12. [20]

    Optimal empirical B ayes estimation for the P oisson model via minimum-distance methods

    Soham Jana, Yury Polyanskiy, and Yihong Wu. Optimal empirical B ayes estimation for the P oisson model via minimum-distance methods. arXiv preprint arXiv:2209.01328 , 2022

    2022 arXiv

  13. [21]

    Minimax estimation of functionals of discrete distributions

    Jiantao Jiao, Kartik Venkat, Yanjun Han, and Tsachy Weissman. Minimax estimation of functionals of discrete distributions. IEEE Transactions on Information Theory , 61(5):2835--2885, 2015

    2015

  14. [22]

    On information and sufficiency

    Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathematical statistics , 22(1):79--86, 1951

    1951

  15. [23]

    Convex optimization, shape constraints, compound decisions, and empirical B ayes rules

    Roger Koenker and Ivan Mizera. Convex optimization, shape constraints, compound decisions, and empirical B ayes rules. Journal of the American Statistical Association , 109(506):674--685, 2014

    2014

  16. [24]

    The performance of universal encoding

    Raphail Krichevsky and Victor Trofimov. The performance of universal encoding. IEEE Transactions on Information Theory , 27(2):199--207, 1981

    1981

  17. [25]

    Kiefer and J

    J. Kiefer and J. Wolfowitz. Consistency of the maximum likelihood estimator in the presence of infinitely many incidental parameters. Ann. Math. Statist. , 27:887--906, 1956

    1956

  18. [26]

    Estimating T -cell repertoire diversity: limitations of classical estimators and a new approach

    Daniel J Laydon, Charles R M Bangham, and Becca Asquith. Estimating T -cell repertoire diversity: limitations of classical estimators and a new approach. Philosophical Transactions of the Royal Society B: Biological Sciences , 370(1675):20140291, 2015

    2015

  19. [27]

    The geometry of mixture likelihoods: a general theory

    Bruce G Lindsay. The geometry of mixture likelihoods: a general theory. The Annals of Statistics , 11(1):86--94, 1983

    1983

  20. [28]

    Mixture models: Theory, geometry and applications

    Bruce G Lindsay. Mixture models: Theory, geometry and applications. In NSF-CBMS regional conference series in probability and statistics , volume 5, pages I--163. American Statistical Association, 1995

    1995

  21. [29]

    A fast, lock-free approach for efficient parallel counting of occurrences of k-mers

    Guillaume Mar c ais and Carl Kingsford. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics , 27(6):764--770, 2011

    2011

  22. [30]

    McAllester and Robert E

    David A. McAllester and Robert E. Schapire. On the convergence rate of Good-Turing estimators. In Proceedings of the 13th Annual Conference on Computational Learning Theory , pages 1--6, 2000

    2000

  23. [31]

    Probability and computing

    Michael Mitzenmacher and Eli Upfal. Probability and computing . Cambridge University Press, Cambridge, 2005. Randomized algorithms and probabilistic analysis

    2005

  24. [32]

    Large-scale multiple testing: Fundamental limits of false discovery rate control and compound oracle

    Yutong Nie and Yihong Wu. Large-scale multiple testing: Fundamental limits of false discovery rate control and compound oracle. arXiv preprint arXiv:2302.06809 , 2023

    2023 arXiv

  25. [33]

    Competitive distribution estimation: Why is G ood- T uring good

    Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why is G ood- T uring good. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 28. Curran Associates, Inc., 2015

    2015

  26. [34]

    On modeling profiles instead of values

    Alon Orlitsky, Narayana P Santhanam, Krishnamurthy Viswanathan, and Junan Zhang. On modeling profiles instead of values. In Proceedings of the 20th conference on Uncertainty in artificial intelligence , pages 426--435, 2004

    2004

  27. [35]

    Santhanam, and Junan Zhang

    Alon Orlitsky, Narayana P. Santhanam, and Junan Zhang. Always Good Turing : Asymptotically optimal probability estimation. Science , 302(5644):427--431, 2003

    2003

  28. [36]

    Self-regularizing property of nonparametric maximum likelihood estimator in mixture models

    Yury Polyanskiy and Yihong Wu. Self-regularizing property of nonparametric maximum likelihood estimator in mixture models. Arxiv preprint arXiv:2008.08244 , Aug 2020

    2008 arXiv

  29. [37]

    Information theory: From coding to learning

    Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning . Cambridge university press, 2025

    2025

  30. [38]

    Asymptotically subminimax solutions of compound statistical decision problems

    Herbert Robbins. Asymptotically subminimax solutions of compound statistical decision problems. In Proceedings of the S econd B erkeley S ymposium on M athematical S tatistics and P robability, 1950 , pages 131--148. University of California Press, Berkeley-Los Angeles, Calif., 1951

    1950

  31. [39]

    An empirical B ayes approach to statistics

    Herbert Robbins. An empirical B ayes approach to statistics. In Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics . The Regents of the University of California, 1956

    1956

  32. [40]

    Maximum likelihood estimation of a compound P oisson process

    L\' e opold Simar. Maximum likelihood estimation of a compound P oisson process. Ann. Statist. , 4(6):1200--1209, 1976

    1976

  33. [41]

    A statistical interpretation of term specificity and its application in retrieval

    Karen Sparck Jones. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation , 28(1):11--21, 1972

    1972

  34. [42]

    A survey of modern authorship attribution methods

    Efstathios Stamatatos. A survey of modern authorship attribution methods. Journal of the American Society for information Science and Technology , 60(3):538--556, 2009

    2009

  35. [43]

    Empirical B ayes estimation: When does g -modeling beat f -modeling in theory (and in practice)? arXiv preprint arXiv:2211.12692 , 2022

    Yandi Shen and Yihong Wu. Empirical B ayes estimation: When does g -modeling beat f -modeling in theory (and in practice)? arXiv preprint arXiv:2211.12692 , 2022

    2022 arXiv

  36. [44]

    J. R. R. Tolkien. The Fellowship of the Ring . George Allen & Unwin, London, 1954. Part I of The Lord of the Rings

    1954

  37. [45]

    Capacity of noisy permutation channels

    Jennifer Tang and Yury Polyanskiy. Capacity of noisy permutation channels. IEEE Transactions on Information Theory , 69(7):4145--4162, 2023

    2023

  38. [46]

    Census Bureau

    U.S. Census Bureau . Frequently occurring surnames from the 2010 census. https://www.census.gov/topics/population/genealogy/data/2010_surnames.html, 2021. Accessed: 2025-04-09

    2010

  39. [47]

    Census Bureau

    U.S. Census Bureau . 2020 census detailed demographic and housing characteristics file A ( D etailed DHC - A ). https://www.census.gov/data/tables/2023/dec/2020-census-detailed-dhc-a.html, 2025. Accessed: 2025-04-09

    2020

  40. [48]

    The complexity of computing the permanent

    Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science , 8(2):189--201, 1979

    1979

  41. [49]

    On the minimum attainable risk in permutation invariant problems

    Asaf Weinstein. On the minimum attainable risk in permutation invariant problems. arXiv preprint arXiv:2110.06250 , 2021

    2021 arXiv

  42. [50]

    Minimax rates of entropy estimation on large alphabets via best polynomial approximation

    Yihong Wu and Pengkun Yang. Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory , 62(6):3702--3720, 2016

    2016

  43. [51]

    Chebyshev polynomials, moment matching, and optimal estimation of the unseen

    Yihong Wu and Pengkun Yang. Chebyshev polynomials, moment matching, and optimal estimation of the unseen. The Annals of Statistics , 47(2):857--883, 2019

    2019

  44. [52]

    The sequential generation of d -optimum experimental designs

    Henry P Wynn. The sequential generation of d -optimum experimental designs. The Annals of Mathematical Statistics , 41(5):1655--1664, 1970

    1970

  45. [53]

    Compound decision theory and empirical B ayes methods

    Cun-Hui Zhang. Compound decision theory and empirical B ayes methods. The Annals of Statistics , 31(2):379--390, 2003. Dedicated to the memory of Herbert E. Robbins

    2003

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.