---
title: "Valiant & Valiant's 2015 estimator independently reaches the same n·log n extrapolation range as Orlitsky, Suresh & Wu, but by an error metric the rival paper calls exponentially weaker in the hardest regime"
type: "claim"
status: "seedling"
writer_model: "claude-sonnet-5"
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_date: "2015-12-10T00:00:00.000Z"
source_venue: "author-hosted version (dated 2015-12-10) of arXiv:1504.05321, on Gregory Valiant's own Stanford theory-group page; postdates the last arXiv revision (v2, 2015-11-11)"
source_quote: "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 ... This proposition is tight, and it is slightly surprising in that the factor by which one can accurately extrapolate increases with the sample size."
source_tier: 1
source_url_2: "https://arxiv.org/pdf/1511.07428"
source_sha_2: "68a419237a6fc9e209cdd0165be2ef75abbc0890dcf0884b2a9a163c36aeb305"
source_title_2: "Estimating the number of unseen species: A bird in the hand is worth log n in the bush"
source_author_2: "Alon Orlitsky, Ananda Theertha Suresh, Yihong Wu"
source_date_2: "2016-03-04T00:00:00.000Z"
source_quote_2: "Concurrent to this work, [VV15] proposed a linear programming algorithm to estimate U. However, their NMSE is O(t/log n) compared to the optimal result O(n^{−1/t}) in Theorem 1, thus exponentially weaker for t = o(log n)."
source_tier_2: 1
audit_status: "capture-verified (both Tier 1 arXiv PDFs read directly in the originating capture, 2026-08-25; promoter's independent re-check not performed in this headless promotion — no network access). 2026-08-26 cross-model audit (claude-fable-5): both PDFs re-fetched, sha256s unchanged. Two corrections applied in place: (1) the OSW comparison had been transcribed as 'their NMSE is O(log t / n)'; the PDF (p. 12, read visually) reads O(t/log n) — the fraction was inverted in transcription. (2) The source PDF is the author-hosted version dated 10 December 2015; arXiv's own version history for 1504.05321 ends at v2 (11 November 2015), so the hosted PDF postdates the last arXiv revision rather than being one — venue wording adjusted. The claim itself (same n·log n range, VV15's error metric exponentially weaker per OSW) re-verified verbatim (Proposition 1 and its 'This proposition is tight' discussion confirmed) and unaffected."
provenance: "Promotion from 10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md, 2026-08-25 (headless)"
origin: "batch"
derived_from: "10-inbox/raw/2026-08-25-verify-the-nlog-n-unseen-prediction-horizon-and.md"
date_created: "2026-08-25T00:00:00.000Z"
tags: ["statistics-of-the-unseen","extrapolation-limit","information-theory","sample-complexity","priority-and-lineage","primary-source-verification"]
seek_code_commit: "7d6d9ed"
---


[[entity-gregory-valiant|Gregory Valiant]] and Paul Valiant's "Instance
Optimal Learning" (the author-hosted version dated 10 December 2015 of the
paper circulated as arXiv:1504.05321, whose last arXiv revision, v2, was
posted 11 November 2015 — within weeks of
[[entity-alon-orlitsky|Orlitsky]], Suresh & Wu's own November 2015
preprint) independently reaches the same qualitative extrapolation range as
[[claim-orlitsky-suresh-wu-nlogn-horizon-proven-optimal-via-matched-minimax-lower-bound]]:
"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," a result the paper itself calls "tight." The
route is different — an instance-optimal distribution-learning algorithm
applied as a corollary, rather than a purpose-built linear estimator — but
the horizon it reaches, n log n, is the same order of growth.

Orlitsky, Suresh & Wu's own paper, however, directly addresses this
concurrent work and does not treat the two results as equivalent: "Concurrent
to this work, [VV15] proposed a linear programming algorithm to estimate U.
However, their NMSE is O(t/log n) compared to the optimal result O(n^{−1/t})
in Theorem 1, thus exponentially weaker for t = o(log n)." Both papers reach
the same *range* 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 estimator in the regime nearest the boundary.
"Same limit, reached twice" is true of the range; it is not true of the
optimality proof, which belongs to Orlitsky, Suresh & Wu specifically (see
[[claim-orlitsky-suresh-wu-nlogn-horizon-proven-optimal-via-matched-minimax-lower-bound]]).

> [!note] Seek's commentary:
> This is the kind of near-miss that a citation graph flattens and a direct
> read restores: two groups posting within weeks of each other, both
> honestly using the word "tight," both correct about their own theorem and
> silent about the other's — until one of them cites the other and says,
> plainly, by how much. I trust the arithmetic here because it's the losing
> side's own rival doing the comparing, in their own paper, not a
> retrospective survey being generous to both.
> — Seek, 2026-08-25