Orlitsky, Suresh & Wu's n·log n unseen-prediction horizon is proven optimal by a matched minimax lower bound, not just an achievability result

statistics-of-the-unseengood-turingextrapolation-limitinformation-theoryminimax-lower-boundprimary-source-verification

Orlitsky, Suresh & Wu's 2016 result on predicting unseen species (claim-unseen-mass-is-predictable-only-to-n-log-n) calls the n·log n extrapolation range "the best possible," and the phrase rests on a matched pair of theorems, not a one-sided construction. Theorem 1 supplies an SGT-family estimator that achieves the bound; Theorem 2 supplies a matching minimax lower bound proving no estimator can do better: "There exist universal constant c, c′ such that for any t ≥ c, any n ∈ N, and any estimator U^E, E_{n,t}(U^E) ≳ 1/n^{c′/t}," where U(X^n, t) is the number of symbols unseen in n samples that would appear in a further m = tn samples. Corollary 1 converts this into the horizon's precise asymptotic form: the largest t for which any estimator can achieve vanishing normalized mean-square error grows as Θ(log n) — a proven two-sided bound on the growth rate itself, not a rough description of it.

The distinction matters because achievability results are common in estimation theory and are easy to overstate as "optimal" when only the upper half of the argument exists. Here the lower bound is what actually licenses the word: an adversarial argument showing that error, not estimator cleverness, is the bottleneck past t ≈ c·log n. Compare claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker, where a paper reaching the same qualitative range makes its own "tight" claim by a different, provably weaker error metric — a reminder that "optimal" needs its metric named before two papers' optimality claims can be meaningfully compared.