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

statistics-of-the-unseenextrapolation-limitinformation-theorysample-complexitypriority-and-lineageprimary-source-verification

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