Verify the n·log n unseen-prediction horizon and its 'best possible' optimality against Orlitsky, Suresh & Wu (PNAS 2016) and Valiant & Valiant

statistics-of-the-unseengood-turingextrapolation-limitinformation-theoryprimary-source-verificationsource-criticism

Answers question-verify-orlitsky-nlogn-unseen-horizon-primary, which flagged claim-unseen-mass-is-predictable-only-to-n-log-n as resting on a hop paraphrase rather than a direct read of the PNAS primary, and specifically asked whether Valiant & Valiant's concurrent proof and the "bird in the hand" title were correctly attributed. The core n·log n horizon and its "best possible" optimality are confirmed directly at the primary. The Valiant & Valiant attribution in the existing note is partly right and partly wrong: they did independently claim a matching extrapolation range, but the memorable title belongs to Orlitsky, Suresh & Wu alone, and the two groups' "optimal" claims use different error metrics that Orlitsky, Suresh & Wu's own paper says are not equivalent in strength.

Claim: Orlitsky, Suresh & Wu prove the number of unseen species is predictable up to t ∝ log n new samples, and prove this range is "the best possible" via a matching minimax lower bound

Claim type: quantitative + technical-mechanism (a specific extrapolation bound and a proof of its optimality). Floor: Tier 1–2 required. Met: Tier 1, direct read of the authors' own preprint.

The abstract states the result directly: "We derive a class of estimators that provably predict U not just for constant t > 1, but all the way up to t proportional to log n. This shows that the number of species can be estimated for a population log n times larger than that observed, a factor that grows arbitrarily large as n increases. We also show that this range is the best possible and that the estimators' mean-square error is optimal up to constants for any t." U is defined precisely as the number of hitherto-unseen symbols that would appear in m further samples, given n samples already collected, with t = m/n. The optimality claim is not asserted loosely — Theorem 2 in the body proves a matching minimax lower bound ("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) ≳ c′/n^{1/t}"), and Corollary 1 states the precise asymptotic limit: the largest t for which any estimator can achieve vanishing normalized mean-square error grows as Θ(log n). Upper bound (Theorem 1, the SGT-family estimators) and lower bound (Theorem 2) together are what license the phrase "best possible" — this is a matched pair, not a one-sided achievability result. This directly confirms the load-bearing claim in claim-unseen-mass-is-predictable-only-to-n-log-n.

Claim: The phrase "a bird in the hand is worth log n in the bush" is the title Orlitsky, Suresh & Wu gave their own paper — it was not coined by Valiant & Valiant, contrary to the existing vault note's attribution

Claim type: bibliographic / attribution (whose paper carries this title). Floor: Tier 3–4 acceptable for a title-attribution check, but confirmed here directly against the Tier 1 primary itself.

The existing note claim-unseen-mass-is-predictable-only-to-n-log-n states: "Valiant & Valiant reached the same limit concurrently, memorably titling the phenomenon 'a bird in the hand is worth log n in the bush.'" This is a misattribution. The phrase is the title page of arXiv:1511.07428 itself: "Estimating the number of unseen species: A bird in the hand is worth log n in the bush / Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu / UCSD, UCSD, UIUC." It is Orlitsky, Suresh & Wu's own title for their own paper (the PNAS-published version drops the subtitle, keeping only "Optimal prediction of the number of unseen species," but the arXiv preprint of the identical paper carries the "bird in the hand" phrasing on its own header). No paper by Gregory or Paul Valiant located in this session carries this title or phrase. This is a clean, checkable correction to route back to the existing claim-note at promotion.

Claim: Valiant & Valiant's concurrent 2015 paper independently claims the same n·log n-scale extrapolation range as "tight," but Orlitsky, Suresh & Wu's own paper states their estimator's error is exponentially weaker than its own in the hardest part of that range — the two "optimal" claims are not the same result reached twice

Claim type: technical-mechanism (what each paper's optimality claim actually covers). Floor: Tier 1–2 required. Met: Tier 1, both papers read directly.

Valiant & Valiant's "Instance Optimal Learning" (the December 10, 2015 revision of arXiv:1504.05321 — dated within weeks of Orlitsky, Suresh & Wu's first posting, so genuinely concurrent) states, as a consequence of its main distribution-learning result: "one can estimate the expected number of unique elements that would be seen in a set of k samples drawn from p, to within error k·c·√(k/(n log n)) for some universal constant c," adding "This proposition is tight, and it is slightly surprising in that the factor by which one can accurately extrapolate increases with the sample size." Its own abstract frames this as being able to "accurately estimate the expected number of distinct elements that will be observed in a sample of any size up to n log n" — the same qualitative range Orlitsky, Suresh & Wu report, reached by a different method (an instance-optimal distribution-learning algorithm applied as a corollary, rather than a purpose-built linear estimator).

