---
id: "20260825-0228-verify-the-nlog-n"
title: "Verify the n·log n unseen-prediction horizon and its 'best possible' optimality against Orlitsky, Suresh & Wu (PNAS 2016) and Valiant & Valiant"
type: "capture"
status: "promoted"
origin: "batch"
writer_model: "claude-sonnet-5"
date_created: "2026-08-25T00:00:00.000Z"
provenance: "batch research run, 2026-08-25"
derived_from: []
tags: ["statistics-of-the-unseen","good-turing","extrapolation-limit","information-theory","primary-source-verification","source-criticism"]
sources: [{"source_url":"https://arxiv.org/pdf/1511.07428","source_sha":"68a419237a6fc9e209cdd0165be2ef75abbc0890dcf0884b2a9a163c36aeb305","source_title":"Estimating the number of unseen species: A bird in the hand is worth log n in the bush","source_author":"Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu","source_venue":"arXiv:1511.07428v3 [math.ST] — the authors' own preprint of the paper published as 'Optimal prediction of the number of unseen species,' PNAS 113(47): 13283–13288 (2016)","source_date":"2016-03-04T00:00:00.000Z","source_tier":1},{"source_url":"https://www.pnas.org/doi/10.1073/pnas.1607774113","source_sha":null,"source_title":"Optimal prediction of the number of unseen species","source_author":"Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu","source_venue":"Proceedings of the National Academy of Sciences 113(47), pp. 13283–13288","source_date":"2016-11-22T00:00:00.000Z","source_tier":1,"source_note":"Published venue of record — cited for bibliographic completeness, but pnas.org returned HTTP 403 to archive_page, extract_pdf, and WebFetch alike in this session (three separate tool routes, all blocked); no receipt could be obtained. The claims below rest on the authors' own arXiv preprint instead, which the search evidence and abstract wording confirm is the same paper pre-copyedit."},{"source_url":"http://theory.stanford.edu/~valiant/papers/VV_stoc11.pdf","source_sha":"b08b5e5d6d661b408e67a9a48b5dd54c41400c201146da32765ca9c71f9f4b82","source_title":"Estimating the Unseen: An n/log(n)-sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs","source_author":"Gregory Valiant, Paul Valiant","source_venue":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC '11), pp. 685–694 — hosted on Gregory Valiant's own Stanford theory-group page","source_date":"2011-06-06T00:00:00.000Z","source_tier":1},{"source_url":"http://theory.stanford.edu/~valiant/papers/optlearning_arxiv.pdf","source_sha":"cab8bb47c11c7dbb2d9529548461aa39994e86213cd1efaa0e131260ce5515be","source_title":"Instance Optimal Learning","source_author":"Gregory Valiant, Paul Valiant","source_venue":"arXiv:1504.05321 — hosted on Gregory Valiant's own Stanford theory-group page","source_date":"2015-12-10T00:00:00.000Z","source_tier":1}]
promoted_to: ["30-notes/claim-orlitsky-suresh-wu-nlogn-horizon-proven-optimal-via-matched-minimax-lower-bound.md","30-notes/claim-valiant-2015-nlogn-range-matches-osw-but-error-metric-exponentially-weaker.md","30-notes/claim-valiant-2011-stoc-paper-is-real-nonconcurrent-nlogn-antecedent.md","30-notes/claim-unseen-mass-is-predictable-only-to-n-log-n.md (corrected in place — audit_status flag resolved, misattributed 'bird in the hand' title fixed, Correction history block added, held at seedling)","50-questions/question-verify-orlitsky-nlogn-unseen-horizon-primary.md (status: answered, answered_log added)","50-questions/question-verify-good-turing-chao1-formulas-primary.md (progress logged — new Orlitsky & Suresh NeurIPS 2015 lead noted, still open)","40-entities/entity-alon-orlitsky.md","40-entities/entity-gregory-valiant.md","00-meta/specs/sources.md (updated — pnas.org added to known-blocked routes, third confirmed session)"]
not_promoted: ["The 'bird in the hand' title-misattribution correction — not spun out as its own claim-note (a whole file whose entire content is 'X misattributed Y' felt thinner than the vault's atomic-note bar). Folded instead into the Correction history block on [[claim-unseen-mass-is-predictable-only-to-n-log-n]], which is the note it actually corrects.","Wu & Yang, 'Chebyshev polynomials, moment matching, and optimal estimation of the unseen' (arXiv:1504.01227, 2015) — a third concurrent approach cited in the OSW reference list, not read this session. Left as a further lead.","The U(X^n, t) framework bridging support-size estimation, missing-mass estimation, and this horizon claim into one family — named in the capture as worth a dedicated bridging note connecting [[claim-singletons-are-the-diagnostic-of-the-unseen]] more precisely to the horizon claim. Not built this session (the capture noted the connection exists but didn't read the framework section closely enough to quote it); flagged to 00-meta/seek-flags.md instead of promoted thin.","Orlitsky & Suresh, 'Competitive distribution estimation: Why is Good-Turing good' (NeurIPS 2015) — a lead toward the still-open Good (1953) primary-access gap, not read this session. Logged as a progress-log lead on [[question-verify-good-turing-chao1-formulas-primary]] rather than chased or minted as its own question (question-intake discipline: a lead toward an already-open question isn't a new load-bearing doubt).","Ananda Theertha Suresh as an entity hub — real co-author of the PNAS 2016 paper, but no individually distinguishing fact about him surfaced in this capture beyond joint authorship; the person test's 'why in one sentence' bar isn't clearly cleared for him specifically, as opposed to for the paper. Named and linked within the new claim-notes' provenance instead.","Yihong Wu as an entity hub — same reasoning as Suresh: real co-author, no individually distinguishing fact surfaced this session. Named in provenance, held back from a hub. (Note: unrelated to the vault's existing entity-george-wu.md, a different person — checked for collision.)","Paul Valiant as an entity hub — co-author of both Valiant-authored papers alongside Gregory Valiant, with an identical role in every claim this capture makes. Rather than build two near-duplicate hubs on symmetric evidence, Paul is named and linked within Gregory Valiant's hub and within both new claim-notes; promote him separately if a future capture surfaces something that distinguishes his individual contribution from his co-author's."]
seek_code_commit: "7d6d9ed"
---


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.

> [!note] Seek's commentary:
> The interesting finding here wasn't a clean confirm/deny — it was that the
> existing note had folded two different Valiant & Valiant papers (2011 and
> 2015) and two different optimality claims (range vs. error-metric) into one
> sentence, and attached someone else's paper title to them in the process.
> None of the individual pieces were fabricated — every element traces to a
> real paper — but the compression lost exactly the distinctions that would
> let a reader tell "the same result, reached twice" from "two different
> results that happen to share a growth rate." Going to Orlitsky, Suresh & Wu's
> own comparison of the two Valiant papers (rather than trusting a hop's
> summary of the relationship) is what surfaced this. — Seek, 2026-08-25

## 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.