However, Orlitsky, Suresh & Wu's own paper directly addresses this concurrent work and does not treat it as an equivalent result: "Concurrent to this work, [VV15] proposed a linear programming algorithm to estimate U. However, their NMSE is O(log t / n) compared to the optimal result O(n^{−1/t}) in Theorem 1, thus exponentially weaker for t = o(log n)." So both papers independently reach the same range (t up to a factor of log n) and both call their own result "tight" or "optimal," but by different error metrics, and the later, more comprehensive paper explicitly claims to dominate the earlier one in the regime that matters most for the boundary. The existing vault note's claim that Valiant & Valiant "reached the same limit concurrently" is defensible as a statement about the range, but conflating it with the "best possible" optimality proof (which is Orlitsky, Suresh & Wu's specific minimax-matching contribution, per the claim above) overstates the equivalence.

Claim: Valiant & Valiant's real, non-concurrent antecedent is their own 2011 STOC paper, which proved a matching O(n/log n) sample complexity — years earlier, and for a related but distinct problem

Claim type: historical / technical-mechanism (priority and problem scope). Floor: Tier 3–4 acceptable for priority framing, escalated here to Tier 1 since it corrects a "concurrent" framing.

Four to five years before either 2015/2016 paper, Gregory and Paul Valiant published "Estimating the Unseen: An n/log(n)-sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs" (STOC 2011). Its abstract states: "Our algorithm estimates these properties up to an arbitrarily small additive constant, using O(n/ log n) samples, where n is a bound on the support size," and the introduction states the paper "settles the longstanding... question of the sample complexities of these estimation problems, up to constant factors" via a matching lower bound of Ω(n/log n) samples. This is the genuine foundational result behind the "log n factor" family of bounds in this area — not a same-problem concurrent proof, but an earlier, different-problem result (how many samples are needed to estimate entropy or support size to fixed accuracy, rather than how far ahead one can predict newly seen species counts) that established the same log-factor structure years before the species-prediction race between Orlitsky-Suresh-Wu and Valiant-Valiant's 2015 paper. Orlitsky, Suresh & Wu's own reference list cites this 2011 paper directly (as [VV11]) and distinguishes it from the concurrent [VV15] paper, confirming the two Valiant-authored works are not the same result.

Central question status

Confirmed at the primary, with one correction and one clarification routed back to the existing note. The n·log n horizon and its "best possible" optimality are real and directly sourced to Orlitsky, Suresh & Wu's own paper (Theorem 1 + Theorem 2 + Corollary 1). The "bird in the hand" title is misattributed in the existing vault note — it is Orlitsky, Suresh & Wu's own title, not Valiant & Valiant's. The "Valiant & Valiant reached the same limit concurrently" framing is directionally true (same range, genuinely concurrent timing, their own "tight" claim) but should not be read as saying Valiant & Valiant independently proved the same optimal bound — Orlitsky, Suresh & Wu's own paper explicitly claims to beat Valiant & Valiant's 2015 estimator's error rate in the hardest part of the range. The paper that actually deserves the word "concurrent" is arXiv:1504.05321 (Instance Optimal Learning); the paper that deserves "foundational, non-concurrent, different problem" is the 2011 STOC paper.

Further leads

• Wu & Yang, "Chebyshev polynomials, moment matching, and optimal estimation of the unseen" (arXiv:1504.01227, 2015, cited as [WY15a] in the Orlitsky-Suresh-Wu paper) — a third concurrent approach to the same estimation family, not read this session.
• The Orlitsky-Suresh-Wu paper's own related-problem framing: support-size estimation (m = ∞) and missing-mass/Good-Turing estimation (m = 1) are both special cases of the same U(X^n, t) extrapolation framework — worth a bridging note connecting claim-singletons-are-the-diagnostic-of-the-unseen to this horizon claim more precisely than "the hard caveat."
• Orlitsky & Suresh, "Competitive distribution estimation: Why is Good-Turing good" (NeurIPS 2015, cited as [OS15]) — direct theoretical treatment of Good-Turing's own optimality, relevant to the still-open Good (1953) primary-access gap in question-verify-good-turing-chao1-formulas-primary.
• pnas.org itself is now a three-times-confirmed blocked route (archive_page, extract_pdf, WebFetch all 403 in this session) — worth adding to sources.md's known-blocked list if a future capture hits the same wall.

Entity candidates

• Gregory Valiant — person — co-author of both the 2011 STOC paper (the true, non-concurrent foundational result this capture had to separate out) and the 2015 "Instance Optimal Learning" paper (the genuinely concurrent one); flagged first because the existing note's error was under-crediting his and Paul Valiant's earlier, more directly comparable 2011 work in favor of a vaguer "concurrent" framing.
• Paul Valiant — person — co-author of both papers above.
• Alon Orlitsky — person — lead author of the PNAS 2016 paper and its arXiv preprint; UCSD.
• Ananda Theertha Suresh — person — co-author of the PNAS 2016 paper; UCSD at the time of writing.
• Yihong Wu — person — co-author of the PNAS 2016 paper; UIUC at the time of writing.